运筹学 北京邮电大学.ch2-3.ppt

《运筹学 北京邮电大学.ch2-3.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、设原问题是（记为LP）：对偶问题是（记为DP）：根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时λj≤0，极小化问题时λj≥0。10/4/2021（1）将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数λj≤0（max）或λj≥0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi<0，则进行换基计算；（2）先确定出基变量。行对应的变量xl出基；（3）再选进基变量。求最小比值（4）求新的基本解，用初等变换将

2、主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。10/4/2021【例2.10】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以（－1），得到用对偶单纯形法，迭代过程如下页或看演示(请启用宏)。10/4/2021表2－410/4/2021应当注意：（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中的绝对值是使得比值非负，在极小化问题时λj≥0，分母aij<0这时必须取绝对值。在极大化问题中，λ≤j0分母ai

3、j<0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成这里λj≤0在求θk时就可以不带绝对值符号。10/4/2021（4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是其目的是保证下一个对偶问题的基本解可行；（6）对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。10/4/2021【例2

4、.12】用对偶单纯形法求解求解过程见演示（链接到Excel文件，需启用宏）。10/4/2021例2.12可用性质6及性质2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值对应于对偶问题的比值失效也说明即对偶问题具有无界解，由性质2知原问题无可行解。10/4/2021本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种特殊线性规划的求解方法—对偶单纯形法。1.对偶单纯形法的应用条件；2.出基与进基的顺序；3.如何求最小比值；4.最优解、无可行解的判断。作业：教材P76T

5、2.7TheEndofSection3灵敏度分析Exit10/4/2021