运筹学

第四章 灵敏度分析运筹学

运筹学

灵敏度分析

现在睡觉的话会做梦,而现在学习的话会让梦实现 哈佛图书馆的训言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