文档介绍：§ 对偶线性规划
解的理论
对
偶
问
题
原
问
题
引例1
常数项
1 1/3 0 1/6 0 4
常数项
0 2/3 0 -1/6 1 1
0 5 1 0 0 15
0 1/3 0 -1/3 0 Z-8
常数项
0 1 0 -1/4 3/2 3/2
1 0 0 1/4 -1/2 7/2
0 0 1 5/4 -15/2 15/2
0 0 0 -1/4 -1/2 Z-17/2
最优单纯形表
y1
y2
y3
y4
y5
y6
y7
常数项
-15
-24
-5
0
0
-M
-M
y6
0
6
1
-1
0
1
0
2
y7
5
2
1
0
-1
0
1
1
-15+5M -24+8M -5+2M -M -M 0 0 +3M
y1
y2
y3
y4
y5
y6
y7
常数项
-15
-24
-5
0
0
-M
-M
y6
0
6
1
-1
0
1
0
2
y7
5
2
1
0
-1
0
1
1
-15+5M -24+8M -5+2M -M -M 0 0 +3M
y1
y2
y3
y4
y5
y6
y7
常数项
10-5M
-14+4M
0
-M
-5+M
0
5-2M
y6
-5
4
0
-1
1
1
-1
1
y3
5
2
1
0
-1
0
1
1
y1
y2
y3
y4
y5
y6
y7
常数项
-15/2
0
0
-7/2
-3/2
7/2-M
3/2-M
y2
-5/4
1
0
-1/4
1/4
1/4
-1/4
1/4
y3
15/2
0
1
1/2
-3/2
-1/2
3/2
1/2
y1
y2
y3
y4
y5
常数项
-15/2
0
0
-7/2
-3/2
y2
-5/4
1
0
-1/4
1/4
1/4
y3
15/2
0
1
1/2
-3/2
1/2
最优单纯形表
最优单纯形表:
对偶问题剩余变量
对偶问题
的变量
最优单纯形表:
原问题的
松弛变量
原问题
的变量
常数项
0 1 0 -1/4 3/2 3/2
1 0 0 1/4 -1/2 7/2
0 0 1 5/4 -15/2 15/2
0 0 0 -1/4 -1/2 Z-17/2
y1
y2
y3
y4
y5
常数项
-15/2
0
0
-7/2
-3/2
y2
-5/4
1
0
-1/4
1/4
1/4
y3
15/2
0
1
1/2
-3/2
1/2
最优值Z*=17/2
最优值W*=17/2
最优解
(7/2,3/2)
最优解
(0,1/4,1/2)
对偶问题的对偶就是原问题。
(即互为对偶规划)
一、对称定理:
设原问题(P) 对偶问题(D)
二、弱对偶性定理:
推论2、若原问题(P)和其对偶问题(D)都存在可
行解,则(P) 和(D)都存在最优解
推论1: 若(P)有可行解,但无上界,则(D)无
可行解。若(D)有可行解,但无下界,则
(P)无可行解