当前位置：文档之家 › 运筹学-3灵敏度分析

运筹学-3灵敏度分析

  • 格式：ppt
  • 大小：94.00 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

灵敏度分析(运筹学)

灵敏度分析(运筹学)

最优基不变，即在最终表中求得的经过变化后 的b列的所有元素要求不小于0
目标函数 m ax z 2 x1 3x2 x1 2 x2 8 4x 16 1 约束条件 : 4 x2 12 x1 , x2 0
0 x3 1 -2 1/2 -3/2 0 x4 1/4 1/2 -1/8 -1/8 0 x5 0 1 0 0 θ

（5）按照下表所列情况得出结论或继续计算的步 骤。
原问题 可行解 可行解 非可行解 非可行解 对偶问题 可行解 非可行解 可行解 非可行解 结论或继续计算的步骤 原最优基不变 用单纯形法继续迭代 用对偶单纯形法继续迭 代 引入人工变量 ，扩大原 单纯形表继续计算


资源数量变化是指资源中某系数 br 发生变化，即 br′=br+Δ br。并假设规划问题的其他系数都不变。 这样使最终表中原问题的解相应地变化为 XB′=B-1(b+Δ b) 这里 Δ b=(0,… ， Δ br,0,… ， 0)T 。只要 XB′≥0 ， 因最终表中检验数不变，故最优基不变，但最优 解的值发生了变化，所以 XB′ 为新的最优解。新 的最优解的值可允许变化范围用以下方法确定。
(d) (e) -2
· · ·
1 0 0
0 1 0
cj - zj
XB x1 x5 cj - zj
b (f) 4
x1
x2
x3
x4
x5
(g) (h) 0
2 (i) 7
-1 1 (j)
1/2 1/2 (k)
0 1 (l)
--7--
--第2章 对偶问题--
以前讨论线性规划问题时，假定αij，bi,cj都是常数。 但实际上这些系数往往是估计值和预测值。如市场 条件一变，cj值就会变化；αij往往是因工艺条件的 改变而改变；bi是根据资源投入后的经济效果决定 的一种决策选择。显然，当线性规划问题中某一个 或几个系数发生变化后，原来已得结果一般会发生 变化。 因此，所谓灵敏度分析，是指当线性规划问题中的 参数发生变化后，引起最优解如何改变的分析。

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第3章 对偶理论与灵敏度分析

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第3章 对偶理论与灵敏度分析

⎟ ⎟ ⎟⎟⎠
⎪⎩x1, x2 ,", xn ≥ 0
min z = b1y1 + b2y2 +" + bm ym
（3-5）
⎪⎧⎜⎛ s.t.⎪⎪⎪⎪⎨⎜⎜⎜⎜⎝
a11 a12 #
a1n
a21 a22 #
a2n
" "
"
am1 ⎟⎞⎜⎛ y1 ⎟⎞ ⎜⎛ c1 ⎟⎞
am2 #
amn
⎟⎜ y ⎟⎟⎟⎠⎜⎜⎜⎝#y
+ −
y3* =3 y3* = 4
把 X * 代入原问题 3 个约束中可知原问题式（3）是不等式，故 y 3 * =0，然后解方程组
得到
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3y2* =3 2 y2* = 4
⎧⎪ ⎨ ⎪⎩
y1* =6/5 y2* = 1/ 5
故对偶最优解为 Y * =(6/5,1/5,0), z * =w * =28.
⎪⎪⎪⎨22yy11++3yy22
− +
y3 y3
≥2 ≥3
⎪⎪3y1 + 2 y2 − y3 ≥ 4
⎪⎩y1, y2 , y3 ≥ 0
由于 x 3 * =x 4 * =4>0，故对偶问题约束方程式（3）、（4）是等式约束，即对 Y * 成立等式
⎧⎪ ⎨ ⎪⎩
2y1* 3y1*
+ +
3 y2* 2 y2*
推论 3 若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。
定理 3.2 最优性准则定理
若 X 和 Y 分别为互为对偶问题的线性规划（3-5）与（3-6）的可行解，且使 CX = bT Y T ，

