第2章 對(duì)偶理論

第2章對(duì)偶理論1.原問題與對(duì)偶問題——掌握由原問題寫出對(duì)偶問題的方法。

2.原始—對(duì)偶關(guān)系——只需了解原問題與對(duì)偶問題之間的關(guān)系。

3.對(duì)偶變量的經(jīng)濟(jì)解釋——只需了解影子價(jià)格的涵義。第2章對(duì)偶理論§2.1原問題與對(duì)偶問題§2.2原始-對(duì)偶關(guān)系基本性質(zhì)§2.3對(duì)偶變量的經(jīng)濟(jì)解釋§2.1原問題與對(duì)偶問題

(LP)(DP)max

zminw

s.t.約束≤s.t.變量

≥0

約束=變量無符號(hào)限制變量

≥0約束≥變量無符號(hào)限制約束=具體對(duì)應(yīng)關(guān)系見下表：§2.1原問題與對(duì)偶問題

§2.1原問題與對(duì)偶問題(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求解下面兩線性規(guī)劃§2.1原問題與對(duì)偶問題

對(duì)原問題(LP)，我們?cè)诘?章例1中已經(jīng)用單純形法求出它的最優(yōu)解和最優(yōu)值。現(xiàn)用單純形法求出對(duì)偶問題(DP)的最優(yōu)解和最優(yōu)值。

例1（續(xù)）§2.1原問題與對(duì)偶問題

用單純形法求對(duì)偶問題(DP)。

min

w=15y1+5y2

+11y3

s.t.3y1

+2y2

+2y3≥5,5y1

+y2

+2y3≥4,

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

化為標(biāo)準(zhǔn)形增加松弛變量S1和S2，第一階段增加人工變量R1和R2

，得到第一階段的最優(yōu)解:

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

R1*=0,R2*=0，最優(yōu)值:

f*=0

得到原來問題的可行解:

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

S1=0,S2=0§2.1原問題與對(duì)偶問題

第二階段得到原來問題的最優(yōu)解:

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

最優(yōu)值：

w*=110/7。注意：（LP）與(DP)最優(yōu)值比較！§2.1原問題與對(duì)偶問題§2.1原問題與對(duì)偶問題(LP)maxz=2x1+3x2+x3

s.t.

x1

+2x2

+x3≤6，

3x1

+5x2

-x3≤12，

x1≥0，

x2≥0，

x3≥0寫對(duì)偶問題(1)(DP)min

w=6y1+12y2

s.t.

y1≥0，

y2≥0,

y1

+3y2

≥2,2y1

+5y2

≥3,

y1

-y2

≥1§2.1原問題與對(duì)偶問題

