当前位置：文档之家 › 常见的运筹学灵敏度分析 PPT

常见的运筹学灵敏度分析 PPT

  • 格式：ppt
  • 大小：693.00 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

运筹学对偶理论与灵敏分析PPT课件

运筹学对偶理论与灵敏分析PPT课件

2x1 x2 3x3 2x4 20
x1
4
0
试验证弱对偶性原理。
第25页/共86页
解：
m i nW 20y1 20y2
（D）
y1 2 y2 1
22
y1 y1
y2 3 y2
2 3
3 y1 2 y2 4
y1 0, y2 0
由观察可知：
__
X =（1.1.1.1），
Y__=（1.1），分别是
（1）若原问题是
MaxZ CX
(P)
s.t.
AX b X 0
(2) 其对偶问题为
MinW bY
(D)
YA C
s.t.
Y
0
这两个式子的变换关系称为“对称形式的对偶关系”。
第11页/共86页
怎样写出非对称形式的对偶问题？ 根据对应规律（参见对偶关系表）直接 写出；
第12页/共86页
原问题（或对偶问题） 对偶问题（或原问题）
第7页/共86页
如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。
原问题与对偶问题之间没有严格的 界限，它们互为对偶。
第8页/共86页
(P) 例1.1
MaxZ 2x1 3x2
x1 2x2 8
s.t.44
x1 x2
16 12
x1, x2 0
第37页/共86页
对偶性质定理总结：
定理2弱对偶定理： 判断原问题（对偶问题）目标函数值的上界 （下界）。
定理3、4、5： 判断原问题（对偶问题）解的两种对应关系。
判断原问题（对偶问题）有无最优解。
定理6互补松弛性定理： 根据原问题（或对偶问题）最优解，直接求出 对偶问题（或原问题）的最优解。

运筹学图解法的灵敏度分析 PPT课件

运筹学图解法的灵敏度分析 PPT课件
交于该顶点的两条直线的斜率即cj变动范围，cj在两 条直线斜率之间变动时，原线性规划问题的最优解
不变，最优值变动（cj变动）。
11
四、约束条件中右边系数bi的 灵敏度分析
例：
max F 6 x 1 4 x 2 s .t . 2 x 1 3 x 2 10 4 x 1 2 x 2 12 x1, x2 0
18
图解法
400
2x1x2 400
可行解域为OABCD 最优解为B点（50，250）
300
A
B
x2 250
200
C
100
x1x2 300
最优生产方案为： 甲生产50，乙生产250；
此时， 总利润为27500元。
D
O
100
200
300
400
5x0110x200
19
现提高设备可利用台时数
（b1=300
12
讨论：当b1=10 b1=11时对 原问题的影响
x2
5
4x12x212
A 3
B
1
2x13x210
O
C
2
4
6
x1
6x14x20 6x14x220
13
讨论：b1变动对原问题的影响 （b1=10 b1=11）
x2
5
4x12x2 12
A’
A3
B’
B
2x13x2 11
1
2x13x210
O
C
2
4
6
x1
6x14x20
100
设备台时的约束条件
为0
D D’
O
100
200
300
400

系统工程概论运筹学6.5灵敏度分析.ppt

系统工程概论运筹学6.5灵敏度分析.ppt

❖ 原问题最优解不变，若反之
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,目标要求是日利润最大化，约束条件为三 种资源的供应量限制和产品销售量限制。

灵敏度分析(运筹学).ppt

灵敏度分析(运筹学).ppt

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 单纯形法灵敏度分析

运筹学——对偶问题与灵敏度分析幻灯片PPT

