线性规划灵敏度分析ppt演示文稿.ppt

文档介绍：Chapter 2线性规划灵敏度分析
上海工程技术大学——管理学院
1
Chapter 2 灵敏度分析
本章提要 Content
单纯形法的矩阵描述
改进单纯形法
对偶问题提出
线性规划对偶理论
对偶问题的基本性质
影子价格
对偶单纯形法
灵敏度分析
案例分析及Matlab求解 <br****题
2
Chapter 2 灵敏度分析
单纯形法的矩阵描述？
单纯形法矩阵的描述
标准型
maxZ=CX
AX=b
X  0
已知：A、b、c
A=(NB)
B=E
3
Chapter 2 灵敏度分析
用非基变量表示基变量
Z= CBB-1b + (CN - CBB-1 N)XN
XB =B-1 b-B-1 NXN
CBB-1b CN - CBB-1 N O
B-1 b B-1 N E
CBB-1b C - CBB-1 A
B-1 b B-1 A
4
Chapter 2 灵敏度分析
C - CBB-1A= (CN CB )- CBB-1 (NB )
= (CN - CBB-1N, CB -CBB-1B)
B-1A= B-1(NB )= (B-1N, B-1B)
单个检验数：λj = Cj - CBB-1 Pj
某列
Pj = B-1 Pj
5
Chapter 2 灵敏度分析
改进单纯形法
对
maxZ=CX
AX  b
X0
A=(P1 P2 … Pn)
(1)、已有初始可行基B，求B-1 ， XB = B-1 b
(2)、计算λj = Cj -CB B-1Pj 若全部 λj 0，则计算Z0 = CB B-1 b, 停；否则，取λm+k =maxλj ， Xm+k换入。
λj&gt;0
6
Chapter 2 灵敏度分析
(3)、计算Pm+k = B-1Pm+k ，若Pm+k 0，则无有限最优解, 停；否则
θ=min
bi
Aim+k
arm+k &gt;0
=
br
arm+k
Xr 换出
(4)、最小θ比值法：
(5)、新基B。转(1)。
7
Chapter 2 灵敏度分析
对偶问题提出
问题一：某公司在计划期内要安排生产I II两种产品已知生产单位产品所需的设备台时及A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？

　　如何安排方案？
举例
有哪些
方面可以考虑呢？
8
Chapter 2 灵敏度分析
先根据图表来列出模型
　　　　 Max Z= 2X1+3X2
X1+2X2 ≤8
　　　　　4X1 ≤16
　　　　　　　　 4X2 ≤12
　　　　　X1, X2 ≥0
II，,,分别表示出租单位设备台时的租金和出让单位原材料A,,作如下比较:若用一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有 Y1+4Y2 ≥2
举例
9
Chapter 2 灵敏度分析
同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有
2Y1+4Y3 ≥3
把工厂所有设备台时和资源都出租和出让,其收入为
f= 8Y1+16Y2+12Y3
从工厂决策者的角度来看W当然是越大越好,但从接受者眼光来说W是越少越好,所以工厂决策者只可以在满足≥ 所有产品的利润条件下,
f= 8Y1+16Y2+12Y3
Y1+4Y2 ≥2