运筹学精品课件之 对偶问题和灵敏度分析

1、第六节第六节 灵敏度分析灵敏度分析CBB-1b C - CBB-1 AB-1 b B-1 A原始数据原始数据A A，b b，C CA=(A=(P1 P2 Pn ) )公式公式 Z Z0= = CBB-1b X XB= = B-1b A = = C - CBB-1 A N = = CN - CBB-1 N j = = Cj- CBB-1 Pj A= A= B-1 A Pj = =B-1 Pj 标准型标准型 maxZ=CX AX = =b X 0(1)、参数、参数A，b，C在什么范围内变动，对当在什么范围内变动，对当前方案无影响？前方案无影响？(2)、参数、参数A，b，C中的一个中的一个(几个几个

2、)变动，对变动，对当前方案影响？当前方案影响？(3)、如果最优方案改变，如何用简便方法求、如果最优方案改变，如何用简便方法求新方案？新方案？例：例： A B C 备用资源备用资源 甲甲 1 1 1 12 乙乙 1 2 2 20 利润利润 5 8 6 产品产品原料原料问：如何安排产品产量，可获最大利润？问：如何安排产品产量，可获最大利润？maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12X1+2X2+2X3 +X5 =20X1 X5 0解解 5 8 6 0 0 X1 X2 X3 X4 X5 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1 0 5 8

3、 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 84 0 0 -2 -2 -3(一一)、目标函数中的价值系数、目标函数中的价值系数Cj的灵敏度分析的灵敏度分析(1)、非基变量系数、非基变量系数Cj由于检验数由于检验数 j = Cj -CBB-1 Pj Cj 改变，改变， j仍仍 0 0 时对最优方案无影响。时对最优方案无影响。例中例中C3改变改变 3 = C3 -CBB-1 P3 =C3 -(5 8) =C3 -8 0 0 2 -1-1 112即即C3 8 C3改为改为10， 3 =20 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 (1) -

4、1 1 84 0 0 (2) -2 -3 5 X1 4 1 0 0 2 -1 X3 8 0 1 1 -1 1 100 0 -2 0 0 -5 单位产品C的利润为10，则最优方案调整为 X=(4,0,8)T,目标值为100。(2)、基变量系数、基变量系数Cj Cj 改变，改变， 全部全部 j 0 0，最优方案不变。最优方案不变。例中例中C1改变改变 A = C -CBB-1 A =(C1 ,8,6,0,0 ) -(C1 8) 1 0 0 2 -10 1 1 -1 1=(0,0,-2,-2C1+8, C1 -8) 0-2C1+8 0C1-8 04 C1 8即单位产品A的利润在4,8之间变化时,最优

5、方案不变。 C1改变改变 C1=10， 5 =20 ,换基换基10 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 (1) 104 0 0 -2 -12 2 10 X1 12 1 1 1 1 0 0 X5 8 0 1 1 -1 1 120 0 -2 -4 -10 0 单位产品A的利润为10，则最优方案调整为 X=(12,0,0)T,目标值为120。(二二)、资源约束数量、资源约束数量 bj 的灵敏度分析的灵敏度分析 由于由于bj 的的改变，并不影响检验数，它只对最优改变，并不影响检验数，它只对最优方案有影响。方案有影响。(1)、bj 改变，改变， B-1 b仍仍 0时，最优方案

6、的生产时，最优方案的生产种类不变，生产数量发生改变。种类不变，生产数量发生改变。例中例中b1改变改变2 -1-1 1b12010 b1 20 B-1 b= 02b1 -20 0-b1+20 0即原料甲的供应在10，20之间时并不影响生产种类。(2)、 b1改变改变, b1=30 ，5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1 120 0 0 -2 -2 -35 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1 100 0 -2 -4 0 -5 2 -1-1 13020B-1 b= 40-10 原料甲的供应为30，则最优方案调整为 X=

7、(20,0,0)T,目标值为100。(三三)、添加新变量的灵敏度分析、添加新变量的灵敏度分析例例 对于新产品对于新产品D D，已知已知1 1个单位个单位D D要消耗要消耗 甲：甲：3 3 乙：乙：2 2 可以得利润可以得利润1010问：投产产品问：投产产品D D是否有利？是否有利？ 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 0 得得 C6 12（2 2） C6 =15 时时 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1 X1 X2 X3 X4 X5 X6 X1 4 1 0 0 2 -

8、1 (4) X2 8 0 1 1 -1 1 -1 84 0 0 -2 -2 -3 3 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0 87 -3/4 0 -2 -7/2 -9/4 0 单位单位D D的利润为的利润为1515时，生产时，生产B B产品产品9 9件，生产件，生产D D产品产品1 1件。件。目标值为87。(四四)、添加新约束的灵敏度分析、添加新约束的灵敏度分析例例 新增加电力约束：新增加电力约束：1313 A A、B B、C C每单位需电每单位需电 2 2、1 1、3 3问：原方案是否改变问：原方案是否改变？2X1 +X2 +3X3

9、1313 原方案原方案 A A：4 B4 B：8 C8 C：0 0需电需电 4 42 28 816 13 16 13 原方案要改变原方案要改变 2X1 +X2 +3X3 +X6 = = 1313 X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 84 0 0 -2 -2 -3 0 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6 -3 0 0 2 (-3) 1 1 84 0 0 -2 -2 -3 0 5 X1 2 1 0 4/3 0 -1/3 2/38 X2 9 0 1 1/3 0 2/3 -1/

10、30 X4 1 0 0 -2/3 1 -1/3 -1/3 82 0 0 -10/3 0 -11/3 -2/3 (五五)、技术系数、技术系数aij改变改变(计划生产的产品工艺结构改变计划生产的产品工艺结构改变) )(1)、非基变量、非基变量Xj工艺改变工艺改变只影响单纯形表只影响单纯形表Pj 列列， j .关键看关键看 j 0? 还是还是0? . 用用(三三)类似方法解决。类似方法解决。(2)、基变量、基变量Xj工艺改变，复杂工艺改变，复杂例：产品例：产品A工艺改变，对甲、乙需求变为工艺改变，对甲、乙需求变为2，2。 利润为利润为7，问最优方案如何？问最优方案如何？先计算先计算 p1= 2 -1

11、 2 = 2 -1 1 2 0一一 1= -7 取代取代 p1 与与 1 放入最优表放入最优表一一一一一一 X1 X1 X2 X3 X4 X5 X1 4 1 2 0 0 2 -1 X2 8 0 0 1 1 -1 1 0 -7 0 -2 -2 -3 7 X1 2 1 0 0 1 -1/2 8 X2 8 0 1 1 -1 1 70 0 0 -2 5 -13/2 0 X4 2 1 0 0 1 -1/2 8 X2 10 1 1 1 0 1/2 80 -5 0 -2 0 -7/2这时最优方案发生了改变。例例 p1 = 1 C1 = 7 3p1 = B-1 p1 = 2 -1 1 = -1 -1 1 3 2 1= -4一一一一也可能也可能 B-1 b出现负数出现负数检验数与基变量均不满足最优解要求检验数与基变量均不满足最优解要求基变量基变量Xj工艺改变工艺改变 X1 X1 X2 X3 X4 X5 X1 4 1 -1 0 0 2 -1 X2 8 0 2 1 1 -1 1 84 -4 0 -2 -2 -3 X1 -4 1 0 0 -2 1 X2 16 0 1 1 3 -1 68 0 0 -2 -10 1 X1 - 2X4 +X5 = -4-X1 +2