第2章 对偶理论

第2章对偶理论1.原问题与对偶问题——掌握由原问题写出对偶问题的方法。

2.原始—对偶关系——只需了解原问题与对偶问题之间的关系。

3.对偶变量的经济解释——只需了解影子价格的涵义。第2章对偶理论§2.1原问题与对偶问题§2.2原始-对偶关系基本性质§2.3对偶变量的经济解释§2.1原问题与对偶问题

(LP)(DP)max

zminw

s.t.约束≤s.t.变量

≥0

约束=变量无符号限制变量

≥0约束≥变量无符号限制约束=具体对应关系见下表：§2.1原问题与对偶问题

§2.1原问题与对偶问题(LP)(DP)

max

z=5x1+4x2

min

w=15y1+5y2

+11y3

s.t.3x1

+5x2

≤15，s.t.

y1≥0，

2x1

+x2

≤5，y2≥0，

2x1

+2x2

≤11，y3≥0，

x1≥0，3y1

+2y2

+2y3≥5,x2≥0，5y1

+y2

+2y3≥4,

例1求解下面两线性规划§2.1原问题与对偶问题

对原问题(LP)，我们在第1章例1中已经用单纯形法求出它的最优解和最优值。现用单纯形法求出对偶问题(DP)的最优解和最优值。

例1（续）§2.1原问题与对偶问题

用单纯形法求对偶问题(DP)。

min

w=15y1+5y2

+11y3

s.t.3y1

+2y2

+2y3≥5,5y1

+y2

+2y3≥4,

y1≥0，y2≥0,y3≥0解：

化为标准形增加松弛变量S1和S2，第一阶段增加人工变量R1和R2

，得到第一阶段的最优解:

y1*=3/7,y2*=13/7,y3*=0,S1*=0,S2*=0,

R1*=0,R2*=0，最优值:

f*=0

得到原来问题的可行解:

y1=3/7,y2=13/7,y3=0,

S1=0,S2=0§2.1原问题与对偶问题

第二阶段得到原来问题的最优解:

y1*=3/7,y2*=13/7,y3*=0,

最优值：

w*=110/7。注意：（LP）与(DP)最优值比较！§2.1原问题与对偶问题§2.1原问题与对偶问题(LP)maxz=2x1+3x2+x3

s.t.

x1

+2x2

+x3≤6，

3x1

+5x2

-x3≤12，

x1≥0，

x2≥0，

x3≥0写对偶问题(1)(DP)min

w=6y1+12y2

s.t.

y1≥0，

y2≥0,

y1

+3y2

≥2,2y1

+5y2

≥3,

y1

-y2

≥1§2.1原问题与对偶问题

(LP)min

z=x1+2x2+5x3

s.t.

x1

-2x2

+5x3≤8，

2x1

+3x2

+x3=3，

4x1

-x2

+2x3≤6，

x1≥0，

x2≥0，

x3≥0写对偶问题（2）§2.1原问题与对偶问题(LP)minz=x1+2x2+5x3

s.t.-x1

+2x2

-5x3≥-8，

2x1

+3x2

+x3=3，

-4x1+x2

-2x3≥-6，

x1≥0，

x2≥0，

x3≥0写对偶问题（2）

(DP)max

w=-8y1+3y2-6y3

s.t.

y1≥0，

y2无符号限制,

y3≥0,-y1

+2y2-4y3

≤1,2y1

+3y2

+y3≤2,-5y1

+y2

-2y3≤5

§2.1原问题与对偶问题

(LP)max

z=x1+2x2+3x3

s.t.3x1

-2x2

+4x3=10，

x1

-x2

+2x3=7，

x1≥0，

x2无符号限制，

x3无符号限制写对偶问题（3）

(DP)min

w=10y1+7y2

s.t.

y1无符号限制，

y2无符号限制,3y1

+y2

≥1,-2y1

-y2

=2,4y1

+2y2

=3§2.1原问题与对偶问题(LP)maxz=2x1+x2-4x3

s.t.

x1

-x2

+2x3-x4

≥3，

2x1

+3x2

-x3+4x4

=6，

5x1

-x2

+x3-2x4

≤9，

x1≥0，

x2≥0，

x3无符号限制，

x4无符号限制写对偶问题（4）§2.1原问题与对偶问题(LP)maxz=2x1+x2-4x3

s.t.-x1

+x2

-2x3+x4

≤

-3，

2x1

+3x2

-x3+4x4

=6，

5x1

-x2

+x3-2x4

≤9，

x1≥0，

x2≥0，

x3无符号限制

x4无符号限制写对偶问题（4）(DP)minw=-3y1+6y2+9y3s.t.

y1≥0，

y2无符号限制

y3≥0,-y1

+2y2

+5y3≥2,

y1

+3y2-y3≥1,-2y1

-y2

+y3=-4

y1

+4y2

-2y3=0

