运筹学对偶单纯形法

第三章对偶模型

•线性规划的对偶关系•线性规划的对偶性质•对偶单纯形法

3.1.1对偶问题

例1：资源分配模型

某装备厂拟生产甲、乙两种新产品，每件利润分别为300元和200元。甲、乙产品的部件分别在A、B两个车间生产，每件甲、乙产品的部件分别消耗A、B车间1,2小时。两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别消耗2小时和3小时。已知A、B、C车间每周可用于这两种产品的最大生产能力分别为6小时、8小时、18小时。该工厂应如何安排生产才能使得工厂获利最大？

工时利润（百元/工时）

y1 y2y3

产品

车间

单耗（工时/件）

甲乙

最大生产能力（工时/天）

A B C

单位利润（百元/件）

102

0 2 3

6 8 18

3 2

ω

由于原拟用于生产每件甲产品的1个A工时和2个c工时能创造3百元利润，所以出租上述数量的各资源的盈利起码应不低于3百元。

w=6y1+8y2+18y3

1y1+0y2+2y3≥ 30y1+2y2+3y3≥ 2y1，y2，y3≥ 0

①②③

min w=6y1 +8y2 +18y3y1 + 2y3≥ 3

2y2 +3y3 ≥ 2 y1 ,y2,y3 ≥ 0

Y*=(5/3,0,2/3)T w*=22maxz=3 x1+2x2

x1≤ 6

2x2≤ 8

2 x1+3x2≤ 18x1，x2≥ 0

z* =22

X*=(6,2)T

max 型min 型

x1≥0x2≥0102

≥

y1≥0y2≥0y3≥0

0 2 3

≥

≤ ≤ ≤z

6 818

w

32

min w=6y1+8y2+18y31y1+0y2+2y3≥3s.t.0y+2y+3y≥2

123

y1，y2，y3≥0

①②③

关系2：标准形LP问题的对偶关系

(P2):

(D2):

maxz=CTX

AX=bs.t.

X≥0

=bTY

ATY≥CY自由

min w

例1

maxz=3 x1 -1 x2 -2 x33 x1 +2 x2 -3 x3 =61 x1-2 x2 +1 x3 =4

x1, x2, x3≥ 0w=6y1 +4y2

3y1 +1 y2 ≥ 3

2y1 -2 y2 ≥ -1-3y1 + 1y2≥ -2y1,y2自由

y1 y2

min

例2

minω= 3x1+2x2 -1x3

2x1+1 x2+3x3 ≥2 3x1 -5 x2≤5

1x1+1x2+1x3=1x1≤0,x3 ≥0maxz = 2y1+5y2+1y32 y1+3 y2 +1y3≥3

1 y1 -5 y2 +1y3=2

3 y1 +1y3≤-1y1≥0,y2 ≤0,y3自由

解

例3

解

minω= 2x1+x2 +3x3+4x4

1x1+3 x2+2x3+x4 =5 2x1 -2 x2+3x3≤1

3x1+1x2-2x3≥2x1 ≥0,x2 ≤0,x4≥0maxz = 5y1+1y2+2y3

1 y1+2 y2 +3y3≤2s.t.3 y1 -2 y2 +1y3≥1

2 y1 +3y2+1y3=3

≤4y1

y1自由,y2 ≤0,y3≥0

3.2 线性规划的对偶性质

对称性

规范原始、对偶问题(P1)与(D1)互相对偶。弱对偶性

设X,Y分别为(P1)与(D1)的任意可行解，则

CTX≤bTY

最优性

设X,Y分别为(P1)与(D1)的可行解，则当

CTX= bTY

时，X,Y分别是(P1)与(D1)的最优解。

线性规划的对偶定理

对(P1)与(D1)而言：

(1)若其中一个问题有最优解，则另一个问题也有最优解，

且二者最优值相等。

（强对偶性）

(2)若其中一个问题的，则另一个问题。

