《运筹学对偶单纯形法》由会员分享，可在线阅读，更多相关《运筹学对偶单纯形法（32页珍藏版）》请在金锄头文库上搜索。
1、本节内容安排本节内容安排v对偶单纯形法的求解思路v对偶单纯形法的求解步骤 对偶单纯形法对偶单纯形法是根据对偶原理和单纯形法的是根据对偶原理和单纯形法的 原理而设计出来求解原理而设计出来求解 原原LPLP的一种方法。的一种方法。 采用的技术是在原问题的单纯形表格上进行采用的技术是在原问题的单纯形表格上进行对偶处理。对偶处理。注意注意: :对偶单纯形法不是求解对偶问题的单纯对偶单纯形法不是求解对偶问题的单纯 形法。形法。一一 对偶单纯形法的求解思路对偶单纯形法的求解思路（一）（一） 什么是对偶单纯形法什么是对偶单纯形法 1 1 单纯形法中原问题单纯形法中原问题(max)(max)的最优解满足的条的
2、最优解满足的条件件: : （ 1 1）是基本解）是基本解 （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 即对偶解可行即对偶解可行 （二）（二） 普通单纯形法普通单纯形法 2 2 2 2 普通单纯形法的求解思路普通单纯形法的求解思路普通单纯形法的求解思路普通单纯形法的求解思路: : : : 从满足（从满足（从满足（从满足（1 1 1 1），（），（），（），（2 2 2 2）的一个初始基本可行解出发）
3、的一个初始基本可行解出发）的一个初始基本可行解出发）的一个初始基本可行解出发 ( ( ( (此时原此时原此时原此时原LPLPLPLP问题中，问题中，问题中，问题中，b b b b列保持列保持列保持列保持0 0 0 0 ， 对偶的解对偶的解对偶的解对偶的解 一般为非可行基解），一般为非可行基解），一般为非可行基解），一般为非可行基解）， 通过逐步迭代，通过逐步迭代，通过逐步迭代，通过逐步迭代，增大原目标函数值，增大原目标函数值，增大原目标函数值，增大原目标函数值， 每一步迭代，都得到一个基本可行解，每一步迭代，都得到一个基本可行解，每一步迭代，都得到一个基本可行解，每一步迭代，都得到一个基本可行
4、解， 并且逐步迭代实现检验数行并且逐步迭代实现检验数行并且逐步迭代实现检验数行并且逐步迭代实现检验数行0 (0 (0 (0 (对偶解可行对偶解可行对偶解可行对偶解可行) ) ) )。0迭代到（迭代到（迭代到（迭代到（3 3 3 3）得到满足，即所有检验数）得到满足，即所有检验数）得到满足，即所有检验数）得到满足，即所有检验数0000，此时，原问题的基可行解达到最优时，此时，原问题的基可行解达到最优时，此时，原问题的基可行解达到最优时，此时，原问题的基可行解达到最优时，对偶的基解由不可行达到可行，对偶的基解由不可行达到可行，对偶的基解由不可行达到可行，对偶的基解由不可行达到可行，得到的这个基可行
5、解也是对偶问题的最优解。得到的这个基可行解也是对偶问题的最优解。得到的这个基可行解也是对偶问题的最优解。得到的这个基可行解也是对偶问题的最优解。 3 3 3 3 普通单纯型法的求解过程：普通单纯型法的求解过程：普通单纯型法的求解过程：普通单纯型法的求解过程：对原问题的一个基可行解，判别是否所有对原问题的一个基可行解，判别是否所有对原问题的一个基可行解，判别是否所有对原问题的一个基可行解，判别是否所有检验数检验数检验数检验数 非正非正非正非正 c c c cj j j j-z-z-z-zj j j j 0(j=1, ,n)0(j=1, ,n)0(j=1, ,n)0(j=1, ,n)；若是若是若是
6、若是，又基变量中，又基变量中，又基变量中，又基变量中无非零人工变量无非零人工变量无非零人工变量无非零人工变量，即找到问题最，即找到问题最，即找到问题最，即找到问题最优解，基变量中含有非零人工变量，则无最优解；优解，基变量中含有非零人工变量，则无最优解；优解，基变量中含有非零人工变量，则无最优解；优解，基变量中含有非零人工变量，则无最优解；若否若否若否若否，再迭代，找出相邻的目标函数值更大的基可，再迭代，找出相邻的目标函数值更大的基可，再迭代，找出相邻的目标函数值更大的基可，再迭代，找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直行解，并继续判别，只要最优解存在，就一直行解
7、，并继续判别，只要最优解存在，就一直行解，并继续判别，只要最优解存在，就一直迭代迭代迭代迭代下去，直到找出最优解为止下去，直到找出最优解为止下去，直到找出最优解为止下去，直到找出最优解为止. . 1 1 1 1 对偶单纯形法求解思路：对偶单纯形法求解思路：对偶单纯形法求解思路：对偶单纯形法求解思路： 换个角度考虑换个角度考虑换个角度考虑换个角度考虑LPLPLPLP求解过程求解过程求解过程求解过程 从满足从满足从满足从满足 （1 1 1 1）（）（）（）（3 3 3 3）的一个非可行基解（检验数行保）的一个非可行基解（检验数行保）的一个非可行基解（检验数行保）的一个非可行基解（检验数行保 持持持
8、持0000）出发，（此时对偶问题的解一般为可行解），）出发，（此时对偶问题的解一般为可行解），）出发，（此时对偶问题的解一般为可行解），）出发，（此时对偶问题的解一般为可行解）， 通过逐步迭代直至（通过逐步迭代直至（通过逐步迭代直至（通过逐步迭代直至（2 2 2 2）得到满足，）得到满足，）得到满足，）得到满足，即直到实现到即直到实现到即直到实现到即直到实现到b b b b列所有的值列所有的值列所有的值列所有的值0000， 原问题的解在迭代过程中原问题的解在迭代过程中原问题的解在迭代过程中原问题的解在迭代过程中 从非可行解变成可行解，从非可行解变成可行解，从非可行解变成可行解，从非可行解变成可
9、行解， 最终达到最优解，最终达到最优解，最终达到最优解，最终达到最优解， 此时，对偶问题也达到最优解。此时，对偶问题也达到最优解。此时，对偶问题也达到最优解。此时，对偶问题也达到最优解。单纯形法中原问题的最优解满足的条件单纯形法中原问题的最优解满足的条件: :（ 1 1）是基本解；）是基本解； （ 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 即对偶解可行即对偶解可行（三）（三） 对偶单纯形法对偶单纯形法普
10、普通通单单纯纯形形法法对对偶偶单单纯纯形形法法前提是前提是原问原问题可行题可行 优化条件优化条件两种方法都从原问题的基解出发两种方法都从原问题的基解出发两种方法都从原问题的基解出发两种方法都从原问题的基解出发前提是前提是对偶对偶可行可行 优化优化条件条件 2 两种方法的联系：两种方法的联系：YA C， Y 0原问题基可行解原问题基可行解 最最优解判断优解判断对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思路基本思路基本思路基本思路普通单纯形法普通单纯形法普通单纯形法普通单纯形法基本思路基本思路基本思路基本思路 3 3 对
11、偶单纯形法的使用条件：对偶单纯形法的使用条件： 原问题的初始基解的检验数全部原问题的初始基解的检验数全部00； b b列至少一个元素列至少一个元素 0 0； 4 4 实施对偶单纯形法的基本原则：实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换在保持对偶可行的前提下进行基变换 每一次迭代过程中取出基变量中的一个负分量每一次迭代过程中取出基变量中的一个负分量 作为换出变量作为换出变量 去替换某个非基变量去替换某个非基变量( (作为换入变量作为换入变量),), 使原始问题的非可行解向可行解靠近。使原始问题的非可行解向可行解靠近。 第一步：第一步： 构造初始单位阵，确定原问题（构造初始单
12、位阵，确定原问题（构造初始单位阵，确定原问题（构造初始单位阵，确定原问题（max ) max ) max ) max ) 的初始基的初始基的初始基的初始基B B B B，使所有检验数，使所有检验数，使所有检验数，使所有检验数 C C C C j j j j - Z- Z- Z- Zj j j j = = = = j j = = C C C Cj j j j - C- C- C- CB B B B B B B B -1 -1 -1 -1 P P P Pj j j j 0 0 0 0， 即即即即 Y = C Y = C Y = C Y = CB B B B B B B B -1-1-1-1 （b
13、b b b 列的值）是对偶可行解，列的值）是对偶可行解，列的值）是对偶可行解，列的值）是对偶可行解，建立初始单纯形表。建立初始单纯形表。建立初始单纯形表。建立初始单纯形表。 第二步：第二步： 可行性检验。可行性检验。可行性检验。可行性检验。 检验检验检验检验 b b b b 列列列列 和和和和j j j j 行（即检查基变量的取值）行（即检查基变量的取值）行（即检查基变量的取值）行（即检查基变量的取值） 若若 b bi i 00 （X X X XB B B B = B = B = B = B -1 -1 -1 -1 b 0b 0b 0b 0）, , j j 0 0 , , 则原问题得到最优解则
14、原问题得到最优解 ，计算停，计算停，计算停，计算停; ; ; ; 若若b bi i 0 , 0 , j j 0 0 , , 则用对偶单纯形法则用对偶单纯形法进行换基迭代进行换基迭代进行换基迭代进行换基迭代. . . . 二二 对偶单纯形法的步骤：对偶单纯形法的步骤： 第三步第三步第三步第三步 先确定先确定先确定先确定换出换出换出换出变量变量变量变量 解答列（解答列（解答列（解答列（b b b b 列）中的负元素对应的基变量出基，列）中的负元素对应的基变量出基，列）中的负元素对应的基变量出基，列）中的负元素对应的基变量出基， 相应的行为主元行。相应的行为主元行。相应的行为主元行。相应的行为主元行
15、。 一般选一般选一般选一般选最小的负元素出基最小的负元素出基， 即若即若即若即若min ( B min ( B min ( B min ( B -1 -1 -1 -1 b )b )b )b )i i i i| (B | (B | (B | (B -1-1-1-1b )b )b )b )I I I I 0 = ( 0 = ( 0 = ( 0 = ( B B B B1 1 1 1 b )b )b )b )l l l l 则选取则选取则选取则选取 x x x x l l l l 为换出变量为换出变量为换出变量为换出变量. . . . 检验第检验第检验第检验第l l l l 行中非基变量行中非基变量行
16、中非基变量行中非基变量 x x x xj j j j 的系数的系数的系数的系数 lj lj lj lj , , , , 若所有的若所有的若所有的若所有的lj lj 0 0，则，则，则，则LP LP LP LP 问题问题问题问题 无可行解，无可行解， （下面进行说明），此时计算结束。（下面进行说明），此时计算结束。（下面进行说明），此时计算结束。（下面进行说明），此时计算结束。 否则转下步否则转下步否则转下步否则转下步当当b bl l00，而对所有，而对所有j=1,nj=1,n，有，有a aljlj 0 0，则原问题无可行解。则原问题无可行解。证明证明：x xl l+a+al,m+1l,m+1x
17、 xm+1m+1+a+al,nl,nx xn n=b=bl l 因因a aljlj 0(j=m+1,n)0(j=m+1,n)，又，又b bl l00， 故有故有x xl l 0 0，即不可能存在即不可能存在x xj j 0(j=1,n)0(j=1,n)的解，的解，故原问题无可行解，故原问题无可行解，此时对偶问题的目标函数值无界。此时对偶问题的目标函数值无界。若有：若有：Min cMin cj j z zj j / / ljlj|lj lj 0 , x 0 , x j j 为非基变量为非基变量 = c = ck k z zk k /lk lk 则确定则确定 x xk k 为换入为换入变量，相应的
18、列为主元列，变量，相应的列为主元列，标出标出主元素主元素lklk , , 应用矩阵的初等行变换得到新的单纯形表。应用矩阵的初等行变换得到新的单纯形表。第四步：第四步：若对于若对于b bl l 0 , 0 , 且有且有a a lj lj 0 , 0 , 则则 确定确定 换入换入变量变量应用最小比值原则目的：应用最小比值原则目的：是在是在保持下一个对偶问题的基解可行保持下一个对偶问题的基解可行的前提的前提下，减少原始问题的不可行性。下，减少原始问题的不可行性。 下面进行说明下面进行说明根据根据最小比值原则：最小比值原则：a alklk为为主元素主元素x xk k为为进进基变量基变量 设下一个表中的
19、检验数为设下一个表中的检验数为(c(cj j-z-zj j) ) ，则，则(1)(1)对对a aljlj 0 0，因，因c cj jz zj j 0 0，故，故 ，又因主，又因主元素元素a alklk00，故有故有 ，所以，所以(c(cj jz zj j) ) 0 0； (2)(2)对对a aljlj00，因，因 ，故，故有有(c(cj jz zj j) ) 0 0；所以，所以，(c(cj jz zj j) ) 0(j=10(j=1，n)n)则有：则有： 第第五五步步：用用换换入入变变量量替替换换换换出出变变量量，得得到到一个一个新的基新的基，对新的基再检查是否所有，对新的基再检查是否所有 如
20、果是，得原问题的最优解；如果是，得原问题的最优解； 如如果果否否，回回到到第第一一步步再再重重复复计计算算，直直到到检验数行非正，基列非负检验数行非正，基列非负，得到最终表，得到最终表. .例例例例6 6 6 6 应用对偶单纯型法求解下面的线性规应用对偶单纯型法求解下面的线性规应用对偶单纯型法求解下面的线性规应用对偶单纯型法求解下面的线性规 划问划问划问划问题题题题CBXBbx1x2x3x4x5 cj-2-3-400-1-2-110-21-301x4x500-2-3-400 cj-zj-3-4minj/lj|lj0x x x x5 5 5 5换出变量换出变量换出变量换出变量x x x x1 1
21、 1 1换入变量换入变量换入变量换入变量0-5/21/21-1/21-1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1XBCB cj00-4-3-2 cj-zjminj/lj|lj0x x x x2 2 2 2换入变量换入变量换入变量换入变量8/52x x x x4 4 4 4换出变量换出变量换出变量换出变量bx5x4x3x2x1XBCB cj00-4-3-2-2/5-1/57/5011/5-2/5-1/510x1x2-2-3-1/5-8/5-3/500 cj-zj11/52/5b bi i0, 0, j j00得到最优解为：得到最优解为：X X* *=(11/
22、5, 2/5,0,0,0=(11/5, 2/5,0,0,0）T T对偶问题最优解为：对偶问题最优解为：例例: : 用对偶单纯形法求解下面线性规划用对偶单纯形法求解下面线性规划 解解: : 构造对偶单纯形表进行迭代，构造对偶单纯形表进行迭代，从最后的表可以看到，从最后的表可以看到，B B-1-1b b列元素中有列元素中有-20-200, ,x xj j为非基变量为非基变量=k k /lklk注意：注意：若若x xl l为换出变量，所有为换出变量，所有ljlj00，则原问题无可行解。则原问题无可行解。初始可行基例例: 用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：对偶问题的对偶问
23、题的初始可行基初始可行基 换出换出换出minminj j/ljlj|ljlj0045y y y y2 2 2 2换入变量换入变量换入变量换入变量最优解最优解对偶单纯形法与原始单纯形法内在的对应关系对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 bi0所有所有 bi0?最优性检验最优性检验所有所有所有所有换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解的进化原始基本解的进化可行可行 最优最优非可行非可行
24、 可行可行( (最优最优) )单纯形法和对偶单纯形法步骤单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数0所有所有计算计算以aek为中心元素进行迭代以alk为中心元素进行迭代停没有最优解没有最优解普通单纯形法对偶单纯形法例例 用对偶单纯形法求用对偶单纯形法求解解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
25、+ 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 000x4x5x6-2 1 -1 1 0 0 1 2 2 0 1 0 0 -2 1 0 0 1-2 -4 -6 0 0 0 b-1012-40-2 1-1/2 1/2 -1/20050x1-25/2 3/21/21070-5-1-50010x2-2-401-1/200-1/22101/4-1/2 0-1/460011/41/215/4200-15/2-10 -5/220初始解为初始解为:x0=(0,0,0,-10,12,-4)T最优解为最优解为:x*=(6,2,0,0,2,0)Tz*= 20
