線性規劃中的退化問題

退化問題是指在線性規劃中，單純形表中的基本可行解中出現一個或多個基變數等於零時，或者按最小比值來確定換出基的變數時，存在兩個以上相同最小比值的線性規劃問題。出現的原因是模型中存在多餘的約束，使多個基本可行解對應統一頂點。這時有可能出現單純形法疊代的循環。

基本介紹

• 中文名：退化問題
• 外文名：Degradation problem
• 拼音：Tuì huà wèn tí
• 隸屬：數理科學
• 學科：運籌學
• 解決方法：攝動法、字典序法等

基本內容

當線性規劃原問題是退化問題時，由線性規劃問題的幾何解釋可知，通過該可行域某個極點的超平面超過n個，所以該點為一個退化的極點。根據攝動法原理，可在退化問題約束方程的右邊項做微小的擾動，使得超平面有一個微小的位移，原來相交於一點的若干個超平面略微錯開一些，退化極點變成不退化極點。決策者可根據問題的實際情況，適當增加或減少某些資源的數量，使得其疊代變為非退化的，以得到問題的最優解。

在線性規劃原問題是退化問題時，不能簡單地認為某一求解過程中的影子價格為0，所對應的資源一定是富餘資源。由上述問題得到的最優解，對約束方程進行計算，得到約束方程的三個方程全部取等式，即三種資源在最優解的情況下，松馳變數均為零。由資源的靈敏度分析可知，在此約束條件下，資源正恰好按最優方式全部用完，目標函式總收益達到最大。所以當線性規劃原問題為退化問題時，資源的影子價格不數的數稱為“下溢”。

處理方法

1. 若在最終表中原問題的解為非退化最優解，而其對偶問題的最優解為退化解，則原問題一定有無窮多個最優解。此時，以檢驗數為零的非基變數為入基變數，用單純形法繼續疊代，即可求出原問題的其它最優解；
2. 若在最終表中原問題的解為退化最優解，而其對偶問題的最優解為非退化解，則對偶問題一定有無窮多個最優解。此時，以原問題基變數中等於零的分量為出基變數，用對偶單純形法繼續疊代，即可求出對偶問題的其它最優解；
3. 若在最終表中原問題與對偶問題的最優解均為退化最優解，則可採用單純形法也可採用對偶單純形法繼續疊代，至於問題是否有無窮多個最優解，要根據具體情況再做判斷。

套用

線性規劃理論在工程設計、生產管理、交通運輸、國防等領域以及自然科學的很多學科中都有著廣泛的套用。線性規劃問題雖然是一個古老的問題，但求解線性規劃問題的方法在不斷發展：從單純形法、對偶單純形法、橢圓方法到內點方法等等。雖然線性規劃有這么多解法，但是單純形方法在其中的統治地位始終沒變。對於退化線性規劃問題，用單純形方法求解時有可能產生循環，因此，研究退化線性規劃問題成為人們研究線性規劃問題的一個重要方面。1952年A. Charnes和W. W. Cooper給出了求解退化線性規劃問題的攝動法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化線性規劃問題的字典序法，1976年G. G. Bland提出了求解退化線性規劃問題的Bland法則，這些方法都能避免循環發生。