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

运筹学24灵敏度分析

  • 格式：pptx
  • 大小：160.82 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

灵敏度分析(运筹学)

灵敏度分析(运筹学)

最优基不变，即在最终表中求得的经过变化后 的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是根据资源投入后的经济效果决定 的一种决策选择。显然，当线性规划问题中某一个 或几个系数发生变化后，原来已得结果一般会发生 变化。 因此，所谓灵敏度分析，是指当线性规划问题中的 参数发生变化后，引起最优解如何改变的分析。

运筹学灵敏度分析

运筹学灵敏度分析

只需由 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 灵敏度分析
灵敏度分析——研究系数变化对最优解的影响.

运筹学 对偶理论和灵敏度分析

运筹学 对偶理论和灵敏度分析
对偶理论和灵敏度分析
1.单纯形的矩阵描述
用矩阵语言描述单纯形法的关键是写出两个基本的 表达式,设线性规划的标准型为 maxz=CX AX=b X≥0
C=(CB,CN)，X=(XB,XN)’，A=(B,N)
由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得 到用非基变量表示基变量的表达式:
-2 -3 -1 -1 1/3 x3 -1/3 0 x1 4/3 1 x5 1/3 0 0
' ' - a 1k / alk ' ' - a 2k / alk ... ' 1 / alk ... ' ' - a mk / alk
3对偶理论
某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最 后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 工时单耗 生产能力 产品 甲 乙 车间 A 1 0 8 B 0 2 12 C 3 4 36 单位产品获利 3 5 • maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0
(4)影子价格在资源采购决策中的应用。
当资源的市场价格低于影子价格，企业买进该资源，扩 大生产，当资源的市场价格高于影子价格，企业应设法转让 该资源。
(5)利用影子价格分析工艺改变后对资源节约的收益。 例如设工厂现有钢材100吨，其影子价格为3/4，采用新 工艺后，钢材可以节约2%，则由此带来的经济收益为：
(3)影子价格在新产品开发决策中的应用。 产品 资源 A B 影子价格(万元)
钢材 煤 机时
单位利润(万元)

运筹学第11讲灵敏度分析1

运筹学第11讲灵敏度分析1

