MBA数模考试复习资料

拉格朗日算法

? 构造拉格朗日函数

Page 45 of 48

对偶单纯形法

对偶单纯形法原理

对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。

对偶单纯形法基本思路：

找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得最优解。

例2.9 用对偶单纯形法求解：

解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数≤0（求max问题）。

Page 46 of 48

原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），Z* =72 其对偶问题的最优解为：Y= （1/3 , 3 , 7/3），W= 72

对偶单纯形法应注意的问题：

*

*

Page 47 of 48

Page 48 of 48