2.4 对偶单纯形法.ppt

第二章 线性规划的对偶理论 与灵敏度分析,§4 对偶单纯形法 在单纯形法中，原问题的最优解满足： （1）是基本解； （2）可行（ XB=B-1b≥0）； （3）检验数C-CBB-1A≤0 YA≥C ，即对偶解可行 单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止而对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解对偶单纯形法计算步骤如下： 步骤1 确定原问题（L）的初始基B，使所有检验数 ，即Y=CBB-1是对偶可行解，建立初始单纯形表 步骤2 检查基变量的取值，若XB=B-1b≥0，则已得最优解，计算停；否则求 min{(B-1b)i│(B-1b)i＜0｝=(B-1b)ι 确定单纯形表第L行对应的基变量为旋出变量 步骤3 若所有aιj≥0,则原问题无可行解，计算停；否则，计算 θ=min｛σj / aιj│ aιj ＜0 ｝=σk/aιk 确定对应的xk为旋入变量。

步骤4 以aιk为主元作（L，K）旋转变换，得新的单纯形表，转步骤2 可以证明，按上述方法进行迭代，所得解始终是对偶可行解例2 用对偶单纯形法求解下述问题 minZ=12x1+8x2+16x3 +12x4 2x1+ x2 +4x3 ≥2 2x1+2x2+4x4 ≥3 x1,x2,x3,x4≥0 解：令 =-Z，则问题可变为 max =-12x1-8x2-16x3-12x4 - 2x1- x2 -4x3 +x5 =-2 -2x1-2x2 -4x4 +x6=-3 x1,x2,x3,x4,x5,x6≥0 取B=（P5,P6）为初始基，易见所有检验数σj≤0， 从而可建立单纯形表，计算结果如下：,,,,L=2，K=4,L=1，K=2,L=2，K=1,最优解：X1=1/2，X2=1，X3=X4=0, minZ=14,本例如果用单纯形法计算，确定初始基可行解时需引入两个人工变量，计算量要多于对偶单纯形法一般情况下，如果问题能够用对偶单纯形法计算，计算量会少于单纯形法但是，对偶单纯形法并不是一种普遍算法，它有一定的局限性，不是任何线性规划问题都能用对偶单纯形法计算的。

当线性规划问题具备下面条件时，可以用对偶单纯形法求解： ①问题标准化后，价值系数全非正； ②所有约束全是不等式。