对偶理论与灵敏度分析
第三章 对偶理论与灵敏度分析
第一节 对偶问题的提出
例：常山机械厂生产Ⅰ和Ⅱ两种产品。生产中需使用A、B、C三种设备进行加工，加工每件Ⅰ产品或Ⅱ产 品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生 产Ⅰ和Ⅱ产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。
4x1 +2x2 - x3 20 y2 x1，x2 ， x3 0 解：该问题的对偶问题： min w = 10 y1 + 20 y2 s.t. y1 + 4y2 10
y1 + 2y2 1 2 y1 - y2 2
y1，y2 0
第一节 对偶问题的提出
例：写出下列线性规划问题的对偶问题 min w = x1 + 2x2 + 3x3
解：化为对称形式。 令 x2 x2，x3 x3 x3 (x3 0, x3 0) max z c1x1 c2x2 c3x3 c3x3
s.t. a11x1 a12x2 a13x3 a13x3 b1
aaa222a111xxx2111x1 aaa222a222xx2x2222x2 aaa222a333xxx23333x3 aaa222a333xxx23333x3 bbb222b2 a3a13x11x1 a3a23x22x2 a3a33x33x3 a3a33x33x3 b3b3 x1, x2 , x3, x3 0
a21x1 + a22x2 + … + a2nxn ≤ b2 ……
am1x1 + am2x2 + … + amnxn ≤ bm xj ≥ 0 （j = 1,2,…,n）
则称下列 LP 问题
min w = b1 y1 + b2 y2 + … +bm ym s.t. a11y1 + a21 y2 + … + am1ym ≥ c1
A
B
C
产品利润（元／件）
Ⅰ
2
4
0
2
Ⅱ
2
0
5
3
设备可用机时数（工时）
12
16
15
第一节 对偶问题的提出
解：设Ⅰ、Ⅱ产品的生产数量分别为x1和x2，建立问题数学模型如下： max z =2x1+3x2 2x1+2x2≤12 4x1 ≤16 5x2 ≤15 xj≥0，j=1，2
现假设有另一家四海机器厂，为了扩大生产想租借常山机器厂拥有的设备资源，问常山厂分别以每小时 什么样的价格才愿意出租自己的设备呢？
第一节 对偶问题的提出
设A、B、C设备的机时单价分别为y1、y2、y3，新的线性规划数学模型为
max z =2x1+3x2 2x1+2x2≤12 4x1 ≤16
5x2 ≤15 xj≥0，j=1，2
min w=12y1+16y2+15y3 2y1+4y2 ≥2 2y1 +5y3≥3 yj≥0，j=1，2，3
原始问题
max z=CX
s.t.
AX≥b
X ≥0
max
C
m
A
n
≥b
对偶问题 min w=bTY s.t. ATY≤CT
Y ≥0
min
bT
n
AT
≤ CT
m
第一节 对偶问题的提出
原问题与对偶问题
设原 LP 问题为
max z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn ≤ b1
s.t. 2y1- 3y2 1 3y1- y2 2 5y1- 7y2 3 y1，y2 0
第一节 对偶问题的提出
例：写出下述线性规划问题的对偶问题
max z = c1x1 + c2x2 + c3x3 s.t. a11x1 + a12x2 + a13x3 ≤ b1
a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 ≥ b3 x1≥0, x2≤0, x3 无约束
a12y1 + a22y2 + … + am2 ym ≥ c2 ……
a1ny1 + a2ny2 + … + amnym ≥ cn yi≥ 0 （i = 1,2,…,m）
第一节 对偶问题的提出
例：写出下列线性规划问题的对偶问题
min w=12x1+8x2 +16x3+12x4
s.t. 2x1+ x2 +4x3
Ⅰ（x1） Ⅱ （x2） 设备可用机时数（工时）
A（y1） 2 2 12
B（y2） 4产品利润（元／件） 2 3
第一节 对偶问题的提出
2
3
x1
x2
原问题
12
y1
2
2
≤
12
16
y2
4
0
≤
16
15
y3
0
5
≤
15
对偶问题
2
3
第一节 对偶问题的提出
原问题与对偶问题的形式关系
s.t. 2x1+3x2 + 5x3 2 3x1+ x2 + 7x3 3 x1，x2 ， x3 0
解：用（-1）乘以第二个约束方程两边 min w=x1+2x2 +3x3
s.t. 2x1+3x2 + 5x3 2 y1 -3x1- x2 - 7x3 -3 y2 x1，x2 ， x3 0
该问题的对偶问题： max z = 2 y1 - 3y2
2 y1
2x1+2x2 + 4x4 3 y2
x1，x2 ， x3 ， x4 0
解：该问题的对偶问题：
max z = 2y1 + 3y2
s.t. 2y1 + 2y2 12
y1 + 2y2 8
4 y1
16
4y2 12
y1，y2 0
第一节 对偶问题的提出
例：写出下列线性规划问题的对偶问题 max z = 10x1 + x2 + 2x3 s.t. x1 + x2 + 2x3 10 y1
第一节 对偶问题的提出
max z c1x1 c2x2 c3x3 c3x3 s.t. a11x1 a12x2 a13x3 a13x3 b1
a21x1 a22 x2 a23x3 a23x3 b2 a2a1x21x1 a2a2 x222x2 a2a3x233x3 a2a3x233x3 b2b2 a31x1 a32x2 a33x3 a33x3 b3
xj yi
u1 u2 ... um
原问题
Max Z
X1 ,
a11 a21 ... am1
c1
X2 , … ,
a12 ... a22 ... ... ... am2 ...
…
c2 ...
Xn
对偶问题 Min w
a1n
b1
a2 n
b2
... ... ...
amn
bm
Max Z = Min w
cn
第一节 对偶问题的提出