第四章 灵敏度分析

运筹学

第四章 灵敏度分析运筹学

运筹学

灵敏度分析

现在睡觉的话会做梦,而现在学习的话会让梦实现 哈佛图书馆的训言1

使用LP求解管理问题时，管理者需要

了解当环境和数据发生变化时，线性规划得出的结论还是否有效；

资源供应发生变化会有什么影响?成本变化后利润会发生什么变化? 如果模型使用的数据不精确会有什么影 响，数据允许在什么范围内变化? 如果结论无效如何快速求解？

运筹学

灵敏度分析主要内容1. 目标函数系数变化的灵敏度分析

2. 右边项变化的灵敏度分析3.约束条件中的系数变化的灵敏度分析 4.求解新的最优解 5.增加新变量的灵敏度分析 6.增加约束条件的灵敏度分析 7.灵敏度分析的几何意义

运筹学

1. 目标函数系数变化的灵敏度分析(1) 分析什么？

假定只有一个 cj 变化，假定 cj 从 cj 变到cj’=cj+Δ cj,当Δ cj在什么范围内变化时，不会

影响最优解。(2) 怎么分析？ 最优解不变的充要条件是：

C B A C 0* B 1 *

运筹学

假定只有一个cj变化，分两种情况讨论：1)cj 是非基变量的系数

设cj 变化量为 cj ,若希望cj 变化后最优基不变，检验数应满足以下条件：

j’= cBB-1pj -(cj + cj )= cBB-1pj - cj - cj = j - cj 0 得到: cj j

运筹学

由 cj j 及最优条件 j 0,cj只在增加方向受限制， 在下降方向不受限制： cj增加时，变量对目标函数的贡献增加，增加足够 大时，检验数会大于零，使该变量入基而引起最优 基改变;

cj下降时，变量对目标函数的贡献下降，检验数变 得更正，最优基不会变化。 非基变量目标系数允许变化范围为: - cj j j JN 满足以上条件，解和目标值不会改变。

运筹学

例: 对最优表如下表对c1进行敏感性分析。解：cB 0 0 5 j xB B b x3 8 x4 0 x2 6 30-1

3 x1 1 -3/2 3/4 3/4

5 x2 0 0 1 0

0 x3 1 0 0 0

0 x4 0 1 0 0

0 x5 0 -1/2 1/4 5/4

c1: x1非基 c1 1 c1 3/4

运筹学

2) cj 是基变量的系数基变量的 cB 变化会引起cBB-1变化, 从而引 起所有检验数变化。若要使所有检验数满 足最优条件, 有以下条件:

k = (cB + cB)B-1pk - ck 0 cj = ( cB)r cB = (0,..., ( cB)r,..., 0) = (0,..., cj,..., 0)

k JN

假定cj 是当前基的第 r 个基变量，即：

运筹学

从而有：

k’ = (cB + cB)B-1pk - ck= cBB-1pk + (0,..,( cB)r,..,0)B-1pk- ck = k + cj (B-1pk)r 0 令 rk = (B-1pk)r 得： k JN

k’ = k + cj rk 0

k JN

运筹学

解不等式组 k’ = k + cj rk 0 k JN 得 cj 的变化范围： maxk {- , - k / rk rk>0} cj mink {+ , - k / rk rk<0} 在上述变化范围内： 目标函数值的改变量： z = cj xj 对偶解的改变量： y = cBB-1

原问题的最优基和最优解

不会改变。

运筹学

例: 对范例的目标函数系数进行敏感性分析。解：生产计划问题的最优单纯形表：

cB 0 5 3 j

xB B b x3 4 x2 6 x1 4 42

-1

3 x1 0 0 1 0

5 x2 0 1 0 0

0 x3 1 0 0 0

0 0 x4 x5 2/3 -1/3 1/2 0 -2/3 1/3 1/2 1

运筹学

cB 0 5 3 j

xB x3 x2 x1

B-1b 4 6 4 42

3 x1 0 0 1 0

5 x2 0 1 0 0

0 x3 1 0 0 0

0 0 x4 x5 2/3 -1/3 1/2 0 -2/3 1/3 1/2 1

c1: x1在基的第三行(r=3), 非基变量下标k=4 和5, 34= -2/3, 35=1/3,可得: max {- , -1/(1/3 )} c1 min{+ ,-1/2/(2/3)} -3 c1 3

运筹学

cB 0 5 3 j

xB B-1b x3 4 x2 6 x1 4 42

3 x1 0 0 1 0

5 x2 0 1 0 0

0 x3 1 0 0 0

0 0 x4 x5 2/3 -1/3 1/2 0 -2/3 1/3 1/2 1

c2 :x2 在基的第二行，r=2, 24=1/2,

25=0,可得：max{- ,(-1/2/(1)} c2 min{+ ,(-1)/(0)}

-1/2 c2

运筹学

2. 右边项发生变化的灵敏度分析(1) 分析什么？

假定只有一个 br 变化，假定 br 从 br 变到br*=br+Δ br,当Δ br在什么范围内变化时，不

会影响最优基。(不改变产品种类，只调整数量) (2) 怎么分析？ 最优基不变的充要条件是：

B (b b) 0 1

运筹学

1 B br

0 B 1b B 1 br br 0 bm b1

b1 ' 1r br br ' mr

运筹学

为了保持最优基不变，应使

X B 0 ,即

b1 ' 1r 0 b r bm ' mr 0 解不等式组，得

bi ' bi ' max ir 0 br min ir 0 ir ir

运筹学

例: 对范例的右边项进行敏感性分析。3 x1 0 0 1 0 5 x2 0 1 0 0 0 x3 1 0 0 0 0 0 x4 x5 2/3 -1/3 1/2 0 -2/3 1/3 1/2 1

cB 0 5 3 j

xB B-1b x3 4 x2 6 x1 4 42

1)对b1进行分析： i=1 对 应 基 的 第 一 列 ， 11= 13=1, 21= 23 = 0, 31= 33 = 0 max{- ,-4/1,-6/0,-4/0} b1 4 b1

运筹学

cB 0 5 3 j

xB B-1b x3 4 x2 6 x1 4 42

3 x1 0 0 1 0

5 x2 0 1 0 0

0 x3 1 0 0 0

0 0 x4 x5 2/3 -1/3 1/2 0 -2/3 1/3 1/2 1

2) 对 b2 进行分析：i = 2 对应基的第二列， 12 = 14 = 2/3, 22 = 24 = ½, 32 = 34 = -2/3 max{- , -4/(2/3),-6/(1/2)} b2 min{+ , -4/(-2/3)} 6 b2 6

运筹学

灵敏度分析一览表变化 内容 不在基中 目标系数 cj 变化 在基中 约束松 右边项 bi 变化 约束紧 允许改变的范围 - cj j max{- , - k / rk rk>0} cj min{+ , - k / rk rk<0} aix - bi bi + max{- , - bk / ki k i 0} bi min{+ , - bk / ki ki 0} 0 0 0 0 0

xB0

z0

y0

cjxj cBB-1

B-1 b bi i

运筹学

3、约束条件

中的系数变化(1) 分析什么？ 假设只有一个 aij 变化。其他数据不变， 并且只讨论 aij 为非基变量的系数的情 况。因此， aij的变化只影响一个检验 数 不会影响最优解 (2) 怎么分析？ 最优解不变的充要条件是： 。当Δ aij在什么范围内变化时， j

CB B A C 0 1 *

运筹学

j j Y

T

0 T T c j aij yi* j Y Pj Y aij 0

a ij

aij c j amj a1 j