第6章 单纯形法的灵敏度分析与对偶2007-10-15

第六章 * 单纯形法的灵敏度分析与对偶v单纯形表的灵敏度分析v线性规划的对偶问题v对偶单纯形法第六章 * 单纯形法的灵敏度分析与对偶v如何利用最优单纯形表进行灵敏度分析。单纯形表 -求解结果：迭代次数基 变量 CB x1 X2 s1 s2 S3 b比 值50 100 0 0 00 x1 50 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250Zj 50 100 50 0 50 Z=275000 0 -50 0 -50第 1节 单纯形表的灵敏度分析一 . 目标函数中变量系数 Ck灵敏度分析现要利用单纯形表法来进行 Ck 的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时 ,分两类来讨论。1.在最终的单纯形表里 , xK 非 基变量 .2.在最终的单纯形表里 , xK 基变量 .第 1节 单纯形表的灵敏度分析1.在最终的单纯形表里 , xK 非基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与 CK 没有任何关系，所以当 CK 变为 CK + CK 时，在最终单纯形表中其系数的增广矩阵不变，又因为 xK 是非基变量，所以基变量的目标函数的系数不变，即 CB 不变，可知 ZK 也不变，只是 CK 变为 CK + CK 。这时 K= CK ZK 变成了 CK + CK ZK= K+ CK .要使得原来的最优解仍为最优解，只要 K+ CK 0 即可，也就是 CK K 即可。第 1节 单纯形表的灵敏度分析 .在最终的单纯形表里 , xK 为基变量。 由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与 CK 没有任何关系，所以当 CK 变为 CK + CK 时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系数CB变了，则 Zj 也变了， 相应地， 也变了。变化规律为：目目 标标 函数：函数：max z=50x1+100x2x1+ x23002x1+x2400x1 0, x20s.t.x2250max z=50x1+100x2x1+ x2+s1=3002x1+x2+s2=400x1 0, x20, si0s.t.x2+s3 =250一、线性规划问题解的基本概念基及基本解 :max z=50x1+100x2+0s1+0s2+0s31x1+1 x2+1s1+0s2+0s3 =3002x1+1 x2+0s1+1s2+0s3 =400x1 0, x20, s10， s20， s30s.t.0x1+1x2+0s1+0s2+1s3 =250表解形式的单纯形法v 例子 :初始单纯形表迭代次数基 变量 CB x1 X2 s1 s2 S3 b比 值50 100 0 0 02 x1 50 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50x2 100 0 1 0 0 1 250Zj 50 100 50 0 50 Z=275000 0 -50 0 -50（）先分析非基变量 s1: c3 3 由于是非基变量，故套用公式（ 1） 当 C3 -3, 时最优解不变 ;已知3=-50, C3 （ 50） =50；c=c+ C0, 不会破坏最优解。（ B） aij=0假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法，一是自己生产，二是出租设备资源。自己生产已有模型。那么，如果出租，那么如何构建模型？设备价格为 Ay1,By2,Cy3;则目标 :min f=300y1+400y2+250y3s.t. y1+2y2=50y1+y2+y3100y1,y2,y3 =0目标 :min f=300y1+400y2+250y3s.t. Y1+2y2=50y1+y2+y3100y1,y2,y3 =0v 目标 :max z=50x1+100x2v S.t.v x1+x2=0原问题 对偶问题1.求目标函数最大问题中有 n个变量 ,m个约束条件 ,它的约束条件都是小于等于不等式 ;其对偶则是 m个变量 ,n个约束条件 ,并且是大于等于不等式 ;