当前位置：文档之家 › 线性规划的灵敏度分析与应用知识点总结

线性规划的灵敏度分析与应用知识点总结

  • 格式：docx
  • 大小：37.40 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

3.5 线性规划灵敏度分析(一)

3.5 线性规划灵敏度分析(一)

当这些数据的变化超出了范围，如何作微小的调整，在原有的最优
基（或最优解）的基础上求出新的最优基（或最优解）。
3
显然，当线性规划问题中某一个或几个系数发生变化后，原来已 得结果一般会发生变化。
当然可以用单纯形法从头计算，以便得到新的最优解。这样做很 麻烦，而且也没有必要。
因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，
可见, 当cr 变化Δcr 后, 最终表中的检验数是
10
当cr 变化Δcr 后, 最终表中的检验数是
若要求原最优解不变, 即必须满足 'j 。0于是得到
当 arj
0,
cr
j
arj
;
arj
0,
cr
j
arj
;
j
= 1,2,, n
Δcr 可变化的范围是
max
j
j
arj
arj
0
cr
min
j
j
arj
(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是 m
σj=cj-CBB-1Pj 或
j = c j − aij yi
当cj变化Δcj后，要保证最终表中这个检验数仍小i=1于或等于零，即
σj’ =cj-CBB-1Pj≤0
那么cj+Δcj≤YPj，即Δcj的值必须小于或等于YPj-cj，才可以满足原最
因此可以把发生变化的个别系数，经过一定计算后直接填入最终 计算表中，并进行检查和分析 系数发生变化后原问题与对偶问题的变化情况
4
1 资源数量变化的分析
资设源规数划量问变题化的是其指他资系源数中都某不系变数。b这r发样生使变最化终，表即中b原r′=问br题+Δ的br解。相并假应 地变化为

3.6 线性规划灵敏度分析(二)

3.6 线性规划灵敏度分析(二)

解 把改进工艺结构的产品Ⅰ看作产品Ⅰ′， x1′为其产量。于是在原计
算的最终表中以x1′代替x1，计算对应x1′的列向量。
B −1P1'
=
0 −2
0.25 0.5
0 2 1.25 1 5 = 0.5
0.5
− 0.125
0
2
0.375
同时计算出x1′的检验数为
c1′-CBB-1P1′=4-(1.5,0.125,0)(2,5,2)T=0.375
7
例 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例 若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数 向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什 么影响?
解 把改进工艺结构的产品Ⅰ看作产品Ⅰ′， x1′为其产量。于是在原计
算的最终表中以x1′代替x1，计算对应x1′的列向量。
(P '1 P2
Pm )x 'B + NxN + xs = b
B−1(P '1 P2
Pm )x 'B + B−1NxN + B−1xs = B−1b
6
例 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例 若原计划生产产品Ⅰ的工艺结构有了改进，这时有关它的技术系数 向量变为P1′=(2,5,2)T，每件利润为4元，试分析对原最优计划有什 么影响?
解 以x1′代替x1，并计算列向量
0
B −1P1'
=
−
2
0.5
0.25 0.5 − 0.125
0 4 1.25
1 5 = − 3.5
0
2
1.375
x1′的检验数为c1′-CBB-1P1′=4-(1.5,0.125,0)(4,5,2)T = -2.625。

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

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

初始单纯形表 x1 x2 1 2 8 x3 1 2 6 x4 1 0 0 x5 0 1 0 bi
12 12
b2 20
0
0
x4 x5 f
1 1 5
0
最优单纯形表 x1 x2 0 1 0 x3 0 1 2 x4 2 1 2 x5 1 1 3 bi 424-b
2
5 x1 8 x2
f
1 0 0
实例1
产品 资源 原料甲 原料乙 A 1 1 5 B 1 2 8 C 1 2 6 资源拥 有量 12kg 20kg
利润 （元/kg）
在实例1中，假设产品C 的资源消耗量由 试分析最优解的变化情况。
1 2
2 变为 1
，
x4 x5 f
x1 1 1 5
•设XB=B1b是最优解，则有XB=B1b 0
•b的变化不会影响检验数 •b的变化量b可能导致原最优解变为非基可行解 设b’=b+ b 为保证最优基不变，必须满足XB=B-1b’ 0
1. 分析b1=16和b2=20时，最优基和最优解的变化
初始单纯形表 x1 x4 x5 f 1 1 5 x2 1 2 8 x3 1 2 6 x4 1 0 0 x5 0 1 0 bi
5 x1 8 x2
f
1 0 0
保持b1=12,分析b2在什么范围内 变化时，最优基不变?
2 B b' 1
1
1 12 1 b2
24 b 2 12 b 2
0
解之得：12≤b2≤24
即:当12≤b2≤24时，最优基不变
3.2 增加新约束条件的分析
产品 资源 原料甲 原料乙 原料丙 利润 （元/kg）

第二章 线性规划问题的对偶理论与灵敏度分析总结

第二章 线性规划问题的对偶理论与灵敏度分析总结

第二章 线性规划问题的对偶理论与灵敏度分析总结一．对偶问题统一归纳表注意：对偶问题允许i b 小于0，也正是对于原问题i b 小于0，才引入了后面的对偶单纯形法解决问题。

二．对偶问题的基本性质⎩⎨⎧≥≤=0X ..max 设原问题为b AX t s CXz⎩⎨⎧≥≥=是列向量,0A .. min 对偶问题为TY Y C Y t s Yb TTω1.对称定理：对偶问题的对偶是原问题2.弱对偶性定理：若Y X 和分别是原问题和对偶问题的可行解，则有b TY X C ≤推论（1）max 问题的任一可行解的目标是对偶问题最优目标值的一个下界。

min 问题的任一可行解的目标函数 值是原问题最优目标值的一个上界。

（2）若原问题可行且其目标函数值无界，则对偶问题无可行解。

反之对偶问题可行且其目标函数值无界，则原问题无可行解。

（3）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而原问题无可行解，则对偶问题目标函数值无界。

3. 最优性定理：若Y X 和分别是原问题和对偶问题的可行解，并且b TY X C =，则X 是原问题最优解，Y 是其对偶问题的最优解4. 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。

5.互不松弛性：若Y X 和分别是原问题和对偶问题的可行解，则它们分别是最优解的充要条件是：0ˆ,ˆˆ0ˆ1j 1=<=>∑∑==i i nj ij i nj j ij i y b xa b x a y则如果，则如果练习：判断下列说法是否正确：(1) 任何线性规划问题存在并具有惟一的对偶问题；(✓)(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(✗)(3) 设j ˆx ，i ˆy 分别为标准形式的原问题与对偶问题的可行解，*j x ，*i y 分别为其最优解，则恒有n n m m**j j j j i i i i j 1j 1i 1i 1ˆˆc x c x b y b y ====≤=≤∑∑∑∑；(✓) (5) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0>，说明在最优生产计划中第i 种资源已完全耗尽；(✓) (6) 已知*i y 为线性规划的对偶问题的最优解，若*i y 0=，说明在最优生产计划中第i 种资源一定有剩余；(✗)简析：对(5)、(6)，由互补松弛性质判断，具体详见课本P59三．对偶单纯形法(1). 对偶单纯形法应用前提： 1.检验数行全部非正2.变量取值有负数(2). 对偶单纯形法计算步骤：1.确定换出基变量 取{}i rb min b =，其对应变量r x 为换出基的变量。

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

第五章线性规划问题的灵敏度分析
2 CB XB b x1 2 X1 3 1 0 x4 4 0 3 x2 3 0 OBJ=15 cj-zj 0
30 x2 x3 0 1/2 0 -1/2 10 0 -1
00 x4 x5 0 -1/5 1 4/5 0 1/5 0 -1/5
max
3 0.5

b1

min
4 0.5

a' 1,n1

a' 1,ni

a' 1, n m


设
B 1


a
'
k
,n1

a' k ,ni

a' k ,nm



a'
m,n1

a' m,ni

a'
m,nm

b b1,b2,, (bk bk ),bm T
Z0=CBTB-1b=CBb’ (2)灵敏度分析原理
（LP）最优基保持不变 σj ≤0 b’≥0
3
(3)分析结论
原问题 对偶问题
可行
可行
结论或继续计算的步骤 仍为最优解
可行 不可行 迭代求出最优（单纯形法）
不可行 可行 迭代求出最优（对偶单纯形法）
不可行 不可行 引入人工变量，编制新单纯形表 进行求解
1300 4.25 5 5.75 4
cj-zj -3.25 0 -2.75 0
00 0 x5 x6 x7 1 1/4 -1 0 1 -1 0 -3/4 1 0 0.25 1 0 -0.25 -1
x1, x3为非基变量 所以 c1 3.25, c1 4.25

线性规划的灵敏度分析

线性规划的灵敏度分析

资源有剩余，在 最优解中就有对 应松弛变量存在， 且其影子价为 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总结

第三章线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质；2、 对偶单纯形法；3、 灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方 法。

要求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§ 1对偶问题的对称形式一、对偶问题弓侧，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及 A 、B 两种原材料的消耗，该工厂每生产一件产品甲可获利 2元，每生产一件产品乙可获利 3元，问应如何安排计划才能使该工厂获利最多？解：设X i 、X 2分别为甲、乙两种产品的产量作一比较：若用一个单位台时和 4个单位原材料 A 生产一件产品甲，可获利 2元，那么生产每件产品甲的设备台 y^ 4y^ 2同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。

即:2力 4y 33将工厂所有设备台时和资源都出租和出让，其收入为则目标函数maxz 二2x 「3x 2x 「2x 2 岂8i4x 1 - 16 i4x 2 兰12约束条件-x 1,x^ 0(1)不再生产甲、乙产品，而将其出租或出售 3分别为出租单位设备台时的租金和出让单位原材料这时要考虑每种资源的定价问题，设A 、B 的附加额。

时和原材料出租和出让的收入应不低于生产一件甲产品的利润。

即:。

=8y 〔+ 16y 2 + 12y 3对工厂来说，••越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足》所有产品的利润前提下, 使其总收入尽可能小，才能实现其愿望。

为此，得到如下模型：min =8y 1 16y 212y 3"+4丫2工 2< 2y i +4y ^ 3 J j > 0 , j =1,2,3我们就称（2）为模型（1）的对偶问题。

管理运筹学 第五章灵敏度分析

3
c8 z8 c8 qi ai 8 9 (5 0 4 0.25 3 1)
i 1
50
结论：生产x8有利。
8
第五章 线性规划问题的灵敏度分析
§5.2 对cj 值的灵敏度分析
概述
•cj 变动可能由于市场价格的波动，或生产成本的 变动 •cj 的灵敏度分析是在保证最优解的基变量不变 的情况下，分析cj 允许的变动范围cj •cj 的变化会引起检验数的变化，有两种情况 –非基变量对应的价值系数变化，不影响其 它检验数 –基变量对应的价值系数变化，影响所有非 基变量检验数
概 述
• b的灵敏度分析就是研究最优解基变量保 持不变但基变量的取值可以变化的条件 下b的取值范围 • 设 XB=B1b 是最优解，则有XB=B1b0 • b 的变化不会影响检验数 • b 的变化量 b 可能导致原最优解变为非 可行解（不满足非负约束）
16
右端项 bi 的灵敏度分析
• 在将“≤”形式的约束条件变为“=”形式时，对第i行 的约束条件方程左端要加一个松弛变量Xn+i，因此， 最优解表中B-1可表示为
25
1、对应基变量的 aij ，且资源bi已全部用完 aij=0 2、对应基变量的 aij ，但资源bi未用完
xn i < aij xj
26
3、对应非基变量的 aij
设 x j为非基变量, 则有 : z 0 a kj qk j
k 1 m
设a ij变动a ij , 则有 : z z a ij qi
二、边际值的求解
以(max,)型为例：
z o 最大利润的增量 前面讨论过 qi =(CBb-1)i bi 第i种资源的增量
Zn+i=CBb-1Pn+i =(CBb-1)i

第二章线性规划的灵敏度分析




4x1 16 4x2 12
x1,x2 0
解: 下表为最优单纯形表
Ci
2
3
CB
XB
x1
x2
2
x1
1
0
0
x5
0
0
3
x2
0
1
σj
0
0
求当b1在由8变动为
12时，原最优解是否 保持不变，若变动求 出新的最优解。
0
0
x3
x4
0
1/4
-2
1/2
1/2
-1/8
-3/2
-1/8
0
B-1b
x5
参数线性规划
5.4 参数线性规划
在线性规划的实际应用中，由于某种原因，线性规划 问题的目标函数的价值系数C和约束条件的右端常数 b会随着某个参数而连续变动。
当数据随着某个参数连续变化时，研究其对最优解的 影响，即为参数线性规划问题。
目标函数的价值系数含有参数的线性规划问题 右端常数含有参数的线性规划问题
-2 x1 1
0
7/5 -1/5 -2/5 11/5
σj
0 0 -9/5+Δc3 -8/5 -1/5 -28/5
从表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 时，原最优解不变。
(2) 若 ck 是基变量的系数
设 c'k ck Δck ,为 基 变 量 的 价 值 系 数 ，则
下表为最优单纯形表,考虑基变量系数c2发生变化
Ci
2
CB
XB
x1
2
x1
1
0

第3章线性规划的灵敏度分析


又获得了10个小时的切割与印染时间，我 们可以扩展问题的可行域，如图3-3所示。可 行域变大了，现在我们考虑是否有新的解会使
目标函数值更大。运用图解法可以看出，极点 S=527.5，D=270.5是最优解点。新的目标函数 值为10×527.5 + 9×270.5=7711.75美元，比原 来利润增加了7711.75 – 7688.00=43.75美元。 因此，利润的增加率为43.75/10=4.375美元/小 时。
在式（3-2）中，我们计算出只要满足 下列条件，极点③仍然是最优点
如果CS升高到13美元，同时使CD降低到8美 元，新的目标函数斜率将变成
由于这个值要小于下限，因此当前的解 S=540,D=252不再是最优的。把CS=13，CD =8代入，可得出极点②是新的最优解。
观察最优范围，我们得出结论，无论是
（3-2） 为了计算标准袋利润最优的范围，我们 假设高级袋的利润CD＝9，代入式（3-2）， 我们得到： 从左边的不等式，我们得到
因此
从右边的不等式，我们得到
因此， 综合标准袋利润CS的极限，标准袋利润最优 范围为：
6.3≤CS≤13.5
在最初Par公司的问题中，标准袋的利润 是10美元。最优解是540个标准袋和252个高级 袋。标准袋利润CS的最优范围告诉Par公司的 管理者：在其他系数不变的情况下，只要标准 袋的利润在6.3美元与13.5美元之间，540个标 准袋和252个高级袋总是最优产量。然而值得 注意的是，即使产量不变，总的利润也可能由 于每一个标准袋利润的变化而变化。
灵敏度分析还可以用来分析模型中的系
数哪个更能左右最优解。比如，管理层认为 高级袋的利润9美元只是一个估计量。如果 通过灵敏度分析得到，当高级袋的利润在 6.67美元与14.29美元之间变化时，模型的最 优解都是540个标准袋和252个高级袋，那么 管理层就必须思考每个高级袋获利9美元这 个估计量的可信程度有多大了。管理层希望 知道如果高级袋的利润下降，最优产量会怎 样变化。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

线性规划的灵敏度分析与应用知识点总结
线性规划是一种重要的数学优化方法，它通过建立一个数学模型，
根据特定的约束条件和目标函数，求解出使目标函数取得最大（最小）值的决策变量的取值。

而灵敏度分析则是针对线性规划模型中的参数
进行变动时，目标函数值和决策变量的取值产生的变化进行评估和分析。

本文将对线性规划的灵敏度分析进行总结，并探讨其在实际应用
中的一些重要知识点。

一、灵敏度分析的基本概念和原理
灵敏度分析是指在线性规划模型中，通过变动参数的大小和取值范围，分析其对目标函数值和决策变量的解产生的影响程度。

主要包括
以下几个方面的分析内容：
1. 目标函数系数的灵敏度分析
目标函数系数表示决策变量对目标函数的贡献程度，通过改变目标
函数系数可以分析目标函数值的变动情况。

当目标函数系数发生较大
变动时，可能导致最优解的决策变量发生改变。

2. 约束条件右侧常数的灵敏度分析
约束条件的右侧常数表示资源的可利用程度，通过改变约束条件右
侧常数可以分析资源的利用程度对决策变量解的影响。

当约束条件右
侧常数发生较大变动时，可能会改变最优解的取值范围。

3. 决策变量的灵敏度分析
决策变量的灵敏度分析可以评估决策变量值的改变对目标函数值和约束条件的违背程度产生的影响。

通过改变决策变量的取值范围，可以判断最优解的稳定性和可行性。

二、灵敏度分析的具体应用
灵敏度分析在实际应用中有广泛的应用价值，主要包括以下几个方面：
1. 评估模型的可靠性
通过灵敏度分析，可以评估线性规划模型中参数的变动对解的影响程度，从而判断模型的可靠性和稳定性。

当参数变动对解的影响较小时，说明模型具有较好的鲁棒性。

2. 制定决策方案
灵敏度分析可以帮助决策者评估决策方案的可行性和稳定性，从而选取出最优的决策方案。

在实际应用中，决策者可以通过改变参数的取值范围，确定决策方案的合理范围。

3. 资源优化分配
通过灵敏度分析，可以评估资源可利用程度的变动对决策变量的解产生的影响。

在资源有限的情况下，通过调整资源的利用程度，实现资源的优化分配。

4. 建立风险模型
灵敏度分析可以帮助建立线性规划的风险模型，通过分析参数的不确定性对目标函数值和决策变量解的影响，评估决策的风险程度。

三、灵敏度分析的注意事项
在进行灵敏度分析时，需要注意以下几个问题：
1. 参数的变动范围
灵敏度分析中，参数的变动范围需要根据实际情况进行合理设定，过大或过小的变动范围可能会引起不准确的分析结果。

2. 参数的改变方式
参数的改变方式可以采用逐步增加或逐步减小的方式，以及随机变动的方式。

不同的改变方式可能会对灵敏度分析的结果产生不同的影响。

3. 模型的可行性
在进行灵敏度分析前，需要先确定线性规划模型的可行性。

如果模型本身不可行，灵敏度分析的结果可能无法提供有效的参考。

4. 模型的精确度
灵敏度分析的结果受到线性规划模型的精确度的影响。

模型中的约束条件和目标函数的表达需要准确无误，否则分析结果可能会产生误导。

综上所述，灵敏度分析在线性规划中具有重要的应用价值。

通过灵敏度分析，可以评估模型的可靠性和稳定性，帮助制定决策方案，优
化资源分配，建立风险模型等。

在进行灵敏度分析时，需要注意参数的变动范围和改变方式，确保模型的可行性和精确度。

通过合理的灵敏度分析，可以提高线性规划方法的应用效果。