-
換出變量
鎖定
- 中文名
- 換出變量
- 外文名
- 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.在一個已得到最優解的單純形表中,如果存在一個非基變量的檢驗數
為零,把這個非基變量作為換入變量進行迭代,在新的單純形表中,基變量的檢驗數為零,用同樣的方法可證明其他的非基變量的檢驗數不變,仍然小於零,這樣就證明了新得到的基本可行解仍然是最優解。即對於某個最優的基本可行解,如果存在某個非基變量的檢驗數為零,則此線性規劃問題有無窮多最優解。