运筹学——对偶问题与灵敏度分析幻灯片PPT
产品A 产品B 资源限制
劳动力
9
4
360
设备
4
5
200
原材料
3
10
300
单位利润 70
120
OR1
18
Cj
CB XB
0 X3 0 X4 0 X5
σj
0 X3 0 X4 120 X2
σj
70 X3 1200 X1
X2 σj
OR1
b
360 200 300 0
240 50 30 3600
84 20 24 4280
〔1〕根据LP问题，列出初始单纯形表。检查b列的数字， 假设都为非负，检验数都为非正，那么已得到最优解， 停顿计算。假设检查b列的数字时，至少还有一个负分 量，检验数保持非正，那么进展以下计算。
〔2〕确定换出变量：将B-1b中最小的负分量所对应的 变量确定为换出变量。
〔3〕确定换入变量：检查换出变量所在行〔第L行〕的
〔3〕在灵敏度分析中，有时需要用对偶单纯形 法，这样可使问题的处理简化。
OR1
29
2.2灵敏度分析〔考研时常考的知识点〕
灵敏度分析通常有两类问题：①是当C,A,b 中某一局部数据发生给定的变化时，讨论 最优解与最优值怎么变化；②是研究 C,A,b中数据在多大范围内波动时，使原 有最优基仍为最优基，同时讨论此时最优 解如何变动？
OR1
22
对偶单纯形法
设有问题maxZ=CX ，
AX ＝b ，
X ≥0
又设B是其一个基，当非基变量都为0时， 可以得到XB=B-1b。假设在B-1b中至少有 一个负分量，设第i个为负分量，并且在单 纯形表的检验数行中的检验数都为非正，
这种情况就可以用对偶单纯形法来进展求 解。

运筹学课件2.5 灵敏度分析


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
增加约束后，最优目标函数值不会更好，一般 会差一些。

运筹学灵敏度分析PPT课件

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

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


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

运筹学精品课件之 对偶问题和灵敏度分析

