文档介绍：线性规划对偶问题
对偶问题的提出
设甲企业有m种资源用于生产n种不同产品，各种资源的拥有量分别为bi(i=1,2, …,m)，又生产每单位的第j 种产品(j=1,2, …,n)消耗第i 种资源aij单位，第j 种产品的单位产值为cj元。假设用xj代表第j 种产品的产量，那么使该企业获得最大产值的线性规划模型应表示为：
maxz=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2
… … … … … … … … …
am1x1+am2x2+…+amnxn≤bm
x1, x2, … , xn≥0
现假定乙企业欲收购甲企业拥有的资源，至少应付出多大代价，才能使甲企业愿意放弃生产活动而出让资源。
显然，甲企业放弃自己组织生产活动的条件是：出让同等数量资源的收益应不低于用其组织生产活动创造的产值。
对偶问题的提出
设用yi代表乙企业收购一单位的第i 种资源付出的代价，从乙企业角度建立的数学模型为：
minw=y1b1+y2b2+…+ymbm
a11y1+a21y2+…+am1ym≥c1
a12y1+a22y2+…+am2ym≥c2
… … … … … … … …
a1ny1+a2ny2+…+amnym≥cn
y1, y2,…,ym≥0
如果前者称为线性规划原问题的话，后者称为它的对偶问题。
对偶问题的提出
原问题与对偶问题〔一〕
maxz=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2
… … … … … … … … …
am1x1+am2x2+…+amnxn≤bm
x1, x2, … , xn≥0
minw=y1b1+y2b2+…+ymbm
a11y1+a21y2+…+am1ym≥c1
a12y1+a22y2+…+am2ym≥c2
… … … … … … … …
a1ny1+a2ny2+…+amnym≥cn
y1, y2,…,ym≥0
原问题
对偶问题
原问题与对偶问题〔二〕
例1：写出下述线性
规划的对偶问题。
max z= 2x1+x2
5x2≤15
6x1+2x2≤24
x1+ x2≤5
x1，x2≥0
解：根据对偶问题的提出，有：
min w =15y1+24y2+5y3
6y2+y3≥2
5y1+2y2+y3≥1
y1 ，y2 ，y3 ≥0
2 1
0 5 15
6 2 24
1 1 5
15 24 5
0 6 1 2
5 2 1 1
例2：写出例1中对偶问题的对偶。
min z’= -2x1 -x2
-5x2 ≥ -15
-6x1 -2x2 ≥ -24
-x1 - x2 ≥ -5
x1，x2≥0
解：
max( -w )= -15y1-24y2-5y3
-6y2 -y3 ≤ -2
-5y1 -2y2 -y3 ≤ -1
y1 ，y2 ，y3 ≥0
结论：原问题与对偶问题之间是互为对偶的关系。
min w =15y1+24y2+5y3
6y2+y3≥2
5y1+2y2+y3≥1
y1 ，y2 ，y3 ≥0
max z= 2x1+x2
5x2≤15
6x1+2x2≤24
x1+ x2≤5
x1，x2≥0
原问题〔对偶问题〕
目标函数 max
n个
≥ 0
≤ 0
无约束
目标函数中变量的系数
m个
≤
≥
=
约束条件右端项
变量
约束条件
对偶问题〔原问题〕
目标函数 min
n个
≥
≤