运筹学-第七周-灵敏度分析-运输问题

第二章 对偶理论与灵敏度分析
线性规划问题的引出 | 线性规划问题的概念和模型 | 线性规划的标准型 | 线性规划模型的标准化
本章内容
对偶理论是线
性规划最重要的基
础理论之一
是进行经济分
析的重要工具
一般形式单纯形法计算的矩阵描述
设线性规划问题 : 目标函数 max z=CX 约束条件 AX≤b; 非负条件 X≥0
1 2
（ 1）
B－1
90 80 b 3
=
1 2 - 5 90 250 - 5b3 0 1 1 80 = 80 b 3 0 - 1 2 b 80 2b 3 3
最优；
（2）若c2=6，求新的最
优计划。
cj
最优单 纯形表 CB 0 5 4 XB x3 x1 x2 b 25 35 10
5
x1 0 1 0 0
4
x2 0 0 1 0 0 x4 2
0
x3 1 0 0 0 0 x5 -5
0
x4 2 1 -1 -1
0
x5 -5 -1 2 -3
σ4 = c2－5 ≤ 0 σ5 = 5－2c2 ≤ 0 5/2 ≤ c2 ≤ 5 最优解X*=（35，10， 25，0，0）保持不变。
6.影子价格可以帮助管理人员进行生产要素对产出贡献的分解；
7.影子价格可以告诉管理人员如何考虑新产品的价格。
什么是对偶单纯形法？
对偶单纯形法 是应用对偶原理求解原始线
性规划的一种方法——在原始问题的单纯形表 格上进行对偶处理。
注意：不是解对偶问题的单纯形法！
对偶单纯形法的实施
1.使用条件： ①检验数全部≤0；
线性规划问题的约束条件加入松弛变量以后，得到标准型：
max z=CX+0Xs AX+IXs=b; X，X s≥0
1 0 I 0 1 mm
矩阵A可以分块记为A=[B，N]
相应地，向量X和C可以记为
maxz C B x B C N x N 0xs s.t. Bx B NxN Ix s b xB , x N , xs 0
' a 列为主元列，主元行和主元列交叉处的元素 lk
为
主元素。
按 主元素进行换基变换 （初等行变
换），将主元素变成1，主元列变成单位向量， 得到新的单纯形表。
最优解判别法则：右端向量满足非负约束
第五节 灵敏度分析
• 以前讨论线性规划问题时，假定αij，bi, cj都是常数，但实 际上这些系数往往是估计值或预测值。
初始单纯形表
0 XS
检验数
CB XB B CB
CN XN N CN
0 XS I 0
0 b b 0
最 优 单 纯 形 表
XB CB XB I
XN B－1N
XS B－1
b B－1b
检验数
0
CN－CBB－1N
－CBB－1
－CBB－1b
当bi发生变化时，将影响所有基变量的取值
① 保持 B-1b≥0, 当前的基仍为最优基，最优解的结构不变 （取值改变）； ②（ B-1b）i<0, 当前基为非可行基，但是仍保持为对偶可行


