xj qi q1 q2 qm Cj
x1
X2
b
1
2
8
4
0
16
0
4
12
2
3
15
例3：建立下列LP 问题的对偶问题
(1) min Z=2X1十4X2十3X3
s.t. X1十2X2－3X3 ≥5
2X1 － 3X2 －2X3≤3
X1十X2十X3 =2 X1，X2，X3 ≥0
(2) max Z=X1十2X2十3X3十4X4 s.t.
为换入基变量,转4；
4.以akr’进行转轴运算,作矩阵行变换使其变为
1,该列其他元素变为0,转2
24
例7：用对偶单纯形法求解下列LP问题
min Z’=6X1十3X2十2X3
s.t.
X1十X2十X3 ≥20
1/2X1十1/2X2十1/4X3 ≥6
2X1十X2十X3
≥10
X1，X2，X3 ≥0
25
解法一:将LP问题化为
0
0
0
1
4
0
6
10
0
q2
q3
q4
0
1
1
1
0
0
0
1
0
6
20
0
0
-10
0
0
0
q5
q6
-1
0
4
-4
-1
2
4
16
-4
-16
9
关系：
➢两个LP问题的最优解的目标函数值相同
➢用单纯形法求解一个LP问题就知道另一 个问题的解
二、对偶问题的概念及实质
1.对每一个LP问题所伴随着的另一个LP问 题，就称为对偶问题；原来的LP问题就称 为原问题
5
(2)若有一个饲料厂制造含有这三种营养成分为1个单 位的营养丸，在1份混合饲料中三种营养丸的价格如 何制定才使其售价最大？
解：(2)设qi表示一份混合饲料中第I种营养丸的价格， i=D,E,F,则
max Z=20q1十6q2十10q3
s.t. q1十1/2q2十2q3 ≤6
q1十1/2q2十q3 ≤3
两端乘以-1
原问题为“min ≥”形式
3.原问题的每一个约束条件方程对应对偶问题的一 个决策变量qi
➢若第i个约束条件为不等式,则限定qi≥0
➢若约束条件方程是“=”形式:将“=”变为“≤”和
“≥”两个约束条件方程,在按照1、2条处理
14
例2：根据下表写出原问题(max)与对偶问题(min)的 表达式
min Z= 6X1十3X2十2X3
s.t. － X1 － X2 － X3十X4
= － 20
－ 1/2X1 － 1/2X2 － 1/4X3 十X5 = － 6
－ 2X1 － X2 － X3
十X6 = － 10
X1，X2，X3 , X4 , X5 , X6 ,≥0
28
cj→
6
3
2
0
0
0
cB XB b
max Z= － 6X1 － 3X2 － 2X3
s.t. － X1 － X2 － X3十X4
= － 20
－ 1/2X1 － 1/2X2 － 1/4X3 十X5 = － 6
－ 2X1 － X2 － X3
十X6 = － 10
X1，X2，X3 , X4 , X5 , X6 ,≥0
cj→
-6
-3
-2
0
0
0
cB XB b
q1+2q2≤2 (1)
题的两个约束条件应取等式， 故有
q1 -q2≤3 (2)
x1 +3x5 =4
2q1+3q2≤5 (3)
2x1 +x5 =3
q1 +q2≤2 (4)
求解得x1=1.x2=1
3q1 +q2≤3 (5)
故原问题的最优解为
将q1,q2的值代入约束条 件，得(2),(3),(4)为严格不
x1
x2
x3
x4
x5
x6
0 x4 (-20) -1
-1
-1*
1
0
0
0 x5 -6 -1/2 -1/2
-1/4
0
1
0
0 x6 -10
-2
-1
-1
0
0
1
zj zj － cj
a12 …
a1n
≤
b1
q2
a21
a22
a2n
≤
b2
…
… …… …
…
…
qm
am1 am2
amn
对偶约束 ≥
≥… ≥
max z
C1
C2 … Cn
≤
bm
13
二、原问题不符合建立规则的处理
1.原问题为“max ≥”形式
约束条件方程
两端乘以-1
原问题为“max ≤”形式
2.原问题为“min 约束条件方程
≤”形式
2x1-x2+3x3 +x4 +x5 ≥3 x1,x2,x3 ,x4 ,x5≥0 已知其对偶问题的最优解为 q1=4/5;q2=3/5;z=5.试用对偶 理论找出原问题的最优解
20
解：先写出其对偶问题：
又因为q1,q2≥0，由互补松弛
max w=4q1+3q2
性qxs=0得xs1=0 ,xs2=0,j即原问
0
1
-2
4
0
-3 x2 4
1
1
0
1
-4
0
0 x6 10
-1
0
0
-1
0
1
zj cj －zj
-3
-3
-2
1
4
0
-3
0
0
-1
-4
270
∵表中所有检验数均不大于0，且b’i≥0∴已达到最优 最优解为X=(0,4,16,0,0,10)T , Zmax=6×4+20×1=44 Z’min= Zmax=44
解法二:将LP问题化为
－X1十X2－X3 －3X4 =5
6X1十7X2十3X3－5X4 ≥8
12X1－ 9X2 － 9X3十9X4≤20
X1，X2，X3 ，X4≥0
16
(3)
17
§3-3 对偶基本理论或性质
一、对称性
➢ 对偶问题的对偶是原问题
二、弱对偶性
➢若 x, q 分别为（LP) 和（DP）的可行 解，那么cx ≤ bTq
q1 ， q2 ， q3 ≥0
8
cj→
6
cB XB B
x1
2 x3 16
0
0 x6 10
-1
3 x2 4
1
zj
3
cj －zj
3
cj→
20
cB qB B
q1
0 q4 3
0
6 q2 4
0
20 q1 1
1
zj
20
－zj
0
3
2
0
0
0
x2
x3
x4
x5
x6
0
1
-2
4
0
0
0
-1
0
1
1
0
1
-4
0
3
2
-1
-4
7
LP1与LP2的关系：
min Z=6XA十3XB十2XC
max w=20q1十6q2十10q3
s.t. XA十XB十XC
≥20
s.t. q1十1/2q2十2q3 ≤20
1/2XA十1/2XB十1/4XC ≥6
q1十1/2q2十q3 ≤3
2XA十XB十XC
≥10
q1十1/4q2十q3 ≤2
XA，XB，XC ≥0
2.将问题变换为统一形式，其中b可以为负数
➢原问题“max ≤” ➢原问题“min ≥”
对偶问题“min ≥” 对偶问题“max ≤”
对偶问题建立的规则；［请同学们抄写下来］
1，原问题目标函数求最大[或者最小]，则所有的约束条件符号 统一成小于或者等于[大于或者等于] 2，原问题一个行约束对应对偶问题的一个变量，如果行约束为 不等式，这个变量就大于等于零
-1/2
-1/2
-1/4
0
1
0
0 x6 -10
-2
-1
-1
0
0
1
zj cj － zj
0
0
0
0
0
0
-6
-3
-2
0
0
0
-2 x3 20
1
1
1
-1
0
0
0 x5 (-1) -1/4 -1/4*
0
-1/4
1
0
0 x6 10
-1
0
0
-1
0
1
zj cj －zj
-2
-2
-2
2
0
0
-4
-1
0
-2
0
0
-2 x3 16
0
1/2XA十1/2XB十1/4XC ≥6 2XA十XB十XC ≥10 XA，XB，XC ≥0 求解结果为：
4
cj→
6
cB XB B
x1
2 x3 16
0
0 x6 10
-1
3 x2 4
1
zj
3
cj －zj
3
3
2
0
0
0
x2
x3
x4
x5