2-3对偶单纯形法ppt课件

1、 2.3 对偶单纯形法对偶单纯形法 一、什么是对偶单纯形法？一、什么是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始线性规划的一对偶单纯形法是应用对偶原理求解原始线性规划的一种方法种方法在原始问题的单纯形表格上进行对偶处理。在原始问题的单纯形表格上进行对偶处理。 留意：不是求解对偶问题的单纯形法！留意：不是求解对偶问题的单纯形法！. .0MaxZstCXAXbX1BC 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 B

2、C B N0NB-1-1BBCCC B BB0CN0 0N 二、对偶单纯形法的基本思想 1、对“单纯形法求解过程认识的提升 从更高的角度理解单纯形法 初始可行基对应一个初始基本可行解） 迭代另一个可行基对应另一个基本可行解），直至所有检验数0为止。 所有检验数0意味着 ，CANBCCBN01说明原始问题的最优基也是对偶问题的可行说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基基。换言之，当原始问题的基B既是可行基既是可行基又是对偶可行基时，又是对偶可行基时，B成为最优基。成为最优基。定理定理2-5 B是线性规划的最优基的充要条件是线性规划的最优基的充要条件是，是，B是可行基，同

3、时也是对偶可行基。是可行基，同时也是对偶可行基。原问题原问题初始基本初始基本可行解可行解保持为基本保持为基本可行解可行解初始对偶可行解初始对偶可行解保持对偶可行性保持对偶可行性始终满足解始终满足解的可行性的可行性始终满始终满足对偶足对偶可行性可行性 2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行的前提下检验数行保持0） ，通过逐步迭代实现基本可行b列0，从非可行解变成可行解）。 三、对偶单纯形法的实施1、使用条件： 检验数全部0； 解答列至少一个元素 0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换

4、某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。 检验数全部检验数全部0（非基变量检验数（非基变量检验数0） 基变换： 先确定换出变量解答列中的负元素一般选最小的负元素对应的基变量出基； 即出基，则选lliiixbBbBbB,)(0)()(min111相应的行为主元行。相应的行为主元行。假设 ,要计算最小比值吗？为什么？0lja min0jkljjljlkaaa(最小比值原则最小比值原则),则选则选 为换入变量为换入变量 , 相应相应的列为主元列的列为主元列 , 主元行和主元列交叉处的元主元行和主元列交叉处的元素素 为主元素。为主元素。kxlka 按主元素进行换基迭代旋转运算、

5、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。 继续以上步骤，直至求出最优解。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