第二章--线性规划的对偶理论与灵敏度分析- -运筹学.ppt

清华大学出版社
《运筹学教程》(第二版)
运筹学基础
胡运权主编
教材
例一
美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ。
设: x1—— A产品的生产量 x2—— B产品的生产量
利润 max z= 2 x1 + x2
约束条件
5x2 ≤ 15
6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
st .
5x2 + x3 = 15
6x1 + 2x2 + x4 = 24
x1 + x2 + x5 = 5
x1,x2 ,x3 ,x4 ,x5 ≥ 0
约束条件
st .
利润 max z= 2 x1 + x2 + 0x3 + 0x4 + 0x5
一、标准化
二、写出初始单纯形表(必定存在有单位矩阵)
C
2 1 0 0 0
θ
CB
XB
b
x1 x2 x3 x4 x5
0
0
0
x3
x4
x5
15
24
5
0 5 1 0 0
6 2 0 1 0
1 1 0 0 1
σ
2 1 0 0 0
三、最优解检验(唯一解、无限多解、无界解和无解)
X*=(7/2,3/2,15/2,0,0)
Z*= 17/2
C
2 1 0 0 0
θ
CB
XB
b
x1 x2 x3 x4 x5
0
2
1
x3
x1
x2
15/2
7/2
3/2
0 0 1 5/4 -15/2
1 0 0 1/4 -1/2
0 1 0 -1/4 3/2
σ
0 0 0 -1/4 -1/2
5x2 ≤ 15
6x1 + 2x2 ≤ 24
x1 + x2 ≤ 5
x1,x2 ≥ 0
约束条件
把解X=(7/2,3/2)代入原问题(因为x3、 x4、 x5为附加变量)
四、分析
5×3÷2=15/2
24
5
A有空闲
B设备已经饱和
调试工序也已经满负荷
一个问题?
市场上设备A、设备B和调试工序每小时值多少钱?在什么价位时,才能使美佳公司愿意出让自己的资源?
<
=
=
6y2 + y3
分
析
设: y1 —设备A值的价值 y2 —设备B值的价值
y3 —调试工序值的价值
≥
2
5y1 + 2y2 + y3
1
≥
z= 15 y1 + 24y2 + 5y3
总价值
min
y1 , y2 , y3
≥
0
st .
例一
6y2 + y3
≥
2
5y1 + 2y2 + y3
1
≥
z= 15 y1 + 24y2 + 5y3
min
y1 , y2 , y3
≥
0
st .
z'= -15 y1 - 24y2 - 5y3
max
st .
6y2 + y3 – y4
=
2
5y1 + 2y2 + y3 – y5
1
=
y1, y2, y3, y4, y5
≥
0
C
-15 -24 -5 0 0 -M -M
θ
CB
YB
b
y1 y2 y3 y4 y5 y6 y7
-M
-M
y6
y7
2
1
0 6 1 -1 0 1 0
5 2 1 0 -1 0 1
σ
M-15 8M-24 2M-5 -M -M 0 0
问题求解
6y2 + y3
≥
2
5y1 + 2y2 + y3
1
≥
z= 15 y1 + 24y2 + 5y3
min
y1 , y2 , y3
≥
0
st .
z'= -15 y1 - 24y2 - 5y3
max
st .
6y2 + y3 – y4
=
2
5y1 + 2y2 + y3 – y5
1
=
y1, y2, y3, y4, y5
≥
0
C
-15 -24 -5 0 0
θ
CB
YB
b
y1 y2 y3 y4 y5
-24
-5
y2
y3
1/4
1/2
-5/4 1 0 -1/4 1/4
15/2 0 1 1/2 -3/2
σ
-15/2 0 0 -7/2 -3/2
Y=(0, ¼, ½ , 0, 0)
z'=-17/2
z = 17/2
问题求解
Y=(0, ¼, ½ , 0, 0 )
问题分析
问题
的解
6y2 + y3
≥
2
5y1 + 2y2 + y3
1
≥
z= 15y1 + 24y2 + 5y3
min
y1 , y2 , y3
≥
0
st .
问题:
?
原问题:
利润 max