§1 单纯形表的灵敏度分析(重点.难点.掌握)
§2 线性规划的对偶问题
一、对偶问题实例
例1 某工厂生产甲、乙两种产品，要消耗A、B和C三种资源，
已知每件产品对这三种资源的消耗、这三种资源的现有数量和每 件产品可获得的利润如表所示.问：如何安排生产计划，使得既能 充分利用现有资源又使总利润最大？
产品 资源
纯
4/5 1 0 -2/5 1/5 -2/5 -1/5 2/5 形 表
4M-2 6M -3 2M-1 -M -M 0
0格
第六章 单纯形法的灵敏度分析
与对偶
窗含西岭千秋雪，门泊东吴万里船
对偶是一种普遍现象
DUAL
学习重点与难点
• §1 单纯形表的灵敏度分析(重点.难点.掌握) • §2 线性规划的对偶问题 (重点.理解.掌握) • §3 对偶规划的基本性质(重点.应用) • §4 对偶单纯形法(难点.掌握---前面已讲)
咋办？
• 考虑：
• 1、定价不能太高？
• 2、定价不能太低？
设A、B、C资源的出售价格分别为 y1 、 y2和y3
甲 乙 资源
min w 65 y1 40 y2 75 y3
限制
A
3
2 65 y1
3y1 2 y2 ≥1500
B
2
1 40 y2
2 y1 y2 3y3 ≥2500
C
0
3 75 y3
分别用大M法和两阶段法求解下列 线形规划问题,并指出解的类型
• minZ=2x1+3x2+x3
•
x1+4x2+2x3≥8
• S.t. 3x1+2x2 ≥6
•
x1,x2,x3 ≥0
• 时间:1:40—2:10
Cj CB XB -M x6
-M x7
检验数j
Cj CB XB -3 X2
-2 x1
检验数j
Y1 2Y2 Y3 5 3Y1 Y2 Y3 4 Y1,Y2 ,Y3 0
怎么样 简单吧
2、非对称型对偶问题
表 对偶变换的规则
好难记呀！
原问题(max,)
对偶问题(min,)
技术系数矩阵 A 价值系数 C
技术系数矩阵 AT
右端项 b
右端项 b
价值系数 C
第 i 行约束条件为 型
对偶变量 yi 0
≤ bm
• 由表可以看出：
1. 从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题 的变量系数矩阵互为转置矩阵。
2. 原问题（Ⅰ）的常数项是对偶问题（Ⅱ）的目标系数，反之， 原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项。
3. 原问题（Ⅰ）有n个决策变量，对偶问题（Ⅱ）有n个约束方程； 原问题有m个约束方程，对偶问题就有m个决策变量。
Min W = 65 y1 + 40 y2 + 75 y3
s.t. 3y1 + 2 y2
≥1500
2y1 + y2 + 3y3 ≥2500
y1, y2 , y3 ≥ 0
min
A=
3 2
20 13
b=
1500 2500
c= 65 40 75
二、对偶问题的形式
1、对称型对偶问题
原问题 Max Z=cX s.t. AX≤b
X ≥0
max
C
对偶问题 Min W=bTY s.t. ATY≥CT
Y ≥0
min bT
m
A
≤b
n AT ≥ CT
n
m
• 对偶关系表
x1
x2
…
c1
c2
…
xm
…
xn
cm
…
cn
maxZ
minW
Y1
A11
a12
…
Y2
a21
a22
…
Ym
am1
am2
…
a1m
…
a2m
…
amm
…
a1n
≤ b1
a2n
≤ b2
amn
0
当迭代若干步，基变量为X B时，新的单纯形表:
Cj
CB
CN
0
XB
XN
-2 -3 -1 0 0 -M -M
b
x1 x2
x3
x4
x5Biblioteka x6x7初 始8 1 4 2 -1 0 1 0 单
纯
6 3 2 0 0 -1 0 1 形 表
4M-2 6M -3 2M-1 -M -M 0
0格
-2 -3 -1 0 0 -M -M
b
x1 x2
x3
x4
x5
x6
x7
最 终
9/5 0 1 3/5 -3/10 1/10 3/10 -1/10 单
§3 对偶规划的基本性质
一、单纯形法计算的矩阵描述:
对称形式线形规划问题为:
Max Z=cX s.t. AX≤b
X ≥0
加上松弛变量化为标准形后为:
Max Z=cX +0Xs s.t. AX+IXs=b
X ≥0,Xs ≥0
初始单纯形表为:
Cj
CB
CN
0
XB
XN
XS
0
X S
b
B
N
I
检验数j
CB
CN
y1, y2 , y3 ≥0
单件 1500 2500 利润
原问题：
max Z=1500x1+2500x2 s.t. 3x1+2x2 65 A资源
2x1+ x2 40 B资源 3x2 75 C资源
x1,x2 0
max 32 A= 2 1 03
65 b= 40
75
c= 1500 2500
对偶问题：
• 对偶变换是一一对应的
例3：
Min z= 5x1+ 25x2 7x1+ 75x2 ≤98
s.t. 5x1 + 6x2 = 78 24x1+ 12x2≥54 x1≥0 、x2 ≤ 0
怎么样， 没问题吧！
Max w= 98y1+ 78y2 + 54y3 7y1+ 5y2 + 24y3 ≤ 5
s.t. 75y1+ 6y2 + 12y3 ≥25 y1 ≤ 0 、y2无限制、 y3≥0
甲
A
3
B
2
C
0
乙
资源 限制
该问题的数学模型为：
2
65
max Z=1500x1+2500x2
s.t. 3x1+2x2 65 A资源
1
40
2x1+ x2 40 B资源 3x2 75 C资源
3
75
x1,x2 0
单件利 润
1500
2500
假设该厂现自己不生产，因而要转让资源A、B和C，请问他
们应如何给这三种资源定价？
第 i 行约束条件为 型
对偶变量 yi 0
第 i 行约束条件为 = 型
对偶变量 yi 不限
决策变量 xj 0
第 j 行约束条件为 型
决策变量 xj 0
第 j 行约束条件为 型
决策变量 xj 不限
第 j 行约束条件为 = 型
• 约束条件的类型(规范与否)与非负条件相互对应 • 非标准的约束条件类型对应非正常的非负条件
4. 原问题的约束是“≤”型，对偶问题的约束是“≥”型。 5. 原问题的目标函数是求极大，对偶问题的目标是求极小。
例2 请给出下列线性规划问题的对偶问题：
max Z＝5x1 +4x2
x1 3x2 90
s
t
2x1 x x1 x2
2 80 45
x1、x2 0
对称型线性规划问题
min W 90Y1 80Y2 45Y3