換出變數

換出變數

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

基本介紹

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

套用

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

相關詞條

熱門詞條

聯絡我們