OR-6灵敏度分析与对偶.ppt

《OR-6灵敏度分析与对偶.ppt》由会员分享，可在线阅读，更多相关《OR-6灵敏度分析与对偶.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 单纯形法的灵敏度分析与对偶单纯形法的灵敏度分析与对偶 李李 娜娜本章内容：本章内容：o6.16.1单纯形表的灵敏度分析单纯形表的灵敏度分析o6.26.2线性规划的对偶问题线性规划的对偶问题o6.36.3对偶规划的基本性质对偶规划的基本性质o6.46.4对偶单纯形法对偶单纯形法本章重点：本章重点：o利用最优单纯形表进行灵敏度分析利用最优单纯形表进行灵敏度分析o线性规划问题的对偶问题线性规划问题的对偶问题o对偶问题的经济解释对偶问题的经济解释6.16.1单纯形表的灵敏度分析单纯形表的灵敏度分析o一、目标函数中变量系数一、目标函数中变量系数Ck灵敏度分析灵敏度分析o1.在最终的单纯形表

2、里，在最终的单纯形表里，X k是非基变量是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行由于约束方程系数增广矩阵在迭代中只是其本身的行的的初等变换与初等变换与Ck没有任何关系，所以当没有任何关系，所以当Ck变成变成Ck+Ck时，在最终单纯形表中其系数的时，在最终单纯形表中其系数的增广矩阵不增广矩阵不变变，又因为，又因为Xk是非基变量是非基变量，所以基变量的目标函数，所以基变量的目标函数的系数不变，即的系数不变，即CB不变不变，可知，可知Zk也不变也不变，只是，只是Ck变变成了成了Ck+Ck。这时。这时K=Ck-Zk就变成了就变成了 K Ck+Ck-Zk=K+Ck。要使原来的最优解仍为

3、最优解，只要要使原来的最优解仍为最优解，只要K+Ck0即即可，也就是可，也就是Ck的增量的增量 Ck-K。2.在最终的单纯形表中，在最终的单纯形表中，X k是基变量是基变量 当当Ck变成变成Ck+Ck时，最终单纯形表中时，最终单纯形表中约束方程的约束方程的增广矩阵不变增广矩阵不变，但是基变量，但是基变量的目标函数的系数的目标函数的系数CB变变了，则了，则Zj(j=1,2,.,n)也也变变了。了。Zj=Zj+Ck aKj j=Cj-Z j=j Ck a Kj。要使最。要使最优解不变，优解不变，只要当只要当j k时，时，j0，也就说，也就说 Ck aKj joa Kj 0，Ck j/aKj oa

4、Kj 0,则有则有 若若 ，则有，则有yi*=06.46.4对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所方法。对偶单纯形法是在保持原有问题的所有有检验数都小于检验数都小于0的情况下，通过迭代使得的情况下，通过迭代使得所有的约束都所有的约束都大于等于大于等于0，最后求得最优解。，最后求得最优解。简化计算是对偶单纯形法的优点，但是它在使用上有很简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大的局限，这主要是大多数线性规划问题很难找到初始大多数线性规划问题很难找到初始解使得其所有检验数

5、都小于解使得其所有检验数都小于0。但是在灵敏度分析中，。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。二节例一为例。上节分析中已知当上节分析中已知当250b1325时第一个约束条件时第一个约束条件的对偶价格不变，现在的对偶价格不变，现在b1=300变成变成b1=350，请问，请问这时第一个约束方程的对偶价格应为多少呢？这时第一个约束方程的对偶价格应为多少呢？解：求出在第二次迭代表上的常数列1.确定出基变量，在常数列中找一个确定出基变量，在常数列中找一个最小的负常量最小的负常量，把这个常量所在，把这个常量所在行作

6、为出基变量行作为出基变量迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50CJ-ZJ0 0 -50 0 -504.检查常数列值，若已经检查常数列值，若已经都非负都非负，结束迭代，即为，结束迭代，即为最优最优，如果还有负，如果还有负 数重复数重复1-4步步迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 1/2 -1/275 S200 0 -2 -1/2 -1/225 X21000 1 0 0 1250 ZJ50 100 0 25 7528750CJ-ZJ0 0 0 -25 -75o作业 P125 89