对偶理论

max Z C B X B C N X N 0 X S BX B NX N EX S b X B , X N , X S 0
用表 2－2 形式表达上述模型， 求出基可行解、 检验数、 单纯形乘子及目标函数值， 见 2－3 所示。 表 2－2 XB XB C B CB XN N CN XS E 0 b b 0
T
对偶问题（或原问题） 目标函数 min 资源限量（目标函数系数）
T
约束条件系数矩阵 A （A） 约 n 个约束 第 j 个约束为≥ 第 j 个约束为≤ 第 j 个约束为=
约
m 个约束 第 i 个约束≤ 第 i 个约束≥
变
m 个变量 第 i 个变量≥0 第 i 个变量≤0
束
第 i 个约束为=
量
第 i 个变量无约束
【解】设 x1，x2，x3 分别为产品 A，B，C 的产量，则线性规划数学模型为：
max Z 100 x1 80 x 2 70 x3 9 x1 8 x 2 6 x3 500 5 x 4 x 7 x 450 1 2 3 8 x1 3x 2 2 x3 300 7 x 6 x 4 x 550 2 3 1 x1 , x 2, x3 0
【解】目标函数求最小值，应将表 2－4 的右边看作原问题，左边是对偶问题，原问题有 3 个约 束 4 个变量，则对偶问题有 3 个变量 4 个约束，对照表 2－4 的对应关系，对偶问题为：
max w 18 y1 10 y 2 14 y 3 7 y1 2 y 3 1 2 y1 6 y 2 8 y 3 5 8 y1 y 3 4 y 5 y 9 2 1 y 0 , y 2 0, y 3 无约束 1

.
2
2
4
inf
x
2 2

wx 2
|
x2

0


w
2

w
w


w2
.
2
2
4
(w) w 2 w 2 4w w 2 4w.
44
2
对偶问题为:

w2
max 4w

2
s.t. w 0
对偶定理
min f ( x ) s.t. g ( x ) 0
x1, x2 0
1）原问题(P1)一可行解 x=(1, 1)T
目标值 =40 40是(D1)最优目标值的上界.
2）对偶问题(D1)一可行解 w=（1 1 1 1）
目标值 =10 10是(P1)最优目标值的下界.
x*
1 5
6 5
最优值28
w*0 0 4 4T 最优值28
推论1 若问题(P)或(D)有无界解，则其对偶问题(D)或(P) 无可行解； 若问题(P)或(D)无可行解，则其对偶问题(D)或(P) 或者无可行解,或者目标函数值趋于无穷。
cT x Ax b
Ax b x0
max bTu bTv
对偶
s .t .
ATu ATv c
u, v 0
令wuv (D)
m ax s .t .
bT w ATw
c
w无 限 制
例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 ≥ 0, x2 ≥0, x3 ≥0

min w 16y1 36y2 65y3
90 y1 3 y 2 y1 2 y 2 5 y 3 70 y , y , y 0 1 2 3
原问题 A b C 约束系数矩阵
对偶问题 约束系数矩阵的转臵
约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量 约束条件的右端项向量 Max z=CX Min w=Y’b 目标函数 AX≤b A’Y≥C’ 约束条件 X≥0 Y≥0 决策变量
若原问题为求极小形式的对称形式线性规划问题， 对偶问题应该具有什么形式？
Min w Y 'b A'Y C Y 0
max w Y 'b A'Y C Y 0
min z CX
Max z CX
AX b X 0
AX b X 0
min w 5 y1 4 y2 6 y3 4 y1 3 y2 2 y3 2 y1 2 y2 3 y3 3 3 y1 4 y3 5 2 y 7 y y 1 2 3 1 y1 0, y2 0, y3无约束
对偶问题 约束系数矩阵的转臵
目标函数中的价格系数向量
目标函数 约束条件
变量
Max z=CX m个 ≤ ≥ = n个 ≥0 ≤0 无约束
约束条件的右端项向量 目标函数 Min w=Y’b m个 ≥0 变量 ≤0 无约束 n个 ≥ 约束条件 ≤ =
【例2-3】写出下列线性规划问题的对偶问题
min 2x1 3x2 5x3 x4
1.初始表中单位阵在迭代后单纯形表中对应的位臵就是B-1 2.对于原问题的最优解，各松弛变量检验数的相反数恰好 是其对偶问题的一个可行解，且两者具有相同的目标函数 值。根据下面介绍的对偶问题的基本性质还将看到，若原 问题取得最优解，则对偶问题的解也为最优解。

1.3 对偶单纯形法
C
-2
-3
-4
CB
XB
b
X1
X2
X3
0
X4
-1
0
[-5/2]
1/2
-2
X1
2
1
-1/2
3/2
0
-4
-1
确定换出变量： X4
确定换入变量： X2
C
CB
XB
b
-3
X2
2/5
-2
X1
11/5
X * = (11 5 2 5)
-2
-3
-4
X1
X2
X3
0
1
-1/5
1
0
7/5
0
0
-3/5
Y * = (8 5 1 5)
初始可行基，则 σ ≤ 0 。
若
~ bi
≥
0, i
= 1,2,L, m，即表中原问题和
对偶问题均为最优解，否则换基。
1.3 对偶单纯形法
基变换方法：
•确定换出基变量
~ bl
=
min i
~ {bi
~ bi
<
0}
对应变量 xl 为换出变量
•确定换入基变量
θ
=
min
⎪⎧σ
⎨
j
j ⎪⎩ alj
alj
<
0
⎪⎫ ⎬
1.3 对偶理论 Dual Theory
对偶是一般形式的对称。 ¾ 对偶问题的引出 ¾ 原问题与对偶问题的对应关系 ¾ 对偶理论
DUAL
1.3 对偶问题
某家电厂家利用现有资源生产两种产品，有关数据如下表：