灵敏度分析
1、什么是灵敏度分析？
是指研究线性规划模型的某些参数(bi, cj, aij）或限制量（xj, 约束条件）的变化对最优解的影响及其程度的分析过程<也称为优化后分析>。
含义和研究对象
.
回答两个问题：
①这些系数在什么范围内发生变化时，最优解不变？
②系数变化超出上述范围，如何用最简便的方法求出新的最优解？
2、灵敏度分析的研究对象：
目标函数的系数 cj 变化对最优解的影响；
约束方程右端系数 bi 变化对最优解的影响；
约束方程组系数矩阵 A 变化对最优解的影响 ；
含义和研究对象
4. 分析增加一个约束条件的变化
灵敏度分析的主要内容
1. 分析 cj 的变化
2. 分析 bi 的变化
3. 分析增加一个变量 xj 的变化
5. 分析系数 aij 的变化
系数矩阵A
.
对偶问题决策变量的最优解<影子价格>：
初始单纯形表
最优单纯形表
X*=B-1b
CN－CBB-1N ≤0
－CBB-1 ≤0
原问题基变量的最优解：
Z*=CBB-1b
最优值：
Y*T= CBB-1
Y*T= CBB-1
XB
I
0
基变量
非基变量
XB
基变量 基变量 基可
系数 行解
CN－CBB-1N
B-1N B-1
XN Xs
B-1b
CB
B-1b
－CBB-1
Z*=CBB-1b
分析 cj 的变化
原问题
对偶问题
结论或继续计算的步骤
可行解
可行解
非可行解
非可行解
可行解
非可行解
可行解
非可行解
问题的最优解或最优基不变
用单纯形法继续迭代求最优解
用对偶单纯形法继续迭代求最优解
引进人工变量，编制新的单纯形表重新计算
最优值可能已变
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = 2x1 + 3x2
4x1 ≤ 16
5x2 ≤ 15
变化
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = (2 +λ1) x1 + (3 +λ2) x2
4x1 ≤ 16
5x2 ≤ 15
q
i
分析λ1和λ2分别在什么范围变化时，最优解不变？
例1
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = 2x1 + 3x2
4x1 ≤ 16
5x2 ≤ 15
变化
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = (2 +λ1) x1 + (3 +λ2) x2
4x1 ≤ 16
5x2 ≤ 15
q
i
当λ2=0时，将λ1 反映
在最终单纯形表中，可得
从而，表中解仍为最优
解的条件是
即当
时问题的最优解不变。
例1
分析λ1和λ2分别在什么范围变化时，最优解不变？
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = 2x1 + 3x2
4x1 ≤ 16
5x2 ≤ 15
变化
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = (2 +λ1) x1 + (3 +λ2) x2
4x1 ≤ 16
5x2 ≤ 15
q
i
当λ1=0时，将λ2 反映
在最终单纯形表中，可得
从而，表中解仍为最优
解的条件是
即当
时问题的最优解不变。
例1
分析λ1和λ2分别在什么范围变化时，最优解不变？
B-1N B-1
Y*T= CBB-1
XB
I
0
基变量
非基变量
XB
基变量 基变量 基可
系数 行解
CN－CBB-1N
XN Xs
B-1b
CB
B-1b
－CBB-1
Z*=CBB-1b
原问题
对偶问题
结论或继续计算的步骤
可行解
可行解
非可行解
非可行解
可行解
非可行解
可行解
非可行解
问题的最优解或最优基不变
用单纯形法继续迭代求最优解
用对偶单纯形法继续迭代求最优解
引进人工变量，编制新的单纯形表重新计算
分析 bi 的变化
最优解或最优值可能已变
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = 2x1 + 3x2
4x1 ≤ 16
5x2 ≤ 15
变化
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12 +λ1
z = 2 x1 + 3 x2
4x1 ≤ 16 +λ2
5x2 ≤ 15 +λ3
分析λi分别在什么范围变化时，最优基不变？
例2
q
i
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12
z = 2x1 + 3x2
4x1 ≤ 16
5x2 ≤ 15
变化
x1, x2 ≥0
max
.
2x1 + 2x2 ≤ 12 +λ1
z = 2 x1 + 3 x2
4x1 ≤ 16 +λ2
5x2 ≤ 15 +λ3
例2
解：
先分析λ1的变化范围:
为使最优基不变，则需 , 即
从而得到
同理可得λ2与λ3的取值范围
分析λi分别在什么范围变化时，最优基不变？
增加一个约束条件
在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，
所以需要增加约束条件。
1）若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。
2)若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。
例3增加约束
CB
XB
cj
2
3
3
0
0
xj
b
x1
x2
x3
x4
x5
0
x4
3
1
1
1
1
0
0
x5
9
1
4
7
0
1
0
x6
5
2
2
1
0
0
2
x1
1
1
0
-1
4/3
-1/3
3
x2
2
0
1
2
-1/3
1/3
0
x6
5
2
2
1
0
0
－Ｚ
-8
0
0
-1
-5/3
-1/3
0
x6
0
0
1
0
0
1
0
CB
XB
cj
2
3
3
0
0
xj
b
x1
x2
x3
x4
x5
0
x4
3
1
1
1
1
0
0
x5
9
1
4
7
0
1
2
x1
1
1
0
-1
4/3
-1/3
3
x2
2
0
1
2
-1/3
1/3
例3增加约束
CB
XB
cj
2
3
3
0
0
0
xj
b
x1
x2
x3
x4
x5
x6
2
x1
1
1
0
-1
4/3
-1/3
0
3
x2
2
0
1
2
-1/3
1/3
0
0
x6
5
2
2
1
0
0
1
2
x1
1
1
0
-1
4/3
-1/3
0
3
x2
2
0
1
2
-1/3
1/3
0
0
x6
-1
0
0
-1
-2
0
1
-8
0
0
-1
-5/3
-1/3
0
最小比值
1
5/6
例3增加约束
CB
XB
cj
2
3
3
0
0
0
xj
b
x1
x2
x3
x4
x5
x6
2
x1
1/3
1
0
-5/3
0
-1/3
2/3
3
x2
13/6
0
1
13/6
0
1/3
-1/6
0
x4
1/2
0
0
1/2
1
0
-1/2
0
0
-1/6
0
-1/3
-5/6
A中元素改变
如果N中数据改变，可以用增加一个变量来处理
如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解
出基
变量
判断
参数
CB
基
b
cj→
cj － zj
≤0
单纯形法:保持可行性，调整最优性
基变
量的
系数
目标函数中变量的系数
决策变量
约束方程组
的系数矩阵
方程
右端
常数
项
各变量的检验数
基
变
量
出发
在迭代运算中设法保持约束常数非负（原问题可行），同时逐个调整检验数，使之全部≤0（对偶问题可行），得最优解。
终止
有若干个>0
≥0
出基
变量
判断
参数
CB
基
b
cj→
cj － zj
≤0
对偶单纯形法:保持最优性，调整可行性
基变
量的
系数
目标函数中变量的系数
决策变量
约束方程组
的系数矩阵
方程
右端
常数
项
各变量的检验数
基
变
量
迭代运算中设法保持所有检验数≤ （对偶问题可行），
把约束常数逐个调整成非负数（原问题可行），得到最优解。
出发
有
若
干
个
<0
终止
≥0
影子价格
1. 影子价格的数学分析：
定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi （第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z* 的改变量称为第 i 种资源的影子价格，其值等于D问题中对偶变量yi*。
由对偶问题得基本性质可得：
对偶问题决策变量的最优解<影子价格>：
Y*T= CBB-1
影子价格
影子价格
2. 影子价格的经济意义
1）影子价格是一种边际价格
在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即：
影子价格
2）影子价格是一种机会成本
影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。
若第i 种资源的单位市场价格为mi ，则有当yi* > mi 时，企业愿意购进这种资源，单位纯利为yi*－mi ，则有利可图；如果yi* < mi ，则企业有偿转让这种资源，可获单位纯利mi－yi * ，否则，企业无利可图，甚至亏损。
结论：若yi* > mi 则购进资源i，可获单位纯利yi*－mi
若yi* < mi则转让资源i ，可获单位纯利mi－yi
影子价格
3）影子价格在资源利用中的应用
根据对偶理论的互补松弛性定理:
Y*Xs=0 , YsX*=0
表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源的影子价格不为0时，表明该种资源在生产中已耗费完。
影子价格
4）影子价格对单纯形表计算的解释
单纯形表中的检验数
其中cj表示第j种产品的价格; 表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。
当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。
*
*
*
*