运筹学灵敏度分析

运筹学灵敏度分析

只需由 j 0解得c j的范围。
(2) c j 是基变量x j的价格系数 这时要影响所有的检验 数
i ci (c1 ci ci cm ) B Pi , 应由所有的 i 0解得公共的c j。
1
p11-2
例1：在（煤电油例）中，其单纯形终表如下：
0 x 7 x 12 x
3 1
运筹学
2

84 20 24
0 1 0
0
0 0 1
0
1 0 0
0
- 0.32 0.4 - 0.12
- 1.36
1.16 - 0.2 0.16
- 0.52
z 428
（1）甲产品的价格在何范围内变化时，现最优解不变？
解：甲产品的价格c1是基变量的价格系数。 0.32 由 4 0 0 7 c1 12 0.4 2.8 0.4c1 1.44 0 0.12 得 c 3.4， 1.16 由 5 0 0 7 c1 12 - 0.2 1.4 0.2c1 1.92 0 0.16 得 c 2.6，
2
运筹学
例1：在（煤电油例）中，其单纯形终表如下：
0 x 7 x 12 x
3
1
2

84 20 24
0 1
0
0 0 1
1 0
0
- 3.12 1.16 0.4 - 0.2
- 0.12 0.16
z 428
0
0
0
- 1.36
- 0.52
（3）若有人愿以每度1元的价格向该厂供应25度电，是 否值得接受？
§3.4 灵敏度分析
灵敏度分析——研究系数变化对最优解的影响.

运筹学线性规划灵敏度分析教学案例

运筹学线性规划灵敏度分析教学案例
2020/8/1
多个资源系数同时变动分析
例如，将 1 个小时的用工时间从3车间移到2车间，对总利润 产生什么影响？
总利润增加 3650 - 3600 = 50 元， 而目标系数未变，所以最优解肯定 发生变化，
2020/8/1
百分之百法则
如果约束右端值同时变动，计算出每一变动占允许变动量的 的百分比，如果所有的百分比之和不超过100%，那么，影子 价格依然有效；否则，就无法确定。
2020/8/1
灵敏度分析的概念
LP 问题的系数有 aij、bi 、 cj，这些系数往往是估计值 或预测值。
市场条件变化， cj 值就会变化；工艺条件和技术水平改 变， aij 就变化； bi 是根据资源投入后的经济效果决定的一种 选择，市场供应条件发生变化时，亦会改变。
提出问题:
• 当 LP 问题的系数有一个或几个发生变化时，已求得的最优 解会有什么变化； • 这些系数在什么范围内变化时，LP 问题的最优解不会变化。
再改变参数
最优解变了
2020/8/1
那么，保持最优解不变的价值系数允许 变化范围？
改变最优解的临界值是什么呢？
敏感性报告
在“规划求解结果”中 选定“敏感性报告”。 得到一个工作表：
2020/8/1
敏感性报告
最优解
目标函数系数
“递减成本” --- 表示目标函数的系数必须改变多少，才能使 决策变量有正数解。 “允许的增量”和“允许的减量” --- 给出最优解不变的范围。 如门的系数范围： 0≤c1≤750；窗的系数范围：c2≥200
2020/8/1
资源数量变化的分析
考虑只有一个右段值 bi 改变：2 车间可用工时由原来的 12小 时增加到 13 小时，最优解如何变化呢？再变化呢？

运筹学单纯形法的灵敏度分析

