文档介绍：2007/08
--第2章对偶问题--
--1--
第二章线性规划的对偶理论
Duality 对偶
Dual Problem 对偶问题
Dual Linear Programming
对偶线性规划
Dual Theory 对偶理论
2007/08
--第2章对偶问题--
--2--
问题的提出
例:某企业计划生产甲、乙两种产品,该两种产品均需经 A、B、C、D 四种不同设备加工,按工艺资料规定,在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问:如何安排产品的生产计划,才能使企业获利最大?
2007/08
--第2章对偶问题--
--3--
设企业生产甲产品为X1件,
乙产品为X2件,则
max z= 2 X1 +3 X2
2 X1 +2 X2 12
X1 +2 X2 8
4 X1 16
4 X2 12
X1 0 , X2 0
(原问题) <========> ( 对偶问题)
设第i种资源价格为yi,( i=1, 2, 3, 4,) 则有
min w= 12y1 + 8y2 + 16y3 +12 y4
2y1 + y2 + 4y3 +0 y4 2
2y1 +2y2 + 0y3 +4 y4 3
yi 0, (i=1, 2, 3, 4 )
y1
y2
y3
y4
2007/08
--第2章对偶问题--
--4--
原问题与对偶问题的关系
一般表示式:
原问题: max z = c1 X1 + c2 X2 + ┈+ cn Xn
a11 X1 + a12 X2 + ┈+ a1n Xn b1
a21 X1 + a22 X2 + ┈+ a2n Xn b2
·······················
am1 X1 + am2 X2 + ┈+ amn Xn bm
xj 0,j=1,2,┈,n
对偶问题: min w = b1 y1 + b2 y2 + ┈+ bm ym
a11 y1 + a21 y2 + ┈+ am1 ym c1
a12 y1 + a22 y2 + ┈+ am2 ym c2
·························
a1n y1 + a2n y2 + ┈+ amn ym cn
yi 0,(i=1,2,···,m )
2007/08
--第2章对偶问题--
--5--
典式模型对应对偶结构矩阵表示
(1) max z = C X
AX b
X 0
min w = Y b
YA C
Y 0
对偶问题
原问题
2007/08
--第2章对偶问题--
--6--
对偶模型其他结构关系
(2)若模型为 max z = C X
AX b X 0
max z = C X
- AX -b
X 0
变形
min w = Y b
YA C
Y 0
Min w=Y ´(-b)
st. Y ´(-A) C Y ´ 0
令 Y=- Y ´
对偶问题
对偶变量Y
2007/08
--第2章对偶问题--
--7--
(3)max z = C X
AX b X 0
变形
设X= -X´
max = -CX ´
st. -AX´ b X´ 0
min w = Y b
YA C
Y 0
则有
min w = Y b
-YA - C
Y 0
2007/08
--第2章对偶问题--
--8--
对偶问题典式:
用矩阵形式表示:
(1) max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0
(2) max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0
(3)max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0
2007/08
--第2章对偶问题--
--9--
原问题与对偶问题关系表
原问题(对偶问题) 对偶问题(原问题)
目标函数系数约束右端项
约束右端项目标函数系数
约束条件系数列向量 A 约束条件系数行向量 AT
变量个数约