[科普中國(guó)]-退化問(wèn)題

退化問(wèn)題是指在線(xiàn)性規(guī)劃中，單純形表中的基本可行解中出現(xiàn)一個(gè)或多個(gè)基變量等于零時(shí)，或者按最小比值來(lái)確定換出基的變量時(shí)，存在兩個(gè)以上相同最小比值的線(xiàn)性規(guī)劃問(wèn)題。出現(xiàn)的原因是模型中存在多余的約束，使多個(gè)基本可行解對(duì)應(yīng)統(tǒng)一頂點(diǎn)。這時(shí)有可能出現(xiàn)單純形法迭代的循環(huán)。

基本內(nèi)容當(dāng)線(xiàn)性規(guī)劃原問(wèn)題是退化問(wèn)題時(shí)，由線(xiàn)性規(guī)劃問(wèn)題的幾何解釋可知，通過(guò)該可行域某個(gè)極點(diǎn)的超平面超過(guò)n個(gè)，所以該點(diǎn)為一個(gè)退化的極點(diǎn)。根據(jù)攝動(dòng)法原理，可在退化問(wèn)題約束方程的右邊項(xiàng)做微小的擾動(dòng)，使得超平面有一個(gè)微小的位移，原來(lái)相交于一點(diǎn)的若干個(gè)超平面略微錯(cuò)開(kāi)一些，退化極點(diǎn)變成不退化極點(diǎn)。決策者可根據(jù)問(wèn)題的實(shí)際情況，適當(dāng)增加或減少某些資源的數(shù)量，使得其迭代變?yōu)榉峭嘶?，以得到?wèn)題的最優(yōu)解。

在線(xiàn)性規(guī)劃原問(wèn)題是退化問(wèn)題時(shí)，不能簡(jiǎn)單地認(rèn)為某一求解過(guò)程中的影子價(jià)格為0，所對(duì)應(yīng)的資源一定是富余資源。由上述問(wèn)題得到的最優(yōu)解，對(duì)約束方程進(jìn)行計(jì)算，得到約束方程的三個(gè)方程全部取等式，即三種資源在最優(yōu)解的情況下，松馳變量均為零。由資源的靈敏度分析可知，在此約束條件下，資源正恰好按最優(yōu)方式全部用完，目標(biāo)函數(shù)總收益達(dá)到最大。所以當(dāng)線(xiàn)性規(guī)劃原問(wèn)題為退化問(wèn)題時(shí)，資源的影子價(jià)格不數(shù)的數(shù)稱(chēng)為“下溢”。1

處理方法若在最終表中原問(wèn)題的解為非退化最優(yōu)解，而其對(duì)偶問(wèn)題的最優(yōu)解為退化解，則原問(wèn)題一定有無(wú)窮多個(gè)最優(yōu)解。此時(shí)，以檢驗(yàn)數(shù)為零的非基變量為入基變量，用單純形法繼續(xù)迭代，即可求出原問(wèn)題的其它最優(yōu)解；

若在最終表中原問(wèn)題的解為退化最優(yōu)解，而其對(duì)偶問(wèn)題的最優(yōu)解為非退化解，則對(duì)偶問(wèn)題一定有無(wú)窮多個(gè)最優(yōu)解。此時(shí)，以原問(wèn)題基變量中等于零的分量為出基變量，用對(duì)偶單純形法繼續(xù)迭代，即可求出對(duì)偶問(wèn)題的其它最優(yōu)解；

若在最終表中原問(wèn)題與對(duì)偶問(wèn)題的最優(yōu)解均為退化最優(yōu)解，則可采用單純形法也可采用對(duì)偶單純形法繼續(xù)迭代，至于問(wèn)題是否有無(wú)窮多個(gè)最優(yōu)解，要根據(jù)具體情況再做判斷。2

應(yīng)用線(xiàn)性規(guī)劃理論在工程設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸、國(guó)防等領(lǐng)域以及自然科學(xué)的很多學(xué)科中都有著廣泛的應(yīng)用。線(xiàn)性規(guī)劃問(wèn)題雖然是一個(gè)古老的問(wèn)題，但求解線(xiàn)性規(guī)劃問(wèn)題的方法在不斷發(fā)展：從單純形法、對(duì)偶單純形法、橢圓方法到內(nèi)點(diǎn)方法等等。雖然線(xiàn)性規(guī)劃有這么多解法，但是單純形方法在其中的統(tǒng)治地位始終沒(méi)變。對(duì)于退化線(xiàn)性規(guī)劃問(wèn)題，用單純形方法求解時(shí)有可能產(chǎn)生循環(huán)，因此，研究退化線(xiàn)性規(guī)劃問(wèn)題成為人們研究線(xiàn)性規(guī)劃問(wèn)題的一個(gè)重要方面。1952年A. Charnes和W. W. Cooper給出了求解退化線(xiàn)性規(guī)劃問(wèn)題的攝動(dòng)法，1954年G. B. Dantzig, A. Orden和P. Wolfe提出了求解退化線(xiàn)性規(guī)劃問(wèn)題的字典序法，1976年G. G. Bland提出了求解退化線(xiàn)性規(guī)劃問(wèn)題的Bland法則，這些方法都能避免循環(huán)發(fā)生。1

本詞條內(nèi)容貢獻(xiàn)者為:

孫和軍 - 副教授 - 南京理工大學(xué)