《对偶单纯形法详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《对偶单纯形法详解ppt课件.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 是应用是应用求解原始求解原始线性规划的一种方法线性规划的一种方法在原始问题的单在原始问题的单纯形表格上进行纯形表格上进行。 不是解对偶问题的单纯形法！不是解对偶问题的单纯形法！ 从更高的层次理解单纯形法从更高的层次理解单纯形法 （对应一个初始基本可行解）（对应一个初始基本可行解） （对应另一个基（对应另一个基本可行解），直至本可行解），直至为止为止。 所有检验数所有检验数0意味着意味着 ，10NBCC B NYAC说明说明。换言之，当原始问题的基。换言之，当原始问题的基B既是原始可既是原始可行基又是对偶可行基时，行基又是对偶可行基时，B成为最优基。成为最优基。 . .0MaxZstCXAXb
2、X1YBC B 1BC B等价等价N00N YAC-1BC B AC0-1BCC B A-1BCC B A0()()BN-1BC BCB0CN()()BN-1-1BBCCC BBB CN0()BN-11B-BCCC B BC B N0NB-1-1BBCCC B BB0CN0 0N (b列保持列保持0)， (检验数行检验数行0) ：保持保持的前提下（的前提下（） ，通过逐步迭，通过逐步迭代代（，从非可行解变成，从非可行解变成可行解）。可行解）。 原问题原问题初始基本初始基本可行解可行解保持为基本保持为基本可行解可行解初始对偶可行解初始对偶可行解保持对偶可行性保持对偶可行性始终满足解始终满足解的可
3、行性的可行性始终满始终满足对偶足对偶可行性可行性 每每一次迭代过程中取出一次迭代过程中取出作为作为去去某个某个(作为作为),使原始问题的非可行解向可行解靠近。使原始问题的非可行解向可行解靠近。 ： （一般选最小的负元素）（一般选最小的负元素）； 即即出基，则选lliiixbBbBbB,)(0)()(min111相应的行相应的行。是：在是：在下，下，。如果如果 0minlkkkljljjjjazcaazc(最小比值原则最小比值原则),则选则选 为换入变量为换入变量 , 相应相应的列为的列为, 主元行和主元列交叉处的元主元行和主元列交叉处的元素素 。kxlka若 ,要计算最小比值吗？为什么？0lj
4、a ，得到新的单纯形表。，得到新的单纯形表。用对偶单纯形法求解用对偶单纯形法求解LP： 12312312312323423. 234,0MinWxxxxxxstxxxx x x 123123412351234523423. . 234,0MaxZxxxxxxxstxxxxx x x x x 123123412351234523423. .234,0MaxZxxxxxxxstxxxxx x x x x -2/-2 - -4/-3 - - 比比 值值 -2 -3 -4 0 0 0 -Z -1 -2 -1 1 0 -2 1 -3 0 1 -3 -4 x4 x5 0 0 -2 -3 -4 0 0 x1
5、 x2 x3 x4 x5 cj xj b XB CB- -4/-5/2 - -1/-1/2 比比 值值 0 -4 -1 0 -1 0 cj-zj 0 -5/2 1/2 1 -1/2 1 -1/2 3/2 0 -1/2 -1 2 x4 x1 0 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB 0 0 -3/5 -8/5 -1/5 0 cj-zj 0 1 -1/5 -2/5 1/5 1 0 7/5 -1/5 -2/5 2/5 11/5 x2 x1 -3 -2 -2 -3 -4 0 0 x1 x2 x3 x4 x5 cj xj b XB CB用对偶单纯形法求
6、解用对偶单纯形法求解LP： 0, 037342. .932121212121yyyyyyyyt syyMinW 0,37342. .935152142132121yyyyyyyyyyyt syyMaxZ -3/-1 -9/-1 - - - 比比 值值 -3 -9 0 0 0 0 -Z -1 -1 1 0 0 -1 -4 0 1 0 -1 -7 0 0 1 -2 -3 -3 y3 y4 y5 0 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB - -6/-3 -3/-1 - - 比比 值值 0 -6 -3 0 0 6 -Z 1 1 -1 0 0 0 -3 -1 1 0 0 -6 -1 0 1 2 -1 -1 y1 y4 y5 -3 0 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB 0 0 -1 -2 0 8 -Z 1 0 -4/3 1/3 0 0 1 1/3 -1/3 0 0 0 1 -2 1 5/3 1/3 1 y1 y2 y5 -3 -9 0 -3 -9 0 0 0 y1 y2 y3 y4 y5 cj yj b XB CB