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

运筹学灵敏度分析题

  • 格式：doc
  • 大小：264.00 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

运筹学-单纯形法灵敏度对偶

运筹学-单纯形法灵敏度对偶

若新增约束如下：
max z 50x1 100x2 x1 x2 300 2x1 x2 400 x2 250 10x1 30x2 5000(电力约束) x1, x2 , 0
x1 x2 s1
把最优解x1=50,x2 =250代入电力约束 1050+30 250=80005000 新约束不满足,最优解变化
例题：已知某线性规划初始可行基是（S1 S2 S3 a1）， 最终单纯形表如下，求对偶价格不变时的△bi变化范围
x1 x2 s1
50 100 0
X1 50
1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0
0
1
Zj
50 100 0
δj
0
0
0
（1） △b1的变化范围： ?
（2） △b2的变化范围：?
（3） △b3的变化范围： ? （4） △b4的变化范围：?
1 0 1 2 0.5
B1 p6'
2
1
1
0.5
2
0 0 1 1.5 1.5
Z6' 50 0.5 0 (2) 100 1.5 175
' 6
C6
Z6'
150 175
25
δ6´<0，最优解不变，即仍生产Ⅰ50件，Ⅱ100件。
2、变量xk系数列由pk变为pk´，在最终单纯形表 上xk是基变量
x1 x2 s1
50 100 0
X1 50 1
0
0
S3 0
0
0
0
X2 100 0
1
0
s1 0
0

运筹学灵敏度分析题

运筹学灵敏度分析题

运筹学灵敏度举例1．已知以下线性规划问题max z= 2x 1 +x 2-x 3 s.t. x 1 +2x 2 +x 3 ≤8 -x 1 +x 2 -2x 3≤4x 1,x 2,x 3≥0 的最优单纯形表如下：z x 1 x 5(1) 求使最优基保持不变的c 2=1的变化范围C 2 1+δ-1 0 0 0C B z 2 x 1 0x 53-δ≥0，δ≤3，即c 2≤4。

当c 2=5，即δ=4z x 1 8/2 x 512/3x2进基，x 1离基z x 2 x 5新的最优解为x 1=0，x 2=0，x 3=0，x 4=0，x 5=0，max z=20 (2) 对c 1=2进行灵敏度分析C 2+δ1 -1 0 0 0C B z 2+δ x 1 0x 53203020+≥+≥+≥⎧⎨⎪⎩⎪δδδ，δδδ≥-≥-≥-⎧⎨⎪⎩⎪3232/，当δ≥-3/2时，即c 1≥1/2时，最优基保持不变。

当c 1=4时，δ=4-2=2，最优基保持不变，最优解的目标函数制为z=16+8δ=32。

（3）增加一个新的变量x 6，c 6=4，a 612=⎡⎣⎢⎤⎦⎥。

[]z c c T666620124242-=-=⎡⎣⎢⎤⎦⎥-=-=-W aY B a 61610111213==⎡⎣⎢⎤⎦⎥⎡⎣⎢⎤⎦⎥=⎡⎣⎢⎤⎦⎥- 新的单纯形表为z x 1 x 5x 6进基，x 5离基z x 1 x 6新的最优解为x 1=4，x 2=0，x 3=0，x 4=0，x 5=0，x 6=4，max z=24。

（4）增加一个新的约束x 2+x 3≥2，求新的最优基和最优解。

z x 1 x 5 x 63/13/1用对偶单纯形法求解z xx x x x x RHSz x 1 x 5 x 2新的最优解为x 1=4，x 2=2，x 3=0，x 4=0，x 5=6，x 6=0，max z=10。

2．(1)利润最大化的线性规划模型为：max z= 25x1+12x2+14x3+15x4s.t. 3x1+2x2+x3+4x4≤24002x1+2x3+3x4≤3200x1+3x2+2x4≤1800x1, x2, x3, x4≥0单纯形表为：zx5x6x7x1进基，x5离基zx1x6x7x3进基，x6离基zx1x3x7x2进基，x1离基zx2x3x7最优解为：x1=0，x2=400，x3=1600，x4=0，x5=0，x6=0，x7=600，max z=27200即最优生产计划为：产品A不生产；产品B生产400万件；产品C生产1600万件；产品D不生产，最大利润：27200万元。

