运筹学课件 灵敏度分析及参数规划共27页

2013-4-7 灵敏度分析与参数规划 5-7
灵敏度分析的任务
线性规划的灵敏度分析要解决两个问题：
一个或几个系数或要素变化后，当前的
最优解或最优基是否有变。
这些系数在什么范围内变动时，当前的
最优解或最优基不变。 另外，一旦当前解受影响就要运用适当 方法对其进行调整，以便得到新的最优解。
2013-4-7 灵敏度分析与参数规划 5-8
分析结果的处理方法
针对上述五种不同的分析结果，可按下列相 应的调整方法进行处理。 分析结果 处理方法
最优解不变
最优基不变 变为可行解 变为正则解 变为普通解
2013-4-7 灵敏度分析与参数规划
计算 CN - CBB-1N
计算 XB(*) = B-1b 原始解法求最优解 对偶解法求最优解 混合解法求最优解
2013-4-7 灵敏度分析与参数规划 5-3
生产计划问题
cj CB XB
0 0 0 -1 0 0 3 -1 2 0 3 -1 2 0 3 -1
b
2 3 x1 x2
0 x3
0 x4
0 x5
0 0 1 0 -1/2 0 1/4 -3/4 -1/2 [2] 1/4 1/4 0 1 0 0
θ
x3 8 x4 16 x5 12 z 0 x3 2 x4 16 x2 3 z -9 x1 2 x4 8 x2 3 z -13 x1 4 x5 4 x2 2 z -14
5-14
2013-4-7
灵敏度分析与参数规划
2. 基变量系数 cr 的变化分析
当基变量 xr 的系数 cr (CB)变化 cr 时，就会引起 CB 的变化，从而影响到各非基变量 xj 对应的j 。 设 CB=( 0, …, cr , …,0 )，若要求原最优解不变，则 新的检验数必须满足 j' = cj - (CB +CB )B-1Pj = cj - CBB-1Pj - CB B-1Pj =j - [(0, …,cr , …,0)(b1j, …, brj, …, bmj)T] =j - cr brj ≤0 于是得到 cr ≤j／brj , brj < 0 j=1 , 2 , …, n cr ≥j／brj , brj > 0 cr的变化范围为是 max { j /brj | brj > 0 }≤ cr ≤ min { j /brj | brj < 0 }

❖ 原问题最优解不变，若反之
j
0
❖ 则以 B1Pj 替代原最优表的第j列，用单纯 形法继续求解至最优解。
❖ （4）改变某基变量系数列向量的分析
❖ 设 x j 基变量的系数列向量变为
Pj
，试分
析原最优解的变化。
❖
Pj
的变化将导致B的变化，因而原最优表
❖ 所有元素都将发生变化，似乎只能重新计算
❖ 但是经过认真分析，还是可以利用原最优解 来计算新的最优解。
-2/5 1/5
-2 X1 11/5 1
σj
0
0 7/5
-1/5 -2/5
0 -9/5+Δc3 -8/5 -1/5
只要-9/5+Δc3 ≤0 ，即Δc3 ≤9/5 则原最优解不变
表中σ3= c3+Δc3-(c2×a13+c1×a23 ) = -9/5+Δc3
❖ 2)设基变量 XB 的价值系数 CB 有增量 CBr ，
备注
CB X B B 1b x1 x2 x3 x4
4 x2 70 0 1 1/2 -1/4
K=1
6 x1 -5 1 0 -1/4 3/8
L=2
j 4 x2 60 0 x3 20
j
0 0 -1 /2 -5/4
2 1 0 1/ 2 4 0 1 3/2
2 0 0 2
新的最优 解为：
x2
x3
6 2
00,
例4
例2增加3x1+ 2x2≤15，原最优解不 满足这个约束。于是
Ci
2
3
000
0
CB XB b
X1
X2
X3 X4 X5
X6
2 X1 4

