当前位置:文档之家› 第五章、灵敏度分析

第五章、灵敏度分析

第五章、灵敏度分析
一、 什么是灵敏度分析
我们前面讨论的线性规划问题,其目标 函数系数,约束系数和约束常数都是确定的 常数,但实际问题中,由于各种因素的影响, 这些常数是有变化的。例如产品的需求量、 产品的售价、原材料和能源的价格以及资源 的供应量等的变动,从而引起
c j 和 bi
a
的值的变化,工艺条件的改变, ij 的值就发 生变化。
a
i 1
m
ij i
y
当 C j 变为 C j j 后, 要保证最终表中这个检验数仍然小于或
j C j j C B B 1 P j 0 等于零,即
那么,
j j
才能满足原最优解条件。这就可以确定
Cj

变化范围。
(1) 若 C j 是基变量 x j 的系数,由于 C j CB ,当 C j 变化 j 时,就引 起了 CB 的变化。这时
C1 这样如上所分析,可知:当-1≤ ≤0 时,顶点 B C2
仍然是最优解,为了计算出C1 在什么范围内变化时最优解 不变,我们假设单位产品Ⅱ的利润为 100 元不变,即
C2 100;则有
C1 -1≤≤0 100
C 0≤ 1 ≤100
也即只要当单位产品Ⅱ的利润为 100 元, 单位产品Ⅰ的 利润在 0 与 100 元之间变化时, 顶点 B x1 50, x2 250 ) ( 仍然是最优解。
优解、最优值不变。
2、基变量的系数有波动
设 C1 有波动为 ,令C1 2 ,同样这一波动对由判别准则知
C B B 1 A C 0
从而,
0 1 1 3 2 1 1 5, 2 1 1 0 6 2 3 2 , 6 , 5, 4 , 0 , 0 0 1 0 1 2 6 1 2 1 3 0
C B B 1 A C 0


0 1 1 3 2 1 1 5, 2 1 1 0 6 2 3 2 6 5 4 0 0 0 1 0 1 2 1 1 0
C 从而, 1 0, 1 ,也就是当 1 或 2 7 是最优基、最
同样假设单位产品Ⅰ的利润为 50 元不变, C1 50, 即 有
50 -1≤≤0 C2
50≤ C2 ≤+∞
也就是说当单位产品Ⅰ的利润为 50 元不变,而单位 产品Ⅱ的利润只要大于等于 50 元时,顶点 B 仍是其最优 解。
如果当C1 和C2 都变化时,则也可以通过不等式
C1 -1≤ ≤0 来判断 B 点是否仍然为其最优解,例如当 C2
'j C j CB B 1 A j ( a j1 , a j 2 ,, a jn )
若要原最优解不变,即必须满足 'j 0 。于是得到
( 1 , 2 ,, n ) j ( a j1 , a j 2 ,, a jn ) 0
从而可以确定出 j 的范围,进而可以确定出 C j 的范围。
化为标准型:
min S ( 2 x1 6 x 2 5 x3 4 x 4 ) 3 x1 4 x 2 3 x3 x 4 x5 26 2 x1 3 x 2 2 x3 3 x 4 x 6 21 x j 0 , j 1, ,6
于是,我们面临这样的问题:当线性规划 问题的某些常数发生变化时,对已求出的最 有解有什么影响?显然,当线性规划问题的 一个或几个常数发生变化以后,原来已求得 的结果一般会发生变化。当然,可以用单纯 形法从头计算,以便得到新的解。这样做很 麻烦,而且也没有必要,因在单纯形表迭代 中,每次都和基变量的系数矩阵B有关,因 此,可以把发生变化的个别系数,经过一定 的计算直接填入最终表中,并进行检查和分 析----灵敏度分析。
产品 资源 设 备 原料 A 原料 B 利润
Ⅰ 1 2 0 50
Ⅱ 1 1 1 100
资源限制 300 台时 400 千克 250 千克
问工厂应分别生产多少个Ⅰ产品和 Ⅱ产品才能使工厂获利最大? 为了解决这个实际问题,我们把它归 结为数学问题来研究。 我们就得到了描述该问题的一组数学 表达式:
max Z 50x1 100x2 x1 x2 300 2 x1 x2 400 x2 250 x1 , x2 0
二、目标函数中价值系数c 的变化分析
技术方法:用单纯形法分析 用图解法分析
j
可以分别就对应的基变量和非基变量来讨论。 若是非基变量的系数

是基变量的系数
若 c j 是非基变量x j 的系数,这时它在计算表中所对应的 检验数是 j C B B Pj C j
1
或 j C j
max{ bi
| air 0} r min{ bi
air
| air 0}
仍然依例 1 来分析常数项的波动。 无妨设b1 有波动,令b1 26 。 因b1 的波动和 B 是基和判别准则无关。 仅影 响单纯形表中的
B 1b 0 ,故只要B 1b 0 ,则 B 仍是最优基。
从图1-1中可以看出只要目标函数的斜率在 直线E(设备约束条件)的斜率与直线F( 原料B的约束条件)的斜率之间变化时,顶 点B仍然是最优解。 如果目标函数直线逆时针旋转,当目标函 数的斜率等于直线F的斜率时,则可知直线 AB上的任一点都是其最优解。如果继续逆 时针旋转,则可知A点为其最优解。
如果目标函数直线顺时针方向旋转,当目标 函数的斜率等于直线E的斜率时,则可知直 线BC上的任一点都是其最优解。如果继续顺 时针旋转,当目标函数的斜率在直线E的斜 率和直线G的斜率之间,则顶点C为最优解。 当目标函数的斜率等于直线G的斜率时,则 直线CD上的任一点都是其最优解,如果在继 续顺时针旋转,可知顶点D为其最优解。
' 资源数量的变化是指系数r 发生变化,即 br br r 。 b
并假设线性规划问题的其他系数都不变,这样是最终表中 原问题的解相应的变化为:
' X B B 1 (b b ) ,这里 b (0,0, ,0,0) 。只要 r
' XB 0
,最终表中检验数不变,则最优基不变,但最优
用图解法或单纯形法求得最优解为:
x1 50, x2 250
我们知道生产一个单位的Ⅰ产品可以获利50元, 生产一个单位的Ⅱ产品可以获利100元,在目前的 生产条件下已求得生产Ⅰ产品50单位,生产Ⅱ产 品250单位可以获得最大利润。假设两种产品中的 某一产品的单位利润增加或减少时,我们意识到 为了获取最大利润就有可能应该增加或减少这一 产品的产量,也就是改变最优解。但是实际上这 一产品利润在一定范围内变化时整个线性规划的 最优解其实是不会变化的,即仍然生产50单位的 Ⅰ产品和250单位的Ⅱ产品而获利最大。当然其中 某一产品利润变化超出一定范围的话,最优解就 会受到影响了。我们的任务就是用简单的图解法 揭示这一变化的范围,定出其上限和下限。
用单纯形法可求得最优基 B= 表:
x1 S 47 x3 x1 5 11 0 0 1 x2 1 1 1 x3 0 1 0 x4
1 3 2 2
p 3 ,p 1
的单纯形
x5 1 2
x6 1 3
1 1
6
最优方案是产品 A 生产 11 吨,产品 C 生产 5 吨,产品 B 和 D 不生产,最大利润为 47 千元。 由最优单纯形表可得
1 1 26 5 即B b 2 3 21 11 2 0
所谓灵敏度分析: 就是在建立数学模型和求得最优解之后, 研究线性规划的一些系数变化时,对最优解 产生或最优基有什么影响?或者这些系数在 什么范围内变化时,最优解或最有基不变。 有了灵敏度分析就不必要为了应付这些变化 而不停的建立新的模型和求解。
用灵敏度分析以下几种情况
一、目标函数的系数发生了变化,对最优解 会产生什么影响 二、约束条件右边的值发生了变化,对最优 解会产生什么影响 三、增加了新变量,对最优解会产生什么影 响 四、用QM软件如何分析
这 时 在 最 终 表 中 求 得 的 b 列 的 所 有 元 素
bi air r 0, i 1,2,, m 由此可得 air r bi , i 1,2, m
当 air 0 时, r 当 ir
bi
a ir
a 0时,
air
r

bi
a ir
于是得到资源系数的变化范围:
' XB
解的值发生了变化,所以
为为新的最优解。新的最优
解的值可允许变化范围用一下方法确定。
0 r B 1 (b b) B 1b B 1b B 1b B 1 0
a1r 0 a1r r B 1 r air r r air a 0 a mr r mr
即 112 1 2 或 2312 C1 5 2 时, 最优基、 最优解 不变、 最优值变。
对于两个变量的线性规划问题的灵敏度 分析,我们还可以用图解法进行
例题2 某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品,已知生产单位产品所需要的设 备台时和A、B两种原材料的消耗以及资源的 限制情况,如表1-1所示:
3 1 B p3 , p1 2 1 C 2 6 5 4 0 0 C B 5, 2 0 1 1 B A 1 1 0
1 3 2
6
1 1 2 3
问题 2 如果产品 A、B、C、D 的利润有波动, 问限制在什么范围,才能是原最优解不变。 1、非基变量目标函数系数波动 对于本题非基变量为x2 , x4 无妨设 x2 的系数C 2 6 有波动,令C 2 6 ,则 这一波动对 B 是可行基无影响。 因此, 要使最优 基、最优解不变,由判别准则知
相关主题