OR6灵敏度分析与对偶

1、OR6灵敏度分析与对偶 第六章第六章 单纯形法的灵敏度分析与对偶单纯形法的灵敏度分析与对偶 OR6灵敏度分析与对偶 本章内容：本章内容： o6.16.1单纯形表的灵敏度分析单纯形表的灵敏度分析 o6.26.2线性规划的对偶问题线性规划的对偶问题 o6.36.3对偶规划的基本性质对偶规划的基本性质 o6.46.4对偶单纯形法对偶单纯形法 OR6灵敏度分析与对偶 本章重点：本章重点： o利用最优单纯形表进行灵敏度分析利用最优单纯形表进行灵敏度分析 o线性规划问题的对偶问题线性规划问题的对偶问题 o对偶问题的经济解释对偶问题的经济解释 OR6灵敏度分析与对偶 6.16.1单纯形表的灵敏度分析单纯形表

2、的灵敏度分析 o一、目标函数中变量系数一、目标函数中变量系数Ck灵敏度分析灵敏度分析 o1.在最终的单纯形表里，在最终的单纯形表里，X k是非基变量是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行由于约束方程系数增广矩阵在迭代中只是其本身的行 的初等变换与的初等变换与Ck没有任何关系，所以当没有任何关系，所以当Ck变成变成 Ck+Ck时，在最终单纯形表中其系数的增广矩阵不时，在最终单纯形表中其系数的增广矩阵不 变，又因为变，又因为Xk是非基变量，所以基变量的目标函数是非基变量，所以基变量的目标函数 的系数不变，即的系数不变，即CB不变，可知不变，可知Zk也不变，只是也不变，只是Ck变

3、变 成了成了Ck+ Ck。这时。这时K= Ck-Zk就变成了就变成了 K Ck+Ck- Zk= K+ Ck。 要使原来的最优解仍为最优解，只要要使原来的最优解仍为最优解，只要K+ Ck0 即可，也就是即可，也就是Ck的增量的增量 Ck- K。 OR6灵敏度分析与对偶 2.在最终的单纯形表中，在最终的单纯形表中， X k是基变量是基变量 当当Ck变成变成Ck+Ck时，最终单纯形表时，最终单纯形表 中约束方程的增广矩阵不变，但是基中约束方程的增广矩阵不变，但是基 变量的目标函数的系数变量的目标函数的系数CB变了，则变了，则 Zj(j=1,2,.,n)也变了。也变了。 OR6灵敏度分析与对偶 Zj=

4、 Zj +Ck aKj j=Cj-Z j= j Ck a Kj 。要使最。要使最 优解不变，优解不变， 只要当只要当j k时，时， j0，也就说，也就说 Ck aKj j oa Kj 0，Ck j/ aKj oa Kj 0,则有则有 若若 ，则有，则有yi*=0 X X Y X Y n j ijij bxa 1 * n j ijij bxa 1 * Y OR6灵敏度分析与对偶 6.46.4对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种对偶单纯形法也是解决线性规划问题的一种 方法。对偶单纯形法是在保持原有问题的所方法。对偶单纯形法是在保持原有问题的所 有检验数都小于有检验数都小

5、于0的情况下，通过迭代使得的情况下，通过迭代使得 所有的约束都大于等于所有的约束都大于等于0，最后求得最优解。，最后求得最优解。 OR6灵敏度分析与对偶 简化计算是对偶单纯形法的优点，但是它在使用上有很简化计算是对偶单纯形法的优点，但是它在使用上有很 大的局限，这主要是大多数线性规划问题很难找到初始大的局限，这主要是大多数线性规划问题很难找到初始 解使得其所有检验数都小于解使得其所有检验数都小于0。但是在灵敏度分析中，。但是在灵敏度分析中， 有时需要对偶单纯形法，这样可以简化处理。下面以第有时需要对偶单纯形法，这样可以简化处理。下面以第 二节例一为例。二节例一为例。 上节分析中已知当上节分析中

6、已知当250b1325时第一个约束条件时第一个约束条件 的对偶价格不变，现在的对偶价格不变，现在b1=300变成变成b1=350，请问，请问 这时第一个约束方程的对偶价格应为多少呢？这时第一个约束方程的对偶价格应为多少呢？ OR6灵敏度分析与对偶 解：求出在第二次迭代表上的常数列 。 250 50 100 0 2 250 50 50 XX 1 1 1 b b b b bB OR6灵敏度分析与对偶 1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在确定出基变量，在常数列中找一个最小的负常量，把这个常量所在 行作为出基变量行作为出基变量 迭代 次数 基变量CBX1 X2 S1 S2 S3b 50 100 0 0 0 2 X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50 CJ -ZJ0 0 -50 0 -50 OR6灵敏度分析与对偶 OR6灵敏度分析与对偶 4.检查常数列值，若已经都非负，结束迭代，即为最优，如果还有负检查常数列值，若已经都非负，结束迭代，即为最优，如果还有负 数重复数重复1-4步步 迭代次 数 基变量CBX1 X2 S1 S2 S3b 50 100 0 0