基本介紹
- 中文名：換出變數
- 外文名：Leaving variables
- 別名：出基變數
- 拼音：Huàn chū biàn liàng
- 學科：運籌學
- 套用：單純形法、運輸問題等
基本內容,確定方法,舉例,特殊情況,套用,
基本內容
單純形法的基本思路：從可行域中某一個頂點開始，判斷此頂點是否是最優解，如不是，則再找另一個使得其目標函式值更優的頂點，稱之為疊代，再判斷此點是否是最優解。直到找到一個頂點為其最優解，就是使得其目標函式值最優的解，或者能判斷出線性規劃問題無最優解為止。
確定方法
在單純形法的求解中，通過檢驗，如果這個初始基本可行解不是最優解，則需要進行基變換找到一個新的可行基。具體的做法是從可行基中換一個列向量，得到一個新的可行基，使得求解得到的新的基本可行解，其目標函式值更優。為了換基就要確定換入變數與換出變數。
從最優解判別定理知道，在確定換入變數之後，以
為換出變數，重新列出單純形法，進行疊代。
當存在退化問題時，需要用勃蘭特法則來確定換入變數和換出變數。在所有檢驗數大於零的非基變數中，選一個下標最小的作為換入變數；在存在兩個和兩個以上最小比值時，選一個下標最小的基變數為換出變數。
舉例
例1.設線性規劃問題為：
解：單純形法求解過程的單純形表如下：
Cj | 4 | 3 | 0 | 0 |  |  | ||
CB | XB | b | x1 | x2 | x3 | x4 | ||
0 | x3 | 4 | 2 | 1 | 1 | 0 | 4 | 2 |
0 | x4 | 6 | 6 | 1 | 0 | 1 | 1 | |
 | 4 | 3 | 0 | 0 | ||||
在第一次疊代中，可以得到
，一般選其中的 最大者的非基變數為換入變數，所以換入變數為
。再根據
確定
為換出變數。
特殊情況
1.對於求最大目標函式的問題，在某次疊代的單純形表中，如果存在著一個大於零的檢驗數，並且該列的係數向量的每個元素
都小於或等於零，即確定了換入變數，卻不能確定換出變數。則此線性規劃問題是無界的。
2.在一個已得到最優解的單純形表中，如果存在一個非基變數的檢驗數 為零，把這個非基變數作為換入變數進行疊代，在新的單純形表中，基變數的檢驗數為零，用同樣的方法可證明其他的非基變數的檢驗數不變，仍然小於零，這樣就證明了新得到的基本可行解仍然是最優解。即對於某個最優的基本可行解，如果存在某個非基變數的檢驗數為零，則此線性規劃問題有無窮多最優解。
3.在單純形法計算過程中，在確定換入變數之後，確定換出變數時有時存在兩個以上的相同的最小比值，這種情況稱之為退化。
