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