运筹学单纯形法的灵敏度分析
的产量就大于零，即需考虑生产丙产品了。
• 所以，丙产品单位利润的变动范围是c3<4；
• 讨论： • 假设此时c3增加到6元，产量应为多少？
C3已超出变动范围
• 代入单纯形表 最后一段 继续计算。
段
Cj ↓
→ 基
0 b
23 x1 x2
6 x3
0 0 Qi x4 x5
2
x1
1
1
0 （-1） 4 -1
0
0
-1 4 -1
1
2 -1 1
0
-3 -5 -1
Bi变化影响哪些因素？
• 当bi变化时，从单纯形法计算过程可知，它不影响检验数， 只影响b列本身，也就是说，它不影响基变量但会改变最优 解的具体数值，如上例中，假设b1发生变化，劳动力使用从 一个劳动力增加到2个劳动力，即b1=2，则
• ∵b变化不影响检验数 • ∴单纯形表最后一段基变量结构不变，仍是x1，x2，改变的
x5
Qi
0
x4
1
1
0
x5
3
Cj-Zj →
1/3
1/3 1/3 1
1/3 （4/3） 7/3 0
2
3
10
0
3
1 9/4 →
0
0
x4 1/4 （1/4）
0
-1/4 1 -1/4 1
→
2
3
x2 9/4 1/4
1 7/4 0 3/4 9
Cj-Zj →
5/4
0 -17/4 0 -9/4
2
x1
1
1
3
3
x2
2
0
Cj-Zj → -8
5b1 3
分析

运筹学第11讲灵敏度分析

运筹学第11讲灵敏度分析

