运筹学教程 胡运权版

第二章 对偶线性规划 对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关 系

DUAL

对偶单纯形法 对偶的经济解释 灵敏度分析2013-7-29 1

线性规划对偶问题的提出一、对偶理论的提出现有甲乙两种原材料生 产A1,A2两种产品，所 需的原料，甲乙两种原 料的可供量，以及生产 A1,A2两种产品可得的单 位利润见表。问如何安 排生产资源使得总利润 为最大？ 甲 已 A1 3 A2 可供量 2 24 40

4 5 利润 4.5 5

2013-7-29

解：设生产A1为x1件，生产A2为x2件，则线性规划问题为： maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 3 2 4x1+5x2≤40 4 5 x1,x2≥0 假设现在不考虑生产产品，而是把甲乙两种原材料卖掉，则 问题变成对于甲乙两种原材料企业以多少最低价愿意出让？ 解：设甲资源的出让价格为y1,乙资源的出让价格为y2 minw=24y1+40y2 s.t. 3y1+4y2≥4.5 3 4 2y1+5y2≥5 2 5 y1,y2≥0

2013-7-29

二、对偶问题的一般形式 一般认为变量均为非负约束的情况下，约束条件在目标函 数取极大值时均取“≤”号；当目标函数求极小值时均取 “≥“号。则称这些线性规划问题具有对称性。max z=c1x1+c2x2+……+cnxn min w=b1y1+b2y2+……+bmym

s.t. a11x1+a12x2+……+a1nxn ≤b1a21x1+a22x2+……+a2nxn ≤b2 ……

s.t. a11y1+a21y2+……+am1ym ≥c1a12y1+a22y2+……+am2ym ≥ c2 ……

am1x1+am2x2+……+amnxn ≤bmx1, x2, ……, xn ≥0

a1ny1+a2ny2+……+amnym ≥ cny1, y2, ……, ym ≥0

Max Z=CX s.t. AX≤b X≥02013-7-29

Minw=Y’b s.t. A’Y≥C’ Y≥04

原始问题 max z=CX s.t. AX≤b X ≥0

max m

C A ≥ b

对偶问题 min w=Y’b s.t. A’Y≥C’ Y ≥0 min b

n

AT

≤ C

nm2013-7-29 5

举例：maxZ=3x1+2x2 s.t. -x1+2x2≤4 3x1+2x2≤14 x1-x2 ≤3 x1,x2≥0 第一种资源 第二种资源 第三种资源 y1 y2 y3

minw=4y1+14y2+y3 s.t. -y1+3y2+y3≥3 2y1+2x2-y3≥2 y1,y2,y3≥0

第一种产品 第二种产品

x1 x2

2013-7-29

原始问题为 min z=2x1+3x2-x3s.t. x1+2x2+x3≥6

原始问题是极小化问题 原始问题的约束全为≥ 原始问题有3个变量，2个约束 原始问题的变量全部为非负

2x1-3x2+2x3≥9x1, x2, x3≥0 根据定义，对偶问题为 max y=6y1+9y2 s.t. y1+2y2≤2 2y1- 3y2≤3 y1+2y2≤-1 y1, y2≥0

对偶问题是极大化问题 对偶问题的约束全为≤ 对偶问题有2个变量，3个约束 原始问题的变量全部为非负

原始问题变量的个数(3)等于对偶问题约束条件的个数(3) 原始问题约束条件的个数(2)等于对偶问题变量的个数(2)2013-7-29 7

对偶问题的对偶max z=6x1+9x2 s.t. x1+2x2≤2 2x1- 3x2≤3 x1+2x2≤-1 x1, x2≥0根据定义写 出对偶问题

minw=2y1+3y2-y3 s.t. y1+2y2+y3≥6 2y1-3y2+2y3≥9 y1, y2, y3≥0

根据定义写出对偶问题

max u=6w1+9w2 s.t. w1+2w2≤2 2w1- 3w2≤3 w1+2w2

≤-1 w1, w2≥0

2013-7-29

对偶问题的对偶就是原始问题。两个问题中的任一个都 可以作为原始问题。另一个就是它的对偶问题。 8

