拉格朗日算法
? 构造拉格朗日函数
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
相关推荐：
loading