換出變數

換出變數，又稱出基變數，是指線上性規劃問題中，在確定換入變數之後，根據確定規則被選定換到非基變數中去的基變數。

基本介紹

• 中文名：換出變數
• 外文名：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.在單純形法計算過程中，在確定換入變數之後，確定換出變數時有時存在兩個以上的相同的最小比值，這種情況稱之為退化。

套用

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