运筹学灵敏度分析

运筹学灵敏度分析

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

运筹学教材编写组《运筹学》章节题库-对偶理论与灵敏度分析(圣才出品)

运筹学教材编写组《运筹学》章节题库-对偶理论与灵敏度分析(圣才出品)
3 / 36
圣才电子书 十万种考研考证电子书、题库视频学习平台

5．已知 Yi 为线性规划的对偶问题的最优解，若 Yi>0，说明（）。[深圳大学 2006 研] A．原问题的最优解 xi=0 B．在最优生产计划中第 i 种资源己完全耗尽 C．在最优生产计划中第 i 种资源有剩余 D．无法判断 【答案】B 【解析】当影子价格为 0 时，表示某种资源未得到充分利用；而当资源的影子价格不为 零时，表明该种资源在生产中已耗费完毕。
【答案】对偶单纯形法
3．某极小化线性规划问题的对偶问题的最优解的第 l 个分量为 yl=-12，则该问题的第 1 个约束条件的右端常数项的对偶价格为：______。[武汉大学 2006 研]
5 / 36
圣才电子书

【答案】-12
十万种考研考证电子书、题库视频学习平台
【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对
4．根据对偶解的经济含义，若天然气资源是我国的一种稀缺能源资源，其影子价格必 然是（）。[北京科技大学 2010 研]
A．不能确定 B．＜0 C．=0 D．＞0 【答案】D 【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越 高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值贡献也越大。天然 气是资源是一种稀缺能源资源，其影子价格必然大于 0。
学 2008 研]
十万种考研考证电子书、题库视频学习平台
【答案】√
【解析】它的对偶问题可能无解，也可能有无界解。
二、选择题
1．用线性规划制定某一企业的生产计划问题，两种资源的影子价格分别为 y甲=5 ， y乙=8 ，说明这两种资源在该企业中的稀缺程度为（）。[北京交通大学 2010 研]

运筹学实验

运筹学实验

1、实验题目运筹学实验2-线性规划灵敏度分析某公司生产三种产品A1、A2、A3，它们在B1、B2两种设备上加工，并耗用C1、C2两种原材料，已知生产单位产品耗用的工时和原材料以及设备和原材料的最多可使用量如表 C －7所示。

表 C －7 生产三种产品的有关数据已知对产品A2的需求每天不低于70件，A3不超过240件。

经理会议讨论如何增加公司收入，提出了以下建议：（a ）产品A3提价，使每件利润增至60元，但市场销量将下降为每天不超过210件； （b ）原材料C2是限制产量增加的因素之一，如果通过别的供应商提供补充，每千克价格将比原供应商高20元；（c ）设备B1和B2每天可各增加40 min 的使用时间，但相应需支付额外费用各350元； （d ）产品A2的需求增加到每天100件；（e ）产品A1在设备B2上的加工时间可缩短到每件2 min ，但每天需额外支出40元。