在目前计算机普及率很高的情况下，通常的方法是程序 中修改A后重新计算成即可。
例2.1 在例1.1中新增一种产品:防盗门
例2.2 在例1.1中新增一个约束：电力限制
作业:P50—52,1,3,5
运筹学 小结： 一般信息的变化： 价值向量—市场变化 右端向量—资源变化 系数矩阵—技术进步
线性规划
C的变化只影响检验数（对偶问题的解），不影响原问题 的基本解；
格，所以它们所需要的主要原料（木材和玻璃）、制作时间、最大销售量与利润均 不相同。该厂每天可提供的木材、玻璃和工人劳动时间分别为600单位、1000单位 与400小时，详细的数据资料见下表。问： （1）应如何安排这四种家具的日产量，使得该厂的日利润最大？ （2）家具厂是否愿意出10元的加班费，让某工人加班1小时？ （3）如果可提供的工人劳动时间变为398小时，该厂的日利润有何变化？ （4）该厂应优先考虑购买何种资源？ （5）若因市场变化，第一种家具的单位利润从60元下降到55元，问该厂的生产计 划及日利润将如何变化？
表1 雅致家具厂基本数据
家具类型 1
劳动时间 （小时/件）
2
木 材（单 位/件）
4
玻 璃（ 单位/件）
6
单位产品利 润（元/件）
60
最大销售量 （件）
100
2
1
2
2
20
200
3
3
1
1ห้องสมุดไป่ตู้
40
50
4
2
2
2
30
100
可提供量
400小时
600单位
1000单位
解：依题意，设置四种家具的日产量分别为决策变量 x1,x2,x3,x4,目标要求是日利润最大化，约束条件为三 种资源的供应量限制和产品销售量限制。

0
0
1
0
0
0
x3
1 0
0 1 1
0 2 -1
-1
0
x4
0 1
0
0
-3/2 -1 1
-1
2.5.1 单纯形法的矩阵描述
1. 约束方程系数矩阵的变化
约束方程系数矩阵
，进行初等行
变换，相当于左乘一个相应的初等阵。
即
，在A中所包含的矩阵B，左
乘 后，则得到
。
2. 约束方程右端项的变化
3. 目标函数系数的变化
1. 灵敏度分析的概念：
当某一个参数发生变化后，引起最优解如何改变的 分析。 可以改变的参数有： bi——约束右端项的变化，通常称资源的改变； cj ——目标函数系数的变化，通常称市场条件的变 化； pj ——约束条件系数的变化，通常称工艺系数的变 化； 其他的变化有：增加一种新产品、增加一道新的工 序等。
2．分析原理及步骤：
（1）借助最终单纯形表将变化后的结果按下述基
本原则反映到最终表里去。
B①-1bi△变b化：=
（b+△b）´=B-1 b´+B-1 △b
（b+△b）=
B-1
b+
②pj变化：（pj+△ pj ）´= B-1 （pj+△ pj ）= B-1 pj+ B-1 △ pj = pj ´+ B-1 △ pj
围来确定最优解是否改变。 由于系数的改变，最优值z可能发生 变化而不再是原值了。
2、约束条件右端值的变化
约束条件右端值每增加一个单位 引起的最优值的改进量称为对偶 价格。
对偶价格只适用于在右端值仅发 生了很小变动的情况
2.5.3 单纯形法灵敏度分析

第六章 单纯形法的灵敏度 分析与对偶
管 理
运 筹
学
1
§1 单纯形表的灵敏度分析 §2 线性规划的对偶问题 §3 对偶规划的基本性质 §4 对偶单纯形法
管 理
运 筹
学
2
第一节 单纯形表的灵敏度分析
管 理
运 筹
学
3
一,目标函数中变量Ck系数灵敏度分析 目标函数中变量C
1.在最终的单纯形表里, 1.在最终的单纯形表里,Xk是非基变量 在最终的单纯形表里 由于约束方程系数增广矩阵在迭代中只是其 没有任何关系, 本身的行的初等变换与ck 没有任何关系,所以当 ck 变成 ck + ck 时,在最终单纯形表中其系数的增 广矩阵不变,又因为X 是非基变量, 广矩阵不变,又因为Xk是非基变量,所以基变量的 目标函数的系数不变, 目标函数的系数不变,即CB不变,可知Zk也不变, 不变,可知Z 也不变,
管 理 运 筹 学
20X2 100 0 0 1 100 0
S1 0 1 -2 0 50 -50
S2 0 0 1 0 0 0
S3 0 -1 1 1 50 27500 -50
CB
50 0
50 1 0
b
50 50 250
2
X2
100 0 ZJ 50 0
CJ -ZJ
管 理
学
5
2. 在最终的单纯形表中, k 是基变量 在最终的单纯形表中, x 当 ck 变成 ck + ck 时,最终单纯形表中约束
方程的增广矩阵不变,但是基变量的目标函数的系 方程的增广矩阵不变, 数 cB 变了,则 变了, 妨设
cB = (cB1 , cB 2 , L , ck , L cBm ), 当 cB 变成 cB = (cB1 , cB 2 ,L , ck +Vck , L cBm ), 则:

运筹学教程
Cj
210
CB 基 b X1 x2 x3
0 x3 15 0
51
2 x1 5 1
10
0 x4 2 0
-4 0
Cj-Zj
0
-1 0
00 x4 x5 00 01 1 -6 0 -2
工厂的最优生产计划改为只生产产品1，每天 的生产数量5件。
解：（2）
设每天的调试可用能力为5
运筹学教程
1 b' B1b 0
x5
x4
5
24
x1, x2 , x3, x4 , x5 0
用单纯形法求解如下：
运筹学教程
Cj
210 0 0
CB 基 b X1 x2 x3 x4
x5
0 x3 15/2 0 2 x1 7/2 1 1 x2 3/2 0
01 00 10
5/4 -15/2 ¼ -1/2 -1/4 3/2
Cj-Zj
0
8
2
3 / 2 0 2
运筹学教程
将其反映到最终的单纯形表，原问题非可行解， 采用dual单纯形法
Cj
2
CB 基 b X1
0 x3 35/2 0
2 x1 11/2 1
1 x2 -1/2 0
Cj-Zj
0
10 x2 x3 01 00 10 00
00 x4 x5 5/4 -15/2 ¼ -1/2 [-1/4] 3/2 -1/4 -1/2
aij
y i
i 1
运筹学教程
（2）、检查原问题是否仍为可行解。 （3）、检查对偶问题是否仍为可行解。
原问题
可行解 可行解 非可行解 非可行解
对偶问题
可行解 非可行解 可行解 非可行解

a11 的变化范围。
由于 y 1.5 0 0 0 1 0 1 B 0 .5 0 0 1.25 1 0
当 a11 从3变为 3 a11 时，x1 的检验数变为
c1 z c1 y1
' 1 ' 1
y2
4 1.5
增加新产品相当于增加一个决策 变量，系数矩阵也将增加一列
设研制出一种新产品—小旅行车，每辆旅
行车用钢材1.5吨，工时1.25小时，座椅 0.25套，利润3千元，试问该新产品是否该 投产？（给出数学模型，再讨论） 1 .5 1.25 p 第一种解法：设该车产量为 x6 ，则 6
4
3
0
0
0
0
xB B 1b x1 x5 200 0 x2 600 0 x1 200 1 x7 -200 0
2600
x2 x3 x4 x5
0 1 0 0 0.5 1 -0.5 -0.5 -0.4 -0.4 0.4 0 1 0 0 0
x7
0 0 0 1
j
0
0
-1
2
-0.4
0
0
cj
CB
0 3 பைடு நூலகம் 0
4
3
0
0
0
0
xB B 1b x1 0 x5 0 x2 200 0 x1 400 1 x3 400 0
2200
x2 x3 x4 x5
0 1 0 0 0 0 0 1 -0.4 -0.4 0.4 0 1 0 0 0
x7
1 2 -1 -2
j
0
0
0
-0.4
0
-2
增加约束后，最优目标函数值不会更好，一般 会差一些。