12.5 x1 7 / 2 1 0 0 1/ 4 1/ 2
12 x2 3/ 2 0 1 0 1/ 4 3/ 2
cj zj
0 0 0 11//84 19//24
第14页
例2-1
产品Ⅰ利润降至1.5百元/单位，产品Ⅱ的利润 增至2百元/单位，生产计划如何变化？
解：(2) 将产品Ⅰ、Ⅱ的利润变化反映在最终单纯形表中，可得
一、含义和研究对象
1、什么是灵敏度分析？
是指研究线性规划模型的某些参数(bi, cj, aij） 或限制量（xj, 约束条件）的变化对最优解的影响及 其程度的分析过程<也称为优化后分析>。
n
max z c j x j
s.t.
n
j 1
aij xj bi （i 1,
j1
x
j
0
（j 1,
2 1 1c2 0 0 0
x1 x2 x3 x4 x5
0 0 1 5/ 4 15/ 2 1 0 0 1/ 4 1/ 2 0 1 0 1/ 4 3/ 2
1 c2 0； 1 3c2 0
44
22
cj zj
0
0
0 14 1/44c2
121/
23c2 2
即故当产品Ⅱ的13利 润c在2 [12
,
1→1+△c2
s.t.
n
j 1
aij xj bi （i 1,
j1
x
j
0
（j 1,
, m） , n）
3. 分析增加一个变量 xj 的变化 4. 分析增加一个约束条件的变化
系数矩阵A
5. 分析系数 aij 的变化
第5页
初 始
基变量 基变量 基可

运筹学 第二章 灵敏度分析

运筹学 第二章 灵敏度分析
改进多少，才能得到该决策变量的正数解。0表示不需再改进。
目标式系数： 指目标函数中的系数 允许增量、允许减量：表示目标函数中的系数在允许的增
量与减量范围内变化时，原问题的最优解不变。
450和1E+30的含义是什么？
2.2.2 图解法
x2
8 7 6 5 4 3 2 1
0<=c1<=750
（2,6）是最优解
2.4.2 图解法——改变车间2的约束
x2 改变车间1的约束又会是如何的？
2x2=18
8 7 6 5 4 3 2 1
（2,6）是最优解
2x2=12
可行域
2x2=6
1 23 4 5 6 7 8
x1
2.5 多个约束右端值同时变化的灵敏度分析
分析1小时的工时从车间3移到车间2，对总利润所产生的 影响。 那么，根据影子价格，可知总利润变化量如下： 车间2: 12-->13，利润增加？元 车间3: 18-->17，利润减
课本P50，例2.3，回答五个问题
1. 产品甲的单位利润将会在3.8万元~5.2万元之间波动，公司该 如何应对这种情况，提前对生产格局做好调整预案？
2. 当资源A的限额（储备量）在42~46之间变化时，对线性规划 的影响？ 3. 材料B在最优生产格局中出现了12.5单位的剩余，那么应如何 重新制定限额，做好节约工作？ 4. 若公司停止生产，把各种原材料变卖。该如何决策？

max z 300 x1 500 x2 x1 4 2 x 12 2 s.t. 3 x1 2 x2 18 x1 , x2 0
现从另一角度提出问题。假定某A公司想把该工厂的资源收购过 来，它至少应付出多大代价，才能使该工厂愿意放弃生产活动， 出让自己的资源？显然该工厂愿意出让自己资源的条件是：出让 代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。 设分别用y1、y2、y3代表单位时间车间1、车间2、车间3的出让代 价，因该工厂用1小时车间1和3小时车间3可生产1扇门，赢利300 元；分别用2小时车间2和车间3可生产1扇窗，赢利500元，由此， y1、y2、y3的取值应满足： y1 + 3y3 ≥ 300 2y2 + 2y3 ≥ 500

运筹学灵敏度分析(最全版)PTT文档

运筹学灵敏度分析(最全版)PTT文档

c + c YP 表中b列中有负数，即解答列有负数，故可用对偶单纯形法求最优解。
1、代表产品的单位利润或单位售价时，灵敏j度分析可用于j 预先确定保j持现有生产规模条件下单位产品利润或单价的可变范围。
解题步骤：先用单纯形法解题，然后考虑参数变化，最后确定变化范围。
△c2/2≤0和△c2/8-1/8≤0
br bi / air ;
i=1，2，…，m i=1，2，…，m
air < 0
br bi / air
得到公式:
5=-8, △b2≤2/0.
ma ab ix irai{r0} brm iab inira{ ir0}
（2）当cr是基底变量xr的系数，即cr CB，cr变化 cr后，有
故△c2的变化范围:
例题: 将上面例题进行实际应用。每台设备台时的影子 价格为元。若该厂又从别处抽出4台时用于生产两种产品， 求这时该厂生产两种产品的最优方案。
表中b列中有负数，即解答列有负数，故可用对偶单纯 形法求最优解。
最优解见下表
cj
CB XB b 2 x1 4 0 x3 2 3 x2 3
cj-zj
230 0 0 x1 x2 x3 x4 x5 1 0 0 0.25 0 0 0 1 -0.25 -05 0 1 0 0 0.25 0 0 0 -0.5 -0.75
5=-8, △b2≤2/0.
2每台3设例备0台：时的0求影子0第价格一为元章。 例题中当第二个约束条件b2变化范围△b2。
△c2≥-1.
每台设备台时的影子价格为元。
设基变量x2的系数c2变化△c2，在原最优解不变的条件下，确定△c2的变化范围。
x1 x2 x3 x4 x5 0 0 1 -0.

运筹学第二章24灵敏度分析


（3）其他情况讨论： 某个产品工艺参数改变； 新品代替原产品等；
（2） N =？
舍弃中间计算过程
只考察初始表和最终表
B-1 = AB-1
2、价值系数C发生变化的情况： （1）当cj是非基变量的价值系数——它的变 化只影响 j 一个检验数。 ≤0 1 j c j CB B Pj ≥0 要进行基变换码？
j c j c j CB B Pj ≤ 0
' 1
c j ≤ CB B1 Pj c j
非基变量的价格系数变化，在原最优解 不变的条件下，确定的变化范围。
（ 2 ）当cj是基变量的价值系数 —— 它的变化 将影响所有非基变量的检验数. 1 N C N CB B N 当cj变化时，如能保持 0 ，则当前解仍 N 为最优解，否则可用单纯形法继续迭代求出 新的最优解。 1 C C B N 0 将cj看作待定参数，令 N N B 解这n-m个不等式，可算出保持最优解不变 时cj的变化范围 ！ 基变量的系数变化，仍用c2代表x2的价值系 数（看成待定参数），原最优表格即为：
(2) 增加1个约束条件： 相当于系数阵A增加1行 首先将原最优解代入新增约束检查是 否满足？是，则说明新增约束不影响最 优解。否则再作下面的讨论：

将新增约束标准化，添加到原最优表 格中（相当于约束矩阵新增1行）；


进行规格化处理 —— 用矩阵的行变换 将当前基变成单位阵； 用适当方法（通常是对偶单纯形法） 进行迭代求出新的最优解。
（1）增加1个新变量：相当于系数阵A增加1列 如开发出一种新产品，已知其有关工艺参数 （或消耗的资源量）和单位产品利润，设该种 产 品 的 产 量 为 xk ， 则 ck 和 Pk 已 知 ， 需 要 进 行 “是否投产”的决策。

运筹学第二章灵敏度分析


CB
-3 -5 -Z’
xB x1 X2
2.4 对偶解的经济解释
一、对偶线性规划 的解： P55
Cj xB x3 x1 x2 z b 7/2 7/2 3/2 x1 1 0 0 y4 Cj yB b y1 15/2 0 原问题变量 x2 0 0 1 0 y5 对偶问题变量 y2 y3 x3 1 0 0 0 y1 原问题变量 x4 5/4 1/4 -1/4 1/4 y2 x5 -15/2 -1/2 3/2 1/2 y3
T.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）
二人因此而共同分享了1975年的第7届诺贝尔经 济学奖。
2.5 灵敏度分析
一、灵敏度分析的含义 是指系统或事物因周围条件变化显示出来的敏感性程度的分析。 对于线性规划问题的灵敏度分析是指参数A，b，C变化引起的 对原问题解的变化的分析。 其中：A为技术参数矩阵，b为资源向量，C为价值向量 可以用参数变化后的问题重新用单纯形法求解？ 没必要，意义不大，有些问题看不出来。 把相应的变化反映到最终单纯形表中，再根据情况用相应的方 法求解。
Z 50 x1 30 x2
2.1 线性规划的对偶问题与对偶理论
假设现有乙公司准备租借用(购买)该木器厂的木工和 油漆工两种劳力的劳务，需要考虑这两种劳务以什么 样的价格租入最合算？而同时甲公司要以什么条件才 会租让？甲公司肯定会以自己利用两种劳力的劳务组 织生产所获得的利润最大为条件，设每个木工的租用 价格为y1，每个油漆工的租用价格为y2，则乙公司愿 意租用的出资为：
0 变量 0 无限制
型 约束 型 型
0 变量 0 无限制
型 约束 型 型

运筹学 灵敏度分析目标规划

增加约束一个之后，应把最优解带 入新的约束，若满足则最优解不变，否则 填入最优单纯形表作为新的一行，引入一 个新的非负变量（原约束若是小于等于形 式可引入非负松弛变量，否则引入非负人 工变量），并通过矩阵行变换把对应基变 量的元素变为0，进一步用单纯形法或对 偶单纯形法求解。
3.灵敏度分析
例3.7:
CI
-2 -3 -4+Δ c3 0 0
CB
XB
b
X1
X2
X3
X4 X5
-3
X2 2/5 0
1
-1/5 -2/5 1/5
-2
X1 11/5 1
0
7/5 -1/5 -2/5
σ j
0
0 -9/5+Δ c3 -8/5 -1/5
从表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 时，原最优解不变。
s.t. Ax ≤ b x ≥0
3.灵敏度分析
最优单纯形表中含有
B-1=( aij ）i=1,…,m; j=n+1,…,n+m
那么
新的xi=(B-1b)i+brair i=1,…, m 。
由此可得，最优基不变的条件是
Max {-bi/airair>0}≤br≤ Min{-bi/airair<0}
3.灵敏度分析
那么
计算出B-1pn+1 , n+1=cn+1-∑cri ari n+1
填入最优单纯形表,
若 n+1 ≤ 0 则 最优解不变；
否则，进一步用单纯形法求解。
3.灵敏度分析
例3.6: 例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5

运筹学讲义-灵敏度分析

k=1 −1 m
qi = ∂f ( x) ∂bi− = (CBB−1)i , 左导数 机会成本 zn+i = CBB−1P +i = (CBB−1)i n zn+i 因此 qi = − zn+i
−1 m
, 松弛变量 人工变量 剩余变量
m
机会成本的另外表达形 式 z j = CBB Pj = ∑(CBB )i aij = ∑qiaij
16
2.4.7 灵敏度分析举例 例2.4.3 某工厂生产三种产品 A, B, C，有五种生产组合方案。 ，有五种生产组合方案。
下两表给出有关数据。 产品至少110 个，求收 下两表给出有关数据。规定每天供应 A产品至少 产品至少 益最大的生产方案。 益最大的生产方案。
17
例2.4.3
为已选定各种组合方案的组数(j=1,2,…,5)， x6为A产品 解：设xj为已选定各种组合方案的组数 ， 产品 的剩余变量， 分别为工人工时和机器工时的松弛变量。 的剩余变量， x7，x8分别为工人工时和机器工时的松弛变量。
©管理与人文学院
1999，4 ，
忻展红
2.4 灵敏度分析
灵敏度分析又称为后优化分析
2.4 线性规划的灵敏度分析
• 线性规划是静态模型 • 参数发生变化，原问题的最优解还是不是最优 参数发生变化， • 哪些参数容易发生变化 – C, b, A • 每个参数发生多大的变化不会破坏最优解 • 灵敏度越小，解的稳定性越好 灵敏度越小，
18
例2.4.3 • • • • • • • • • 最优解的B 最优解的 –1是什么 产品A的影子价为多少 产品 的影子价为多少 组方案的生产费用提高2元 第II组方案的生产费用提高 元，是否要调整生产组别 组方案的生产费用提高 若工人加班费为1元 小时 小时， 若工人加班费为 元/小时，是否要采取加班措施 若通过租借机器增加工时， 若通过租借机器增加工时，租费的上限应为多少 A产品的订购合同是否有利 产品的订购合同是否有利 若要选用第IV组方案，该组的生产费用应降低多少 若要选用第 组方案， 组方案 若工人加班费为0.3元 小时 小时， 若工人加班费为 元/小时，最多允许加班时间多少 若机器租费低于44元 小时 问租几部机器才合适(每天 小时， 若机器租费低于 元/小时，问租几部机器才合适 每天 8小时计 小时计) 小时计 • 若第 组方案使机器工时减少 小时，能否被选入 若第III组方案使机器工时减少 小时， 组方案使机器工时减少0.5小时
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
非基变量的价格系数变化，在原最优解 不变的条件下，确定的变化范围。
（2）当cj是基变量的价值系数——它的变化 将影响所有非基变量的检验数.
N CN CB B 1 N 为当最cj优变解化，时否，如则能可保用持单纯 N形法0 继，续则迭当代前求解出仍 新的最优解。
将cj看作待定参数，令 N CN CB B1N 0
②（B-1b）i<0, 当前基为非可行基, 可用对偶单纯形法 求出新的最优解；
③如何求出保持最优基不变的bi的范围? 把bi看作待定参数,令B-1b≥0,求解该不等式组即可；
b发生变化， XB B1(b b)
X B B 1b
B1(b b) B1b B1b
B1b B1(0 , 0 ,L , 0 , br , 0 ,L , 0)T (a1r br ,L , air br ,L , amr br )T br (a1r ,L , air ,L , amr )T
（或消耗的资源量）和单位产品利润，设该种 产 品 的 产 量 为 xk， 则 ck 和 Pk 已 知 ， 需 要 进 行 “是否投产”的决策。
如果算出的σk<0,说明新产品D不宜 投产，否则会使产品总利润下降！
(2) 增加1个约束条件：
相当于系数阵A增加1行
首先将原最优解代入新增约束检查是 否满足？是，则说明新增约束不影响最 优解。否则再作下面的讨论：
将新增约束标准化，添加到原最优表 格中（相当于约束矩阵新增1行）；
进行规格化处理——用矩阵的行变换 将当前基变成单位阵；
用适当方法（通常是对偶单纯形法） 进行迭代求出新的最优解。
（3）其他情况讨论： 某个产品工艺参数改变； 新品代替原产品等；
bi air br ≥ 0 i 1 , 2 ,L , m
当
air
>
0 时，
br ≥ bi / air
air < 0
br ≤ bi / air
max i
bi / air
air > 0
≤
br
≤ห้องสมุดไป่ตู้
min i
bi / air
air < 0
4、系数阵A的元素发生变化：
（1）增加1个新变量：相当于系数阵A增加1列 如开发出一种新产品，已知其有关工艺参数
2、灵敏度分析的内容： 目标函数的系数变化对最优解的影响； 约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响 ；
二、手工进行灵敏度分析的基本原则
1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
1、研究最优表格中的数据来源： （1）能否从表格中直接看出B-1？
（2） N =？ 舍弃中间计算过程
只考察初始表和最终表 B-1 = AB-1
2、价值系数C发生变化的情况：
（1）当cj是非基变量的价值系数——它的变 化只影响 j 一个检验数。
≤0 j c j CB B1Pj ≥0 要进行基变换码？
' j c j c j CB B1Pj ≤ 0
c j ≤ CB B1Pj c j
解这n-m个不等式，可算出保持最优解不变 时cj的变化范围 ！
基变量的系数变化，仍用c2代表x2的价值系 数（看成待定参数），原最优表格即为：
3、右端常数b发生变化： 当bi发生变化时，将影响所有基变量的取值。 为什麽？ 因为 X B B 1b 若bi的变化→
①保持B-1b≥0, 当前的基仍为最优基，最优解的结构不 变（取值改变）；