1
灵敏度分析
2
一,什么为灵敏度分析？
引起因素内容具体项目
3
1.引起因素产品单位利润 cj的变化生产条件改变引起约束系数 aij的变化资源投入量的改变会引起右端项 bi的变化新产品的开发会引起决策变量的增加增加新的资源限制（或其它限制）引起约束条件的增加
4
2.内 容对原有模型及最优解进行分析,
当模型的数据中有一个或几个发生变化时，最优解会有什么变化这些数据在什么范围内变化时，已求解的最优解（或最优基）不变若是最优解（或最优基）发生变化后，
如何求出新的最优解（或最优基）
5
3.具体项目对于标准化的形式
m a x
..
0
Z C X
A X b
st
X
6
是最优解的条件是 1
0
B
N
X BbX
X
1
1
0
0
B
C C B A
Bb
7
（ 1）目标函数系数 C的变化。
（ 2）右端常数 b的变化。
（ 3）增加新变量和新的约束条件的变化。
（ 4）目标系数或右端项包含参数的变化。
8
二,目标系数的变化
1
1
0
0
B
C C B A
Bb
9
是最优解的条件是 1
0
B
N
X BbX
X
1 0
BX B b
1 0
BC C B A
可行性条件最优性条件
10
1.非基变量目标系数的变化
'
j j jc c c
设 ' ' 1
1
1
()
()
0
j j B j
j j B j
j B j j
jj
c C B p
c c C B P
c C B P c
c
则
jjc
所以保持最优解与最优基不变的条件是：
11
结 论为保持原最优解不变时非基变量的目标系数的变化范围,当超出这个范围时,原最优解不再是最优解 。
jjc
12
例 1
1 2 3
1
1 2 32
1 2 3
m a x 6 30 13
4 24
s.t,4 4 60
0 ( 1,2,3 )
i
Z x x x
x x x
x x x
xi
13
最终单纯形表
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
14
x2的目标系数的变化范围为
2 16c
2 16
2 16c
'
2 2 2 3 0 1 6 4 6c c c
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
15
'
2 5 0 4 6c
已超出 c2的变化范围2c
' ' 1
2 2 2
12
5 0 ( 6,1 3 )
2
5 0 4 6 4 0
B
c C B P?
若此时 x2为进基变量,x1
为出基变量进行下一轮迭代，
最优解被改变。
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
16
0 -16 0 -11 1/2 294
1 12 0 4 -1 36
0 -2 1 -1 1/2 6
-1/3 0 0 -37/3 -1/6 306
1/12 1 0 1/3 -1/12 3
1/6 0 1 -1/3 1/3 12
x1 x2 x3 x4 x5 RHS
Z
x1
x3
Z
x2
x3
改变
17
2.基变量的目标系数的变化
18
当最优基 B的某个变量 的目标系数 改变为 时，由于 是 的分量，
则相应的最优解中 发生变化其中,是 的第 行，于是变化后的检验数为
0ix
0ic
0 0 0i i ic c c
0ic BC
BC
0
0 0 0 0
1
11
1
12
()
( 0,,,,0)
(,,,)
BB
Bi
B i i i i n
C C B A
C B A c B A
C B A c a a a
0 0 012(,,,)i i i na a a
1BA?
0i
00
1()j j B B J i i jc C C B A c a
19
要使最优基与最优解不变，必有
，
即当 时，有当 时，有因此，有 范围是
0 ( 1,2,,)j jn
0 0ia? 0
o
ji
ij
c a
0 0ia? 0
o
ji
ij
c a
0ic?
0 0 0
00
m a x 0 m i n 0jji j i i j
jj
i j i j
a c a
aa
20
例 2
4800121x30
—1601004x40
31210040x50
000032-Z
22-1/20101x30
-9-3/40002-Z
—31/40010x23
41601004x40
x5x4x3x2x1XBCB θB-1b
00032C
21
—2-1/20101x12
4821-400x40
1231/40010x23
-131/40-200-Z
401/4001x12
-140-1/8-3/200-Z
20-1/81/210x23
411/2-200x50
x5x4x3x2x1XBCB θB-1b
00032C
22
对 C1进行灵敏度分析
1
1 1,2,3,4,5
1 0 0 1 / 4 0
1 1,5,2 0 0 2 1 / 2 1
0 1 1 / 2 1 / 8 0
3 1 1
2 1,3,0,0,0 2 1,3,,1,0
2 4 8
3 1 1 1
0,0,,1,0 0 1
2 4 8 2
T
BB
C C C B A
c c c c c c
c c c c
c c c
cc
23
请同学们对例 2中的 C2进行灵敏度分析
24
401/4001x12
0-1/8-3/2△ c20-Z
20-1/81/210x23
411/2400x50
x5x4x3x2x1XBCB θB-1b
0003+△ c22C
25
401/4001x12
0△ c2/8
-1/8
-3/2-
△ c2
00-Z
20-1/81/210x23+
△ c2
411/2-400x50
x5x4x3x2x1XBCB θB-1b
0003+△ c22C
2c?
26
百分之百法则如果若干个目标函数系数同时变动,计算出每一系数变动量占该系数允许变动量的百分比,再将所有系数变动百分比相加,若所得之和不超过百分之一百,则最优解不会改变,若所得之和超过了百分之一百,则不能确定最优解是否改变 。
27
EXCEL的求解图 5-2“规划求解结果”对话框
28
图 5-3目标系数灵敏度分析报告
29
三,右端常数项的变化
1 0Bb
1 0
BC C B A
30
00ii
bb
0
0 0 0
0 0 0 0
0 0 0
1 1 1 1 1
' * '
*
1 1 1
1
* ' * '
*
' * '
0
0
i
i i i
k k i i k k i i
m
m i m m i i
B b b B b B b B b B b
a b a b
b
b a b b a b
b a b a b
设
31
为 中的第 i0列
0 0 0' ' '1,,,Ti k i m ia a a
1B?
* * * 112,,..,,Tmb b b B b
1 0B b b
上述条件满足时，最优解才不改变
32
以例 2为例为松弛变量的系数矩阵，若对 b1进行灵敏度分析，则设 列式如下：
1B?
1 1 1b b b
1
0 1 / 4 0 8 1
2 1 / 2 1 1 6 0
1 / 2 1 / 8 0 1 2
4 1 2
b
Bb
b
33
请同学们对 b2进行灵敏度分析
34
若 bi超出变化范围则必有基变量的值不满足非负，根据对偶单纯形法，选择不满足非负的基变量为出基变量，再确定入基变量进一步进行迭代。
35
EXCEL
图 5-6右端项灵敏度分析报告同样具有百分百法则
36
四,约束系数的灵敏度分析
1
1
m a x
..
0
0
0
B
z CX
A X b
st
X
Bb
C C B A
1
0
B
N
X B b
X
为原问题最优解
1BY C B 为对偶问题一可行解
37
分析项目非基变量 xj的系数向量 Pj发生变化基变量 xj的系数向量 Pj发生变化增加新的决策变量增加新的约束条件
38
1.非基变量 xj的系数向量 Pj的变化范围设
1
1
11
1
()
j j B j
j B j j
j B j B j
j B j
jj
c C B P
c C B P P
c C B P C B P
C B P
YP
j j jP P P
1BCB? 为原问题最终单纯形表中松弛变量的相反数
39
12
0
0
,,,
0
0
j m ij i ij j
Y P y y y a y a?
0iy?
时，
j
ij
i
a y
j
ij
i
a y时，0iy
40
例 1
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 5 3 4
2 3 2 8 0 0 ;
5 4 3 4 1 2 0 0 ;
..
3 4 5 3 1 0 0 0 ;
0 1,2,3,4
j
Z x x x x
x x x x
x x x x
st
x x x x
xj
41
最终单纯形表
-1300-1-1/400-11/40-13/4
1001-3/40011/41-3/4
200-1101-202
100-11/410-13/401/4
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 4
x 2
-Z
42
（ 1）为保持现有最优解不变，分别求非基变量 x1,x3的系数的变化范围；
（ 2）若非基变量 x3的系数由（ 1 3 5） T
变为（ 1 4 1） T，考察原最优解是否仍然保持最优？若不是，该怎么办？
43
（ 1）的解答解：
（ 1）由最优表可以查得 y1 =0,y2 =1/4，
y3 =1，且 y2 >0,y3 >0。
故
1
21
2
1
31
3
3
23
2
3
33
3
13 / 4
13,
1 / 4
13 / 4
13 / 4,
1
11 / 4
11,
1 / 4
11 / 4
11 / 4.
1
a
y
a
y
a
y
a
y
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 5 3 4
2 3 2 8 0 0 ;
5 4 3 4 1 2 0 0 ;
..
3 4 5 3 1 0 0 0 ;
0 1,2,3,4
j
Z x x x x
x x x x
x x x x
st
x x x x
xj
44
（ 2）的解答
1 3 2 3 3 31 1 0,4 3 1,1 5 4,a a a
3
1 1 0
4 3 1,
1 5 4
P
33
0
0,1 / 4,1 1 15 / 4 11 / 4,
4
YP?
所以原最优解已不再是最优解。
（ 2）当 x3的系数由（ 1 3 5） T变为
（ 1 4 1） T时，显然有即则
45
（ 2）寻找新的最优解求新的检验数为：
13 3 3
1
3 0,1 / 4,1 4 1 0,
1
Bc C B P?
故取 x3为进基变量，再计算
1
3
1
11
114
0 1 1 4 3
3 1 2
01
4
BP
46
再进行基变化
-1300-1-1/40010-13/4
1001-3/400-21-3/4
200-1101302
100-11/410101/4
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 4
x 2
-Z
47
-4100/3-2/3-7/120-1/300-47/12
700/31/3-1/1202/3017/12
200/3-1/31/301/3102/3
100/3-2/3-1/121-1/300-5/12
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 3
x 2
-Z
48
2.基变量 xj的系数向量 Pj的变化
1
1
0
0B
Bb
C C B A
均发生变化因而单纯形表变化较大，一般得不出变化范围的一般公式，需重新求解。
49
例 2
1 2 3 4 5
1 2 3
14
25
m a x 2 3 0 0 0
2 8
4 1 6
..
4 1 2
0,1,2,,5
j
z x x x x x
x x x
xx
st
xx
xj
50
最终单纯形表
x1 x2 x3 x4 x5 b
x 1
x 5
x 2
-Z -140-1/8-3/200
20-1/81/210
411/2-200
401/4001
51
分析原计划生产产品的工艺结构发生变化。若原计划生产产品 Ⅰ 的工艺有了改进，这时有关它的技术系数向量变为,每件利润为 4元。试分析对原最优计划有什么影响？
1 2,5,2 TP
52
解解：把改进工艺结构的产品 Ⅰ 看作产品 Ⅰ ’，设 x1’
为其产量。于是计算在最终表中对应 x1’的列向量，并以 x1’代替 x1。
1
1
0 0,2 5 0 2 1,2 5
2 0,5 1 5 0,5
0,5 0,1 2 5 0 2 0,3 7 5
BP
同时计算出 x1’的检验数为
1
11 4 ( 2,0,3 ) ( 1,2 5,0,5,0,3 7 5 ) 0,3 7 5
T
Bc C B P
53
将以上计算结果填入最终表 x1的列向量位置。得
1.25 0 0 0.25 0 4
0.5 0 -2 0.5 1 4
0.375 1 0.5 0.125 0 2
0.375 0 -1.5 -0.125 0
x1’ x2 x3 x4 x5 b
x1
x5
x2
-Z
54
0-0.2-1.500
0.80-0.20.510
2.410.4-200
3.200.2001
x1’ x2 x3 x4 x5 b
x1’
x5
x2
-Z
原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品
Ⅰ ’3.2单位；生产产品 Ⅱ 0.8单位。可获利
15.2元。
55
若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解。
56
例 3
假设上例的产品 Ⅰ ’的技术系数向量变为,而每件获利仍为 4元。试问该厂应如何安排最优生产方案？
1 ( 4,5,2) TP
57
解：以 x1’代替 x1,计算
1
1
0 0,2 5 0 4 1,2 5
2 0,5 1 5 3,5
0,5 0,1 2 5 0 2 1,3 7 5
BP
58
x1’的检验数为
111 4 ( 1,5,0,1 2 5,0 ) * ( 4,5,2 ) 2,6 2 5Bc C B P
将这些数字填入最终表的 x1列位置，得
0-0.125-1.50-2.625
200.1250.511.375
410.5-20-3.5
400.25001.25
x1’ x2 x3 x4 x5 b
x1
x5
x2
-Z
59
将 x1’替换变量中的 x1，得
00.4-1.500
-2.40-0.40.510
15.211.2-200
3.200.2001
x1’ x2 x3 x4 x5 b
x1’
x5
x2
-Z
可见原问题和对偶问题都是非可行解。
60
于是引入人工变量 x6。在 x2所在行，用方程表示时为
1 2 3 4 50 0,5 0,4 0 2,4x x x x x
引入人工变量 x6后，为
2 3 4 60,5 0,4 2,4x x x x
将 x6作为基变量代替 x2，得下表
61
00-0.8+
0.4M
-0.5M3-M0
2.4100.4-0.5-10
15.2011.2-200
3.2000.2001
x1’ x2 x3 x4 x5 x6 b
x1’
x5
x6
-Z
62
-M+200-110
62.501-1.25-2.50
8-310-0.530
20.5000.250.51
x1’ x2 x3 x4 x5 x6 b
x1’
x5
x4
-Z
63
-M+3-0.330-0.8300
12.66700.8311.66700
2.667-10.330-0.16710
0.6670-0.3300.3301
x1’ x2 x3 x4 x5 x6 b
x1’
x2
x4
-Z
最优生产方案为生产产品 Ⅰ ’0.667单位；生产产品
Ⅱ 2.667单位。可获利 10.67元 。
64
3.增加新的决策变量 xk
A增加一列
1
2
k
k
k
mk
a
a
P
a
65
例 4
分析在原计划中是否应该安排一种新产品。
以上例为例。设该厂除了生产产品 Ⅰ,
Ⅱ 外，现有一种新产品 Ⅲ 。已知生产产品 Ⅲ,每件需消耗原材料 A,B各为 6kg，
3kg，使用设备 2台时；每件可获利 5元。
问该厂是否应生产该产品和生产多少？
66
解解 （ 1）设生产产品 Ⅲ x3’台，其技术系数向量,然后计算最终表中对应的检验数 3 ( 2,6,3 ) TP
1
3 3 3
5 ( 1,5,0,1 2 5,0 ) ( 2,6,3 )
1,2 5 0
B
T
c C B P
说明安排生产产品 Ⅲ 是有利的。
67
（ 2）计算产品 Ⅲ 在最终表中对应 x3’的列向量
1
3
0 0.25 0 2 1.5
2 0.5 1 6 2
0.5 0.12 5 0 3 0.25
BP?
填入最终表，可得
68
1.250-0.125-1.500
20.250-0.1250.510
4210.5-200
41.500.25001
x1 x2 x3 x4 x5 x3’ b
x1
x5
x4
-Z
由于 b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，
说明目标函数值还可以改善。
69
（ 3）将 x3’作为换入变量,x5作为换出变量，进行迭代，求出最优解。
0-0.625-0.4375-0.2500
1.50-0.125-0.18750.7510
210.50.25-100
10-0.75-0.1251.501
x1 x2 x3 x4 x5 x3’ b
x1
x3’
x2
-Z
最优解 x1=1,x2=1.5,x3’=2。总的利润为 16.5
元。比原计划增加了 2.5元。
70
4.增加新的约束条件请同学们自学教材 P109。
71
五,参数规划系数中含有某个未知参数。
72
1、参数 c的变化分析试分析以下参数线性规划问题。当参数
t>=0时的最优解变化。 12
1
2
12
12
m a x ( ) ( 3 2 ) ( 5 )
4
2 1 2
..
3 2 1 8
,0
z t t x t x
x
x
st
xx
xx
73
解：将模型化为标准型
12
13
24
1 2 5
m a x ( ) ( 3 2 ) ( 5 )
4
2 12
..
3 2 18
0,1,2,,5
j
z t t x t x
xx
xx
st
x x x
xj
74
令 t=0，用单纯形法求解
x1 x2 x3 x4 x5 b
-1-3/2000
21/3-1/3001
601/2010
2-1/31/3100x3
x2
x1
-Z
75
x1 x2 x3 x4 x5 b
000
21/3-1/3001
601/2010
2-1/31/3100x3
x2
x1
-Z 3726t 21 3 t
考察 t 的变化对最优解的影响第一临界点,t=（ 3/2） /（ 7/6） =9/7，此时 δ 4=0。
0<=t<=9/7 时，最优解如上表（ 2,6,2,0,0） T。
将 c的变化直接反映到表中
76
当 t > 9/7时,δ 4 >0，以 x4为入基变量
4
3
6
x1 x2 x3 x4 x5 b
000
00101
1/20-3/210
-11300x4
x2
x1
-Z 9722t? 5122t
考察 t 的变化对最优解的影响第二临界点,t=（ 5/2） /（ 1/2） =5，此时 δ 5=0。
9/7 <=t<=5时，最优解如上表（ 4,3,0,6,0） T。
77
当 t > 5时,δ 5 >0，以 x5为入基变量
4
6
12
x1 x2 x3 x4 x5 b
000
00101
10-320
01020x4
x5
x1
-Z 32t5 t?
当 t>5时，恒有 δ 2< 0,δ 3<0,最优解如上表，为（ 4,0,0,12,6） T。
78
2、参数为 b的变化分析分析以下线性规划问题，当 t>=0时，其最优解的变化。
12
12
12
12
m a x 3
6
.,2 6
,
z x x
x x t
s t x x t
x x o
79
解：将上述模型化为标准型
12
1 2 3
1 2 4
1 2 3 4
m ax 3
6
.,2 6
,,,
z x x
x x x t
s t x x x t
x x x x o
80
令 t=0，用单纯形法求解
-2/3-5/300
41/31/310
2-1/32/301
x1 x2 x3 x4 b
x1
x2
-Z
81
将 b的变化直接反映到表中
-2/3-5/300
41/31/310
2-t-1/32/301
x1 x2 x3 x4 b
x1
x2
-Z
当 0≤ t≤ 2时，最优解为（ 2-t,4,0,0） T。
当 t> 2时，表中的解为非可行解，于是按照对偶单纯形法进行迭代。
82
t> 2迭代以后
0-30-2
6-t0111
-6+3t1-20-3
x1 x2 x3 x4 b
x4
x2
-Z
当 2<=t<=6时，问题的最优解为
（ 0,6-t,0,-6+3t） T。
当 t> 6时，问题无可行解。
灵敏度分析
2
一,什么为灵敏度分析？
引起因素内容具体项目
3
1.引起因素产品单位利润 cj的变化生产条件改变引起约束系数 aij的变化资源投入量的改变会引起右端项 bi的变化新产品的开发会引起决策变量的增加增加新的资源限制（或其它限制）引起约束条件的增加
4
2.内 容对原有模型及最优解进行分析,
当模型的数据中有一个或几个发生变化时，最优解会有什么变化这些数据在什么范围内变化时，已求解的最优解（或最优基）不变若是最优解（或最优基）发生变化后，
如何求出新的最优解（或最优基）
5
3.具体项目对于标准化的形式
m a x
..
0
Z C X
A X b
st
X
6
是最优解的条件是 1
0
B
N
X BbX
X
1
1
0
0
B
C C B A
Bb
7
（ 1）目标函数系数 C的变化。
（ 2）右端常数 b的变化。
（ 3）增加新变量和新的约束条件的变化。
（ 4）目标系数或右端项包含参数的变化。
8
二,目标系数的变化
1
1
0
0
B
C C B A
Bb
9
是最优解的条件是 1
0
B
N
X BbX
X
1 0
BX B b
1 0
BC C B A
可行性条件最优性条件
10
1.非基变量目标系数的变化
'
j j jc c c
设 ' ' 1
1
1
()
()
0
j j B j
j j B j
j B j j
jj
c C B p
c c C B P
c C B P c
c
则
jjc
所以保持最优解与最优基不变的条件是：
11
结 论为保持原最优解不变时非基变量的目标系数的变化范围,当超出这个范围时,原最优解不再是最优解 。
jjc
12
例 1
1 2 3
1
1 2 32
1 2 3
m a x 6 30 13
4 24
s.t,4 4 60
0 ( 1,2,3 )
i
Z x x x
x x x
x x x
xi
13
最终单纯形表
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
14
x2的目标系数的变化范围为
2 16c
2 16
2 16c
'
2 2 2 3 0 1 6 4 6c c c
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
15
'
2 5 0 4 6c
已超出 c2的变化范围2c
' ' 1
2 2 2
12
5 0 ( 6,1 3 )
2
5 0 4 6 4 0
B
c C B P?
若此时 x2为进基变量,x1
为出基变量进行下一轮迭代，
最优解被改变。
294-1/2-110-160
1/2
-1
6-11-20
3640121
x1 x2 x3 x4 x5 RHS
Z
x1
x3
16
0 -16 0 -11 1/2 294
1 12 0 4 -1 36
0 -2 1 -1 1/2 6
-1/3 0 0 -37/3 -1/6 306
1/12 1 0 1/3 -1/12 3
1/6 0 1 -1/3 1/3 12
x1 x2 x3 x4 x5 RHS
Z
x1
x3
Z
x2
x3
改变
17
2.基变量的目标系数的变化
18
当最优基 B的某个变量 的目标系数 改变为 时，由于 是 的分量，
则相应的最优解中 发生变化其中,是 的第 行，于是变化后的检验数为
0ix
0ic
0 0 0i i ic c c
0ic BC
BC
0
0 0 0 0
1
11
1
12
()
( 0,,,,0)
(,,,)
BB
Bi
B i i i i n
C C B A
C B A c B A
C B A c a a a
0 0 012(,,,)i i i na a a
1BA?
0i
00
1()j j B B J i i jc C C B A c a
19
要使最优基与最优解不变，必有
，
即当 时，有当 时，有因此，有 范围是
0 ( 1,2,,)j jn
0 0ia? 0
o
ji
ij
c a
0 0ia? 0
o
ji
ij
c a
0ic?
0 0 0
00
m a x 0 m i n 0jji j i i j
jj
i j i j
a c a
aa
20
例 2
4800121x30
—1601004x40
31210040x50
000032-Z
22-1/20101x30
-9-3/40002-Z
—31/40010x23
41601004x40
x5x4x3x2x1XBCB θB-1b
00032C
21
—2-1/20101x12
4821-400x40
1231/40010x23
-131/40-200-Z
401/4001x12
-140-1/8-3/200-Z
20-1/81/210x23
411/2-200x50
x5x4x3x2x1XBCB θB-1b
00032C
22
对 C1进行灵敏度分析
1
1 1,2,3,4,5
1 0 0 1 / 4 0
1 1,5,2 0 0 2 1 / 2 1
0 1 1 / 2 1 / 8 0
3 1 1
2 1,3,0,0,0 2 1,3,,1,0
2 4 8
3 1 1 1
0,0,,1,0 0 1
2 4 8 2
T
BB
C C C B A
c c c c c c
c c c c
c c c
cc
23
请同学们对例 2中的 C2进行灵敏度分析
24
401/4001x12
0-1/8-3/2△ c20-Z
20-1/81/210x23
411/2400x50
x5x4x3x2x1XBCB θB-1b
0003+△ c22C
25
401/4001x12
0△ c2/8
-1/8
-3/2-
△ c2
00-Z
20-1/81/210x23+
△ c2
411/2-400x50
x5x4x3x2x1XBCB θB-1b
0003+△ c22C
2c?
26
百分之百法则如果若干个目标函数系数同时变动,计算出每一系数变动量占该系数允许变动量的百分比,再将所有系数变动百分比相加,若所得之和不超过百分之一百,则最优解不会改变,若所得之和超过了百分之一百,则不能确定最优解是否改变 。
27
EXCEL的求解图 5-2“规划求解结果”对话框
28
图 5-3目标系数灵敏度分析报告
29
三,右端常数项的变化
1 0Bb
1 0
BC C B A
30
00ii
bb
0
0 0 0
0 0 0 0
0 0 0
1 1 1 1 1
' * '
*
1 1 1
1
* ' * '
*
' * '
0
0
i
i i i
k k i i k k i i
m
m i m m i i
B b b B b B b B b B b
a b a b
b
b a b b a b
b a b a b
设
31
为 中的第 i0列
0 0 0' ' '1,,,Ti k i m ia a a
1B?
* * * 112,,..,,Tmb b b B b
1 0B b b
上述条件满足时，最优解才不改变
32
以例 2为例为松弛变量的系数矩阵，若对 b1进行灵敏度分析，则设 列式如下：
1B?
1 1 1b b b
1
0 1 / 4 0 8 1
2 1 / 2 1 1 6 0
1 / 2 1 / 8 0 1 2
4 1 2
b
Bb
b
33
请同学们对 b2进行灵敏度分析
34
若 bi超出变化范围则必有基变量的值不满足非负，根据对偶单纯形法，选择不满足非负的基变量为出基变量，再确定入基变量进一步进行迭代。
35
EXCEL
图 5-6右端项灵敏度分析报告同样具有百分百法则
36
四,约束系数的灵敏度分析
1
1
m a x
..
0
0
0
B
z CX
A X b
st
X
Bb
C C B A
1
0
B
N
X B b
X
为原问题最优解
1BY C B 为对偶问题一可行解
37
分析项目非基变量 xj的系数向量 Pj发生变化基变量 xj的系数向量 Pj发生变化增加新的决策变量增加新的约束条件
38
1.非基变量 xj的系数向量 Pj的变化范围设
1
1
11
1
()
j j B j
j B j j
j B j B j
j B j
jj
c C B P
c C B P P
c C B P C B P
C B P
YP
j j jP P P
1BCB? 为原问题最终单纯形表中松弛变量的相反数
39
12
0
0
,,,
0
0
j m ij i ij j
Y P y y y a y a?
0iy?
时，
j
ij
i
a y
j
ij
i
a y时，0iy
40
例 1
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 5 3 4
2 3 2 8 0 0 ;
5 4 3 4 1 2 0 0 ;
..
3 4 5 3 1 0 0 0 ;
0 1,2,3,4
j
Z x x x x
x x x x
x x x x
st
x x x x
xj
41
最终单纯形表
-1300-1-1/400-11/40-13/4
1001-3/40011/41-3/4
200-1101-202
100-11/410-13/401/4
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 4
x 2
-Z
42
（ 1）为保持现有最优解不变，分别求非基变量 x1,x3的系数的变化范围；
（ 2）若非基变量 x3的系数由（ 1 3 5） T
变为（ 1 4 1） T，考察原最优解是否仍然保持最优？若不是，该怎么办？
43
（ 1）的解答解：
（ 1）由最优表可以查得 y1 =0,y2 =1/4，
y3 =1，且 y2 >0,y3 >0。
故
1
21
2
1
31
3
3
23
2
3
33
3
13 / 4
13,
1 / 4
13 / 4
13 / 4,
1
11 / 4
11,
1 / 4
11 / 4
11 / 4.
1
a
y
a
y
a
y
a
y
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
m a x 5 3 4
2 3 2 8 0 0 ;
5 4 3 4 1 2 0 0 ;
..
3 4 5 3 1 0 0 0 ;
0 1,2,3,4
j
Z x x x x
x x x x
x x x x
st
x x x x
xj
44
（ 2）的解答
1 3 2 3 3 31 1 0,4 3 1,1 5 4,a a a
3
1 1 0
4 3 1,
1 5 4
P
33
0
0,1 / 4,1 1 15 / 4 11 / 4,
4
YP?
所以原最优解已不再是最优解。
（ 2）当 x3的系数由（ 1 3 5） T变为
（ 1 4 1） T时，显然有即则
45
（ 2）寻找新的最优解求新的检验数为：
13 3 3
1
3 0,1 / 4,1 4 1 0,
1
Bc C B P?
故取 x3为进基变量，再计算
1
3
1
11
114
0 1 1 4 3
3 1 2
01
4
BP
46
再进行基变化
-1300-1-1/40010-13/4
1001-3/400-21-3/4
200-1101302
100-11/410101/4
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 4
x 2
-Z
47
-4100/3-2/3-7/120-1/300-47/12
700/31/3-1/1202/3017/12
200/3-1/31/301/3102/3
100/3-2/3-1/121-1/300-5/12
x1 x2 x3 x4 x5 x6 x7 b
x 5
x 3
x 2
-Z
48
2.基变量 xj的系数向量 Pj的变化
1
1
0
0B
Bb
C C B A
均发生变化因而单纯形表变化较大，一般得不出变化范围的一般公式，需重新求解。
49
例 2
1 2 3 4 5
1 2 3
14
25
m a x 2 3 0 0 0
2 8
4 1 6
..
4 1 2
0,1,2,,5
j
z x x x x x
x x x
xx
st
xx
xj
50
最终单纯形表
x1 x2 x3 x4 x5 b
x 1
x 5
x 2
-Z -140-1/8-3/200
20-1/81/210
411/2-200
401/4001
51
分析原计划生产产品的工艺结构发生变化。若原计划生产产品 Ⅰ 的工艺有了改进，这时有关它的技术系数向量变为,每件利润为 4元。试分析对原最优计划有什么影响？
1 2,5,2 TP
52
解解：把改进工艺结构的产品 Ⅰ 看作产品 Ⅰ ’，设 x1’
为其产量。于是计算在最终表中对应 x1’的列向量，并以 x1’代替 x1。
1
1
0 0,2 5 0 2 1,2 5
2 0,5 1 5 0,5
0,5 0,1 2 5 0 2 0,3 7 5
BP
同时计算出 x1’的检验数为
1
11 4 ( 2,0,3 ) ( 1,2 5,0,5,0,3 7 5 ) 0,3 7 5
T
Bc C B P
53
将以上计算结果填入最终表 x1的列向量位置。得
1.25 0 0 0.25 0 4
0.5 0 -2 0.5 1 4
0.375 1 0.5 0.125 0 2
0.375 0 -1.5 -0.125 0
x1’ x2 x3 x4 x5 b
x1
x5
x2
-Z
54
0-0.2-1.500
0.80-0.20.510
2.410.4-200
3.200.2001
x1’ x2 x3 x4 x5 b
x1’
x5
x2
-Z
原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品
Ⅰ ’3.2单位；生产产品 Ⅱ 0.8单位。可获利
15.2元。
55
若碰到原问题和对偶问题均为非可行解时，这就需要引进人工变量后重新求解。
56
例 3
假设上例的产品 Ⅰ ’的技术系数向量变为,而每件获利仍为 4元。试问该厂应如何安排最优生产方案？
1 ( 4,5,2) TP
57
解：以 x1’代替 x1,计算
1
1
0 0,2 5 0 4 1,2 5
2 0,5 1 5 3,5
0,5 0,1 2 5 0 2 1,3 7 5
BP
58
x1’的检验数为
111 4 ( 1,5,0,1 2 5,0 ) * ( 4,5,2 ) 2,6 2 5Bc C B P
将这些数字填入最终表的 x1列位置，得
0-0.125-1.50-2.625
200.1250.511.375
410.5-20-3.5
400.25001.25
x1’ x2 x3 x4 x5 b
x1
x5
x2
-Z
59
将 x1’替换变量中的 x1，得
00.4-1.500
-2.40-0.40.510
15.211.2-200
3.200.2001
x1’ x2 x3 x4 x5 b
x1’
x5
x2
-Z
可见原问题和对偶问题都是非可行解。
60
于是引入人工变量 x6。在 x2所在行，用方程表示时为
1 2 3 4 50 0,5 0,4 0 2,4x x x x x
引入人工变量 x6后，为
2 3 4 60,5 0,4 2,4x x x x
将 x6作为基变量代替 x2，得下表
61
00-0.8+
0.4M
-0.5M3-M0
2.4100.4-0.5-10
15.2011.2-200
3.2000.2001
x1’ x2 x3 x4 x5 x6 b
x1’
x5
x6
-Z
62
-M+200-110
62.501-1.25-2.50
8-310-0.530
20.5000.250.51
x1’ x2 x3 x4 x5 x6 b
x1’
x5
x4
-Z
63
-M+3-0.330-0.8300
12.66700.8311.66700
2.667-10.330-0.16710
0.6670-0.3300.3301
x1’ x2 x3 x4 x5 x6 b
x1’
x2
x4
-Z
最优生产方案为生产产品 Ⅰ ’0.667单位；生产产品
Ⅱ 2.667单位。可获利 10.67元 。
64
3.增加新的决策变量 xk
A增加一列
1
2
k
k
k
mk
a
a
P
a
65
例 4
分析在原计划中是否应该安排一种新产品。
以上例为例。设该厂除了生产产品 Ⅰ,
Ⅱ 外，现有一种新产品 Ⅲ 。已知生产产品 Ⅲ,每件需消耗原材料 A,B各为 6kg，
3kg，使用设备 2台时；每件可获利 5元。
问该厂是否应生产该产品和生产多少？
66
解解 （ 1）设生产产品 Ⅲ x3’台，其技术系数向量,然后计算最终表中对应的检验数 3 ( 2,6,3 ) TP
1
3 3 3
5 ( 1,5,0,1 2 5,0 ) ( 2,6,3 )
1,2 5 0
B
T
c C B P
说明安排生产产品 Ⅲ 是有利的。
67
（ 2）计算产品 Ⅲ 在最终表中对应 x3’的列向量
1
3
0 0.25 0 2 1.5
2 0.5 1 6 2
0.5 0.12 5 0 3 0.25
BP?
填入最终表，可得
68
1.250-0.125-1.500
20.250-0.1250.510
4210.5-200
41.500.25001
x1 x2 x3 x4 x5 x3’ b
x1
x5
x4
-Z
由于 b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，
说明目标函数值还可以改善。
69
（ 3）将 x3’作为换入变量,x5作为换出变量，进行迭代，求出最优解。
0-0.625-0.4375-0.2500
1.50-0.125-0.18750.7510
210.50.25-100
10-0.75-0.1251.501
x1 x2 x3 x4 x5 x3’ b
x1
x3’
x2
-Z
最优解 x1=1,x2=1.5,x3’=2。总的利润为 16.5
元。比原计划增加了 2.5元。
70
4.增加新的约束条件请同学们自学教材 P109。
71
五,参数规划系数中含有某个未知参数。
72
1、参数 c的变化分析试分析以下参数线性规划问题。当参数
t>=0时的最优解变化。 12
1
2
12
12
m a x ( ) ( 3 2 ) ( 5 )
4
2 1 2
..
3 2 1 8
,0
z t t x t x
x
x
st
xx
xx
73
解：将模型化为标准型
12
13
24
1 2 5
m a x ( ) ( 3 2 ) ( 5 )
4
2 12
..
3 2 18
0,1,2,,5
j
z t t x t x
xx
xx
st
x x x
xj
74
令 t=0，用单纯形法求解
x1 x2 x3 x4 x5 b
-1-3/2000
21/3-1/3001
601/2010
2-1/31/3100x3
x2
x1
-Z
75
x1 x2 x3 x4 x5 b
000
21/3-1/3001
601/2010
2-1/31/3100x3
x2
x1
-Z 3726t 21 3 t
考察 t 的变化对最优解的影响第一临界点,t=（ 3/2） /（ 7/6） =9/7，此时 δ 4=0。
0<=t<=9/7 时，最优解如上表（ 2,6,2,0,0） T。
将 c的变化直接反映到表中
76
当 t > 9/7时,δ 4 >0，以 x4为入基变量
4
3
6
x1 x2 x3 x4 x5 b
000
00101
1/20-3/210
-11300x4
x2
x1
-Z 9722t? 5122t
考察 t 的变化对最优解的影响第二临界点,t=（ 5/2） /（ 1/2） =5，此时 δ 5=0。
9/7 <=t<=5时，最优解如上表（ 4,3,0,6,0） T。
77
当 t > 5时,δ 5 >0，以 x5为入基变量
4
6
12
x1 x2 x3 x4 x5 b
000
00101
10-320
01020x4
x5
x1
-Z 32t5 t?
当 t>5时，恒有 δ 2< 0,δ 3<0,最优解如上表，为（ 4,0,0,12,6） T。
78
2、参数为 b的变化分析分析以下线性规划问题，当 t>=0时，其最优解的变化。
12
12
12
12
m a x 3
6
.,2 6
,
z x x
x x t
s t x x t
x x o
79
解：将上述模型化为标准型
12
1 2 3
1 2 4
1 2 3 4
m ax 3
6
.,2 6
,,,
z x x
x x x t
s t x x x t
x x x x o
80
令 t=0，用单纯形法求解
-2/3-5/300
41/31/310
2-1/32/301
x1 x2 x3 x4 b
x1
x2
-Z
81
将 b的变化直接反映到表中
-2/3-5/300
41/31/310
2-t-1/32/301
x1 x2 x3 x4 b
x1
x2
-Z
当 0≤ t≤ 2时，最优解为（ 2-t,4,0,0） T。
当 t> 2时，表中的解为非可行解，于是按照对偶单纯形法进行迭代。
82
t> 2迭代以后
0-30-2
6-t0111
-6+3t1-20-3
x1 x2 x3 x4 b
x4
x2
-Z
当 2<=t<=6时，问题的最优解为
（ 0,6-t,0,-6+3t） T。
当 t> 6时，问题无可行解。