0 a1r br
a1r
B 1
br
air br
br
air
0 amr br
amr
B-1的第r列
进一步得，最终表中 b 列元素
B-1b
bi + a ir br 0,
air br bi
i=1，2，…，m i=1，2，…，m
air > 0
br bi / air ; air < 0
0 4 0.25 0
B1b
+
B1
b2
4
+
0.5
b2 0
0 2 0.125 0
可得 △b2≥-4/0.25=-16, △b2≥-4/0.5=-8, △b2≤2/0.125=16 由公式知△b2变化范围[-8,16], 显然b2变化范围[8,32]
例题: 将上面例题进行实际应用。每台设备台时的影子价格为1.5元。若该 厂又从别处抽出4台时用于生产两种产品，求这时该厂生产两种产品的最优方 案。
生产规模条件下单位产品利润或单价的可变范围。 2、代表单位原料单价时，灵敏度分析用于预先确定保持现有配方条件下，原
料单价的可变动范围。
第10页/共11页
感谢您的观看！
第11页/共11页
解：这时最终计算表为
第7页/共11页
cj
2 3 + △c2 0
0
0
CB XB b x1
x2
x3
x4
x5
2 x1 4 1 0
0 0.25 0
0 x5 4 0 0
-2 0.5
1
3 x2 2 0 1 0.5 –0.125 0
cj-zj
0 △c2 -1.5 -0.125 0

00 x4 x5 5/4 -15/2 ¼ -1/2 [-1/4] 3/2 -1/4 -1/2
第15页/共35页
Cj
210
CB 基 b X1 x2 x3
0 x3 15 0
51
2 x1 5 1
10
0 x4 2 0
-4 0
Cj-Zj
0
-1 0
工厂的最优生产计划改为只生产产品1，每天 的生产 数量5件。
00 x4 x5 00 01 1 -6 0 -2
15 / 20 10
1/ 2
8
2
3 / 2 0 2
第14页/共35页
将其反映 到最终 的单纯 形表， 原问题 非可行 解，采 用dual 单纯形 法
Cj
2
CB 基 b X1
0 x3 35/2 0
2 x1 11/2 1
1 x2 -1/2 0
Cj-Zj
0
10 x2 x3 01 00 10 00
Cj CB 基 b 0 x3 15/2 2 x1 7/2
1+ x2 3/2
Cj-Zj
2 1 + 0 0
0
X1 x2 x3 0 01
x4 5/4
x5 -15/2
1 00 ¼
-1/2
0 1 0 -1/4 3/2
0
0 0 -1/4+ /4 -1/2-3 /2
第11页/共35页
1 0, 1 3 0
第13页/共35页
仍然来看例1-1：
（1）如果设备A和调试工序的每天的能力不变，设备B 每天的能力增加到32h，分析公司最优的生产计划的变 化；
（2）如果设备A和设备B每天的能力不变，则调试工序 在什么范围内变化，问题的最优基不变。

第2章 线性规划 灵敏度分析
关于运筹学第二章 线性规划灵敏度分析
东北财经大学工商管理学院
第1页，此课件共33页哦
2.1 线性规划灵敏度分析
第2章 线性规划 灵敏度分析
▪ 在第1章的讨论中，假定以下的线性规划
模型中的各个系数cj、bi、aij是确定的常
数，并根据这些数据，求得最优解。
n
Max(Min) z c j x j j 1
▪ 使用电子表格进行分析(重新运行规划求解)
东北财经大学工商管理学院
规划求解后，最优 解发生了改变，变 成了（2/3，8）， 总利润也由3600元 增加到了4200元。 可见，车间2更新生 产工艺后，为工厂 增加了利润。
第23页，此课件共33页哦
2.7 增加一个新变量
第2章 线性规划 灵敏度分析
▪ 例2.1 如果工厂考虑增加一种新产品：防盗门，其单位利润为400元。 生产一个防盗门会占用车间1、车间2、车间3各2、1、1工时,总利
第2章 线性规划 灵敏度分析
▪ 方法1：使用电子表格进行分析（重新运 行规划求解）
总利润为3750元，
增加了：3750-
3600=150元。由于
总利润增加了，而目标 函数系数不变，所以最 优解一定会发生改变， 从图中可以看出，最优 解由原来的（2，6）
变为（1.667，6.5）
东北财经大学工商管理学院
电最多为90kw),最优解是否会发生变化? ▪ 使用电子表格进行分析(重新运行规划求解)
东北财经大学工商管理学院
可见电力约束 的确限制了新 产品门和窗的 产量，最优解 变成(1.5,6),总 利润也相应的 下降为3450元 。
第25页，此课件共33页哦
2.9 影子价格