运筹学对偶单纯形法ppt课件

1、v对偶单纯形法的求解思路v对偶单纯形法的求解步骤 对偶单纯形法是根据对偶原理和单纯形法的对偶单纯形法是根据对偶原理和单纯形法的 原理而设计出来求解原理而设计出来求解 原原LPLP的一种方法。的一种方法。 采用的技术是在原问题的单纯形表格上进行采用的技术是在原问题的单纯形表格上进行对偶处理。对偶处理。留意留意: :对偶单纯形法不是求解对偶问题的单纯对偶单纯形法不是求解对偶问题的单纯 形法。形法。（一）（一） 什么是对偶单纯形法什么是对偶单纯形法（二）（二） 普通单纯形法普通单纯形法BXNXSX1SYNBCCBN1 1 BCB02SY Y 单纯形法中原问题的最优解满足的条件单纯形法中原问题的最优解

2、满足的条件: :（ 1 1是基本解；是基本解； （ 2 2可行解可行解XB =B-1 b0);XB =B-1 b0);（3) 3) 检验数检验数C CCBB-1ACBB-1A0 0 ， -CB B-10-CB B-10 即即YA YA C C， Y Y0 0 即对偶解可行即对偶解可行（三）（三） 对偶单纯形法对偶单纯形法前提是原问前提是原问题可行题可行0 NBXX 优化条件优化条件0BC0ABCC1B1B 前提是对偶前提是对偶可行可行 优化优化条件条件YA C， Y 0原问题基可行解原问题基可行解 最优解判断最优解判断0jjjzc01bBb对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解

3、判断最优解判断 第一步：第一步： 构造初始单位阵，确定原问题构造初始单位阵，确定原问题max ) max ) 的的初始基初始基B B，使所有检验数，使所有检验数 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 行即检查基变量的取值）行即检查基变量的取值） 假设假设 bi 0 bi 0 （XB

4、= B -1 b 0XB = B -1 b 0）, j 0 , , j 0 , 则原问题得到最优解则原问题得到最优解 ，计算停，计算停; ; 若若bi 0 , j 0 , bi 0 , j 0 , 则用对偶单纯形法进行换基迭代则用对偶单纯形法进行换基迭代. .当当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)的解，的解，故原问题无可行解，故原问题无可行解，此时对偶问题的目标函数值无界。此时对偶问题的目标函数值无界。若有：若有：Min cj Min cj zj / lj|lj 0 , x j zj / lj|lj 0 , x j 为非基变为非基变量量 = ck = ck zk /lk zk /lk 则确定则确定 xk xk 为换入变量，相应的列为主元列，为换入变量，相应的列为主元列，标出主元素标出主元素lk ,lk , 应用矩阵的初等行变换得到新的单纯形表。应用矩阵的初等行变换得到新的单纯形表。第四步：若对于第四步：若对于bl 0 , bl 0

6、 , 且有且有a lj 0 , a lj 0 , 那么那么 确定确定 换入变量换入变量应用最小比值原则目的：应用最小比值原则目的：是在保持下一个对偶问题的基解可行的前提是在保持下一个对偶问题的基解可行的前提下，减少原始问题的不可行性。下，减少原始问题的不可行性。 下面进行说明下面进行说明根据最小比值原则：根据最小比值原则：lkkkljljjjjazc0aazcmin 计计算算alkalk为主元素为主元素xkxk为进基变量为进基变量 设下一个表中的检验数为设下一个表中的检验数为(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)则有：则有： 第五步：用换入变量替换换出变量，得到一第五步：用换入变量替换换出变量，得到一个新的基，对新的基再检查是否所有个新的基，对新的基再检查是否所有 如果是，得原问题的最优解；如果是，得原问题的最优解；

8、如果否，回到第一步再重复计算，直到检如果否，回到第一步再重复计算，直到检验数行非正，基列非负，得到最终表验数行非正，基列非负，得到最终表. . 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得到最优解为：得到最优解为：X X* *=(11/5, 2/5,0,0,0=(11/5, 2/5,0,0,0T T对偶问题最优解为：对偶问题最优解为：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为换出变量，所有为换出变量，所有lj0lj0，则原问题无可行解。则原问题无可行解。初始可行基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最优解最优解对偶单纯形法与原始单纯形法内在的对应关系对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件一切一切 bi0一切一切 bi0?最优性检验最优性检验一切一切

13、0j0 ?j一切一切换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解的进化原始基本解的进化可行可行 最优最优非可行非可行 可行可行( (最优最优) )是是是是否否否否一切一切得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数0一切一切计算计算以aek为中心元素进行迭代以alk为中心元素进行迭代停没有最优解没有最优解普通单纯形法对偶单纯形法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) 检验数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