基本內容
當線性規劃原問題是退化問題時,由線性規劃問題的幾何解釋可知,通過該可行域某個極點的超平面超過n個,所以該點為一個退化的極點。根據攝動法原理,可在退化問題約束方程的右邊項做微小的擾動,使得超平面有一個微小的位移,原來相交於一點的若干個超平面略微錯開一些,退化極點變成不退化極點。決策者可根據問題的實際情況,適當增加或減少某些資源的數量,使得其疊代變為非退化的,以得到問題的最優解。
線上性規劃原問題是退化問題時,不能簡單地認為某一求解過程中的影子價格為0,所對應的資源一定是富餘資源。由上述問題得到的最優解,對約束方程進行計算,得到約束方程的三個方程全部取等式,即三種資源在最優解的情況下,松馳變數均為零。由資源的靈敏度分析可知,在此約束條件下,資源正恰好按最優方式全部用完,目標函式總收益達到最大。所以當線性規劃原問題為退化問題時,資源的影子價格不數的數稱為“下溢”。
處理方法
若在最終表中原問題的解為非退化最優解,而其對偶問題的最優解為退化解,則原問題一定有無窮多個最優解。此時,以檢驗數為零的非基變數為入基變數,用單純形法繼續疊代,即可求出原問題的其它最優解;
若在最終表中原問題的解為退化最優解,而其對偶問題的最優解為非退化解,則對偶問題一定有無窮多個最優解。此時,以原問題基變數中等於零的分量為出基變數,用對偶單純形法繼續疊代,即可求出對偶問題的其它最優解;
若在最終表中原問題與對偶問題的最優解均為退化最優解,則可採用單純形法也可採用對偶單純形法繼續疊代,至於問題是否有無窮多個最優解,要根據具體情況再做判斷。
1.若在最終表中原問題的解為非退化最優解,而其對偶問題的最優解為退化解,則原問題一定有無窮多個最優解。此時,以檢驗數為零的非基變數為入基變數,用單純形法繼續疊代,即可求出原問題的其它最優解;
2.若在最終表中原問題的解為退化最優解,而其對偶問題的最優解為非退化解,則對偶問題一定有無窮多個最優解。此時,以原問題基變數中等於零的分量為出基變數,用對偶單純形法繼續疊代,即可求出對偶問題的其它最優解;
3.若在最終表中原問題與對偶問題的最優解均為退化最優解,則可採用單純形法也可採用對偶單純形法繼續疊代,至於問題是否有無窮多個最優解,要根據具體情況再做判斷。
套用
線性規劃理論在工程設計、生產管理、交通運輸、國防等領域以及自然科學的很多學科中都有著廣泛的套用。線性規劃問題雖然是一個古老的問題,但求解線性規劃問題的方法在不斷發展:從單純形法、對偶單純形法、橢圓方法到內點方法等等。雖然線性規劃有這么多解法,但是單純形方法在其中的統治地位始終沒變。對於退化線性規劃問題,用單純形方法求解時有可能產生循環,因此,研究退化線性規劃問題成為人們研究線性規劃問題的一個重要方面。1952年A. Charnes和W. W. Cooper給出了求解退化線性規劃問題的攝動法,1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化線性規劃問題的字典序法,1976年G. G. Bland提出了求解退化線性規劃問題的Bland法則,這些方法都能避免循環發生。