当前位置：文档之家 › 第三讲线性规划灵敏度分析与最优解解释

第三讲线性规划灵敏度分析与最优解解释

  • 格式：ppt
  • 大小：572.00 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

第4章线性规划灵敏度分析

第4章线性规划灵敏度分析

-2 x1 1
0
σj
0
0
-4 0 0 B-1b
x3 x4 x5 -1/5 -2/5 1/5 2/5 7/5 -1/5 -2/5 11/5 -9/5 -8/5 -1/5 -28/5
从表中看到 c3= -4, σ3= -9/5 可得到Δc3 ≤-σ3 = 9/5 时，即 c’3≤-4 + 9/5 = -11/5 时原最优解不变。
（1）参数在什么范围内变化时，原最优解或最优基不变—— 数据的稳定区间；
（2）当参数超出（1）的变化范围时，最优解或最优基有何变 化——如何求出新的最优解和最优基。
当模型的参数发生变化后，可以不必对线性规划问题重新 求解，而用灵敏度分析方法直接在原线性规划取得的最优结果 的基础上进行分析或求解，既可减少计算量，又可事先知道参 数的变化范围，及时对原决策作出调整和修正。
xk为换入变量
对 所 有 aik>0 计 算 θi=bi/aik 令θl=min{θi} 第l个基变量为换出变
量，alk为主元素
令 bl/alk→bl; alj/alk→ajl 对主元素列(第k列)令1→alk; 0→其它 元素表中其它行列元素 令 aij-ali/alk·aik→aij
bi-bl/alk·aik→bi бj- alj/alk· бk → бj
4
3+Δc2 x2 0 1
1/2
-1/8
0
2
σj
0 0 -3/2-Δc2 /2 -1/8+ Δc2 /8 0 14+2Δc2
17
Ci
2 3+Δc2
0
0
0
B-1b
CB XB x1 x2
x3
x4

线性规划问题的灵敏度分析

线性规划问题的灵敏度分析

a' 1, n 1
a' 1, n i
a' 1,n m
设
B 1
a' k ,n1
a' k ,ni
a' k ,n m
a
'
m
,n
1
a' m,ni
a
' m,nm
b b1, b2 , , (bk bk ), bm T
为保证最优解的基变量 不发生变化 , 必须满足
XB
B b b 0 1
注意：若碰到原问题和对偶问题均为非可行解时， 就需要引进人工变量后重新求解。
线性规划问题的灵敏度分析
最优解/最优值的变化情况； (2)分析线性规划相关参数和条件在什么范围内变化，其最优
基/最优解/最优值不变。
灵敏度分析内容：
(1)参数 Cj,bi,aij的影响分析;
(2) 增加约束或变量的影响分析；
线性规划问题的灵敏度分析
2
5.2 灵敏度分析工具与原理
(1)灵敏度分析工具
Pj’ =B-1Pj
b’=B-1b
– 已知 c6=4, p6=(2,4,5)
– 计算 x6 的检验数可知生产是否
有利
线性规划问题的灵敏度分析
18
5.7 技术系数aij的变化
约束矩阵A随之变化
若xj在最终表中为非基变量，其约束条件中系数 aij的变化分析步骤参考增加一个变量时的情形
若xj在最终表中为基变量，则aij的变化将使相应 的基矩阵B和B-1发生变化，可能出现原问题和对 偶问题均为非可行解的情况，需引进人工变量将 原问题化为可行解，再用单纯形法
σj =Cj-CBB-1Pj=Cj-CBPj’

线性规划的灵敏度分析与最优解的解释

