运筹学-对偶单纯形法.
《运筹学-对偶单纯形法.》由会员分享，可在线阅读，更多相关《运筹学-对偶单纯形法.（32页珍藏版）》请在文档大全上搜索。
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,j=1,n,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,0(j=m+1,n),n)，又，又b bl l00， 故有故有x xl l0 0，即不可能存在即不可能存在x xj j 0(j=1,0(j=1,n),n)的解，的解，故原问题无可行解，故原问题无
5、可行解，此时对偶问题的目标函数值无界。此时对偶问题的目标函数值无界。若有：若有：Min Min c 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 lk
7、00，故有故有 ，所以，所以(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)则有：则有： 第五步：第五步：用换入变量替换换出变量，得到一用换入变量替换换出变量，得到一个个新的基新的基，对新的基再检查是否所有，对新的基再检查是否所有 如果是，得原问题的最优解；如果是，得原问题的最优解； 如果否，回到第一步再重复计算，直到如果否，回到第一步再重复计算，直到
