对偶理论与灵敏度分析解析.pptVIP

3.对偶单纯形法的实施 （1）使用条件： ①检验数全部≤0； ②解答列至少一个元素 0； （2）实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。 （3）计算步骤 ①建立初始单纯形表，计算检验数行。 解答列≥0——已得最优解； 至少一个元素0,转下步; 解答列≥0——原始单纯形法； 至少一个元素0,另外处理； 检验数全部≤0 （非基变量检验数0） 至少一个检验数0 ?基变换： 先确定换出变量——解答列中的负元素（一般选最小的负元素）对应的基变量出基； 即 相应的行为主元行。 然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。 如果 (最小比值原则),则选 为换入变量 , 相应的列为主元列 , 主元行和主元列交叉处的元素 为主元素。 若 ,要计算最小比值吗？为什么？ ?按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。 循环以上步骤，直至求出最优解。 例——用对偶单纯形法求解P： 化为标准型 → 将两个等式约束两边分别乘以-1，得 以此形式进行列表求解，满足对偶单纯形法的基本条件，具体如下： -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 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 最优解: X*=（11/5，2/5, 0, 0, 0）T， 最优值: minW= -maxZ* = -[11/5×(-2)+2/5×(-3)]= 28/5 例——用对偶单纯形法求解P： 化为 标准型 → 将三个等式约束两边分别乘以-1，然后 列表求解如下： -3/-1 -9/-1 --- --- --- 比 值 -3 -9