线性规划的灵敏度分析与最优解的解释
对偶价格可能只适用于 在右端值仅发生了很小的变动时的情况。随着所获得的资 源越来越多，从而右端值越来越大，其他的约束条件也可 能会约束和限制目标函数值的变化。
3.3 灵敏度分析：计算机求解
为了使用管理科学家软件，我们使用小数代替分数。Par 公司的问题用小数形式的系数表示如下：
现在，模型的最优解540个标准袋和252个高级袋。每个目 标函数系数都有一个最优范围，即目标函数系数在什么范围 内变化，模型的最优解保持不变。
3.2 图解法灵敏度分析
3.2.1 目标函数系数 认真观察图发现，只要
目标函数直线的斜率处于 直线A（和切割与印染约 束线重合）的斜率与直线 B（与成型约束线重合） 的斜率之间，极点3 （S=540，D=252）就是最 优解的点。
则直线A和直线B的斜率都已经计算出来了，我们来看 保持极点3仍然为最优解点，应满足条件：
-3/2≤目标函数的斜率≤-7/10
3.2 图解法灵敏度分析
现在让我们考虑目标直线斜率的一般形式。用CS表示标
准袋的利润，CD表示高级袋的利润，P表示目标函数值。 使用这些标识，目标函数直线可以写成：
P=CSS+CDD 把上面方程写成斜截式，得到
第三章 线性规划的灵敏度分析与最优解 的解释
引言
灵敏度分析是研究当一个线性规划问题中的系 数发生变化时，其对函数最优解的影响程度。运 用灵敏度分析，我们可以回答以下问题： 1.如果目标函数的系数发生了变化，对最优解会产 生什么影响？ 2.如果改变约束条件的右端值，对最优解会产生什 么影响？
首先我们将介绍如何使用图解法进行双变量 线性规划问题的灵敏度分析，然后介绍如何使用 管理科学家软件得到灵敏度分析报告。
顺时针转动目标函数直线，使其斜率变成一个绝对值更 大的负数，从而斜率变小了。直到与B重合，我们又获得了 多重最优解——极点3和极点2之间都是最优点。因此B的斜 率是目标函数直线斜率的下限。

第3章 线性规划灵敏度分析与最优解的解释

第3章 线性规划灵敏度分析与最优解的解释

使用Excel Excel进行灵敏度分析 3.4 使用Excel进行灵敏度分析 LINGO的灵敏度分析报告 3.5 LINGO的灵敏度分析报告
�
x2
5 4 Q4 3 2 5x1+2x2=20 (1.5, 3.25) 4x2=13 Q3 (2,3) Q2(3,2.5) x1+2x2=8 Q1 1 2 3 4 5
1.5 X = 3.25
*
ቤተ መጻሕፍቲ ባይዱz = 19.25
*
1 0
x1
对偶价格: 对偶价格:约束条件右端项每增加一个单位引起的最优 值的改进量称为对偶价格. 值的改进量称为对偶价格.
max
z = 2 x1 + 5 x2 x1 + 2 x2 ≤ 8 5 x + 2 x ≤ 20 1 2 4 x2 ≤ 12 x1 , x2 ≥ 0
x2
5 4 3 2 1 0 Q1 1 2 3 4 5 Q4 5x1+2x2=20 Q3 (2,3) 4x2=12 Q2 (3,2.5) x1+2x2=8
线性规划的灵敏度分析与最优解的解释31灵敏度分析简介32图解法与灵敏度分析321目标函数系数322约束条件右端值204x32523直线q204x3252315325对偶价格
第3章 线性规划的灵敏度分析 与最优解的解释 3.1 灵敏度分析简介 3.2 图解法与灵敏度分析 3.2.1 目标函数系数 3.2.2 约束条件右端值
灵敏度分析: 3.3 灵敏度分析:计算机求解 Scientist) (Management Scientist)
目标函数系数的100%法则: 法则: 目标函数系数的 法则 对所有变化的目标函数系数, 对所有变化的目标函数系数,计算其占允许增加量和 允许减少量的百分比之和.如果和没有达到100%,最优 允许减少量的百分比之和.如果和没有达到 , 解就不会改变. 解就不会改变. 约束条件右端值的100%法则: 法则: 约束条件右端值的 法则 对所有变化的右端值, 对所有变化的右端值,计算其占允许增加量和允许减 少量的百分比之和.如果和没有达到100%,对偶价格就 少量的百分比之和.如果和没有达到 , 不会改变. 不会改变.

线性规划模型-灵敏度分析

线性规划模型-灵敏度分析

0.8千克B1
获利44元/千克
至多100公斤A1
制订生产计划，使每天净利润最大
• 30元可增加1桶牛奶，3元可增加1小时时间，应否投 资？现投资150元，可赚回多少？ • B1，B2的获利经常有10%的波动，对计划有无影响？
钢管下料
原料下料问题 生产中通过切割、剪裁、冲压等 手段，将原材料加工成所需大小 按照工艺要求，确定下料方案， 使所用材料最省，或利润最大
整数非线性规划模型
钢管下料问题2
增加约束，缩小可行域，便于求解
每根原料钢管长19米
需求：4米50根，5米10 根，6米20根，8米15根
4 50 5 10 6 20 8 15 26 原料钢管总根数下界： 19
引 言
由于战争的需要, 美国的经济学家T. C. Koopmans (库普曼斯) 重新独立的研究运输问 题, 并很快看到了线性规划在经济学中应用的 意义. 在这之后, 线性规划也被人们广泛地用 于军事、经济等各方面。 由于Kantorovich 和 Koopmans在这方面 的突出贡献,他们一起得到1975年诺贝尔经济 学奖。 为更好地理解线性规划所描述的问题， 我们先看一个例子。
原料最多增加10 时间最多增加53
• 35元可买到1桶牛奶，每天最多买多少？ 最多买10桶!
例2 奶制品的生产销售计划 在例1基础上深加工
1桶 牛奶 或 3千克A1 12小时 1千克 获利24元/千克
2小时,3元 获利16元/千克 8小时 4千克A2 1千克 获利32元/千克 0.75千克B2 50桶牛奶, 480小时 2小时,3元
35 <48, 应该买！
• 聘用临时工人付出的工资最多每小时几元？ 2元！

