whut运筹学-8 对偶单纯形法.ppt

对偶单纯形法 (Dual Simplex Algorithm) 单纯形法思想： 二 者 模 型 均 为 原 问 题 对偶单纯形法思想： X* Y* ….. X* Y* ….. (B (0))- 1b ? 0 (B(k))-1b≥0 (B (0))- 1b ? 0 (B(k))-1b≥0 1. 对偶单纯形法思想 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2. 对偶单纯形法的计算步骤 Step 0 (建立初始单纯形表) 给定一个初始正则解 X(0),对应的正则基 B， 建立相应的初始单纯形表。转下步。 正则基： 满足 的原问题的基 B 正则解: 与正则基 B 对应的原问题的一个基本解X Step 1 （最优解的判别）计算 若 则停止计算, 当前的正则解便是最优解; 否则转下步。 Step 2 （确定离基变量）令 则 为离基变量， 是主行。转下步。 对偶单纯形法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Step 3 (无可行解的判别) 检查单纯形表的第 r 行系数： 若所有的 则原问题无可行解。否则转下步。 Step 4 （确定进基变量） 令 则 xk 为进基变量，转下步。 Step 5 （迭代）以 为主元素进行消元变换，得到新的单纯形表，并 迭代到下一个正则解。转 Step 1。 对偶单纯形法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例 1 用对偶单纯形法求解下列线性规划问题: 解: 将此问题化为如下等价的形式： 对偶单纯形法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 应用对偶单纯形法求解如下: 迭代 XB x1 x2 x3 x4 x5 b x4 -1 2 -1 1 0 -4 x5 -2 -1 1 0 1 -6 -w -1 -2 0 0 0 0 XB x1 x2 x3 x4 x5 b x4 0 5/2 -3/2 1 -1/2 -1 x1 1 1/2 -1/2 0 -1/2 3 -w 0 -3/2 -1/2 0 -1/2 3 对偶单纯形法 迭代 R 1/2 2 - - - R - - 1/3 - 1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose