运筹学第三章灵敏度分析

发布时间：2024-11-25

运筹学课件

六、灵敏度分析

灵敏度分析：研究线性规划模型结构中元素变化对问题最优解的影响。解决的问题： (1)当参数中的某个发生变化时，目前的最优基是否仍最优？(即目前的最优生产方案是否要变化) (2)为保持目前最优基仍是最优基，参数允许变化范围是什么？(即最优解的相对参数变化的稳定性) (称为模型参数的灵敏度分析) (3)增加一个变量或增加一个约束条件时，目前的最优基是否仍最优？(称为模型结构的灵敏度分析)1

运筹学课件

灵敏度分析的方法是在以求得最优基B*下进行的。 c1 c2 … cn

x1CB* XB*

…B*--1 A

B*--1 b

σj

C— CBB*--1 A

考察当参数A、b、c中的某一个或几个发生变化时，是否影响以下两式的成立？

C CB B * 1 A 0 B * 1 b 0 2

运筹学课件

1、对价值系数cj变化的分析(1) cj是非基变量xj的价值系数当CN中某个cj发生变化时，只影响到非基变量xj的检验数由于 C C B * 1 P (C C ) (C B * 1 P ) j j B j j j B j

(C j C B B * 1 Pj ) C j j C j 0 所以,当 j 0 即当 C j j时,最优解不变反之,当 j 0 时,最优解改变,需要用单纯形法重新进行迭代,以求得新的最优解.3

运筹学课件

例1、(课本例3-9) 已知LP问题

Minw 2 x1 3x 2 x3 0 x 4 0 x5 3 x1 x 2 x3 x 4 s.t. x1 4 x 2 7 x3 x5 9 x ,x ,x ,x ,x 0 1 2 3 4 5单纯形求解可得如下表所示的最终单纯形表，问： (1)C3在什么范围内变化时，最优解保持不变； (2)C3由“-1”减少至“-6”,求新的最优解。

运筹学课件

解：(1)由于在最终单纯形表中 x3 是非基变量，因此c3 的变化只会影响 x3 自身的检验数 3,而与其他变量的检验数无关。cj CB XB -2 x1 -3 x2 -1 x3 0 x4 0 x5

b1 28

-2 -3

x1 x2

1 00

0 10

-1 23

4/3 -1/35/3

-1/3 1/31/3

σj

c3 3 3

c3 c3 c3 1 ( 3) 45

运筹学课件

(2)将 c3 6 直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解。cj CB XB -2 x1 -3 x2 -1 x3 0 x4 0 x5

b1 28 2 1 10

-2 -3

x1 x2

1 00

0 10 1/2 1/2 1

-1 23 0 1 0

4/3 -1/35/3 7/6 -1/6 4/3

-1/3 1/31/3 -1/6 1/6 2/3

σj-2 -6 x1 x3

1 0 0

σj

新的最优解： * (2,1 0,,最优值： * X 0, 0) T , w

106

运筹学课件

例2、对于下列线性规划模型,为使最优解不变，讨论非基变量x3的目标函数系数c3的变化范围。max Z 4 x1 3 x2 2 x3 2 x1 3 x2 x3 24 s.t. 3 x1 2 x2 2 x3 26 x1 , x2 , x3 0 (材料约束) (工时约束)

用单纯形法求得其最优表为：cj CB XB b 4 x1 3 x2 2 x3 0 x4 0 x5

3 4Z

x2 x1

4 636

0 10

1 00

-1/5 4/5-3/5

3/5 -2/5-1/5

-2/5 3/5-6/57

运筹学课件

解：因为x3为非基变量，其目标函数系数c3的变化只会影响到x3的检验数，因此为使最优解不变，只需 3 0

3 7 c3 c3 c3 2 5 5 2 若C3=3,则代入最优单纯形表中相应位置，可得 3 5cj CB 3 4 XB x2 x1 b 4 6 4 x1 0 1 3 x2 1 0 3 y1 -1/5 4/5 0 x3 3/5 -2/5 0 x4 -2/5 3/5

3 c3 3 5

2/5

-1/5

-6/5

继续迭代以求出新的最优解。8

运筹学课件

(2)cr是基变量xr的价值系数当CB(即基变量的目标函数系数)中某个Cr发生变化时则会影响到所有非基变量的检验数

N C N CB B 1 N

j c j (CB CB ) B 1Pj c j [CB (0, , cr, ,)]B 1Pj 0

j (0, , cr , ,) B 1Pj 0 j arj cr 0可得到使最优解不变 cr 的允许变化范围：

Max{j

a rj

a rj 0} c r min {j

a rj

a rj 0}

运筹学课件

例3、(课本例3-10)对于例9中的线性规划问题，问： (1)在什么范围内变化时，最优解保持不变； (2)由“-2”减少至“-6”,求新的最优解。解：(1)由最终单纯形表可知，为保持原最优解不变应有： 3 5 4 Max{ , } cr min { } a13 a15 a141 5 3 Max{ ,3 } c1 Min{ 3 } 1 4 1 3 3

5 1 c1 4

3 3 c1 c1 4

3 c1 [ 3, ] 410

运筹学课件

(2)将 c1 6 直接反映进最终单纯形表，用单纯形法继续迭代即可得到新的最优解。cj CB XB -6 x1 -3 x2 -1 x3 0 x4 0 x5

b1 212 2 1 13 3 6 1811

-6 -3

x1 x2

1 00

0 10 1/2 1/2 1/2 1 3 3

-1 2-1 0 1 0 1 6 5

4/3 -1/37 7/6 -1/6 41/6 1 -1 6

-1/3 1/3-1 -1/6 1/6 -5/6 0 1 0

σj-6 -1 x1 x3

1 0 0

σj-6 0 x1 x5

1 0 0

σj

运筹学课件

矩阵形式的单纯形表为

b XB B-1b≥0对原问题可行 Z C BB-1b优化后分析按如下方式进行

X B-1A C BB-1A-C≥0对对偶问题可行

原问题可行解

对偶问题可行解

结论或继续计算的步骤问题的最优解或最优基不变

可行解非可行解非可行解

非可行解可行解非可行解

用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解

引进人工变量,编制新的单纯形表重新计算12

运筹学课件

2、资源数量bk的灵敏度分析从矩阵形式的单纯形表中可以看出，bk的变化只影响最优解的变化和最优值的变化。

XB Z 1

b B*-1b C BB*-1b

X B*-1A C-C BB*-1A

因此，当 B* b 0 时，最优基不变(即生产产品的品种不变，但数量及最优值会变化)。若B*-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。13

运筹学课件

记原最优基

B * 1 ij m ,则 m

b B * 1 b (b1, ,bm )

0 b1 1k 1 1 b )

b 0 B * (b b) B * (b k k bm mk , 0

bi ik bk 0 由此可知使最优基 B *保持不变时 bk的允许变化范围：Max{j

ik 0} bk Min{j

ik 0}14

运筹学课件

例1、 (课本例3-11) 已知LP问题

Minw 5 x1 12 x2 4 x3 0 x4 Mx5 5 x1 2 x2 x3 x4 x5 2 s.t. 2 x1 x2 3x3 x ,x ,x ,x ,x 0 1 2 3 4 5单纯形求解可得如下表所示的最终单纯形表，问 (1)b2 在什么范围内变化时，最优解(在此实际上是最优基)保持不变； (2)b2 由2增加至15,求新的最优解。

运筹学课件

cj CB XB

-5 x1

-12 x2

-4 x3

0 x4

M b x5

-12-5

x2x1

01 0

10 0

-1/57/5 -3/5