《运筹学》课程教学资源（PPT课件讲稿）第二章 线性规划的进一步研究（2.3）对偶单纯形法

23对偶单纯形法 、什麽是对偶单纯形法? 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法在原始问题的单 纯形表格上进行对偶处理 注意:不是解对偶问题的单纯形法!

2.3 对偶单纯形法 一、什麽是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！

二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提 升 从更高的角度理解单纯形法 初始可行基(对应一个初始基本可行解) →迭代→另一个可行基(对应另一个基 本可行解),直至所有检验数≤0为止

二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提 升—— 从更高的角度理解单纯形法 初始可行基（对应一个初始基本可行解） →迭代→另一个可行基（对应另一个基 本可行解），直至所有检验数≤0为止

所有检验数<0意味着 C-CBN≤0→zA≥C 说明原始问题的最优基也是对偶问题的可行 基。换言之,当原始问题的基B既是原始可 行基又是对偶可行基时,B成为最优基。 定理25B是线性规划的最优基的充要条件 是,B是可行基,同时也是对偶可行基

所有检验数≤0意味着 CN −CB B N   A  C ， − 0  1 说明原始问题的最优基也是对偶问题的可行 基。换言之，当原始问题的基B既是原始可 行基又是对偶可行基时，B成为最优基。 定理2-5 B是线性规划的最优基的充要条件 是，B是可行基，同时也是对偶可行基

单纯形法的求解过程就是: 在保持原始可行的前提下(b列保持≥0), 通过逐步迭代实现对偶可行(检验数行≤0)。 2、对偶单纯形法思想: 换个角度考虑LP求解过程:保持对偶可行 的前提下(检验数行保持<0),通过逐步迭 代实现原始可行(b列≥0,从非可行解变成 可行解)

单纯形法的求解过程就是： 在保持原始可行的前提下（b列保持≥0）， 通过逐步迭代实现对偶可行（检验数行≤0）。 2、 对偶单纯形法思想： 换个角度考虑LP求解过程：保持对偶可行 的前提下（检验数行保持≤0） ，通过逐步迭 代实现原始可行（b列≥0，从非可行解变成 可行解）

三、对偶单纯形法的实施 1、使用条件:①检验数全部<0; ②解答列至少一个元素<0; 2、实施对偶单纯形法的基本原则 在保持对偶可行的前提下进行基变换每 次迭代过程中取出基变量中的一个负分量作为 换出变量去替换某个非基变量(作为换入变 量),使原始问题的非可行解向可行解靠近

三、对偶单纯形法的实施 1、使用条件： ①检验数全部≤0； ②解答列至少一个元素 < 0； 2、实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换——每一 次迭代过程中取出基变量中的一个负分量作为 换出变量去替换某个非基变量（作为换入变 量），使原始问题的非可行解向可行解靠近

3、计算步骤: ①建立初始单纯形表,计算检验数行。 解答列≥0已得最优解 检验数全部≤0 (非基变量检验数0 至少一个元素<0另外处理

3、计算步骤： ①建立初始单纯形表，计算检验数行。 解答列≥0——已得最优解； 至少一个元素0

②基变换: 先确定换出变量一—解答列中的负元素 (一般选最小的负元素)对应的基变量出基; 即 m1B"b)(Bb)<0}=(Bb),则选出基, 相应的行为主元行

 基变换： 先确定换出变量——解答列中的负元素 （一般选最小的负元素）对应的基变量出基； 即  i i  l 则选 l 出基， i min (B b) (B b) 0 (B b) , x −1 −1 −1  = 相应的行为主元行

然后确定换入变量原则是:在保持对偶 可行的前提下,减少原始问题的不可行性。 如果 k k min ×0 (最小比值原则),则选x为换入变量,相 应的列为主元列,主元行和主元列交叉处的 元素ak为主元素

然后确定换入变量——原则是：在保持对偶 可行的前提下，减少原始问题的不可行性。 如果 ' ' ' min 0 l k k k l j l j j j j a c z a a c z − =          − （最小比值原则），则选 为换入变量，相 应的列为主元列，主元行和主元列交叉处的 元素 为主元素。 k x ' alk

③按主元素进行换基迭代(旋转运算、枢 运算),将主元素变成1,主元列变成单位向 量,得到新的单纯形表。 继续以上步骤,直至求出最优解。 课后小组订论4讨论对偶单纯形法中确定换入 变量的最小比值原则的依据,给出详细的证明 过程(附上必要的说明,可以采用必要的文字 说明加上证明思路图,主线框图等)。写出研 究报告和工作报告。(两周后交)

按主元素进行换基迭代（旋转运算、枢 运算），将主元素变成1，主元列变成单位向 量，得到新的单纯形表。 继续以上步骤，直至求出最优解。 课后小组讨论4 讨论对偶单纯形法中确定换入 变量的最小比值原则的依据，给出详细的证明 过程（附上必要的说明，可以采用必要的文字 说明加上证明思路图，主线框图等）。写出研 究报告和工作报告。（两周后交）

4、举例—用对偶单纯形法求解LP Mn=3y1+9y2 Maxz=-3v,-9 y y+12≥2化为 y+y2-y3=2 y1+4y2≥3标准型 y s.t.. s t y1+7y2≥3 y+7y2-y3=3 ≥0,y2≥0 y,…,y5≥0 将三个等式约束两边分别乘以-1,然后 列表求解如下:

4、举例——用对偶单纯形法求解LP：          +  +  +  = + 0, 0 7 3 4 3 2 . . 3 9 1 2 1 2 1 2 1 2 1 2 y y y y y y y y st MinW y y 化为 标准型 →         + − = + − = + − = = − − , , 0 7 3 4 3 2 . . 3 9 1 5 1 2 5 1 2 4 1 2 3 1 2 y y y y y y y y y y y st MaxZ y y  将三个等式约束两边分别乘以-1，然后 列表求解如下：