運籌學(xué)對偶單純形法ppt課件

1、v對偶單純形法的求解思路v對偶單純形法的求解步驟 對偶單純形法是根據(jù)對偶原理和單純形法的對偶單純形法是根據(jù)對偶原理和單純形法的 原理而設(shè)計出來求解原理而設(shè)計出來求解 原原LPLP的一種方法。的一種方法。 采用的技術(shù)是在原問題的單純形表格上進行采用的技術(shù)是在原問題的單純形表格上進行對偶處理。對偶處理。留意留意: :對偶單純形法不是求解對偶問題的單純對偶單純形法不是求解對偶問題的單純 形法。形法。（一）（一） 什么是對偶單純形法什么是對偶單純形法（二）（二） 普通單純形法普通單純形法BXNXSX1SYNBCCBN1 1 BCB02SY Y 單純形法中原問題的最優(yōu)解滿足的條件單純形法中原問題的最優(yōu)解

2、滿足的條件: :（ 1 1是基本解；是基本解； （ 2 2可行解可行解XB =B-1 b0);XB =B-1 b0);（3) 3) 檢驗數(shù)檢驗數(shù)C CCBB-1ACBB-1A0 0 ， -CB B-10-CB B-10 即即YA YA C C， Y Y0 0 即對偶解可行即對偶解可行（三）（三） 對偶單純形法對偶單純形法前提是原問前提是原問題可行題可行0 NBXX 優(yōu)化條件優(yōu)化條件0BC0ABCC1B1B 前提是對偶前提是對偶可行可行 優(yōu)化優(yōu)化條件條件YA C， Y 0原問題基可行解原問題基可行解 最優(yōu)解判斷最優(yōu)解判斷0jjjzc01bBb對偶問題的可行解對偶問題的可行解對偶問題對偶問題最優(yōu)解

3、判斷最優(yōu)解判斷 第一步：第一步： 構(gòu)造初始單位陣，確定原問題構(gòu)造初始單位陣，確定原問題max ) max ) 的的初始基初始基B B，使所有檢驗數(shù)，使所有檢驗數(shù) C j - Zj = j = Cj - CB B -1 Pj 0C j - Zj = j = Cj - CB B -1 Pj 0， 即即 Y = CB B -1 Y = CB B -1 （b b 列的值是對偶可行解，建列的值是對偶可行解，建立初始單純形表。立初始單純形表。 第二步：第二步： 可行性檢驗。可行性檢驗。 檢驗檢驗 b b 列列 和和j j 行即檢查基變量的取值）行即檢查基變量的取值） 假設(shè)假設(shè) bi 0 bi 0 （XB

4、= B -1 b 0XB = B -1 b 0）, j 0 , , j 0 , 則原問題得到最優(yōu)解則原問題得到最優(yōu)解 ，計算停，計算停; ; 若若bi 0 , j 0 , bi 0 , j 0 , 則用對偶單純形法進行換基迭代則用對偶單純形法進行換基迭代. .當(dāng)當(dāng)bl0bl0，而對所有，而對所有j=1,nj=1,n，有，有aljalj0 0，則原問題無可行解。則原問題無可行解。證明：證明：xl+al,m+1xm+1+al,nxn=blxl+al,m+1xm+1+al,nxn=bl 因因aljalj0(j=m+1,n)0(j=m+1,n)，又，又bl0bl0， 故有故有xl0 xl0，即不可能存

5、在即不可能存在xj xj0(j=1,n)0(j=1,n)的解，的解，故原問題無可行解，故原問題無可行解，此時對偶問題的目標(biāo)函數(shù)值無界。此時對偶問題的目標(biāo)函數(shù)值無界。若有：若有：Min cj Min cj zj / lj|lj 0 , x j zj / lj|lj 0 , x j 為非基變?yōu)榉腔兞苛?= ck = ck zk /lk zk /lk 則確定則確定 xk xk 為換入變量，相應(yīng)的列為主元列，為換入變量，相應(yīng)的列為主元列，標(biāo)出主元素標(biāo)出主元素lk ,lk , 應(yīng)用矩陣的初等行變換得到新的單純形表。應(yīng)用矩陣的初等行變換得到新的單純形表。第四步：若對于第四步：若對于bl 0 , bl 0