（无界性）

：(2)之逆命题不成立。因为一个问题时，

另一个问题可能，也可能。

性。

互补性原始问题与对偶问题的变量或基本解之间具有互补决策变量vs 松弛变量

基变量vs 非基变量

(P1):

maxz = CTX(D1):minw = bTY

AX≤bX≥0

(Ps):

maxz = CTXAX+Xs=bX,Xs≥0

X vs YsYvs Xss.t.AT

Y≥C

Y≥0

s):minw = bTY

s.t.

ATY-Ys=CY,Ys≥0

xjvs ym+jyivs xn+j

(D

cj

-6-18

-6

基解

y15/3 1y32/3

-8-18 00y1 y2 y3 y4 y5

-4/3

0 -1

2/3

比值

0 2/3 1 0

4

0 6

-1/3

2

-22 0

x3x4x5x1x2

: maxz= 3x1+2x2(P1)

x1 ≤ 6

2x2 ≤ 8

2x1 +3x2 ≤ 18x1 ，x2 ≥ 0

X*=(6 ,2)T

(Ps): maxz= 3x1+2x2

x1 +x3 = 6

= 82x2 +x4

2x1 +3x2 +x5= 18

x1,x2 ,x3 ,x4 ,x5≥ 0*=(6 ,2 ,0,4 ,0)T

z*=22= w*

(D1):min w=6y1+8y2+18y3

s.t.

y1 ,y2,

y3 ≥ 0

(Ds):min w=6y1+8y2+18y3

y1 +2y3≥ 3 y1 +2y3 -y4=3

s.t.2y2+3y3 ≥ 2

2y2+3y3 -y5=2

y1 ,y2 ,y3 ,y4 ,y5 ≥0

Y*=(5/3 ,0,2/3)T

*=(5/3 ,0 ,2/3,0,0)T

(P)的基本解与(D)的基本解相互对应,且二者目标值相等。我们把这样一对基本解与，称为(P)与(D)的。

序极号点

(P)

目标值

(D)

12345678

O

DCABGFE

Xk可行z=wYk可行基本解k基本解k

(006818)是0否(000-3-2)(04606)8是否(010-30)(34300)17是否(0-1/43/200)(60086)18是否(3000-2)(62040)22是是(5/302/300)(066-40)12否否(002/3-5/30)(6400-6)26否是(31000)(90-380)27否是(003/205/2)

设

T

=( x1, x2, …, xn, xn+1, …, xn+m)

T

=( y1, y2, …, ym, ym+1, …, ym+n)是(P1)(D1)的一对互补基本解，那么⑴xjym+j=0，j = 1, 2 , … , n⑵xn+iyi=0，i = 1, 2 , … , m

特别对非退化的和，若可行，则有

⑶xj>0 ⇔ym+j=0，j = 1, 2 , … , n⑷xn+i>0 ⇔yi=0，i = 1, 2 , … , m若可行，则有

⑸ym+j>0 ⇔xj =0，⑹yi>0 ⇔xn+i=0，

j = 1, 2 , … , ni = 1, 2 , … , m

3.2.2 对偶关系的经济解释

根据对偶性质，线性规划的互补基本解目标函数值相等：

z= ∑cjxjz=∑bi yi= w

求z关于bi的偏导数，得

z=yibi

可见，对偶变量yi 在经济上表示原始问题第i 种资源的,即当bi单独增加一个单位时，相应的目标值z的增量∆z；特别对最优解来说，对偶变量的值yi* 所表示的第i 种资源的边际价值，称为。

对偶变量的经济解释

当目标函数值z 表示时，yi* 相应地称为；当z 表示时，yi*相应地称为。

一、当yi* 代表影子价格（即企业的目标是实现最大总产值）时

(1) 对资源i 总存量的评估。设资源i 的市场价格为pi，那么，当yi* ≥pi 时，企业可以买进该资源，即增加其总存量；当yi*

(2) 对资源i 现行分配量的评估。当资源i 在市场上脱销时，其总存量无法增加，但可酌情调整其在企业内部的现行分配量，以便获得最佳经济效益。

二、当yi* 代表影子利润（即企业的目标是实现最大总利润）时：

(1) 对资源i总存量的评估。

(2) 对资源i现行分配量的评估。

对偶问题的经济解释

问题(D1):minw =∑byi ii =1mj = 1, 2 , … , n

i = 1, 2 , … , m

由前已知: ≥ayc，jiijs.ti =1yi≥0，m①②

yi ——一个单位的资源i 对总产值ω的贡献

bi ——在这n项经营活动中，资源i 的投入量

cj ——一个单位的第j 项经营活动所创造的产值

aji ——一个单位的第j 项经营活动消耗的资源i 的数量

所以①式意味着：这m种资源对一个单位的第j 项经营活动的贡献，至少应当跟经营一个单位的第j 项活动所创造的产值一样多,否则，这些资源的利用就未臻尽善。

而②式意味着：资源i 对产值的单位贡献不得为负，否则就不能利用这种资源。⓪式意味着：测定各项经营活动所消耗的各种资源的总的隐含价值所能接受的最低限度。

互补松弛性的经济解释

考虑性质8(1) ：xj > 0 →ym+j=0 因有

ayy=c，-jii m+jji =1

所以ym+j= 0必然导致

i =1mj =1, 2 , … , n ajiyi=cj，m

j =1, 2 , … , n

因此，性质8(1) 的经济解释是: 当一个单位的任一经营活动j在严格正水平(xj >0)上经营时，它所消耗的各种资源的边际价值总和必定等于该项活动所产生的单位价值cj 。

譬如，已知

X*=(6, 2, 0,4, 0)T，Y*=(5/3,0, 2/3,0, 0)T

x1 =6> 0 →y4=0，则使y1+2y3-y4=3→ y1+2y3=3

类似考虑：

xn+i > 0→yi=0, i =1, 2 , … , m

其中xn+i 是约束i的松弛变量，而xn+i > 0意味着约束i有松弛部分.

因此，的经济解释是：当资源i的供量未被各项经营活动耗尽时，该种资源的边际价值必定为0。

按供求规律，供应过剩的货物必然跌价，以至无利可赚，甚至蚀本。譬如：xn+2 =x4 =4> 0，这说明B工时这种资源的供量除满足甲、乙产品之需外，还多余4个工时，这就导致它的影子利润y2=0。这意味着即便再增加它的供量，对甲、乙产品的总利润也毫无贡献, 即无利可赚。

4°：先确定离基变量，按

min { bi︱bi

确定第l行的基变量xBl 离基，第l行为主行；

后确定进基变量，按：

max { j /alj︱alj

确定进基变量xk 及主元alk。

5°按主元alk 对当前表格进行一次，

得到一个新单纯形表，返2°。

例3-4

max(-w)=-6y1-8y2-18y3s.t.

y1 +2y3 -y4

=3

2y2+3y3 -y5=2y1 ,y2 ,y3 ,y4 ,y5 ≥0

max(-w)=-6y1-8y2-18y3s.t.

-y1 -2y3 +y4

=-3

-2y2-3y3 +y5=-2y1 ,y2 ,y3 ,y4 ,y5 ≥0

3. 3. 2 人工对偶单纯形法

当获得排列阵形式的初始基时，若检验数不全非负，就需要引进一个人工变量x0≥0，并引进一个：

x0+xj+xj+ …+xj= M

1

2

t

(3-7)

其中

xj——一切负检验数对应的变量(r= 1, 2, …, t)

r

从中找出最小检验数对应的变量xp ，并将(3-7)改写成

xp = M-x0-jx≠pj

r

r

(3-8)

将其代入目标函数和除(3-7)以外的各约束中, 得到人工问题. 建立初始单纯形表，必然所有检验

j≥0. 以下可按规范对偶单纯形法的步骤运行，

但2°须作以下调整：

2°若解列存在bi

否则停止迭代. 这时, 若除了人工变量x0以外，其他变量取值均为有限，则得到原问题的最优解；否则原问题为解无界。

例3-5

maxz=3x1-2x2+x3x1+x2-x3≥ 42x1+3x2+x3≤ 203x1+x2+x3≤ 28x1,x2，x3≥ 0

标准化

maxz=3x1-2x2+x3x1+ x2-x3-x4= 4

+x5= 202x1+3x2+x3

+x6= 283x1+x2+x3

x1,x2，x3,x4，x5，x6≥0

以x4，x5，x6为基变量，算得非基变量的检验数：

1 =-30，3 =-1

因1，3为负，故引入人工约束

x0+x 1 +x 3 =M (a)

因最小检验数为1 =-3，故将上式改写成

x1=M -x0-x 3

代入(3-9)中，并添上人工约束(a)，得人工问题：

maxz= -3x0-2x2-2x3+3M

x0

-x2+2x3+x4

-2x0

+3x2-x3-3x0

+x2

-2x3

x0+x1

+x3

x0,x1, x2，x3,x4，=M -4

x5

=-2M+20+x6=-3M+28

=M

x5，x6≥0

+s.t.

cj000000-30

-30-2-2 0 00x0x1x2 x3 x4 x5 x6基解

x410-12 1 00M-4

x5-2M+20-20 3 -1 0 10x6-3M+28-330 1 -20 01

x11 1 0 1 0 0 0M

3M30 2 20 00

x4

x5

x0

x1

16/3 0 0 -2/3 4/3 4/3 0 0 7/3 1/3 M-28/3 1 0 -1/3 2/3 28/3 0 1 1/3 1/3

28 0

0 3 0

1 0 1/30 1 -2/30 0 -1/30 0 1/3

0 0

1

cj

00-30

-3

x0基解

x416/3 0 0 -2/3 4/3 1 x50 4/3 0 0 7/3 1/3

Tx0M-28/3 1 X1*=(28/3,0 ,0)0 -1/3 2/3 0

x128/3 0 1 1/3 1/3 0

x1-2-2 0 00x2 x3 x4 x5 x6

0 1/31 -2/30 -1/30 1/30 011 -4 3

3 -2-2 1-1 101

x4

-2x3

28 00 3 0 0 0 -10 4 M-12 8 28

-3

x0

x1

0 0 7 1 0 -5 *X2=,0 ,0 1(8-2 00 3

z*=28

0 1 0 T4)0 0

0 0 0 0

X*

=( 828/3

8X*

=μ 0 +(1 -μ)

0 04

8+4μ/3

=

0 4 -4μ

+4μ/3,0, 4-4μ)T

, μ∈[0, 1]

例3-6

max z=x1+2x2x1 -x2≥ 12x1+x2≥ 2x1 ,x2≥ 0

标准化：

max z=x1+2x2x1-x2-x3=12x1 +x2-x4=2x1 ,x2,x3 ,x4≥ 0

典式化：

max z=x1+2x2-x1+x2+x3=-1-2x1 -x2+x4=-2x1 ,x2,x3 ,x4≥ 0

cj

基

解

120 0x1 x2 x3 x4-1 1 1

1 1-20

-2 0 0 10 0 1 0 3 2 3 1 0 0

010

尚不能判定解无界

00

0212

x3x4

-1-2

0 -1 x3-3x22

x1

1 1

0 -10 -2 -1/3-1/32/3-1/3 1 -1 x2

41 0 1

例3-7

max z=x1+x22x1 +3x2≤-1x1+x2≥ 2x1 ,x2≥ 0

标准化：

max z=x1+x2-2x1-3x2+x3 =1x1 +x2-x4=2x1 ,x2,x3 ,x4≥ 0