《运筹学》课程授课教案（讲稿）第9讲 对偶单纯形法

课程名称：《运筹学》第_9_讲次对偶单纯形法授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，了解并掌握对偶单纯形法。。[重点及难点]用对偶单纯形法求解。内容[本讲课程的引入]在此之前，我们学习了单纯形法，今天我们开始学习对偶单纯形法，[本讲课程的内容]一、对偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系（性质7）时指出：在单纯形表中进行选代时在b’列中得到的是原问题的可行解，而在检验数行得到的是对偶问题的基解。通过逐步选代，当在检验数行得到对偶问题的解也是基可行解时，则原问题与对偶问题都达到最优解。根据对偶问题的对称性，也可以这样考虑：若保持对偶问题的解是基可行解，即所有非基变量的检验数不大于0，而原问题在非基可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定要是基可行解。可从非基可行解开始迭代。具体方法是：每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解向可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤：（1）根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若b列的数字中至少有一个负分量，检验数保持非正，那么进行以下计算。（2）确定换出变量按min((Bb)i/（Bb）i-10=（Bb对应的-1变量xl为换出变量

课程名称：《运筹学》 第 9 讲次 授课题目 对偶单纯形法 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，了解并掌握对偶单纯形法。 [重点及难点] 用对偶单纯形法求解。 内 容 [本讲课程的引入] 在此之前，我们学习了单纯形法，今天我们开始学习对偶单纯形法。 [本讲课程的内容] 一、对偶单纯形法 前节讲到原问题与对偶问题的解之间的对应关系（性质 7）时指出：在单纯形表中进行迭代时， 在 b＇列中得到的是原问题的可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在 检验数行得到对偶问题的解也是基可行解时，则原问题与对偶问题都达到最优解。 根据对偶问题的对称性，也可以这样考虑：若保持对偶问题的解是基可行解，即所有非基变量 的检验数不大于 0，而原问题在非基可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最 优解。其优点是原问题的初始解不一定要是基可行解。可从非基可行解开始迭代。具体方法是：每次 迭代是将基变量中的负分量 xl 取出，去替换非基变量中的 xk，经基变换，所有检验数仍保持非正。 从原问题来看，经过每次迭代，原问题由非可行解向可行解靠近。当原问题得到可行解时，便得到了 最优解。 对偶单纯形法的计算步骤： （1）根据线性规划问题，列出初始单纯形表。检查 b 列的数字，若都为非负，检验数都为非 正，则已得到最优解，停止计算。若 b 列的数字中至少有一个负分量，检验数保持非正，那么进行以 下计算。 （2）确定换出变量 按 min｛（B b）-1i | （B b）i ＜-1 0 =（B b）l 对应的基变量 -1 xl 为换出变量

内容（3）确定换入变量在单纯形表中检查xl所在行的系数alj，若所alj≥0，则无可行解，停止计算。若存在alj0且B'p,≤0无解：存在(Bb)0变量xilaaan例1用对偶单纯形方法求解：minF=3x,+2x23x+x≥34x +3x2 ≥6X +3x2≥2X,X≥0

内 容 （3）确定换入变量 在单纯形表中检查 xl 所在行的系数 alj ，若所 alj ≥ 0 ，则无可行解，停止计算。 若存在 alj ＜ 0 ，计算 θ= min（σj /alj | alj ＜ 0 =σk / alk 按θ规则所对应的列的非基变量 xk 为换入变量，这样才能保持对偶问题的解仍为可行解。 （4）以 alk 为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。 重复（1）－（4）的步骤。 对偶单纯形法的特点 （1）初始解可以是非可行解，当检验数都为非正时，就可以进行基的变换，这时不 需要加入人工变量，因此可以简化计算。 （2）当变量多于约束条件，对这样的线形规划问题，用对偶单纯形法计算可以减少 计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问 题，然后用对偶单纯形法求解。 （3）在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。 （4）对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可 行基，因此这方法在求解线性规划问题时很少单独应用。 原始与对偶单纯形法的对比 例 1 用对偶单纯形方法求解： 原始单纯形法 对偶单纯形法 初始解 原问题可行：Ax  b, x  0 对偶可行：yA  c, y  0 最优检验 条件：  = c - cBB -1A  0 无界：存在j >0 且 B -1 pj 0 条件： x = B -1 b  0 无解：存在(B -1 b)i<0 且i0 确定入基 变量 xk k=max{cj -cBB -1 pj , jJN} rk k r rj j j min                = < 0 确定出基 变量 xr rk r ik ik i a b a a b min           0 i  = (B -1 b)r = min{(B -1 b)i iJB}                 , 0 3 2 4 3 6 3 3 min 3 2 1 2 1 2 1 2 1 2 1 2 x x x x x x x x f x x

内容：（1）引入松弛变量x3，x4，x5化为标准形，并在约束等式两侧同乘-1，得到max Z=-3x,-2x2[-3x, - X, +x3=-3-4x, -3x2+x4 =-6+ xs = -2-xi-3x2[x, ≥0, j=1,2,,5取x3，x4，x5为基变量，此式即为典式形式，并且检验数皆非正，因此可构初始对偶单纯形表0-3-200B"bXBX1X2X3X4XsCB-11000-3-3X30010-6-4(-3)X4-2-1-30010X5000000元00-3-200a1-1-5/3000-1/3X32100-24/3-1/3X2400103-1X5400-2/30-1/3a3/510-3/51/50-3X1010-2 6/54/5-3/5X200109/5-8/511/5xs0021/50-1/5-3/5a写出结论。max Z=-x-X2例2用对偶单纯形法求解下面线性规划-2x + X2 +X33 = 21+x = -112*2[x, ≥0,j =1,2,3,4

内 容 解: （1）引入松弛变量 x3 , x4 , x5 化为标准形，并在约束等式两侧同乘-1，得到 取 x3 , x4 , x5 为基变量，此式即为典式形式，并且检验数皆非正，因此可构初始对 偶单纯形表 写出结论。 例 2 用对偶单纯形法求解下面线性规划                            0, 1,2, ,5 3 2 4 3 6 3 3 max 3 2 1 2 5 1 2 4 1 2 3 1 2 x j  x x x x x x x x x Z x x j -3 -2 0 0 0 cB xB B -1 b x1 x2 x3 x4 x5 0 x3 -3 -3 -1 1 0 0 0 x4 -6 -4 (-3) 0 1 0 0 x5 -2 -1 -3 0 0 1  0 0 0 0 0 0  0 -3 -2 0 0 0 0 x3 -1 -5/3 0 1 -1/3 0 -2 x2 2 4/3 1 0 -1/3 0 0 x5 4 3 0 0 -1 1  4 -1/3 0 0 -2/3 0 -3 x1 3/5 1 0 -3/5 1/5 0 -2 x2 6/5 0 1 4/5 -3/5 0 0 x5 11/5 0 0 9/5 -8/5 1  21/5 0 0 -1/5 -3/5 0                      0, 1,2,3,4 1 2 1 2 2 max 1 2 4 1 2 3 1 2 x j x x x x x x Z x x j

容内解：构造对偶单纯形表进行选代，-1-100B'bCBXBXiX2X3X4-21100(-2) X310-11-1/20X400000元0-1-100a11-1/2-1/20-1Xi-200101/2X410-3/2-1/20a从最后的表可以看到，Bb列元素中有-2<0，并且，-2所在行各元素皆非负，因此，原规划没有可行解。[本讲小结】对偶单纯形法适合于解如下形式的线性规划间题：Nmin f=Zcx,(c,≥0)n[2ag,2b,i=1,2,"",m=lx, ≥0, j =1,2,.,n在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。[本讲课程的作业]】76页2.9

内 容 解: 构造对偶单纯形表进行迭代， 从最后的表可以看到，B -1 b 列元素中有-2<0，并且，-2 所在行各元素皆非负，因此， 原规划没有可行解。 [本讲小结] 对偶单纯形法适合于解如下形式的线性规划问题: 在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基 本解，可以直接建立初始对偶单纯形表进行求解，非常方便 。 [本讲课程的作业] 76 页 2.9 -1 -1 0 0 cB xB B -1b x1 x2 x3 x4 0 x3 -2 (-2) 1 1 0 0 x4 -1 1 -1/2 0 1  0 0 0 0 0  0 -1 -1 0 0 -1 x1 1 1 -1/2 -1/2 0 0 x4 -2 0 0 1/2 1  1 0 -3/2 -1/2 0                  x j n a x b i m f c x c j n j ij j i n j j j j 0, 1,2, , 1,2, , min 0 1 1  