對(duì)偶單純形法

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

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

3、B1 ）的不可行性逐步消失（即檢驗(yàn)數(shù)逐步變?yōu)榉钦恢钡絯0是（DP）的可行解，x0就是（LP）的最優(yōu)解。因（LP）和（DP）互為對(duì)偶問(wèn)題，故基于對(duì)稱的想法，我們也可以把迭代過(guò)程建立在滿足對(duì)偶問(wèn)題（DP）的可行解上，即在迭代過(guò)程中保持對(duì)應(yīng)的對(duì)偶問(wèn)題的解w0的可行性（從而x0的檢驗(yàn)數(shù)全部非正），逐步消除原問(wèn)題（LP）的基本解x0的不可行性（即使x0非負(fù)），最后達(dá)到雙方同時(shí)為可行解，x0和w0也就同時(shí)為最優(yōu)解了。這就是對(duì)偶單純形法的基本思想。按照此設(shè)想，為求原問(wèn)題（LP）的最優(yōu)解，出發(fā)點(diǎn)將是一個(gè)不一定可行的基本解（某些變量可能取負(fù)值），但滿足最優(yōu)性判別條件（所有j 0）。下面將討論對(duì)偶單純形法的迭

4、代步驟。 設(shè)x0是（LP）的一個(gè)基本解（不一定可行），不失一般性，可設(shè)相應(yīng)的典式為其中j 0，ai 可正可負(fù)。作單純形表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迭代的基本方式與單純形法一樣，只是離基變量與進(jìn)基變量的選擇方法不同。如果說(shuō)原始單純形法是“按列選主元”的話，那末對(duì)偶單純形法就是“按行選主元”。具體步驟如下：step1) 若，則為最優(yōu)解；step2) 設(shè)，可選擇離基變量：。此時(shí)，若，則原問(wèn)題是不可行的；否則轉(zhuǎn)下一步；step3) 選擇進(jìn)基變量

5、，其要求是迭代后任滿足。假設(shè)則選擇是進(jìn)基變量。（理由呢？）；step4) 施行 k, l 旋轉(zhuǎn)變換，使進(jìn)基，離基，得到一個(gè)新的基本解（滿足所有的），轉(zhuǎn)step1)。注 在step2)中，原問(wèn)題是不可行的理由是：若，則方程沒(méi)有解（即原問(wèn)題的解不可行），否則方程的右邊小于0（<），而左邊不小于0（）。例1 利用對(duì)偶單純形法求解以下線性規(guī)劃：min f=2x1+x2 (LP): s.t. 解 引入剩余變量x3,，x4，x5，則原問(wèn)題變成min f=2x1+x2 (LP1) : s.t. 將約束等式兩端同乘以-1，就直接得到基變量x3，x4，x5，從而得到第一個(gè)單純形表為 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取為進(jìn)基變量。經(jīng)旋轉(zhuǎn)變換后得表 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為進(jìn)基變量，得表 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至此，基變量值已全部非負(fù)，故已得最優(yōu)解x= ( 3/5, 6/5, 0, 0, 1 )T若用原始單純形法求解，則需在問(wèn)題（LP1）中再引進(jìn)三個(gè)非負(fù)的人工變量，然后利用兩階段法求解。實(shí)際計(jì)算可知，這樣做的計(jì)算量較大。從這個(gè)例題可以看到，對(duì)于某些線性規(guī)劃問(wèn)題來(lái)說(shuō)，使用對(duì)偶單純形法比用原始單純形法更具優(yōu)越性。一般來(lái)說(shuō)，對(duì)偶單純形法適合于求解如下形式的線性規(guī)劃問(wèn)題（設(shè)b0） min bT y s.t. 在引入變量化為標(biāo)準(zhǔn)形之后，約束等式兩端同乘以-1，能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃的基本解，可以直接建立初始對(duì)偶單純形表進(jìn)行求解，非常方便。需要注意的是，對(duì)于有些線性規(guī)劃模型，若在開(kāi)始求解時(shí)，我們不能很快使所有檢驗(yàn)數(shù)非正，最好還是采用