maxZ=x1+4x2+2x3 s.t. 5x1-x2+2x3≤8 x1+3x2-3x3≤5 x1,x2,x3≥0

minw=8y1+5y2 s.t. 5y1+y2≥1 -y1+3y2≥4 2y1-3y2 ≥2 y1,y2≥0

2013-7-29

三、非对称形式的原—对偶问题minz=2x1+3x2-5x3+x4 s.t. x1+x2-3x3+x4≥5 2x1 +2x3-x4≤4 x2+x3+x4=6 x1≤0,x2,x3≥0变为一般形式

x2+x3+x4≥6 x2+x3+x4≤6

-x1=x1’,x1≥0;x4’-x4”=x4,x4’ ≥0,x4” ≥0

minz=-2x1’+3x2-5x3+(x4’-x4”) s.t.-x1’+x2-3x3+(x4’-x4”)≥5 2x1’ -2x3+(x4’-x4”)≥-4 x2+x3 +(x4’-x4”) ≥6 -x2-x3-(x4’-x4”) ≥-6 x1’,x2,x3 ,x4’,x4” ≥02013-7-29

maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’ ≤-2 y1 y1 +(y3’-y3”) ≤3 y2’ 写出对偶问题 -3y1-2y2’ +(y3’-y3”) ≤ -5 y3’ y1+y2’+(y3’-y3”) ≤ 1 y3” -y1-y2’-(y3’-y3”) ≤-1 y1,y2’ ,y3’,y3”≥010

maxw=5y1-4y2’+6(y3’-y3”) s.t.-y1+2y2’ ≤-2 y1 +(y3’-y3”) ≤3 -3y1-2y2’ +(y3’-y3”) ≤ -5 y1+y2’+(y3’-y3”) ≤ 1 -y1-y2’-(y3’-y3”) ≤-1 y1,y2’ ,y3’,y3”≥0

设y2=-y2’,y3=y3’-y3”,则y2≤0,y3无约束 此时对偶问题变为 maxw=5y1+4y2+6y3 minz=2x1+3x2-5x3+x4 s.t. y1+2y2 ≥2 比较原问题 s.t. x1+x2-3x3+x4≥5 和对偶问题 y1 +y3 ≤3 2x1 +2x3-x4≤ 4 -3y1+2y2+y3 ≤ -5 x2+x3+x4 = 6 y1 -y2 +y3 = 1 x1≤0,x2,x3≥0 y1≥0 ,y2≤0,y3无约束2013-7-29 11

写对偶问题的练习(1)min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 ≥ 6 -x1+2x2-3x3 = 12 2x1+x2+2x3 ≤ 8 x1+3x2-x3 ≥ 15 x1≥0 x2≤0 x3: Free

max y=6w1+12w2+8w3+15w4 s.t. 3w1- w2+2w3+ w4≤ 2 -w1+2w2+ w3+3w4 ≥ 4 2w1- 3w2+2w3- w4 = -1 w1 ≥ 0,w2Free 3 ≤ 0,w4 ≥ 0 ,w

原始问题变量的个数(3)等于对偶问题约束条件的个数(3); 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。 原始问题变量的性质影响对偶问题约束条件的性质。 原始问题约束条件的性质影响对偶问题变量的性质。2013-7-29 12

写对偶问题的练习(2)原始问题

对偶问题

max z=2x1-x2+3x3-2x4 s.t. x1 +3x2 - 2x3 + x4≤12 -2x1 + x2 -3x4≥8 3x1 - 4x2 +5x3 - x4 = 15 x1≥0, x2:Free, x3≤0, x4≥0

min y=12w1+8w2+15w3 s.t. w1 - 2w2 + 3w3≥2 3w1 + w2 - 4w3=-1 -2w1 +5w3≤3 w1 - 3w2 - w3≥-2

w1≥0,w2≤0, w3:Free

2013-7-29

