06第六章--单纯形法的灵敏度分析与对偶问题(新)-2.ppt

分别用大M法和两阶段法求解下列线形规划问题,并指出解的类型
minZ=2x1+3x2+x3
x1+4x2+2x3≥8
. 3x1+2x2 ≥6
x1,x2,x3 ≥0
时间:1:40—2:10
初始单纯形表格
最终单纯形表格
第六章 单纯形法的灵敏度分析与对偶
DUAL
窗含西岭千秋雪，门泊东吴万里船
对偶是一种普遍现象
§1 单纯形表的灵敏度分析()
§2 线性规划的对偶问题 ()
§3 对偶规划的基本性质()
§4 对偶单纯形法(---前面已讲)
学****重点与难点
§1 单纯形表的灵敏度分析()
§2 线性规划的对偶问题
一、对偶问题实例
例1 某工厂生产甲、乙两种产品，要消耗A、B和C三种资源，已知每件产品对这三种资源的消耗、：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？
产品
资源
甲
乙
资源限制
A
3
2
65
B
2
1
40
C
0
3
75
单件利润
1500
2500
该问题的数学模型为：
max Z=1500x1+2500x2
. 3x1+2x2  65 A资源
2x1+ x2  40 B资源
3x2 75 C资源
x1,x2  0
考虑：
1、定价不能太高？
2、定价不能太低？
假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？
咋办？
设A、B、C资源的出售价格分别为 y1 、 y2和y3
≥1500
≥2500
≥0
原问题：
max Z=1500x1+2500x2
. 3x1+2x2  65 A资源
2x1+ x2  40 B资源
3x2 75 C资源
x1,x2  0
对偶问题：
Min W = 65 y1 + 40 y2 + 75 y3
. 3y1 + 2 y2 ≥1500
2y1 + y2 + 3y3 ≥2500
y1, y2 , y3 ≥ 0
2
1
0 3
A=
65
40
75
b=
1500 2500
c=
2 0
2 1 3
A=
1500
2500
b=
65 40 75
c=
max
min
对偶问题 Min W=bTY . ATY≥CT
Y ≥0
≥
max
b
A
C
CT
AT
bT
≤
min
m
n
m
n
二、对偶问题的形式
1、对称型对偶问题
原问题 Max Z=cX . AX≤b
X ≥0
对偶关系表
由表可以看出：
从行看是原问题（Ⅰ