《北邮运筹学ch23对偶单纯形法》由会员分享，可在线阅读，更多相关《北邮运筹学ch23对偶单纯形法（9页珍藏版）》请在金锄头文库上搜索。
1、2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 1 of 9设原问题是（记为LP）： 对偶问题是（记为DP）： 根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。 对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，极小化问题时j0。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 2 of 9 （1）将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数j
2、0（max）或j0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；（2）先确定出基变量。 行对应的变量xl出基； （3）再选进基变量。求最小比值（4）求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 3 of 9【例例2.10】用对偶单纯形法求解【解解】先将约束不等式化为等式，再两边同乘以（1），得到用对偶单纯形法，迭代过程如下页或看演示(请启用宏)。
3、8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 4 of 9表248/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 5 of 9 应当注意： （1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中 的绝对值是使得比值非负，在极小化问题时j0，分母aij0 这时必须取绝对值。在极大化问题中，j0分母aij0
4、， 总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成这里j0在求k时就可以不带绝对值符号。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 6 of 9（4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是其目的是保证下一个对偶问题的基本解可行； （6）对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于
5、零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 7 of 9【例【例2.12】用对偶单纯形法求解】用对偶单纯形法求解求解过程见演示求解过程见演示（链接到（链接到Excel文件，需启用宏）。文件，需启用宏）。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 8 of 9例2.12可用性质6 及性质2来说明，表（2）的第2行对应于对偶问题的第2列（相
6、差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值 对应于对偶问题的比值 失效也说明 即对偶问题具有无界解，由性质2知原问题无可行解。8/15/20242.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 9 of 9本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种特殊线性规划的求解方法对偶单纯形法。1.对偶单纯形法的应用条件；2.出基与进基的顺序；3.如何求最小比值；4.最优解、无可行解的判断。作业：教材P76 T2.7The End of Section 3灵敏度分析Exit8/15/2024
