1、精選優質文檔-傾情為你奉上§6 對偶單純形法在介紹對偶單純形法之前，讓我們先利用對偶理論來重溫一下單純形法的基本思想，以便給單純形法一種新的解釋。考慮線性規劃（LP）和其對偶規劃（DP）： (LP) s.t (DP) s.t 我們已經知道，（LP）的單純形表為 基變量 x1 x2 x n xB B-1 A B-1b f cBT B-1 A cT cBT B1b定理1 設(LP)的任一基本解為x0，它對應于基B，并作(w0 )T= cBT B1。若x0 和w0 分別是(LP)和（DP）的可行解，則x0 和w 0 也分別是(LP)和（DP）的最優解。證明 因w0 是（DP）的可行解，即

2、(w0 )T A cT 從而有 cBT B1A - cT 0此式說明，x0是對應于基B的基本可行解，且所有的檢驗數j 0故x0是（LP）的最優解。此外，還有(w0 )T b = cBT B1 b = cBT xB0 = c x0從而由線性規劃的對偶定理知，w 0 也是（DP）的最優解。 證畢。由以上證明過程可看到：x0（LP）的任一基本解）的檢驗數全部非正與(w0 )T= cBT B1是對偶問題（DP）的可行解等價。據此我們可對單純形法作如下解釋：從一個基本解x0出發迭代到另一個基本解，在迭代過程中始終保持解的可行性（基本可行解），同時使它所對應的對偶規劃的解w0（滿足（w0 ）T= cBT

3、B1 ）的不可行性逐步消失（即檢驗數逐步變為非正）；直到w0是（DP）的可行解，x0就是（LP）的最優解。因（LP）和（DP）互為對偶問題，故基于對稱的想法，我們也可以把迭代過程建立在滿足對偶問題（DP）的可行解上，即在迭代過程中保持對應的對偶問題的解w0的可行性（從而x0的檢驗數全部非正），逐步消除原問題（LP）的基本解x0的不可行性（即使x0非負），最后達到雙方同時為可行解，x0和w0也就同時為最優解了。這就是對偶單純形法的基本思想。按照此設想，為求原問題（LP）的最優解，出發點將是一個不一定可行的基本解（某些變量可能取負值），但滿足最優性判別條件（所有j 0）。下面將討論對偶單純形法的迭

4、代步驟。 設x0是（LP）的一個基本解（不一定可行），不失一般性，可設相應的典式為其中j 0，ai 可正可負。作單純形表xBx1 x mxm+1 xl x nx1xkxm1 00 11 m+1 1l 1 n k m+1 k l k n m m+1 m l m na1a ka mf0 0m+1 l nf 0迭代的基本方式與單純形法一樣，只是離基變量與進基變量的選擇方法不同。如果說原始單純形法是“按列選主元”的話，那末對偶單純形法就是“按行選主元”。具體步驟如下：step1) 若，則為最優解；step2) 設，可選擇離基變量：。此時，若，則原問題是不可行的；否則轉下一步；step3) 選擇進基變量

5、，其要求是迭代后任滿足。假設則選擇是進基變量。（理由呢？）；step4) 施行 k, l 旋轉變換，使進基，離基，得到一個新的基本解（滿足所有的），轉step1)。注 在step2)中，原問題是不可行的理由是：若，則方程沒有解（即原問題的解不可行），否則方程的右邊小于0（<），而左邊不小于0（）。例1 利用對偶單純形法求解以下線性規劃：min f=2x1+x2 (LP): s.t. 解 引入剩余變量x3,，x4，x5，則原問題變成min f=2x1+x2 (LP1) : s.t. 將約束等式兩端同乘以-1，就直接得到基變量x3，x4，x5，從而得到第一個單純形表為 x1 x2 x3 x4

6、 x5 x3x4x5 -3 -1 1 0 0 -4 -3* 0 1 0 -1 -2 0 0 1-3-6-2 f -2 -1 0 0 0 0 這里a3=-3, a4=-6, a5=-2, 最小值是a4，故x4為離基變量。在x4行中考慮比值,有 min =所以x2取為進基變量。經旋轉變換后得表 x1 x2 x3 x4 x5 x3x2x5 -5/3 0 1 -1/3 0 4/3 1 0 -1/3 0 5/3 0 0 -2/3 1-122 f -2/3 0 0 -1/3 0 2再取x3為離基變量，x1為進基變量，得表 x1 x2 x3 x4 x5 x1x2x5 1 0 -3/5 1/5 0 0 1 4

7、/5 -3/5 0 0 0 1 -1 13/56/51 f 0 0 -2/5 -1/5 012/5至此，基變量值已全部非負，故已得最優解x= ( 3/5, 6/5, 0, 0, 1 )T若用原始單純形法求解，則需在問題（LP1）中再引進三個非負的人工變量，然后利用兩階段法求解。實際計算可知，這樣做的計算量較大。從這個例題可以看到，對于某些線性規劃問題來說，使用對偶單純形法比用原始單純形法更具優越性。一般來說，對偶單純形法適合于求解如下形式的線性規劃問題（設b0） min bT y s.t. 在引入變量化為標準形之后，約束等式兩端同乘以-1，能夠立即得到檢驗數全部非正的原規劃的基本解，可以直接建立初始對偶單純形表進行求解，非常方便。需要注意的是，對于有些線性規劃模型，若在開始求解時，我們不能很快使所有檢驗數非正，最好還是采用