2.PPTVIP

x3 x4 x2 1.求b1: 设b1’=b1+△b1, 则b’=b+△b, △b=[△b1 0 0]T， 令XB’=B-1b’=B-1(b+△b)=XB+B-1△b≥0 即：x1’ 4 0 1/4 0 △b1 x5 = 4 + -2 1/2 1 0 x2’ 2 1/2 -1/8 0 0 4 0 4 = 4 + △b1 -2 = 4-2△b1 ≥0 2 1/2 2+△b1/2 解得：-4≤△b1≤2,b1变化范围：[8-4,8+2]=[4,10] 即设备台时在[4,10]范围内变化，原最优解中基变 量名称不变,但值改变。 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 x1 x5 x2 2 0 3 ?j 0 0 -1.5 -1/8 0 例7 求例1中3种资源的变化范围 2.求b2: 此时△b=[0 △b2 0]T，令： x1’ 4 0 1/4 0 0 x5’ = 4 + -2 1/2 1 △b2 x2’ 2 1/2 -1/8 0 0 4 1/4 4+△b2/4 = 4 + 1/2 △b2= 4+△b2/2 2 -1/8 2-△b2/8 ≥0 解得：△b2≥-16, △b2≥-8,△b2≤16, △b2变化范围-8≤△b2≤16, b2变化范围： [16-8,16+16]=[8,32], 即A材料数量在[8,32]范围 内变化,原最优解中基变量 名称不变,但值改变。 * * 对偶问题的提出 资源\产品 I II 资源限量 设备 1 2 8 台时 原材料A 4 0 16 kg 原材料B 0 4 12 kg 利润（元/件） 2 3 ? 若企业不打算自己生产而将资源出售（租），企业应考虑如何定价。设 y1﹑y2﹑y3为3种资源的单位售价，则有如下模型，我们称其为原问题的对偶模型。 Min W=8Y1+16Y2+12Y3 Y1+4Y2 ≥2 2Y1 +4Y3≥3 Y1﹑Y2 ﹑Y3≥0 Max Z=2X1+3X2 Min W=8Y1+16Y2+12Y3 X1+2X2≤8 Y1+4Y2 ≥2 4X1 ≤16 互为对偶 2Y1 +4Y3≥3 4X2 ≤12 Y1﹑Y2 ﹑Y3≥0 X1﹑X2≥0 称以下问题DP为其对偶问题 DP： Min W=bTY ATY≥C Y≥0 对于LP问题 P： Max Z=CX AX≤b X≥0 比较上述模型，可以得出两者之间的一些关系： 1.两个问题，一个是极大化，另一个是极小化； 2.一个问题的变量数等于另一问题的方程数，反之亦 然； 3.一个问题的目标函数系数是另一个问题的约束方程右端常数，反之亦然； 4.两个问题的约束方程系数矩阵互为转置； 对于不是P（规范）形式的LP问题，可先将其改写成P形式，写出DP后，再改成合适形式。 令X2= X2’-X2” Max Z=3X1+2X2’-2X2” X1 - X2’+X2” ≤ 1; -X1+ X2’-X2” ≤-1 -2X1 -4 X2’+4X2” ≤- 5 X1, X2’,X2”≥0 Max Z=3X1+2X2 X1-X2=1 2X1 +4X2 ≥ 5 X1≥0 令X2= X2’-X2” Max Z=3X1+2X2’-2X2” X1 - X2’+X2” ≤ 1 -X1+ X2’-X2” ≤-1 -2X1 -4 X2’+4X2” ≤- 5 X1, X2’,X2”≥0 Min W=z1-z2-5z3 z1 - z2 –2z3 ≥3 -z1+ z2