用對偶單純形法求解線性規(guī)劃問題

1、例4-7用對偶單純形法求解線性規(guī)劃問題Min z =5x 1+3x2s.t.-2 Xi + 3x 2 A 6X1 - 6 x 2 A 4A 0 (j=1,2 )解：將問題轉(zhuǎn)化為XjMax z = -5X1 -3 x 2s.t. 2xi - 3xX 3 = -6-3 xi + 6 X2 + x 4A -4Xj其中，X3 , X4,3,4 )A 0 (j=1,2為松弛變量，可以作為初始基變量，單純形表見表表4-17例4-7單純形表4-17.e-6-3-40Cb迭代0次XbbX1X2焉X0X4-62-3100X-4-3601zcZj0-5-300CB迭代1次XbbXXaX3X4-3X42-2/31-

2、1/300X3-161021ZCjZj6-70-10在表4-17中,b=-16<0,而yA 0,故該問題無可行解.注意：對偶單純形法仍是求解原問題，它是適用于當(dāng)原問題無可行基，且所有檢驗(yàn)數(shù)均為負(fù)的情況.若原問題既無可行基，而檢驗(yàn)數(shù)中又有小于0的情況.只能用人工變量法求解.在計(jì)算機(jī)求解時，只有人工變量法，沒有對偶單純形法.3.對偶問題的最優(yōu)解,可以根據(jù)這些關(guān)系，由對偶理論可知，在原問題和對偶問題的最優(yōu)解之間存在著密切的關(guān)系 從求解原問題的最優(yōu)單純形表中，得到對偶問題的最優(yōu)解.(1)設(shè)原問題(P)為Min z= ex則標(biāo)準(zhǔn)型 (LP) 為AX bs.t.X0Max z=CXAX bs.t.X

3、0其對偶線性規(guī)劃(D)為Max z=bTYAX bs.t.X0用對偶單純形法求解時，有 Pj=-ei， cj=0(LP),得最優(yōu)基B和最優(yōu)單純形表 T ( B)。對于(LP)來說，當(dāng)j=n+iT (B )中，對于檢驗(yàn)數(shù)，有(b n+1,b n+2b n+m) = (Cn+i, cn+2，cn+m) -CbB-1 (Pn+1,Pn+2 ,Pn+m) =- CbB-1 (-I)于是，Y*= (b n+1,b n+2b n+m T 。可見，在(LP)的最優(yōu)單純形表中，剩余變 量對應(yīng)的檢驗(yàn)數(shù)就是對偶問題的最優(yōu)解。同時，在最優(yōu)單純形表T ( B)中，由于剩余變量對應(yīng)的系數(shù)所以從而，在最優(yōu)單純形表b n+

4、2 bB 1 = ( -y n+1 , -y n+2 -y n+m)例 4-8 求下列線性規(guī)劃問題的對偶問題的最優(yōu)解。Min z =6x 1+8x2s.t.Xi + 2x2 >20X1 + 2x 2 A 50Xj > 0 (j=1,2 )解： 將問題轉(zhuǎn)化為Max z =-6x 1-8x 2s.t.-x1 2x 2 + x 3=20-3X1 - 2X 2 + X 4 =50Xj > 0 (j=1,2 , 3,4 )用對偶單純形法求解如表表4-18例4-8單純形表C-6-800CBXbbX1X2XiX迭代0 次-8X45/201-3/41/4-6X515101/2-1/2ZCjZ

5、j-1100031在引入松弛變量化為標(biāo)準(zhǔn)型之后，約束等式兩側(cè)同乘-1,能夠立即得到檢驗(yàn)數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進(jìn)行求解，非常方便。對于有些線性規(guī)劃模型， 如果在開始求解時不能很快使所有檢驗(yàn)數(shù)非正，最好還是采用單純形法求解。因?yàn)?，這樣可以免去為使檢驗(yàn)數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補(bǔ)充。除此之外，在對線性規(guī)劃進(jìn)行靈敏度分 析中有時也要用到對偶單純形方法，可以簡化計(jì)算。標(biāo)準(zhǔn)化：s.t.Min f = 2x1 + 3x2 + 4x3S.t.x1 + 2x2 + x332x1 - x2 + x34x1 , x2 , x3 >0Max z = - 2x1 - 3x2-4x3例4-9：求解線性規(guī)劃問題:-x1-2x2-x3+x4= -3-2x1+x2-3x3+x5= -4x1,x2,x3,x4,