[第二讲对偶理论与灵敏度分析.ppt

对偶单纯形法 对于任何一个可行基B , 为原问题的一个基可行解，单纯形法是从一个基可行解到另一个相邻的基可行解，直到基B满足 为止。 对偶单纯形法 Dual Simplex Method 单纯形法首先化问题为标准型： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对偶单纯形法 Dual Simplex Method 原始单纯形法的思想： 从满足可行性条件的一个基可行解(即基B满足 )出发，经过换基运算迭代到另一个基可行解，直到找到满足最优性条件( )的基可行解，这就是原问题的最优解。 －CBB－1b C-CBB－1A λ B-1b B-1A XB b X 对于任意基B ,对应的单纯形表为 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 若上表为最优单纯形表，则下列两个式子同时成立： 对偶单纯形法 Dual Simplex Method 问题：可否从满足条件(2)的基出发去找原问题的最优解？ 对偶单纯形法思想： 从满足条件(2) 的基(一般称为正则基)B出发，经过换基运算到另一个正则基，即一直保证条件(2)成立，直到找到一个满足条件(1)的正则基。 －CBB－1b C-CBB－1A λ B-1b B-1A XB X Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对偶单纯形法的计算步骤： (1)将线性规划的约束化为等式，找出一个正则基，即全部检验数λj≤0（max）或λj≥0（min）, 求出其对应的基本解，当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算； (2) 换基计算 (i)先确定出基变量: l 行对应的变量出基； (ii)再选进基变量: 求最小比值 (3)求新的基本解，用初等变换将主元素alk化为l, k列其它元素化为零，得到新的基本解，转到第(1)步重复运算。 对偶单纯形法 Dual Simplex Method Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 【例7】用对偶单纯形法求解 【解】先将约束不等式化为等式，再两边同乘以(－1)，得到 x4、x5 为基变量，用对偶单纯形法，迭代过程如表2-7所示。 对偶单纯形法 Dual Simplex Method Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. XB 表(1) λj x 4 x5 x1 -1 -1 4 x2 [-1] 1 1↑ x 3 -1 4 3 x 4 1 0 0 x 5 0 1 0 b －5→ －3 表2-7 对偶单纯形法 Dual Simplex Method 最优解：X＝(4，1，0)T；Z=17 表(2) λj x2 x5 1 [-2] 3↑ 1 0 0 1 3 2 -1 1 1 0 1 0 5 －8→ 表(3) λj x2 x1 0 1 0 1 0 0 5/2 -3/2 13/2 -1/2 -1/2 5/2 1/2 －1/2 3/2 1 4 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Asp