換出變量

單純形法的基本思路：從可行域中某一個頂點開始，判斷此頂點是否是最優解，如不是，則再找另一個使得其目標函數值更優的頂點，稱之為迭代，再判斷此點是否是最優解。直到找到一個頂點為其最優解，就是使得其目標函數值最優的解，或者能判斷出線性規劃問題無最優解為止。

所謂最優性檢驗就是判斷已求得的基本可行解是否是最優解。對於求最大目標函數的問題中，對於某個基本可行解，如果所有檢驗數

，則這個基本可行解是最優解。對於求目標函數最小值的情況，只需把

改為

。 ^[1] 

在單純形法的求解中，通過檢驗，如果這個初始基本可行解不是最優解，則需要進行基變換找到一個新的可行基。具體的做法是從可行基中換一個列向量，得到一個新的可行基，使得求解得到的新的基本可行解，其目標函數值更優。為了換基就要確定換入變量與換出變量。

從最優解判別定理知道，在確定換入變量之後，以

為換出變量，重新列出單純形法，進行迭代。

當存在退化問題時，需要用勃蘭特法則來確定換入變量和換出變量。在所有檢驗數大於零的非基變量中，選一個下標最小的作為換入變量；在存在兩個和兩個以上最小比值時，選一個下標最小的基變量為換出變量。 ^[2] 

例1.設線性規劃問題為：

用單純形法求解過程第一次迭代中的換入變量和換出變量是？

解：單純形法求解過程的單純形表如下：

在第一次迭代中，可以得到

，一般選其中的

最大者的非基變量為換入變量，所以換入變量為

。再根據

確定

為換出變量。

1.對於求最大目標函數的問題，在某次迭代的單純形表中，如果存在着一個大於零的檢驗數，並且該列的係數向量的每個元素

都小於或等於零，即確定了換入變量，卻不能確定換出變量。則此線性規劃問題是無界的。

2.在一個已得到最優解的單純形表中，如果存在一個非基變量的檢驗數

為零，把這個非基變量作為換入變量進行迭代，在新的單純形表中，基變量的檢驗數為零，用同樣的方法可證明其他的非基變量的檢驗數不變，仍然小於零，這樣就證明了新得到的基本可行解仍然是最優解。即對於某個最優的基本可行解，如果存在某個非基變量的檢驗數為零，則此線性規劃問題有無窮多最優解。

3.在單純形法計算過程中，在確定換入變量之後，確定換出變量時有時存在兩個以上的相同的最小比值，這種情況稱之為退化。 ^[1] 

單純形法是一種主要的解決線性規劃問題的方法，它在生活的成本問題、交通選擇或規劃學術問題等方面得到廣泛應用。其中，要掌握單純形法的計算過程，根據目標方程，約束條件建立初始單純形表；找出初始可行基，確定初始基可行解；算出非基變量的檢驗數是否大於零；若檢驗數全部小於等於零，則可停止計算，若檢驗數有大於零，取最大的檢驗數所對應的為換入變量，再按確定規則找出換出變量，重新列出單純形法，進行迭代。正確的應用單純形法解決問題能夠提高準確率，從而進行合理的規劃安排，使得效果或收益達到期待化或最優化。 ^[3]