线性规划的灵敏度分析

线性规划的灵敏度分析

资源有剩余，在 最优解中就有对 应松弛变量存在， 且其影子价为 0
影子价为 0， 资源并不一定有 剩余
4
5.2 价值系数 cj 的灵敏度分析
• cj 变动可能由于市场价格的波动，或生产成本的变动 • cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分
析cj 允许的变动范围cj • cj 的变化会引起检验数的变化，有两种情况:
1300 4.25 5 5.75 4 0 0.25 1
zj-cj 3.25 0 2.75 0 0 0.25 1
c c j k

由于基变m量对应的价值系数 cj 在CB中出现，
2 基变量 zj zj (cjk c因jki )此ai它j 会影c响jk a所ij 有非cj基k a变kj (量z的j 检验zj数) 。
5.4 （技术系 数 aij 的灵敏 度分析）暂不 讲授(转5.5）
技术系数aij变化的影响比较复杂
对应基变量的 aij ，且资源bi已全部用完 对应基变量的 aij ，但资源bi未用完 对应非基变量的 aij ，且资源bi全用完或未用完
1、对应基变量的 aij ，且资源bi已全部用完 aij=0 2、对应基变量的 aij ，但资源bi未用完 aijxn+i /xj
3
z8c8 qiai8c8(5040.2 531)9 i1
50
结论：生产x8有利。 将B–1P8加入最优单纯型表中，以x8为入基变量进行迭代。 （过程学生完成）
17
5.6 新增约束 条件的分析
1、将最优解代入新的约束条件，若满足，则最优解不变 2、若不满足，则当前最优解要发生变化；将新增约束条件
(x)
b
i
i1
(C
B

运筹学：第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

线性规划(5)


若要保证最优解不变，必须有：-5+0.5a≤0，a≤10 -15-1.5a≤0，a≥-10 即-10≤a≤10，c1在[40,60]之间变化，最优解不变。 仍为：x1=15,x2=20;但最优值将随着c1的增大而增大；缩小而 缩小。那么c2=30在多大范围内发生变化，最优解不变？
2、b1=120，问b1在多大范围内发生变化最优基不变，最优 解和最优值是否发生变化？ 设b1变化为b1+a， 由最终单纯形表和初始单纯形表可以看出，基矩阵B和B-1分别为：
0 x4 2 1 -1 -1
0 x5 -5 -1 2 -3
xB
0 5 4
X3 25 X1 35 X2 10 cj
松弛变量的检验数对应着对偶问题的最优解。
而且是这三种资源的影子价格。
即∶资源一的影子价格为=y1=-c3=0
资源二的影子价格为=y2=-c4=1 资源三的影子价格为=y3=-c5=3
分析∶资源一的影子价格为0，说明增加这种资源
引例：生产计划问题
胜利家具厂生产桌子和椅子两种家具。桌 子售价50元/个，椅子销售价格30/个，生产 桌子和椅子要求需要木工和油漆工两种工 种。生产一个桌子需要木工4小时，油漆工 2小时。生产一个椅子需要木工3小时，油 漆工1小时。该厂每个月可用木工工时为 120小时，油漆工工时为50小时。问该厂如 何组织生产才能使每月的销售收入最大？
2 1 5 5 1 B 1 1 * 3 3 2 3 2 2
C3 X3 -1 2 0 X4 1 -1/2 -5 0 X5 -2 3/2 -15 20 15 1350 b
C3-70
若希望生产书柜，那么就需要把X3变为基变量，则要求 C3-70 ≥0， 即C3 ≥70元生产书柜有利。

第三章 线性规划的灵敏度分析和最优解的解释

3
3.1 灵敏度分析简介
灵敏度分析是研究线性规划的参数(非可控输入)发生 变化对最优解的影响程度
线性规划的参数包括：
• 目标函数系数 • 约束条件右侧值 • 约束条件系数矩阵
最优解中包含的信息：
• 目标函数值 • 决策变量值 • 递减成本(reduced cost) • 松弛/剩余变量
4
3.1 灵敏度分析简介
利用Lingo 软件做灵敏度分析
16
17
利用Excel做灵敏度分析
Microsoft Excel 16.0 敏感性报告 工作表: [数据模型与决策第3章例题.xlsx]第三章例题1 报告的建立: 2021/5/29 10:48:56
可变单元格
单元格 $B$15 $C$15
名称 决策变量值 x1 决策变量值 x2
作者
John Loucks
St. Edward’s University
1
第三章 线性规划的灵敏度分析和最优解的解释
3.1 灵敏度分析简介 3.2 目标函数系数变化的分析 3.3 约束条件右端值变化的分析 3.4 传统灵敏度分析的局限性
2
第三章 线性规划的灵敏度分析和最优解的解释
3.1 灵敏度分析简介 3.2 目标函数系数变化的分析 3.3 约束条件右端值变化的分析 3.4 传统灵敏度分析的局限性
6
x1 < 6
2x1 + 3x2 < 19 x1 + x2 < 8
x1, x2 > 0
固定x2的系数7，改变x1 的系数
5
最优解:
Max 14/3x1 + 7x2
4
x1 = 5, x2 = 3
3
Max 7x1 + 7x2

线性规划的灵敏度分析

23
,
b3
33
5
1
,
5 1
,
15
1
5,5,15
故有 15 b3 5,b3 在[0，20]上变化时最优基不变。
若线性规划模型是一个生产计划模型，当求出cj或bi 的最大允许变化范围时，就可随时根据市场的变化来掌握 生产计划的调整。
灵敏度分析方法还可以分析工艺系数aij的变化对最优解 的影响，对增加约束、变量或减少约束、变量等情形的分 析，下面以一个例子来说明这些分析方法。
（8）增加新约束 5x1 x2 2x3 10
§2.4 灵敏度分析
Ch2 Dual Problem
Sensitivity Analysis
2023年2月1日星期三 Page 19 of 34
【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如2－7所 示。
表2－7
Cj
2 -1
4
0
0
0
b
CB XB x1
x2
x3
x4
x5
x6
4 x3 0 5/7
1
1/7 3/7
0
2
2 x1 1 2/7
0 －1/7 4/7
0
1
0 x6 0 －2
0
0
－1
1
1
λj
0 －31/7 0 －2/7 －20/7 0
§2.4 灵敏度分析 Sensitivity Analysis
Ch2 Dual Problem
2023年2月1日星期三 Page 20 of 34
§2.4 灵敏度分析 Sensitivity Analysis
cj
－2 1
－4
0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
物流管理系
Par问题的数学描述
max 10S+9D
S.t.
7 S1D630 切割与印染 10
1S5D600 缝合 26
1S 2D708 成型 3
1 S1D135 检查与包装 10 4
S，D≥0
灵敏度分析
研究当一个线性规划问题中的系数发生变化时， 其对目标函数最优解的影响程度。
1．如果目标函数的系数发生变化，对最优解会 产生什么影响？
灵敏度分析：计算机求解
使用管理科学家软件求解Par公司的线性规划问 题。
最优解 松弛/剩余变量
目标函数最优解
对偶价格
减少的成本—目 标函数的每个系数 应提高多少，目标 函数的变量值才能
是正数
目标系数范围
右端值范围——对偶价格适用范围的限制条件
多系数同时变化——100%法则
假设，Par公司的会计部门发现原来高档袋和标准袋的利 润计算——分别为10美元和9美元有误，正确的利润分 别应该是11.50美元和8.25美元。
max S.t.
10S+9D
8.5 7 S1D630
10
切割与印染
1S5D600
2
6
缝合
1S 2 D708 3
成型
1 S1D135 10 4
检查与包装
S，D≥0
灵敏度分析简介（2）
问题——模型中的系数哪个更能左右最优解？
max 10S+9D
(6.67-14.29) (8.9-9.25)
S.t.
2．如果改变约束条件右边的值，对最优解会产 生什么影响？
主要内容
灵敏度分析简介 图解法灵敏度分析 灵敏度分析：计算机求解 多于两个决策变量的情况
灵敏度分析简介（1）
问题——如果我们要用LP模型去解决实际问题，模型中 的系数就不可能是一成不变的。这些系数的变化会对模 型的最优解产生什么样的影响呢？
新的目标函数值 10×527.5+9×270.7 5=7711.75美元，
利润增量7711.757668.00=43.75美元。
利润增加率 43.75/10=4.375美 元。
对偶价格
约束条件右端值每增加一个单位引起的最优解的增加量。 对偶价格可以用来求出当某个约束条件右端值变化一个单位
时目标函数值将会有什么变化。 对偶价格只适用于约束条件的右侧值变化比较小的情况。 任何非束缚性约束条件的对偶价格都是0。 负的对偶价格告诉我们，如果使右端值增加，目标函数值不
会增加，反而会减少。在最小化问题中，目标函数结果变得 更坏意味着总成本的增加。 影子价格——每增加一个单位的约束条件右端值最优解的变 化量。一般来说，对于最大化问题，影子价格和对偶价格相 同；对于最小化问题，影子价格是对偶价格的相反数。
主要内容
灵敏度分析简介 图解法灵敏度分析 灵敏度分析：计算机求解 多于两个决策变量的情况
假设标准袋的利润增加到13美元，高档袋的利润减少到8美元。
6.3CS1.35
新的目标函Байду номын сангаас的斜率：
6.6 7CD1.2 49
CS 131.625 CD 8
右端项
假设Par公司的切割印染部门又多出了10个小时的可 工作时间。
新的约束条件： 7 S1D640 10
运用图解法
新的最优解
S=527.5， D=270.75。
第一步：目标函数直线斜率的范围 直线B斜率≤目标函数的斜率≤直线A的斜率
3目标函数的斜 7率
2
10
第二步：目标函数系数的范围
P=CSS+CDD
3CS 7
2
CD
10
6.3CS1.35
6.6 7CD1.2 49
另一例——目标函数继续旋转
CS 3
CD
2
多系数同时改变
3CS 7 2 CD 10
总产量约束 时间约束
关于对偶价格的解释
小于等于型约束条件的对偶价格总是大于或等于0的，因为 增加其右端值不会使目标函数变得更坏。
大于等于型约束条件的对偶价格总是小于或等于0的，因为 增加其右端值不会对最优解有所改进。
当约束条件的右端值表示某种资源的可利用量时（沉没成 本），对偶价格通常可以解释为公司对额外支付一单位这种 资源所愿意提供的金额。
7 S1D630 10
切割与印染
1S5D600
2
6
缝合
1S 2 D708 3
成型
1 S1D135 10 4
检查与包装
S，D≥0
灵敏度分析简介（3）
问题——右端值变化对最优解有什么影响？
max S.t.
10S+9D
利润
7 S1D630 10
切割与印染
1S5D600
2
6
缝合
1S 2 D708 3
例：假设切割与印染部门能够获得额外的20小时时间， 同时成型部门能够获得额外的100小时时间。对偶价格 是否适用？
计算机输出的解释——
M&D公司的最小化问题
min 2A+3B s.t.
1A ≥125 产品A的需求量 1A + 1B ≥350 总产量 2A + 1B ≤600 生产时间 A，B ≥0
1.50美元。占总允许增加量的 （0.75/2.333 30）
（1.50/3.499 93）
×100%=32.14%。
×100%=42.86%。
可行增加（42.86%）和可行减少（32.14%）百分率变化的 和是75.00%。
约束条件右端值的100%法则
对所有变化的右端值，计算其占允许增加量和允许减少 量的百分比之和。如果没有达到100%，对偶价格就不会 改变。
目标函数系数S的上限是13.499 D的下限是6.6667，允许减少量：
93，允许增加量：上限-目前值 目前值-下限=9-6.6667
=13.49993-10=3.49993。标 =2.33330。高档袋的利润减少
准袋的利润增加到11.50美元， 了0.75（从9美元到8.25美元）
增加了（从10美元到11.50美元） 美元，占允许减少量的
允许增加量——对于目标函数的系数，在不超过最优范 围的情况下，系数可能增加的最大量；
允许减少量——在不低于最优范围下限的情况下，系数 可能减少的最大量。
目标函数系数的100%法则
对所有变化的目标函数系数，计算其占允许增加量和允许减少量 的百分比之和。如果和没有达到100%，最优解就不会改变。
成型
1 S1D135 10 4
检查与包装
S，D≥0
图解法灵敏度分析
目标函数系数变化——多系数同时改变 右端项改变
目标函数系数
问题——目标函数系数变化会对Par公司的最优 产量产生什么样的影响。
目标函数的最优范围——目标函数系数在什么范 围内变化时，模型的最优解保持不变。
目标函数系数
目标函数系数