《对偶单纯形法wxp》由会员分享，可在线阅读，更多相关《对偶单纯形法wxp（21页珍藏版）》请在金锄头文库上搜索。
1、 2.3 2.3 对偶单纯形法对偶单纯形法一、什么是对偶单纯形法？一、什么是对偶单纯形法？对偶单纯形法对偶单纯形法是应用对偶原理对偶原理求解原始 线性规划的一种方法在原始问题的单纯形表格上进行对偶处理对偶处理。注意：注意：不是解对偶问题的单纯形法！二、对偶单纯形法的基本思想二、对偶单纯形法的基本思想1 1、对、对“ “单纯形法单纯形法” ”求解过程认识的提升求解过程认识的提升从更高的层次理解单纯形法初始可行基初始可行基（对应一个初始基本可行解）迭代迭代另一个可行基另一个可行基（对应另一个基本 可行解），直至所有检验数所有检验数 0 0为止。所有检验数0意味着什么？ 以上分析过程说明原问题的最优
2、基也是对偶原问题的最优基也是对偶 问题的可行基问题的可行基。换言之，当原问题的基B既 是原问题的可行基又是对偶问题的可行基时 ，B成为原问题的最优基。定理定理2-52-5 基基B B是线性规划的是线性规划的最优基最优基的充要条的充要条 件是，件是，B B是是可行基可行基，同时也是，同时也是对偶可行基对偶可行基。单纯形法的求解过程就是：在保持原始可行的前单纯形法的求解过程就是：在保持原始可行的前 提下提下(b列保持0)，通过逐步迭代实现对偶可行通过逐步迭代实现对偶可行(检 验数行0)。2 2、 对偶单纯形法思想：对偶单纯形法思想：换个角度考虑换个角度考虑LPLP求解过程求解过程：保持对偶可行对偶
3、可行 的前提下（检验数行保持检验数行保持 0 0） ，通过逐步迭 代实现原始可行实现原始可行（b b列列 0 0）。 对偶单纯形法的思想（图示）对偶单纯形法的思想（图示）原问题初始基本 可行解保持为基本 可行解初始对偶可行解保持对偶可行性最优解最优解基本可行性基本可行性对偶可行性对偶可行性始终满足解 的可行性始终满 足对偶 可行性三、对偶单纯形法的实施三、对偶单纯形法的实施1 1、使用条件：、使用条件： 检验数全部检验数全部 0 0；解答列至少一个元素解答列至少一个元素 00 基变换：基变换：先确定换出变量先确定换出变量解答列中的负元素对解答列中的负元素对应的基变量应的基变量出基出基，即相应的
4、行为主元行为主元行。然后然后确定换入变量确定换入变量原则原则是：在保持对偶保持对偶可行的前提可行的前提下，减少原始问题的不可行性减少原始问题的不可行性。如果 (最小比值原则),则选 为换入变量 , 相应的列为主元列主元列 , 主元行和主元列交叉处的元素 为主元素为主元素。若 ,要计算最小比 值吗？为什么？按主元素进行换基迭代按主元素进行换基迭代（旋转运算、枢（旋转运算、枢 运算）运算），将主元素变成将主元素变成1 1，主元列变成单位向，主元列变成单位向量量，得到新的单纯形表。循环以上步骤，直至求出最优解。循环以上步骤，直至求出最优解。3 3、举例、举例用对偶单纯形法求解LP： 化为标准型化为标
5、准型 将两个等式约束两边分别乘以将两个等式约束两边分别乘以-1-1，得，得以此形式进行列表求解，满足对偶单纯形以此形式进行列表求解，满足对偶单纯形 法的基本条件，具体如下：法的基本条件，具体如下：-2/-2 - -4/-3 - -比 值-2 -3 -4 0 0 0 -Z-1 -2 -1 1 0-2 1 -3 0 1-3-4x4 x5 00-2 -3 -4 0 0x1 x2 x3 x4 x5cjxjb XB CB- 8/5 - - 2比 值0 -4 -1 0 -1 0 cj-zj0 -5/2 1/2 1 -1/21 -1/2 3/2 0 -1/2-12x4 x1 0-2-2 -3 -4 0 0x
6、1 x2 x3 x4 x5cjxjb XB CB0 0 -3/5 -8/5 -1/5 0 cj-zj0 1 -1/5 -2/5 1/51 0 7/5 -1/5 -2/52/511/5x2 x1 -3-2-2 -3 -4 0 0x1 x2 x3 x4 x5cjxjb XB CB最优解最优解: : X*=X*=（11/511/5，2/5, 0, 0, 02/5, 0, 0, 0）T T， 最优值最优值: : minWminW= -= -maxZmaxZ* = * = -11/5(-2)+2/5(-3)= 28/5 -11/5(-2)+2/5(-3)= 28/54 4、举例、举例用对偶单纯形法求解L
7、P： 化为化为标准型标准型 将三个等式约束两边分别乘以将三个等式约束两边分别乘以-1-1，然后，然后列表求解如下：列表求解如下：-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-3y3 y4 y5000-3 -9 0 0 0y1 y2 y3 y4 y5cjyjb XB CB- -6/-3 -3/-1 - -比 值0 -6 -3 0 0 6 -Z1 1 -1 0 00 -3 -1 1 00 -6 -1 0 12-1-1y1 y4 y5-300-3 -9 0 0 0y1 y2 y3 y4 y5cjyj
8、b XB CB0 0 -1 -2 0 8 -Z1 0 -4/3 1/3 00 1 1/3 -1/3 00 0 1 -2 15/31/31y1 y2 y5-3-90-3 -9 0 0 0y1 y2 y3 y4 y5cjyjb XB CB最优解是最优解是Y*=Y*=（5/35/3，1/31/3，0 0，0 0，1 1）T T，目标函数最优值为目标函数最优值为WWminmin=-=-Z Zmaxmax=8=8 思考题：思考题：能否不要化为最大化问题，直接按能否不要化为最大化问题，直接按极小化问题用单纯形表格迭代求解？极小化问题用单纯形表格迭代求解？（结合课后小组讨论（结合课后小组讨论4 4一并思考研究）一并思考研究）