(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寫對(duì)偶問題（2）§2.1原問題與對(duì)偶問題(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寫對(duì)偶問題（2）

(DP)max

w=-8y1+3y2-6y3

s.t.

y1≥0，

y2無符號(hào)限制,

y3≥0,-y1

+2y2-4y3

≤1,2y1

+3y2

+y3≤2,-5y1

+y2

-2y3≤5

§2.1原問題與對(duì)偶問題

(LP)max

z=x1+2x2+3x3

s.t.3x1

-2x2

+4x3=10，

x1

-x2

+2x3=7，

x1≥0，

x2無符號(hào)限制，

x3無符號(hào)限制寫對(duì)偶問題（3）

(DP)min

w=10y1+7y2

s.t.

y1無符號(hào)限制，

y2無符號(hào)限制,3y1

+y2

≥1,-2y1

-y2

=2,4y1

+2y2

=3§2.1原問題與對(duì)偶問題(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無符號(hào)限制，

x4無符號(hào)限制寫對(duì)偶問題（4）§2.1原問題與對(duì)偶問題(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無符號(hào)限制

x4無符號(hào)限制寫對(duì)偶問題（4）(DP)minw=-3y1+6y2+9y3s.t.

y1≥0，

y2無符號(hào)限制

y3≥0,-y1

+2y2

+5y3≥2,

y1

+3y2-y3≥1,-2y1

-y2

+y3=-4

y1

+4y2

-2y3=0

Return

§2.2原始-對(duì)偶關(guān)系基本性質(zhì)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（續(xù)）§2.2原始-對(duì)偶關(guān)系基本性質(zhì)

用單純形法求(LP)及對(duì)偶問題(DP)的最優(yōu)解和最優(yōu)值§2.2原始-對(duì)偶關(guān)系基本性質(zhì)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原始-對(duì)偶關(guān)系基本性質(zhì)例2求下列線性規(guī)劃問題及對(duì)偶最優(yōu)解.

max

z=6x1-3x2

+3x3

s.t.2x1

+x2

≤8，

-4x1-2x2

+3x3

≤14，

x1

-2x2

+x3

≤18，

x1,x2

,x3≥0

§2.2原始-對(duì)偶關(guān)系基本性質(zhì)x1x2x3u1u2u3右端z10-60-5-10-54x111/201/2004x30012/31/3010u30-5/20-7/6-1/314§2.2原始-對(duì)偶關(guān)系基本性質(zhì)原問題的最優(yōu)解:

x1*=4,x2*=0,x3*=10,原問題的最優(yōu)值：

z*=54------------------------------對(duì)偶問題的最優(yōu)解:

y1*=5,y2*=1,y3*=0,對(duì)偶問題的最優(yōu)值：

w*=54§2.2原始-對(duì)偶關(guān)系基本性質(zhì)§2.2原始-對(duì)偶關(guān)系基本性質(zhì)兩個(gè)基本定理（LP）min

z=CTXs.t.

AXbX0（DP）maxw=bTY

s.t.

ATYC

Y0

§2.2原始-對(duì)偶關(guān)系基本性質(zhì)

【定理1】

CTX

bTY,X,Y.

CTX=bTY

X,Y分別是(LP)與(DP)的最優(yōu)解?！?.2原始-對(duì)偶關(guān)系基本性質(zhì)【定理2】（互補(bǔ)松弛）

若X,Y分別是(LP)和(DP)的最優(yōu)解，則有(cj-YTaj)xj=0,j=1,2,…,nyi(

j=1naijxj-bi)=0,i=1,2,…,m§2.2原始-對(duì)偶關(guān)系基本性質(zhì)

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原始-對(duì)偶關(guān)系基本性質(zhì)

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)

解:標(biāo)準(zhǔn)化§2.2原始-對(duì)偶關(guān)系基本性質(zhì)用圖解法求(DP)的最優(yōu)解、最優(yōu)值：(y1,y2)=(6,0),w=6松弛變量的值：(y3,y4,y5)=(0,2,3)解(續(xù))§2.2原始-對(duì)偶關(guān)系基本性質(zhì)由定理2：y1>0x4=0,y4>0x2=0y5>0x3=0再由(LP)約束：x1+x2-x4=1,x1+2x2+x3-x5=-1得：x1=1,x5=2（LP)的最優(yōu)解、最優(yōu)值：(x1,x2,x3)=(1,0,0),z=6

Return解(續(xù))§2.3對(duì)偶變量的經(jīng)濟(jì)解釋

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（續(xù)）原問題的最優(yōu)解、最優(yōu)值:x1*=10/7,x2*=15/7,z*=110/7對(duì)偶問題的最優(yōu)解、最優(yōu)值:y1*=3/7,y2*=13/7,y3*=0

w*=15y1*+5y2*+11y3*=110/7§2.3對(duì)偶變量的經(jīng)濟(jì)解釋

如果第一種資源從15

16，則利潤為

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

稱y1*是第一種資源的影子價(jià)格?！?.3對(duì)偶變量的經(jīng)濟(jì)解釋§2.3對(duì)偶變量的經(jīng)濟(jì)解釋

只要根據(jù)原問題的最優(yōu)單純形表(不必再解對(duì)偶問題,不必寫出對(duì)偶問題的單純形表！)就可以寫出原問題的最優(yōu)解和對(duì)偶問題的最優(yōu)解（檢驗(yàn)數(shù)的相反數(shù)）?！?.3對(duì)偶變量的經(jīng)濟(jì)解釋

原問題一個(gè)約束，對(duì)應(yīng)對(duì)偶問題的