分别讨论上述各条建议的可行性，哪些可直接利用“敏感性报告”中的信息，哪些需要重新规划求解2、模型设1X 为A1的产量，2X 为A2的产量，3X 为A3的产量1）数学模型由题目可建立线性规划模型：321502030max x x x z ++=)3,2,1(0240703004204460234302323212131321=≥≤≥≤++≤+≤+≤++i x x x x x x x x x x x x x i2）用Excel 建模求解3、实验结果及敏感性分析1）实验结果以得出题得最优解 x1=0,x2=70,x3=230 时，最优值为 12900，即生产 A1,A2，A3 产品分别是 0 件， 70 件，230 件时，公司可获得最大利润 12900 元2）敏感性报告①A3 产品每件利润提到 60 元，这在灵敏度分析的最优基不变范围 A3[50-23.3333，5 0+∞]内，但市场销量下降为不超过 210 件，而从求解报告中中最优解 A3=230 时，有最大目标值，故此建议可行。

运筹学灵敏度分析(最全版)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灵敏度分析

非基变量的价格系数变化，在原最优解 不变的条件下，确定的变化范围。
（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

运筹学讲义影子价格-灵敏度分析-运输问题


2)
0.000000
48.000000
3)
0.000000
2.000000
4) 40.000000
0.000000
35元可买到1桶牛奶，要买吗？ 35 <48, 应该买！
聘用临时工人付出的工资最多每小时几元？ 2元！
21
结果解释
DO RANGE(SENSITIVITY) ANALYSIS?
Yes
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES
20桶牛奶生产A1, 30桶生产A2，利润3360元。
18
模型求解
OBJECTIVE FUNCTION VALUE
1)
3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000
0.000000
X2 30.000000
0.000000
ROW SLACK OR SURPLUS DUAL PRICES
16
1桶
12小时 3公斤A1
牛奶 或 8小时 4公斤A2
获利24元/公斤 获利16元/公斤
每天 50桶牛奶 时间480小时 至多加工100公斤A1
决策变量 目标函数
约束条件
x1桶牛奶生产A1 x2桶牛奶生产A2
获利 24×3x1
获利 16×4 x2
每天获利 Max z 72 x1 64 x2
原料供应
12
影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投 入量每增加一个单位所带来总收益的增加量。
影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态 配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间 的关系，不能代替资源本身的价值。

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

的产量就大于零，即需考虑生产丙产品了。
• 所以，丙产品单位利润的变动范围是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
分析

运筹学课件 灵敏度分析举例


x2
1 0
x3
1 -1/2
x4
-2 3/2

20 x1 15
j cj z j
CB
30 50
cj xB
50
30
0
0
35 0 x1 7.5 1 j c j z j 1425 0
x2
b
x1
x2
1 0 0
x3
x4

1/2 -1/2 -1/4 3/4 -2.5 -22.5

木工用量 4 x1 3x2 120 木工可使用量 油漆工用量 负条件。
2 x1 x2 50 油漆工可使用量 决策变量还应当满足 x 0 ， x2 0，叫做非 1
例1的数学模型
max z 50x1 30x2
s.t.
4 x1 3x2 120 2 x1 x2 50 x1 , x2 0
x3
1
0
x4
0
1

30
25
x4
j cj z j
0
50
30
0
0
第一次换基并求解
CB
0 50
x3 x1
cj xB b
20 25 1250
50
30
0
x1
0 1 0
x2
（1） 1/2 5
x3
1 0 0
x4
-2 1/2 -25 20 50
0
j cj z j
第二次换基和求解
cj xB
50 30 0 0
CB
30 50
x2
b
x1
0 1 0
x2
1 0 0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

运筹学灵敏度举例
1．已知以下线性规划问题
max z= 2x 1 +x 2
-x 3 s.t. x 1 +2x 2 +x 3 ≤8 -x 1 +x 2 -2x 3
≤4
x 1,
x 2,
x 3
≥0 的最优单纯形表如下：
z x 1 x 5
(1) 求使最优基保持不变的c 2=1的变化范围
C 2 1+δ
-1 0 0 0
C B z 2 x 1 0
x 5
3-δ≥0，δ≤3，即c 2≤4。

当c 2=5
，即δ=4
z x 1 8/2 x 5
12/3
x
2进基，x 1离基
z x 2 x 5
新的最优解为x 1=0，x 2=0，x 3=0，x 4=0，x 5=0，max z=20 (2) 对c 1=2进行灵敏度分析
C 2+δ
1 -1 0 0 0
C B z 2+δ x 1 0
x 5
3203020+≥+≥+≥⎧⎨⎪⎩⎪δδδ，δδδ≥-≥-≥-⎧⎨⎪
⎩
⎪3232/，当δ≥-3/2时，即c 1≥1/2时，最优基保持不变。

当c 1=4时，δ=4-2=2，最优基保持不变，最优解的目标函数制为z=16+8δ=32。

（3）增加一个新的变量x 6，c 6=4，a 612=⎡⎣⎢⎤⎦
⎥。