z C B (B b B NX N B X S ) C N X N C B B b (CN C B B N)X N C B B X S
1 1 1
1
1
1
max Z C B X B C N X N 0 X S BX B NX N EX S b X B , X N , X S 0
新问题：如开发出一种新产品，已知其有关工艺参数（或
消耗的资源量）和单位产品利润，设该种产品的产量为
xn+1，则cn+1和Pn+1已知，需要进行“是否投产”的决策。
（1）增加1个新变量：相当于系数阵A增加1列
max z c1 x1 c2 x2 cn xn cn1 xn1
0
1 0 0 0 1 0
0
0 1 0 0 0 1
1
0 0 0 1/2 -1/2 1/2
[2]
1 -1 1 1 0 0
-5
-1 2 -7 -5/2 3/2 -1/2
σj
0
0
-1/2
0
-9/2
x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2
2. 右端常数bi (资源系数)的变化分析
cj
5 b 25 35 10 x1来自0 1 0 04 x2 0 0 1 0
0 x3 1 0 0 0
0 x4 2 1 -1 -1
0 x5 -5 -1 2 -3
最优
单纯 形表
CB 0 5 4
XB x3 x1 x2
最优基：
1 B－ 1 = 0 0
B=（P3，P1，P2）
2 1 -1
最优单纯形表的A中 - 5 松弛变量的系数
1. 将参数的改变通过计算反映到最终单纯形表上
2. 检查原问题和对偶问题是否还是可行解 3. 按照下表所列情况分别进行讨论
原问题 可行解 可行解 对偶问题 可行解 非可行解 结论或继续计算方法 问题的最优解保持不变 用单纯形法继续求解
非可行解
非可行解
可行解
非可行解
对对偶单纯形法求解
引用人工变量，构造基，重新计算
及其程度的分析过程，称为线性规划的灵敏度分析。
2. 线性规划灵敏度分析的内容
目标函数的价值系数变化
max z=CX
约束方程右端向量变化 约束方程组系数阵变化 决策变量或约束条件变化
AX=b X≥0
对解的影响主要有:
1. 最优解保持不变，即基变量和它们的取值没有变化 2. 基变量保持不变，但它们的值改变了 3. 基解完全变了
b -25 25 30
5 30 20
5 x1 0 1 0 0 0 1 0 0
4 x2 0 0 1 0 0 0 1 0
0 x3 1 0 0 0 -1/5 -1/5 2/5 -3/5
0 x4 2 1 -1 -1 -2/5 3/5 -1/5 -11/5
0 x5 [-5] -1 2 -3 1 0 0 0
3. 增加一个新决策变量xj 的变化分析 资源的合理利用问题：
（2）当cj 是基变量的价值系数——它的变化将
影响所有非基变量的检验数，
N C N CB B N
1
当cj 变化时，如能保持 N 0，则当前解仍为最优解，否则 可用单纯形法继续迭代求出新的最优解。
1 C C B N 0 将cj 看作待定参数，令 N N B
解这n-m个不等式，可算出保持最优解不变时cj的变化范围 。
基,可用对偶单纯形法求出新的最优解；
③ 如何求出保持最优基不变的bi 的范围?
把bi看作待定参数，令B-1b≥0，求解该不等式组即可。
例17：对于上例中的线性规划作下列分析：
（1）b3在什么范围内变化，原最优基不变？
（2）若b3=55，求出新的最优解。
m ax Z 5 x1 4 x 2 x1 3 x 2 90 2 x1 x 2 80 x1 x 2 45 x1 , x 2 0
z C B (B1b B 1 NX N B 1 X S ) C N X N C B B 1b (CN C B B 1 N)X N C B B 1 X S
初始单纯形表
0 XS 检验数
CB XB B
CB
XB
CN XN N
CN
XN B－1N
0 XS I
0
0 b b
右端向量列≥0——已得最优解； 右端向量至少一个元素<0,转下步;
右端向量列≥0——原始单纯形法；
至少一个检验数>0
至少一个元素<0,另外处理；
基变换： 先确定换出变量——右端向量列中的
负元素（一般选最小的负元素） 对应的
基变量出基；
min ( B b)i ( B b)i 0 ( B b)l , 则 选xl出 基 ，
②右端向量列至少一个元素 < 0；
2. 实施对偶单纯形法的基本原则：
在保持对偶可行的前提下进行基变换——每一次迭代
过程中取出基变量中的一个右端负分量作为换出变量去替 换某个非基变量（作为换入变量），使原始问题的非可行 解向可行解靠近。
3. 计算步骤：
① 建立初始单纯形表，计算检验数行。
检验数全部≤0 （非基变量检验数<0）
可行性 B－1b ≥0 最优性CN－CBB－1N ≥0
LP灵敏度分析最终回答： 1. 这些系数在什么范围内变化时，原先求出的线性规 划问题的最优解或最优基不变。 2. 如果系数的变化超出了上述范围，如何用最简便的方 法求出新的最优解。 计算量少，充分利用到原 最优的单纯形表结果
三、灵敏度分析的步骤
XB X , X N
C
C , C
B N
XB=B-1b — B-1NXN — B-1Xs
对于一个确定的基B，目标函数z可以写成
XB z C X C B , C N . C B X B C N X N X N
目标函数z用非基变量表出的形式
cj CB 0 XB x3 b 25
5 x1 0
c2 x2 0
0 x3 1
5
c2
x1
x2
35
10
1
0 0
0
1 0
0
0 0
1
-1 c2 - 5
-1