運(yùn)籌學(xué)課件-對偶單純形法

對偶單純形法并不是求解對偶問題解的方法，而是利用對偶理論求解原問題的解的方法。以標(biāo)準(zhǔn)型線性規(guī)劃為例，對于線性規(guī)劃：

若B是A中的一個基，當(dāng)B對應(yīng)的基本解也是可行解時，稱B是可行基，當(dāng)B對應(yīng)的基本可行解是最優(yōu)解時，稱B為最優(yōu)基。若是對偶問題的可行解，則稱B是對偶可行基。2.2對偶單純形法可見對偶可行基還是原問題的一個基，且使單純形乘子成為對偶問題的可行解，即滿足。由第一章的知識可知最優(yōu)基既應(yīng)該是可行基，也應(yīng)該使檢驗(yàn)數(shù)，而這就意味著B也是對偶可行基。反之當(dāng)B是可行基，且也是對偶可行基時，對應(yīng)于B的基本可行解的檢驗(yàn)數(shù)，因此B也是最優(yōu)基。定理

B是線性規(guī)劃的最優(yōu)基的充要條件是：B是可行基，而且也是對偶可行基。單純形法的基本過程可以歸納為保持基的可行性，逐步迭代最終達(dá)到基的對偶可行性。

先找到一個對偶可行基，然后保持基的對偶可行性，逐步迭代直至最終達(dá)到基的可行性。這種算法就稱為對偶單純形法。

對偶單純形法的基本思想對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗(yàn)數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗(yàn)數(shù)非正）。

如果得到的基本解的分量皆非負(fù)則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚校?dāng)同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。

對偶單純形法在什么情況下使用：

應(yīng)用前提：有一個基，其對應(yīng)的基滿足:

①單純形表的檢驗(yàn)數(shù)行全部非正（對偶可行）；

②變量取值可有負(fù)數(shù)（非可行解）。

注：通過矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形表。設(shè)原問題是（記為LP）：對偶問題是（記為DP）：

根據(jù)對偶性質(zhì)6，可以構(gòu)造一個求線性規(guī)劃的另一種方法，即對偶單純形法。

對偶單純形法的計算步驟：對偶單純形法的條件是：初始表中對偶問題可行，即極大化問題時，極小化問題時。

（1）建立初始對偶單純形表,將線性規(guī)劃的約束化為等式，求出一組基本解，因?yàn)閷ε紗栴}可行，即全部檢驗(yàn)數(shù)（max）或

（min）,當(dāng)基本解可行時，則達(dá)到最優(yōu)解；若基本解不可行，即有某個基變量的解bi<0，則進(jìn)行換基計算；（2）先確定出基變量。行對應(yīng)的變量xl出基；

（3）再選進(jìn)基變量。求最小比值（4）求新的基本解，用初等變換將主元素alk化為l,k列其它元素化為零，得到新的基本解，轉(zhuǎn)到第一步重復(fù)運(yùn)算?！纠?.10】用對偶單純形法求解【解】先將約束不等式化為等式，再兩邊同乘以（－1），得到用對偶單純形法，迭代過程如下頁。表2－4

應(yīng)當(dāng)注意：（1）用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解；（2）初始表中一定要滿足對偶問題可行，也就是說檢驗(yàn)數(shù)滿足最優(yōu)判別準(zhǔn)則；（3）最小比值中的絕對值是使得比值非負(fù)，在極小化問題時

，分母aij<0這時必須取絕對值。在極大化問題中，

分母aij<0，總滿足非負(fù)，這時絕對值符號不起作用，可以去掉。如在本例中將目標(biāo)函數(shù)寫成這里

在求θk時就可以不帶絕對值符號。（4）對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進(jìn)基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進(jìn)基變量；（5）普通單純形法的最小比值是其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是其目的是保證下一個對偶問題的基本解可行；（6）對偶單純形法在確定出基變量時，若不遵循規(guī)則，任選一個小于零的bi對應(yīng)的基變量出基，不影響計算結(jié)果，只是迭代次數(shù)可能不一樣。例2.11：求解線性規(guī)劃問題：

單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計算計算以為中心元素進(jìn)行迭代以為中心元素進(jìn)行迭代停沒有最優(yōu)解沒有最優(yōu)解單純形法對偶單純形法

對偶單純形法的適用范圍對偶單純形法適合于解如下形式的線性規(guī)劃問題

在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進(jìn)行求解，非常方便。對于有些線性規(guī)劃模型，如果在開始求解時不