[]
z c c T
666620124242-=-=⎡⎣⎢⎤
⎦
⎥-=-=-W a
Y B a 61
610111213==⎡⎣⎢⎤⎦⎥⎡⎣⎢⎤⎦⎥
=⎡⎣⎢⎤
⎦
⎥- 新的单纯形表为
z x 1 x 5
x 6进基，x 5离基
z x 1 x 6
新的最优解为x 1=4，x 2=0，x 3=0，x 4=0，x 5=0，x 6=4，max z=24。

（4）增加一个新的约束x 2+x 3≥2，求新的最优基和最优解。

z x 1 x 5 x 6
3/1
3/1
用对偶单纯形法求解
z x
x x x x x RHS
z x 1 x 5 x 2
新的最优解为x 1=4，x 2=2，x 3=0，x 4=0，x 5=6，x 6=0，max z=10。

2．
(1)利润最大化的线性规划模型为：
max z= 25x1+12x2+14x3+15x4
s.t. 3x1+2x2+x3+4x4≤2400
2x1+2x3+3x4≤3200
x1+3x2+2x4≤1800
x1, x2, x3, x4≥0
单纯形表为：
z
x5
x6
x7
x1进基，x5离基
z
x1
x6
x7
x3进基，x6离基
z
x1
x3
x7
x2进基，x1离基
z
x2
x3
x7
最优解为：x1=0，x2=400，x3=1600，x4=0，x5=0，x6=0，x7=600，max z=27200
即最优生产计划为：产品A不生产；产品B生产400万件；产品C生产1600万件；产品D不生产，最大利润：27200万元。

原料甲：耗用2400吨，没有剩余；原料乙：耗用3200吨，没有剩余；原料丙：耗用1200吨，剩余600吨。

（问三种原料的利用率？）
（2） 产品A 利润变化范围： -C -25+δ -12 -14 -15 0 0 0 0
-C B z -12 x 2 -14 x 3 0
x 7
-1-δ≤0，δ≥-1，-c 1’=-c 1+δ≥-25-1=-26，即c 1≤26（万元/万件）
产品B 利润变化范围： -C -25 -12+δ -14 -15 0 0 0 0
-C B
z
-12+δ x 2 -14 x 3 0
x 7
--≤-+≤-+≤--≤⎧⎨
⎪⎪⎩⎪⎪102154061204140δδδδ///，δδδδ≥-≤≤≥-⎧⎨⎪⎪
⎩⎪⎪18451216
/，-1≤δ≤12，-13≤-12+δ≤0，-13≤-c 2’≤
0， 即：0≤c 2’≤13。

产品C 利润的变化范围： -C -25 -12 -14+δ -15 0 0 0 0 -C B z -12
x 2
-14+δ x 3
0 x 7
--≤-+≤-+≤⎧⎨⎪⎩⎪10213204120δδδ//，δδδ≥-≤≤⎧⎨⎪⎩
⎪1148 -1≤δ≤8，-15≤-14+δ≤-6，-15≤-c 3’≤-6，6≤c 3’≤15
产品D 的变化范围 -C -25 -12 -14 -15+δ
0 0 0 0 z x
x x x x x x RHS -C B z -12 x 2 -14 x 3 0
x 7
-21-δ≤0，δ≥-21，-15+δ≥-36，-c 4’≥-36，c 4’≤36。

（3） 求三种原料的影子价格和四种产品的机会成本
由最优单纯形表可知，原料甲、乙、丙的影子价格分别为：
6万元/吨、4万元/吨、0万元/吨。

产品A 、B 、C 、D 的机会成本分别为（
∑=m
i ij
i a
q 1
）：
26万元/万件、12万元/万件、14万元/万件、36万元/万件。

产品A 、D 在最优解中不安排生产的原因是机会成本大于利润。

（4） 在最优解中，原料甲的影子价格（6万元/吨）最大，因此这种原料最紧缺。

如果原料A 增加120吨，最优单纯形表的右边常数成为：
B b -'=--⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+⎡⎣⎢⎢⎢⎤⎦
⎥
⎥⎥=
⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+-⎡⎣⎢⎢⎢⎤
⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎤
⎦
⎥⎥⎥≥11214001203234124001203200180040016006006000180100016004200///// 因此最优基保持不变，影子价格不变，原料的紧缺程度不变。