6、 , 且有且有a lj 0 , a lj 0 , 那么那么 確定確定 換入變量換入變量應(yīng)用最小比值原則目的：應(yīng)用最小比值原則目的：是在保持下一個對偶問題的基解可行的前提是在保持下一個對偶問題的基解可行的前提下，減少原始問題的不可行性。下，減少原始問題的不可行性。 下面進行說明下面進行說明根據(jù)最小比值原則：根據(jù)最小比值原則：lkkkljljjjjazc0aazcmin 計計算算alkalk為主元素為主元素xkxk為進基變量為進基變量 設(shè)下一個表中的檢驗數(shù)為設(shè)下一個表中的檢驗數(shù)為(cj-zj)(cj-zj)，那么，那么 lkkkljjjljkklkljjjjjazcazcazcaazczc(1)(

7、1)對對aljalj0 0，因，因cjcjzj zj0 0，故，故 ，又因主元素，又因主元素alk0alk0，故有故有 ，所以，所以(cj(cjzj)zj) 0 0； 0azcljjj 0azclkkk (2)(2)對對alj0alj0，因，因 ，故有，故有(cj(cjzj)zj) 0 0；0azcazclkkkljjj 所以，所以，(cj(cjzj)zj)0(j=10(j=1，n)n)則有：則有： 第五步：用換入變量替換換出變量，得到一第五步：用換入變量替換換出變量，得到一個新的基，對新的基再檢查是否所有個新的基，對新的基再檢查是否所有 如果是，得原問題的最優(yōu)解；如果是，得原問題的最優(yōu)解；

8、如果否，回到第一步再重復(fù)計算，直到檢如果否，回到第一步再重復(fù)計算，直到檢驗數(shù)行非正，基列非負，得到最終表驗數(shù)行非正，基列非負，得到最終表. . 0m, 1ibi 321432minxxx 0,43232321321321xxxxxxxxx321432maxxxxz 0,432325432153214321xxxxxxxxxxxxx 0,432325432153214321xxxxxxxxxxxxxCBXBbx1x2x3x4x5 cj-2-3-400-1-2-110-21-301x4x500-2-3-400 cj-zj-3-4minj/lj|lj0122 3434 0-5/21/21-1/21-

9、1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1XBCB cj00-4-3-2 cj-zjminj/lj|lj08/52bx5x4x3x2x1XBCB cj00-4-3-2-2/5-1/57/5011/5-2/5-1/510 x1x2-2-3-1/5-8/5-3/500 cj-zj11/52/5bi0, j0bi0, j0得到最優(yōu)解為：得到最優(yōu)解為：X X* *=(11/5, 2/5,0,0,0=(11/5, 2/5,0,0,0T T對偶問題最優(yōu)解為：對偶問題最優(yōu)解為：TTyyY) 5/ 1 , 5/ 8 (),(*2*1* 4,3,2,1j,0 x1xx21x

10、2xxx2xxZmaxj42132121從最后的表可以看到，從最后的表可以看到，B-1bB-1b列元素中有列元素中有-20-20,xjminj/lj|lj0,xj為非基變量為非基變量=k =k /lk/lk留意：留意：若若xl xl為換出變量，所有為換出變量，所有l(wèi)j0lj0，則原問題無可行解。則原問題無可行解。初始可行基0y,y,y 1yy2y5 2yy6t . s32132132 321y5y24y15wmin 0,y 125 26.5215321432yyyyyyyyyts32152415maxyyyw0,y 125- 26.5215321432yyyyyyyyyts32152415ma

11、xyyyw對偶問題的對偶問題的初始可行基初始可行基2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjcjjzc 換出42) 1, 2min(y換出換出minj/lj|ljminj/lj|lj00452/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/1240052415101251001

12、16020005241532525454321yyyyyyyyyyybYCBBjjzcjjzc2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzcjjzc最優(yōu)解最優(yōu)解對偶單純形法與原始單純形法內(nèi)在的對應(yīng)關(guān)系對偶單純形法與原始單純形法內(nèi)在的對應(yīng)關(guān)系原始單純形法原始單純形法對偶單純形法對偶單純形法前提條件前提條件一切一切 bi0一切一切 bi0?最優(yōu)性檢驗最優(yōu)性檢驗一切一切

13、0j0 ?j一切一切換入、出基換入、出基變量的確定變量的確定先確定換入基變量先確定換入基變量后確定換出基變量后確定換出基變量先確定換出基變量先確定換出基變量后確定換入基變量后確定換入基變量原始基本解的進化原始基本解的進化可行可行 最優(yōu)最優(yōu)非可行非可行 可行可行( (最優(yōu)最優(yōu)) )是是是是否否否否一切一切得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)0一切一切計算計算以aek為中心元素進行迭代以alk為中心元素進行迭代停沒有最優(yōu)解沒有最優(yōu)解普通單純形法對偶單純形法0j0ib0maxjjk 0bbminbiil 0ika0ljaekeikikiab0aabmin lkkljljia0aamin min z = 2x1+4x2+6x3 s.t. 2x1 - x2 + x3 10 x1+2x2+2x3 12 2x2 - x3 4 x1，x2，x3 0將問題化為：將問題化為：max z= -2x1- 4x2 - 6x3 s.t. -2x1 + x2 - x3+ x4=-10 x1+2x2+2x3 +x5=12 -2x2 + x3 +x6 =-4 xj 0 ( j=1,2,6) 檢驗數(shù)ccBxB-2 -4 -6 0 0 0 x1 x2 x3 x4 x5 x6 000 x4x5x6-2 1 -1 1 0 0 1 2 2 0 1