Return

§2.2原始-对偶关系基本性质max

z=5x1+4x2

minw=15y1+5y2

+11y3

s.t.3x1

+5x2

≤15，s.t.

y1≥0，

2x1

+x2

≤5，y2≥0,2x1

+2x2

≤11，y3≥0,x1≥0，3y1

+2y2

+2y3≥5,x2≥0，5y1

+y2

+2y3≥4,(LP)(DP)例1（续）§2.2原始-对偶关系基本性质

用单纯形法求(LP)及对偶问题(DP)的最优解和最优值§2.2原始-对偶关系基本性质x1x2u1u2u3右端z100-3/7-13/70-110/7x2012/7-3/7015/7x110-1/75/7010/7u300-2/7-4/7127/7松弛变量

x3=u1,x4=u2,x5=u3y1y2y3v1v2右端w00-27/7-10/7-15/7110/7y2014/7-5/73/713/7y1102/71/7-2/73/7松弛变量

S1=v1,,S2=v2§2.2原始-对偶关系基本性质例2求下列线性规划问题及对偶最优解.

max

z=6x1-3x2

+3x3

s.t.2x1

+x2

≤8，

-4x1-2x2

+3x3

≤14，

x1

-2x2

+x3

≤18，

x1,x2

,x3≥0

§2.2原始-对偶关系基本性质x1x2x3u1u2u3右端z10-60-5-10-54x111/201/2004x30012/31/3010u30-5/20-7/6-1/314§2.2原始-对偶关系基本性质原问题的最优解:

x1*=4,x2*=0,x3*=10,原问题的最优值：

z*=54------------------------------对偶问题的最优解:

y1*=5,y2*=1,y3*=0,对偶问题的最优值：

w*=54§2.2原始-对偶关系基本性质§2.2原始-对偶关系基本性质两个基本定理（LP）min

z=CTXs.t.

AXbX0（DP）maxw=bTY

s.t.

ATYC

Y0

§2.2原始-对偶关系基本性质

【定理1】

CTX

bTY,X,Y.

CTX=bTY

X,Y分别是(LP)与(DP)的最优解。§2.2原始-对偶关系基本性质【定理2】（互补松弛）

若X,Y分别是(LP)和(DP)的最优解，则有(cj-YTaj)xj=0,j=1,2,…,nyi(

j=1naijxj-bi)=0,i=1,2,…,m§2.2原始-对偶关系基本性质

min

z=6x1+8x2+3x3

maxw=y1-y2

s.t.

x1

+x2

1，s.t.

y1+y26

，

x1

+2x2

+x3-1，y1+2y2

8,

x1,x2,x3≥0y2

3,

y1,y20(LP)(DP)例3§2.2原始-对偶关系基本性质

min

z=6x1+8x2+3x3

maxw=y1-y2

s.t.

x1

+x2

-x4

=1,

s.t.

y1+y2+y36

，

x1+2x2

+x3-x5

=-1，y1+2y2

+y48,

x1,x2,x3,x4,x5

0y2+y53,y1,y2,y3,y4,y50

(LP)(DP)

解:标准化§2.2原始-对偶关系基本性质用图解法求(DP)的最优解、最优值：(y1,y2)=(6,0),w=6松弛变量的值：(y3,y4,y5)=(0,2,3)解(续)§2.2原始-对偶关系基本性质由定理2：y1>0x4=0,y4>0x2=0y5>0x3=0再由(LP)约束：x1+x2-x4=1,x1+2x2+x3-x5=-1得：x1=1,x5=2（LP)的最优解、最优值：(x1,x2,x3)=(1,0,0),z=6

Return解(续)§2.3对偶变量的经济解释

maxz=5x1+4x2

min

w=15y1+5y2

+11y3

s.t.3x1

+5x2

≤15，s.t.

y1≥0，

2x1

+x2

≤5，y2≥0,2x1

+2x2

≤11，y3≥0,x1≥0，3y1

+2y2

+2y3≥5,x2≥05y1

+y2

+2y3≥4(LP)(DP)例1（续）原问题的最优解、最优值:x1*=10/7,x2*=15/7,z*=110/7对偶问题的最优解、最优值:y1*=3/7,y2*=13/7,y3*=0

w*=15y1*+5y2*+11y3*=110/7§2.3对偶变量的经济解释

如果第一种资源从15

16，则利润为

w=(15+1)y1*+5y2*+11y3*=15y1*+y1*+5y2*+11y3*=w*+y1*。

称y1*是第一种资源的影子价格。§2.3对偶变量的经济解释§2.3对偶变量的经济解释

只要根据原问题的最优单纯形表(不必再解对偶问题,不必写出对偶问题的单纯形表！)就可以写出原问题的最优解和对偶问题的最优解（检验数的相反数）。§2.3对偶变量的经济解释

原问题一个约束，对应对偶问题的