82 0 0 -10/3 0 -11/3 -2产品工艺结构改变) (1)、非基变量Xj工艺改变 只影响单纯形表Pj 列， σ j .
关键看σ j 0? 还是>0? . 用(三)类似方法解决。
(2)、基变量Xj工艺改变，复杂
例：产品A工艺改变，对甲、乙需求变为2，2。 利润为7，问最优方案如何？
0 X4 2 8 X2 10
80
1 0 0 1 -1/2 1 1 1 0 1/2 -5 0 -2 0 -7/2
这时最优方案发生了改变。
基变量Xj工艺改变
•也可能 B-1 b出现负数
•检验数与基变量均不满足最优解要求
例 p1’ = 1
3
C1’ = 7
p一1’ = B-1 p1’ = σ一1’= -4
(2)、 b1改变, b1=30 ，B-1 b= 2 -1
30 40 =
-1 1 20 -10
5 X1 40 1 0 0 2 -1 8 X2 -10 0 1 1 (-1) 1
120 0 0 -2 -2 -3
5 X1 20 1 2 2 0 1 0 X4 10 0 -1 -1 1 -1
100 0 -2 -4 0 -5
问：如何安排产品产量，可获最大利润？
解 maxZ=5X1 +8X2 +6X3
X1+ X2 + X3+X4 = 12 X1+2X2+2X3 +X5 =20
X1 … X5 0
58 60 0
X1 X2 X3 X4 X5 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1
058 60 0
② C1改变 C1=10， σ 5 =2>0 ,换基
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
CBB1b3 416212
将上述数字替换最优单纯形表中相应位置的数据得：
用对偶单纯形法迭代，求出的最优单纯形表如下： 得到新的最优解为：x1=0,x2=3; maxz=9
大家有疑问的，可以询问和交流
可以互相讨论下，但要小声点
9
2.对价值系数Cj变化的分析
（1）当CN（非基变量的目标函数系数）中某个Cj发生变 化时，只影响到非基变量xj的检验数
maxZ 4x13x2 2 y1
s.t.32xx1123xx22
y1 24 2 y1 26
x1, x2 0
(材料约束 ) (工时约束 )
用单纯形法求得其最优表为：
解：因为y1为非基变量，其目标函数系数c3的变化只会影
响到y1的检验数，因此为使最优解不变，只需 3 0
即
C 323/51/3 5
由于
j ( C B B 1 P j) ( C j C j)j C j
所以,当 j 0 即当 Cj j 时,最优解不变（最小值）
反之,当 j 0 时,最优解改变,需要用单纯形法重新进 行迭代,以求得新的最优解.
例题17 对于下列线性规划模型,为使最优解不变，讨论非 基变量y1的目标函数系数c3的变化范围。
s.t.32xx1123xx22
y1 24 2 y1 26
x1, x2 0
(材料约束 ) (工时约束 )
解： 3 C B B 1P 3 C 3 1 /56/5 1 1 2 5 3
最优解改变。此时其系数列改为：
B 1P 3 3 2 //5 5
2/51 1/5 3/5 1 1/5
（3）技术系数aij变化的分析 第一种情况（当jJN）：即aij为非基变量xj的技术系数
时，它的变化只影响xj的系数列B-1Pj和检验数 j ，为使最
优方案不变，只需 j 0
例18 对于下列规划问题的最优解，若由于工艺改进，y1的 技术系数改为p3=(1,1)T，试讨论最优解的变化。
maxZ 4x13x2 2 y1
灵敏度分析=对于市场的变化，我们的决策 究竟怎样变化（不需要将 它当成一个新z cjxj
或
j1
n
ajxj
bi(i 1,2,L,m)
j1 xj 0(j1,2,L,n)
maxz=cx
AX b
X
0
灵敏度分析（2）
面对市场变化，灵敏度分析的任务是须解决以下两类问题
解：
C B B 1 A C 3 4 C 1 1 0 0 1 3 / 2 5 /5 3 2 / /5 5 4 C 13 0 0
4 C 131 5 5 2 C 15 6 5 3 C 1 4 C 1300
0
0
12
55C 1
5 65 3C 10
增加新产品应在不影响企业目前计划期内最优生产的前 提下进行。因此可从现行的最优基B出发考虑：
若σn+1=CBB-1Pn+1－Cn+1<0，则应投产 若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。
1 55 2C 10 5 65 3C 10
2C 11 2 即 2C 14.5
若 C 1 5 ,则 C B B 1 A C 00 1 58 5 C B B 1 b 3 6 6 C 1 4 将上述数字替换单纯形表中相应位置的数字得：
用单纯形法迭代得最优解表如下：
b变化的时候，仅对B-1b有影响
此时，基变量不变
P33 例题16 对于生产计划问题，为使最优方案不变，试 讨论第二个约束条件b2的变化范围。
解：生产计划问题的数学模型和最优单纯形表为：
maxZ 4x13x2
2
x13x2
24
s.t.3x12x2 26
x1, x2 0
(材料约束) (工时约束)
从矩阵形式的单纯形表中可知，b2的变化只影响解 的可行性B-1b≥0,因此，为使最优解不变，只需变化以后的
将上述数据替换最优表中相应位置的数据，然后再用单
纯形法求得新的最优解。
第二种情况（当jJB）：由于B中元素的改变影响到B-1 的变化，因此也影响到整个单纯形表T(B)的变化。目前的 基B对应的解有可能既不是原始可行，也不是对偶可行。 于是不如重新求解
（4）对增加新产品的分析
设某企业在计划期内，拟议生产新产品Xn+1，并已知新 产 品 的 单 位 利 润 为 Cn+1 ， 消 耗 系 数 向 量 为 Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此时应如何分析才能确定该新 产品是否值得投产？
一、当系数A、b、C中的某个发生变化时,目前的最优基是 否仍最优（即目前的最优生产方案是否要变化）?(称为模 型参数的灵敏度分析)
二、增加一个变量或增加一个约束条件时，目前的最优基 是否仍最优（即目前的最优生产方案是否要变化） (称为 模型结构的灵敏度分析)
灵敏度分析的方法是在目前最优基B下进行的。即当参 数A、b、c中的某一个或几个发生变化时，考察是否影响 以下两式的成立？
B 1b 0
CBB
1AC
0
1、对于参数b的灵敏度分析
从矩阵形式的单纯形表中可以看出，b的变化只影响最优 解的变化和最优值的变化。
因此，当 B1b0时，最优基不变（即生产产品的品种 不变，但数量及最优值会变化）。
B1b0 是一个不等式组，从中可以解得b的变化范围
若B-1b中有小于0的分量，则需用对偶单纯形法迭代，以 求出新的最优方案。
若C3=3,则
3
2 5
代入最优单纯形表中相应位置
继续迭代以求出新的最优解。
（2）当CB(即基变量的目标函数系数)中某个Cj发生变化时
则会影响到所有变量的检验数σ=CBB-1A－C
解不等式组
CBB1AC0
就可得到 Cj的范围
例18 设基变量x1的系数C1变化为 C1C1 ，在最优性不变 的条件下，试确定 C1 的范围
B-1b≥0即可。
B1b32//55 32//552b247545285253bb220
由
72 5
2 5
b2
48 5
3 5
b
0 20
解得：
16b236
写 B-1
若b2变化超过范围，则需用对偶单纯形法进行求解。如 b2=6，则
B 1b 3 2 //5 5 3 2 //5 5 2 6 4 16 2 0