第二章 线性规划的对偶理论
Duality Theory 对偶问题的经济解释——影子价格 线性规划的对偶问题 对偶单纯形法 灵敏度分析 对偶问题的基本性质
1、什么是灵敏度分析？ 是指研究线性规划模型的某些参数(bi, cj, aij）或限制量（xj, 约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。
设备A(h)
设备B(h)
调试工序(h)
利润(百元)
Ⅰ
Ⅱ
每天可用能力
资源
产品
0
5
6
2
1
1
2
1
15
24
5
例2-1
如何安排生产计划才能使总利润最多？
解：
(1) 设x1, x2分别表示Ⅰ、Ⅱ两种产品的生产数量，得LP模型
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
用单纯形法求解得最终单纯形表
得最优解为：
X*=(7/2, 3/2, 15/2, 0, 0)T
zmax=8.5(百元)。
即每天生产3.5单位产品Ⅰ，1.5单位产品Ⅱ时总利润最多，且
max z = 2x1+x2 s.t. 5x2 ≤15 6x1+2x2 ≤24 x1+ x2 ≤5 x1, x2 ≥0
5. 分析系数 aij 的变化
系数矩阵A
s.t.
对偶问题决策变量的最优解<影子价格>：
初始单纯形表
最优单纯形表
X*=B-1b
CN－CBB-1N ≤0
－CBB-1 ≤0
原问题基变量的最优解：

运筹学：第1章 线性规划 第3节 对偶问题与灵敏度分析


s.t.
4x1 3x1
5x2 200 10x2 300
x1, x2 0
9x1 4x2 360
s.t.
34xx11
5x2 10 x
200 2 300
3x1 10x2 300
x1, x2 0
则D为
min z 360y1 200y2 300y3 300y4
9 y1 4 y2 3y3 3y4 7 s.t.4 y1 5y2 10 y3 10 y4 12
amn xn bm ym xn 0
机会成本 a1 j y1 a2 j y2 aij yi amj ym
表示减少一件产品所节省的可以增加的利润
（3）对偶松弛变量的经济解释——产品的差额成本
机会成本
利润
min w b1 y1 b2 y2 bm ym
a11 y1
st
a12
y1
a1n y1
max z CX
（P）
AX b
s
.t
.
X
0
（D）
min w Yb
s.t.
YA C Y 0
• （2）然后按照（D）、（P）式写出其对偶
例：写出下面线性规划的对偶规划模型：
max z 2x1 3x2
min w 3 y1 5y2 1y3
x1 2x2 3 y1 0
s.t.
2xx11
例如，在前面的练习中已知
max z 2.5x1 x2 的终表为
3x1 5x2 15 s.t.5x1 2x2 10
x1, x2 0
0 x3 9 2.5 x1 2
0 19 1 - 3
5
5
1
2
0
1
5

《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案《运筹学》期末考试试卷习题库答案第三章线性规划对偶理论与灵敏度分析习题一、思考题1．对偶问题和对偶变量的经济意义是什么？2．简述对偶单纯形法的计算步骤。

它与单纯形法的异同之处是什么？3．什么是资源的影子价格？它和相应的市场价格之间有什么区别？4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）xn k 0，其经济意义是什么？7．在线性规划的最优单纯形表中，松弛变量xn k的检验数求最小值），其经济意义是什么？n k0（标准形为ji的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解 8．将ij将会出现什么变化？有多少种不同情况？如何去处理？二、判断下列说法是否正确1．任何线性规划问题都存在且有唯一的对偶问题。

2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

a,c,b6．已知在线性规划的对偶问题的最优解中，对偶变量yi 0，说明在最优生产计划中，第i种资源已经完全用尽。

7．已知在线性规划的对偶问题的最优解中，对偶变量yi 0，说明在最优生产计划中，第i种资源一定还有剩余。

ji来说，每一个都有有限的变化范围，当其改变超出了这个范围 8．对于ij 之后，线性规划的最优解就会发生变化。

a,c,b9．若某种资源的影子价格为，则在其它资源数量不变的情况下，该资源增加k 个单位，相应的目标函数值增加 k。

10．应用对偶单纯形法计算时，若单纯形表中某一基变量xi 0，且xi所在行的所有元素都大于或等于零，则其对偶问题具有无界解。

运筹学讲义-灵敏度分析


(I A)1Δ Y Δ X

ΔY 0
5
2.4.2 价值系数 cj 的灵敏度分析 • cj 变动可能由于市场价格的波动，或生产成本的变动
• cj 的灵敏度分析是在保证最优解的基变量不变的情况 下，分析cj 允许的变动范围cj
• cj 的变化会引起检验数的变化，有两种情况
– 非基变量对应的价值系数变化，不影响其它检验数 – 基变量对应的价值系数变化，影响所有非基变量检验数
bi

bk ak ,ni
bi

bk ak ,ni
要求对所有 k 都成立 , 从而有
max k

ak
bk
,n
i
ak ,ni
0

bi

min k

bk ak ,ni
ak ,n i
0

此时 , 基变量的解值和目标函 数会发生变化
2.4.6 新增约束条件的分析
16
2.4.7 灵敏度分析举例
例2.4.3 某工厂生产三种产品 A, B, C，有五种生产组合方案。
下两表给出有关数据。规定每天供应 A产品至少110 个，求收 益最大的生产方案。
产量 组别
品种
I II III IV V
单位售价 (元 )
A 产品数量
32440
10
B 产品数量
x5 x6 x7 00 0 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1
cj-zj -3.25 0 -2.75 0 0 -0.25 -1
以b2为例, x6是对应的初始基变量，所以有
max01 .205,02100b2min 01.7050 200b213.33, 1000b2133.33

管理运筹学灵敏度分析


4 x3 0 0 0 1
0 x4 1 1/3 0 1/3
0 x5 0 0 1 0
0 x6 2 -2/3 1 1/3
RHS
17+ 1/3+1/3 6 13/3+1/3
由此可以看出，当第一个约束的右边常数b1变化时， 新的单纯形表的RHS列就是原来最优单纯形表的 RHS列加上第一个松弛变量x4在原来单纯形表中对 应的列与的乘积。
≤15 ≤24
6x1 +2x2
X1
x1,
+x2
x2,
≤5
≥0
首先得到以上问题的最优单纯形表： C z 2 x1 1 x2 0 x3 0 x4 0 x5 RHS
z
x3 x1 x2
1
0 2 1
0
0 1 0
C Z x1 0 0 1 0
0
0 0 1
2+ 1 x2 0 0 0 1
0
1 0 0
0 x3 0 1 0 0
C -2 z CB -2 0 z x1 x5 1 0 0 x1 c2 x2 -1 x3 -1 1 1 0 x4 -2 1 1 0 x5 0 0 1
RHS
0 -2-c2 1 0 1 3
-12 6 10
当c2=-3时，已经超出保持最优基不变的范围，因此单纯形 表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下 单纯形表： x2进基
1.目标函数系数C的变化范围
目标函数系数变化，只会影响最优 解中检验数行，不会影响基变量的 取值。即C中元素的变化只会影响 最优解的对偶可行性而不会影响原 始可行性。
（1）非基变量在目标函数中系数的灵敏度分析
m个基变量xBr（r=1,2,…,m）在目标函数中的系数为：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

作业：P386 T13.7
批量折扣分析 Exit
总费用增加率为
i f (Q) f (Q*) 2
f (Q*)
2(1 )
当 1时i 0 ,说明总费用增加了,只有当是δ<－1时,i<0 总费
用才减少，但无论是增加还是减少，总费用的变化幅度比δ小得多， 如δ=100%时，i=25%,即总费用增加率是订货批量增加率的1/4。
§9.3 灵敏度分析
§9.3 灵敏度分析
Sensitivity Analysis
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 6 of 6
例如，总费用对存储费C1的弹性为。
f C1
C1 f
Q 2
QC1
/
C1 2 RC3
/ Q 1
说明f(Q)对C1是非弹性的。
设需求量增加δ倍,变化后的需求量为R‘=δR则变化后的订货批量为
Q 2C3R 2C3R
C1
C1
总费用为(不计购置费)
f ' 2C1C3 R' 2C1C3 R
这说明当R增加δ倍，订货批量和总费用只增加
中，当 R' 1500时，δ=1.5，则
倍。例如在例1
Q' Q* 82 1.5 100.
Sensitivity Analysis 三．各费用的变化对总费用的影响
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 4 of 6
设 C1 和 C3 的 偏 差 分 别 为 δ1C1 和 δ3C3 则 实 际 存 储 、 订 货 费 分 别 为
Sensitivity Analysis
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 5 of 6
i f (Q) f (Q*) f (Q*)
1 1
1 3－1
现在的问题是订货时往往是按预测的费用C1，C3来订货，而实际结
算时的总费用是实际的费用 C'1 , C'3结算的，这时的总费用为
§9.3 灵敏度分析
Sensitivity Analysis
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 1 of 6
10.3.1灵敏度分析 灵敏度分析,主要分析模型中各因素发生变动时对订货批量或总
成本的影响程度,下面我们仅以模型一为例说明其分析方法. 一、需求量对经济订货批量及总费用的影响
§9.3 灵敏度分析
Sensitivity Analysis
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 2 of 6
二、经济订货批量对总费用的影响
如果需求量或各项费用在计划前预测不精确,那么按式(10.3)得 到 的 最 优 批 量 会 有 偏 差 , 记 偏 差 为 δQ* 即 实 际 订 货 批 量 为 Q=Q*+δQ*=（1+δ）Q*。由式（10.2）得到实际总费用为
和 C1 (1 1)C,1为了方C便3 ，(1令K13=)1C+3δ1 , K3=1+δ3，则实际订货批
量为
Q 2C'3 R 2K3C3R Q K3
C'1
K1C1
K1
实际费用为
f (Q)
Q 2
C
'1
R Q
C
'3
2RC1C3 K1K3
f (Q*) 1 1 1 3
费用增加率为
§9.3 灵敏度分析
f
(Q)
1 2
C1 (1
)Q
*
C3R
(1 )Q
*
1 2
C1 (1
)
2C3 R C3 R
C1 1
122(1 )2C1C3 R
1
2
2(1
)
f
(Q*)
C1 2C3 R
§9.3 灵敏度分析
Sensitivity Analysis
Ch9 Inventory Theory
2022002年0年6月6月2200日日星星期期六六 Page 3 of 6
f
(Q)
Q* 2
C'1
R Q*
C'3
1 2
2C3 R C1
K1C1
C1 2C3
R
R
K3C3
K1 K3 2
2C1C3 R
1
1
3
2
f
(Q*)
即总费用增加率之和的一半 i (1 3 ) / 2 以上不论那一种情况，结果表明，总费用的变化率要比参数的
变化率小。这一结论还可从弹性的角度来解释。