文档介绍:第三章 线性规划的对偶理论
组合优化理论
Combinatorial
Optimization Theory
1
§1 对偶问题的提出
一、对偶问题的实例
产品 资源
资源 甲 乙 限制
A 3 2 65
B 2 1 40
C 0 3 75
单件利润 1500 2500
max z =1500x1+2500x2
. 3x1+2x2 ≤65
2x1 +x2 ≤40 (1)
3x2 ≤75
x1 , x2 ≥ 0
最优解为: x1* =5 , x2* =25 zmax =70000
设 y1, y2, y3 分别为 A, B, C 三种资源出售的价格
3y1 +2y2 ≥ 1500
2y1 + y2 +3y3 ≥ 2500
w= 65y1 +40y2 +75y3
min w = 65y1 +40y2 +75y3
. 3y1 +2y2 ≥ 1500 (2)
2y1 + y2 +3y3 ≥ 2500
y1, y2, y3≥ 0
最优解为: y1*= 500
y2*= 0 , y3* = 500,
wmin = 70000
如果称(1)为LP 问题的
原问题,则称(2)为(1)
的对偶问题。
2
第三章 线性规划的对偶理论
二、对偶问题的形式
1、对称型对偶问题
max z = c1x1 + c2x2 + … + cnxn
. a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≤ b2
(3) … …
am1x1 + am2x2 + … + amnxn ≤ bm
xj ≥ 0 (j = 1,2,…,n)
min w = b1 y1 + b2 y2 + … +bm ym
. a11y1 + a21 y2 + … + am1ym ≥ c1
a12y1 + a22y2 + … + am2 ym ≥ c2
(4) … …
a1ny1 + a2ny2 + … + amnym ≥ cn
yi≥ 0 (i = 1,2,…,m)
定义1 设原 LP 问题为
则称下列 LP 问题
为其对偶问题,其中 yi ≥ 0 (i = 1,2,…,m)称为对偶变量,
并称(3)、(4)为一对对称型对偶问题
max z=cx
(P) . Ax ≤b
x ≥ 0
min w= yb
(D) . yA ≥ c
y ≥ 0
3
§1 对偶问题的提出
2、非对称型对偶问题
max z = cx
(P) . Ax = b
x ≥ 0
max z = cx
. Ax ≤ b
-Ax ≤ -b
x ≥ 0
引入对偶变量(u,v),其中 u = (u1,u2,…,um)
为对应于第一组不等式约束 Ax ≤b 的对偶变
量,v = (v1,v2,…,vm) 为对应于第二组不等式约
束 -Ax ≤-b 的对偶变量,按对称型的结论:
min w = (u-v) b
. (u-v) A ≥ c
u,v ≥ 0
令 y=u-v
min w= yb
(D) . yA ≥ c
y ≥ 0
min w = yb
(D) . yA ≥c
y 无符号限制
4
第三章 线性规划的对偶理论
3、混