运筹学-对偶单纯形法

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

2、可行解（X XB B =B =B-1 -1 b0); b0);（3) 3) 检验数检验数C CC CB BB B-1 -1A A 0 0 ， -C-CB B B B-1 -100 即即YA YA C C， Y Y 0 0 即对偶解可行即对偶解可行（三）（三） 对偶单纯形法对偶单纯形法前提是前提是原问原问题可行题可行0 NBXX 优化条件优化条件0BC0ABCC1B1B 前提是前提是对偶对偶可行可行 优化优化条件条件YA C， Y 0原问题基可行解原问题基可行解 最优解判断最优解判断0jjjzc01bBb对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断 原问题的初始基解的检验

3、数全部原问题的初始基解的检验数全部00； b b列至少一个元素列至少一个元素 0 0； 在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换 每一次迭代过程中取出基变量中的一个负分量每一次迭代过程中取出基变量中的一个负分量 作为换出变量作为换出变量 去替换某个非基变量去替换某个非基变量( (作为换入变量作为换入变量), ), 使原始问题的非可行解向可行解靠近。使原始问题的非可行解向可行解靠近。 第一步：第一步： j j = 第二步：第二步： 若若 b bi i 00 （, , j j 0 0 , , 则原问题得到最优解则原问题得到最优解 若若b bi i 0 , 0 , j j 0

4、 0 , , 则用对偶单纯形法则用对偶单纯形法最小的负元素出基最小的负元素出基lj lj 0 0无可行解，无可行解，当当b bl l00，而对所有，而对所有j=1,nj=1,n，有，有a alj lj 0 0，则原问题无可行解。则原问题无可行解。证明证明：x xl l+a+al,m+1l,m+1x xm+1m+1+a+al,nl,nx xn n=b=bl l 因因a alj lj 0(j=m+1,n)0(j=m+1,n)，又，又b bl l00， 故有故有x xl l0 0，即不可能存在即不可能存在x xj j 0(j=1,n)0(j=1,n)的解，的解，故原问题无可行解，故原问题无可行解，此

5、时对偶问题的目标函数值无界。此时对偶问题的目标函数值无界。若有：若有：Min cMin cj j z zj j / / lj lj|lj lj 0 , x 0 , x j j 为非基变量为非基变量 = c = ck k z zk k /lk lk 则确定则确定 变量，相应的列为主元列，变量，相应的列为主元列，标出标出, , 应用矩阵的初等行变换得到新的单纯形表。应用矩阵的初等行变换得到新的单纯形表。第四步：第四步：若对于若对于b bl l 0 , 0 , 且有且有a a lj lj 0 , 0 , 则则 确定确定 换入换入变量变量应用最小比值原则目的：应用最小比值原则目的：是在是在保持下一个对

6、偶问题的基解可行保持下一个对偶问题的基解可行的前提的前提下，减少原始问题的不可行性。下，减少原始问题的不可行性。 下面进行说明下面进行说明根据根据最小比值原则：最小比值原则：lkkkljljjjjazc0aazcmin 计计算算a alk lk为为主元素主元素x xk k为为进进基变量基变量 设下一个表中的检验数为设下一个表中的检验数为(c (cj j-z -zj j) ) ，则，则 lkkkljjjljkklkljjjjjazcazcazcaazczc(1)(1)对对a alj lj 0 0，因，因c cj jz zj j 0 0，故，故 ，又因主元素，又因主元素a alk lk00，故有故

7、有 ，所以，所以(c (cj jz zj j) ) 0 0； 0azcljjj 0azclkkk (2)(2)对对a alj lj00，因，因 ，故有，故有(c (cj jz zj j) ) 0 0；0azcazclkkkljjj 所以，所以，(c (cj jz zj j) ) 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-1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1

9、XBCB 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/5b bi i0, 0, j j00得到最优解为：得到最优解为：X X* *=(11/5, 2/5,0,0,0=(11/5, 2/5,0,0,0）T T对偶问题最优解为：对偶问题最优解为：TTyyY) 5/ 1 , 5/ 8 (),(*2*1*用对偶单纯形法求解下面线性规划用对偶单纯形法求解下面线性规划 4,3,2,1j,0 x1xx21x2xxx2x

10、xZmaxj42132121 构造对偶单纯形表进行迭代，构造对偶单纯形表进行迭代，从最后的表可以看到，从最后的表可以看到，B B-1 -1b b列元素中有列元素中有-20-200, ,x xj j为非基变量为非基变量=k k /lk lk注意：注意：若若x xl l为换出变量，所有为换出变量，所有lj lj00，则原问题无可行解。则原问题无可行解。初始可行基0y,y,y 1yy2y5 2yy6t . s32132132 321y5y24y15wmin 0,y 125 26.5215321432yyyyyyyyyts32152415maxyyyw0,y 125- 26.5215321432yyy

11、yyyyyyts32152415maxyyyw对偶问题的对偶问题的初始可行基初始可行基2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjcjjzc 换出42) 1, 2min(y换出换出minminj j/ljlj|ljlj00452/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/12

12、4005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzc2/32/7002/152/32/1102/152/154/14/1014/54/12404101513/13/2053/1006/16/1103/124005241510125100116020005241532525454321yyyyyyyyyyybYCBBjjzcjjzcjjzc最优解最优解对偶单纯形法与原始单纯形法内在的对应关系对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 bi0所有所有 b

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

14、eikikiab0aabmin 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