练习maxZ=x1-2x2+3x3 s.t. 2x1+4x2+3x3≥100 3x1-2x2+6x3≤200 5x1+3x2+4x3=150 x1, x3≥0minw=100y1+200y2+150y3 s.t. 2y1+3y2+5y3≥1 4y1-2y2+3y3= -2 3y1+6y2+4y3≥3 y1≤0,y2≥0

minZ=2x1+2x2+4x3 s.t. x1+3x2+4x3≥2 2x1+ x2+3x3≤3 x1+4x2+3x3=5 x1 ≥0, x2≤02013-7-29

maxw=2y1+3y2+5y3 s.t. y1+2y2+ y3≤2 3y1+ y2+4y3≥ 2 4y1+3y2+3y3≥4 y1≥0,y2≤014

原始和对偶问题可行解目标函数值比较min z=2x1+3x2 s.t. x1+3x2≥3 2x1+x2 ≥4 x1, x2 ≥04 C(0,4)

可行解 AD(2,2)B(1.8,0.4) A(3,0)

z 6 4.8 12 10

最优解 是

32 1 0 3 1

B C D

2

3

max w=3y1+4y

2 s.t. y1+2y2≤2 3y1+y2 ≤3 y1, y2 ≥02013-7-29

可行解 O AC(0,1) B(1.9,0.4) A(1,0) 0 1 2

w 0 3 4.8 4

最优解

21 O(0,0)

B C

是

对偶问题的基本性质一、单纯形法计算的矩阵描述Max Z=CX AX≤b X≥0 其中X=(x1,x2……xn)TMax Z=CX+0Xs AX+IXs=b X,Xs≥0 其中Xs=(xn+1,xn+2……xn+m)T I 为m×m的单位矩阵

2013-7-29

非基变量

基变量

XB0 Xs cj-zj …… 基变量 XB CB XB cj-zj B-1 b I 0 b B CB

XNN CN 非基变量 XN B-1N CN-CBB-1N

XsI 0

Xs B-1 -CBB-1

对应初始单纯形表中的单位矩阵I,迭代后的单纯形表中为B-1; 初始单纯形表中基变量Xs=b,迭代后的表中为XB=B-1b; 约束矩阵(A,I)=(B,N,I),迭代后为 (B-1B,B-1N,B-1I)=(I,B-1N,B-1); 初始单纯形表中xj的系数向量为Pj,迭代后为Pj’,且Pj’=B-1Pj’2013-7-29 17

当B为最优基时，XB为最优解时，则有： CN-CBB-1N≤0 -CBB-1≤0

∵CB-CBI=0代入得： CN-CBB-1N+CB-CBI≤0 C-CBB-1(B+N)≤0 整理得： C-CBB-1 A≤0 -CBB-1≤0

令CBB-1为单纯形乘子，Y‘=CBB-1 则： C-Y’ A≤0 Y’ A≥C’ -Y’≤0 Y’ ≥0 W=Y’b=CBB-1b=Z 所以当原问题为最优解时，对偶问题为可行解且具有相 同的目标函数值。 2013-7-29 18

maxZ=4.5x1+5x2 s.t. 3x1+2x2≤24 4x1+5x2≤40 x1,x2≥0

y1 y2

maxZ=4.5x1+5x2 s.t. 3x1+2x2+x3=24 4x1+5x2+x4=40 x1,x2,x3,x4,≥0

y1 y2

minw=24y1+40y2 s.t. 3y1+4y2≥4.5 2y1+5x2≥5 y1,y2≥0

x1 x2

minw=24y1+40y2 s.t. 3y1+4y2-y3=4.5 2y1+5x2-y4=5 y1,y2,y3,y4≥0

x1 x2

2013-7-29

解原问题：cj 4.5 5 0 0 θ 12 8

CB0 0

XBx3 x4 cj-zj

b24 40

x13 4 4.5

x22 5 5

x31 0 0

x40 1 0

2013-7-29

cj

4.5

5

0

0

θ 12 8

CB0 0 0

XBx3 x4 cj-zj x3

b24 40 8

x13 4 4.5 7/5

x22 5 5 0

x31 0 0 1

x40 1 0 -2/5

5

x2cj-zj

8

4/51/2

10

00

1/5-1

2013-7-29