引原例问1题 生ma产x 计Z 划 2问x1题 3 x 2 某工厂用三 2台x1 设 2备x 2生 产12 两种产品，已知的条 件如表设所备示 3xx，11x,2x试22 Ix9制产2 0品订8总II利产品润最大总的有生效产台时计划
A
B
C 单位产品的利
润（千元）
2对偶问2题
12
1 0 2
233min22yy1112y求21y2ym2898y2a23xy39y33
约束条件
第 j个为
约束条件右端项
m个
yi yi
变量
y i无约束
目标函数中变量的系数
例2：给出下列线性规划的对偶问题：
min Z=2X1+ 8 X2 -4X3 X1+3X2 – 3X3 > =30 -X1 +5X2 + 4X3 =80
st. 4X1+ 2X2 -4X3 < =50 X1 < =0, X2 > =0, X3 无约束
最优解的充分必要条件 ： n 1）如 yˆi 0时，必ai有 jxˆj bi; j1
n
当 aijxˆj bi时，必 yˆi 有 0；i1,2,,m j1 m
2）如 xˆj 0时，必a有 ijyˆi cj; i1
m
当 aijyˆi cj时，必 xˆj 有 0；j1,2,,n i1
利用互补松弛定理,在已知一个问题的最优解的情况下, 可以不要列单纯形表求出另一个的最优解.
yi 0 i 1,2,3
换一角度：将设备卖出，售价定为多少适宜？
两个互为对偶规划问题之间的关系 （对称形式）
1）目标函数的目标互为相反。(max,min) 2）目标函数的系数是另一个约束条件右端 的向量
3）约束系数矩阵是另一个的约束系数矩阵 的转置
4）约束方程的个数与另一个的变量的个数 相等
原问题
二、弱对偶定理
如果 X , Y 分别是（1）和（2）的可行解，
则有
CX。Yb
三、最优性定理
如果 Xˆ , Yˆ 分别是(1)和(2)的可行解，且 有 CXˆ Yˆb，则 Xˆ , Yˆ 分别是(1)和(2)的最优解.
原问题 max Z CX
对偶问题 min Yb
AX b
s.t.
X
0
（3）
m Z ax 1 x 2 x 2 3 x 3 4 x 4
2x1x12xx22
2x3 3x3
3x4 2x4
20 20
xj 0 ( j 1,2,3,4)
其对偶问题为： mW i n2y0 12y0 2
y1 2 y2 1
2 2
y1 y1
y2 3y
2 23
3
y
1
2 y2
4
y 1 , y 2 0
2x3 3x3
3x4 2x4
20 20
xj 0 ( j 1,2,3,4)
其对偶问题为： mW i n2y0 12y0 2
y1 2 y2 1
2 2
y1 y1
y2 3y
2 23
3
y
1
2 y2
4
y 1 , y 2 0
试估计它们的目标函数值的界，并验证弱对偶定理的正确性。
解: 由观察知
例4：已知线性规划问题
minZ 2x1 x2 2x3 x1 x2 x3 4 x1 x2 x3 6 x1 0, x2 0, x3无约束
要求：1）写出对偶问题； 2）已知原问题的最优解为x1= -5, x2=0, x3= -1; 试根据对偶理论直接求出对偶问题最优解。
解：1）对偶问题 max 4 y1 6 y 2
max
min
限定向量b
价值向量
价值向量C
限定向量
m个约束，n个变量
n个约束，m个变量
约束条件“=”
变量自由变量
原问题（对偶问题）
目标函数max
n个
变量
x
j
0
x
j
0
x
j
无约束
目标函数中变量的系数
m个
约束条件
第
i个为第ຫໍສະໝຸດ i个为第 i个为
约束条件右端项
对偶问题（原问题）
目标函数min
n个
第 j个为 第 j个为
YA C s.t.Y自由变量
（4）
四、强对偶定理
对于一对对偶问题，其中一个有有限最优
解，则另一个也有最优解，且两个目标函数值 相等。
五、无界性定理
对于一对对偶问题，若一个有无界解， 则另一个无可行解。
例 3 已知原问题
m Z ax 1 x 2 x 2 3 x 3 4 x 4
2x1x12xx22
y1 y2 2
y1 y1
y2 y2
1 2
y1 , y 2 无 约 束
2）由互补松弛定理，因原问题最优解中x1= -5≠0, 必使对偶问题第一个约束条件为等式，于是有，
y1y1
y2 y2
2
2
y10,y22
例 5:已知下列线性规划问题的对偶问题的最优解为 (6/5, 1/5),求该线性规划问题的最优解.
对偶问题
maxZ CX
min bTY T
s.t.XAX0b
对称式对偶
ATY T s.t.
CT
Y 0
max
min
限定向量b
价值向量
价值向量C
限定向量
m个约束，n个变量
n个约束，m个变量
约束条件“≤”
变量“≥”
变量“≥”
约束条件“≥”
原问题
对偶问题
maxZ CX
min bTYT
s.t.XAX0b 非对称式对偶s.t.YA自TY由T 变C量T
其对偶问题为：
MAX w=30 y1 +80 y2 +50y3 y1 - y2 +4y3 〉=2
st. 3 y1 +5y2 +2 y3 <=8 -3y1 +4y2 -4y3 =-4 y1 >=0, y2 无约束，y3 <=0
原问题
对偶问题
max 2Z.3C对X 偶问题基本min性 质 Yb
一s、.t.对XAX称对性0偶b定问（理题1）的对偶是原s.t问.YY题A。0C（2）
X(1,1,1,1)T 和 Y (1,1)
分别是原问题和对偶问题的可行解，
且原问题的目标函数值
，
对偶问题的目标函数值
ZCX10
WYb40
故 CXYb ，弱对偶定理 成立，
并且我们知对偶问题的目标函数值 W10
原问题的目标函数值
Z40
六、互补松弛性定理
若Xˆ和Yˆ分别(1是 )和(2)的可行解，则它
原问题的松弛变量为: X5 , X6 , 对偶问题的剩余变量为: Y3,Y4, Y5,Y6, 将(6/5,1/5)代入1)和2)知: Y3,Y4, 均不为0,于是由松
弛互补定理知:
X1, X2 , =0 又由 Y1>0,Y2>0和松弛互补定理知:
X5 , X6 ,=0 从而,原问题的约束变为:
2X3 + 3X4 =20 3X3 + 2X4 =20 解此方程得: X3 = X4 =4 于是原问题的最优解为:(0,0,4,4)