(完整版)对偶单纯形法详解

2.3对偶单纯形法一、什么是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！二、对偶单纯形法的基本思想1、对“单纯形法”求解过程认识的提升——从更高的层次理解单纯形法初始可行基（对应一个初始基本可行解）→迭代→另一个可行基（对应另一个基本可行解），直至所有检验数≤0为止。所有检验数≤0意味着，10NBCCBNYAC说明原始问题的最优基也是对偶问题的可行基。换言之，当原始问题的基B既是原始可行基又是对偶可行基时，B成为最优基。定理2-5B是线性规划的最优基的充要条件是，B是可行基，同时也是对偶可行基。..0MaxZstCXAXbXLP原问题:若B是A中的一个基可行基B对应的解是基本可行解，则B是可行基对偶可行基若单纯形乘子是对偶问题的可行解，则B是对偶可行基1YBCB是对偶问题的可行解检验数1BCB等价N00NYAC-1BCBAC0-1BCCBA-1BCCBA0()()BN-1BCBCB0CN()()BN-1-1BBCCCBBBCN0()BN-11B-BCCCBBCBN0NB-1-1BBCCCBBB0CN0证明：0N单纯形法的求解过程就是：在保持原始可行的前提下(b列保持≥0)，通过逐步迭代实现对偶可行(检验数行≤0)。2、对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0），通过逐步迭代实现原始可行（b列≥0，从非可行解变成可行解）。对偶单纯形法的思想（图示）原问题初始基本可行解保持为基本可行解初始对偶可行解保持对偶可行性最优解基本可行性对偶可行性始终满足解的可行性始终满足对偶可行性三、对偶单纯形法的实施1、使用条件：①检验数全部≤0；②解答列至少一个元素0；2、实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。3、计算步骤：①建立初始单纯形表，计算检验数行。解答列≥0——已得最优解；至少一个元素0,转下步;解答列≥0——原始单纯形法；至少一个元素0,另外处理；检验数全部≤0（非基变量检验数0）至少一个检验数0基变换：先确定换出变量——解答列中的负元素（一般选最小的负元素）对应的基变量出基；即出基，则选lliiixbBbBbB,)(0)()(min111相应的行为主元行。然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果'''0minlkkkljljjjjazcaazc(最小比值原则),则选为换入变量,相应的列为主元列,主元行和主元列交叉处的元素为主元素。kx'lka若,要计算最小比值吗？为什么？'0lja按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。循环以上步骤，直至求出最优解。3、举例——用对偶单纯形法求解LP：12312312312323423..234,,0MinWxxxxxxstxxxxxx化为标准型→123123412351234523423..234,,,,0MaxZxxxxxxxstxxxxxxxxx将两个等式约束两边分别乘以-1，得123123412351234523423..234,,,,0MaxZxxxxxxxstxxxxxxxxx以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下：-2/-2----4/-3------比值-2-3-4000-Z-1-2-110-21-301-3-4x4x500-2-3-400x1x2x3x4x5cjxjbXBCB----4/-5/2----1/-1/2比值0-4-10-10cj-zj0-5/21/21-1/21-1/23/20-1/2-12x4x10-2-2-3-400x1x2x3x4x5cjxjbXBCB00-3/5-8/5-1/50cj-zj01-1/5-2/51/5107/5-1/5-2/52/511/5x2x1-3-2-2-3-400x1x2x3x4x5cjxjbXBCB最优解:X*=（11/5，2/5,0,0,0）T，最优值:minW=-maxZ*=-[11/5×(-2)+2/5×(-3)]=28/54、举例——用对偶单纯形法求解LP：0,037342..932121212121yyyyyyyytsyyMinW化为标准型→0,,37342..935152142132121yyyyyyyyyyytsyyMaxZ将三个等式约束两边分别乘以-1，然后列表求解如下：-3/-1-9/-1---------比值-3-90000-Z-1-1100-1-4010-1-7001-2-3-3y3y4y5000-3-9000y1y2y3y4y5cjyjbXBCB----6/-3-3/-1------比值0-6-3006-Z11-1000-3-1100-6-1012-1-1y1y4y5-300-3-9000y1y2y3y4y5cjyjbXBCB00-1-208-Z10-4/31/30011/3-1/30001-215/31/31y1y2y5-3-90-3-9000y1y2y3y4y5cjyjbXBCB最优解是Y*=（5/3，1/3，0，0，1）T，目标函数最优值为Wmin=-Zmax=8思考题：能否不要化为标准型，直接按极小化问题用单纯形表格迭代求解？（结合课后小组讨论4一并思考研究）