線性規劃中的退化問題

線性規劃中的退化問題

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

基本介紹

  • 中文名:退化問題
  • 外文名: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法則,這些方法都能避免循環發生。

相關詞條

熱門詞條

聯絡我們