對偶問題運(yùn)籌學(xué)-課件

第四節(jié)對偶問題第四節(jié)對偶問題12.4.1對偶問題的提出2.4.2原問題與對偶問題2.4.3對偶問題的性質(zhì)2.4.4對偶變量的經(jīng)濟(jì)含義2.4.5對偶單純形法

第四節(jié)對偶問題2.4.1對偶問題的提出第四節(jié)對偶問題2精品資料精品資料3你怎么稱呼老師？如果老師最后沒有總結(jié)一節(jié)課的重點的難點，你是否會認(rèn)為老師的教學(xué)方法需要改進(jìn)？你所經(jīng)歷的課堂，是講座式還是討論式？教師的教鞭“不怕太陽曬，也不怕那風(fēng)雨狂，只怕先生罵我笨，沒有學(xué)問無顏見爹娘……”“太陽當(dāng)空照，花兒對我笑，小鳥說早早早……”對偶問題運(yùn)籌學(xué)-ppt課件4一、對偶問題的提出

某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，如表1-1所示。每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問應(yīng)如何安排計劃使該工廠獲利最多?一、對偶問題的提出某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、51.最大生產(chǎn)利潤模型設(shè)企業(yè)生產(chǎn)甲產(chǎn)品為X1件，乙產(chǎn)品為X2件，則

2.資源最低售價模型(原問題)<========>(對偶問題)設(shè)第i種資源價格為yi,(i=1,2,3)則有y1y2y3y46--第2章對偶問題--1.最大生產(chǎn)利潤模型設(shè)企業(yè)生產(chǎn)甲產(chǎn)品為X1件，6二、

原問題與對偶問題的關(guān)系一般表示式：原問題：maxz=c1X1+c2X2+┈+

cnXns.t

a11X1+a12X2+┈+

a1nXn

b1

a21X1+a22X2+┈+

a2nXn

b2

·······················

am1X1+am2X2+┈+

amnXn

bm

xj0，j=1,2,┈,n

對偶問題：minw=b1y1+b2y2+┈+bmym

s.t

a11y1+a21y2+┈+am1ym

c1

a12y1+a22y2+┈+am2ym

c2

·························

a1ny1+a2ny2+┈+amnym

cn

yi0，(i=1,2,···,m)二、原問題與對偶問題的關(guān)系一般表示式：7典式模型對應(yīng)對偶結(jié)構(gòu)矩陣表示（1） maxz=CX

s.tAX

b

X0

minw=Ybs.tYA

C

Y

0對偶問題原問題典式模型對應(yīng)對偶結(jié)構(gòu)矩陣表示（1） maxz=C8對偶模型其他結(jié)構(gòu)關(guān)系（2）若模型為 maxz=CX s.tAX

b

X0 maxz=CXs.t-AX-b

X0變形minw=Ybs.tYA

C

Y

0Minw=Y′(-b)st.Y′(-A)

C Y′

0令Y=-Y′對偶問題對偶變量Y

對偶模型其他結(jié)構(gòu)關(guān)系（2）若模型為 maxz9（3）maxz=CXs.tAX

b

X

0變形設(shè)X=-X′max=-CX′st.-AX′

b X′

0minw=Yb

s.tYA

C

Y

0則有minw=Yb

s.t-YA-C Y

0（3）maxz=CX10對偶問題典式：用矩陣形式表示：

（1）maxz=CXminw=Ybs.tAX

b<========>s.tYA

CX0Y0

（2）maxz=CXminw=Ybs.tAX

b<========>s.tYA

CX0Y

0

（3）maxz=CXminw=Ybs.tAX

b<========>s.tYA

CX

0Y0對偶問題典式：用矩陣形式表示：11原問題與對偶問題關(guān)系表

原問題(對偶問題)對偶問題(原問題)

目標(biāo)函數(shù)系數(shù) 約束右端項約束右端項 目標(biāo)函數(shù)系數(shù)約束條件系數(shù)列向量A 約束條件系數(shù)行向量AT

變量個數(shù) 約束條件個數(shù)

max min

變量xj: 約束方程i: xj

0

xj

無約束 = xj0

約束方程: 變量yi: yi

0 = yi

無約束

yi0 原問題與對偶問題關(guān)系表原問題(12例2-10寫出下述線性規(guī)劃問題的對偶問題。例子例2-10寫出下述線性規(guī)劃問題的對偶問題。例子13則由表中原問題和對偶問題的對應(yīng)關(guān)系，可以直接寫出上述問題的對偶問題對偶問題解法則由表中原問題和對偶問題的對應(yīng)關(guān)系，可以直接寫出上述問題的對14練習(xí)max

z=2y1+5y2+1y32y1+3y2+1y3

3

1y1-5y2+1y3

2

3y1

+1y3

-1≥=≤y1

≥0,y2≤0,y3自由s.t.解

min

ω=3

x1+2

x2-1

x32

x1+1x2+3x3≥

2

3

x1-5x2

≤

5

1

x1+1

x2+1

x3

=

1

x1≤0,

x3≥0

s.t.練習(xí)maxz=2y1+5y2+1y3≥=≤y1≥0,15三、對偶問題的性質(zhì)

性質(zhì)1

對稱性

規(guī)范原始、對偶問題(P1)與(D1)

互相對偶。即對偶問題的對偶是原問題。

性質(zhì)2

弱對偶性

設(shè)X,

Y分別為(P1)與(D1)的任意可行解，則

CX

≤Y

b

性質(zhì)3

最優(yōu)性

設(shè)X,Y分別為(P1)與(D1)的任意可行解，則當(dāng)

CX

=Yb

時，X,

Y分別是(P1)與(D1)的最優(yōu)解。三、對偶問題的性質(zhì)性質(zhì)1對稱性16三、對偶問題的性質(zhì)

性質(zhì)4無界性互為對偶的兩個線性規(guī)劃問題，若其中一個問題的解無界，則另一個問題無可行解。

性質(zhì)5對偶定理互為對偶的兩個線性規(guī)劃問題，若其中一個問題有最優(yōu)解，則另一個問題也有最優(yōu)解，且二者最優(yōu)值相等。

注意：無界性之逆命題不成立。因為一個問題無可行解時，另一個問題可能解無界，也可能無可行解。三、對偶問題的性質(zhì)性質(zhì)4無界性17三、對偶問題的性質(zhì)

兼容性

原始問題的檢驗行的相反數(shù)給出對偶問題的一個基本解。

X*=(4,6,4,0,

0)T,

z*

=

42y1y2y3y4y5Y*=(0,1/2,1,0,

0)T,

w*

=

42σ3σ4σ5σ1σ2互補(bǔ)基本解x3x2x1

x1x2x3x4x5

3

5

00

005

360

1

01/2

040

0

11/3

-1/3

4100-2/3

1/3420

0

0-1/2

-1cj

比值

基

解

三、對偶問題的性質(zhì)X*=(4,6,4,0,0)T18

:max

z=3x1

+5x2

x1≤82x2≤123x1+4x2≤36x1，

x2≥0s.t.(

P1):minw=8y1+12y2+36y3

y1+3y3≥32y2+4y3≥5y1,y2,y3≥0s.t.(

D1):max

z=3x1

+5x2

x1+x3=82x2+x4

=123x1+4x2+x5

=36x1,

x2,

x3,

x4,

x5

≥0s.t.(

Ps):minw=8y1+12y2+36y3

y1+3y3-y4

=32y2+4y3-y5

=5y1,

y2,y3,

y4,y5≥

0s.t.(

Ds)X*=

(4,6)TY*=

(0,?,1)TX*=(4,6,4,0,

0)T

Y*=(0,1/2,1,0,

0)T,

z*=

42

=w*:maxz=3x1+5x2s.t.(P1):19

(P)的基本解

與(D)的基本解

相互對應(yīng),

且二者目標(biāo)值相等。我們把這樣一對基本解

與

，稱為(P)與(D)的互補(bǔ)基本解。(P)

目

標(biāo)

值

(D)

序號

極點

基

本

解

k

Xk可

行

z

=

w

Yk可

行

基

本

解

k

1

O

(0

，0

，8

，12

，36)

是

0

否

(0

，0

，0

，-3

，-5)

2

A

(8

，0

，0

，12

，12)

是

24

否

(3

，0

，0

，0

，-5)

3

D

(0

，6

，8

，0

，12)

是

30

否

(0

，5/2

，0

，-3

，0)

4

B

(8

，3

，0

，6

，0)

是

39

否

(-

3/4

，0

，5/4

，0

，0)

5

C

(4

，6

，4

，0

，0)

是

42

是

(0

，1/2

，1

，0

，0)

6

E

(12

，0

，-4

，12

，0)

否

36

否

(0,0,1,0,-1)

7

G

(0

，9

，8

，-6

，0)

否

45

是

(0,

0,5/4,3/4,0)

8

F

(8

，6

，0

，0,-

12)

否

54

是

(3,5/2,0,0,0)

(P)的基本解與(D)的基本解相互對應(yīng)207.

互補(bǔ)松弛性

設(shè)

=

(x1

,x2

,…

,xn

,xn+1,

…

,xn+m)T

=

(y1

,y2

,…

,ym

,ym+1,

…

,ym+n)T是(P1)

(D1)的一對互補(bǔ)基本解，那么

⑴xj

ym+j

=

0，j=1,2,…,n

⑵

xn+i

yi

=

0，i=1,2,…,m7.互補(bǔ)松弛性設(shè)⑴xj21例

已知線性規(guī)劃問題minω=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其對偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試用對偶理論找出原問題的最優(yōu)解。例已知線性規(guī)劃問題minω=2x1+3x2+5x3+222解：先寫出它的對偶問題maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0﹥解：先寫出它的對偶問題maxz=4y1+3y2﹥23將y1*=4/5,y2*=3/5的值代入約束條件，得②=1/5<3，③=17/5<5，④=7/5<2

它們?yōu)閲?yán)格不等式；由互補(bǔ)松弛性得x2*=x3*=x4*=0。因y1，y2﹥0；原問題的兩個約束條件應(yīng)取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問題的最優(yōu)解為X*=(1，0，0，0，1)T；ω*=5將y1*=4/5,y2*=3/5的值代入約束條件，得②=24對偶變量的意義代表對企業(yè)資源的估價，與該種資源的市場價格不同，因此我們稱之為影子價格。四、

對偶變量的經(jīng)濟(jì)含義對偶變量的意義代表對企業(yè)資源的估價，與該種資源的市場價格不同25（1）資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價格也隨之改變。（2）影子價格是一種邊際價格，在（2-12）式中將Z對

求偏導(dǎo)數(shù)得

，這說明

相當(dāng)于在給定的生產(chǎn)條件下，

每增加一個單位目標(biāo)函數(shù)Z的增量。（3）資源的影子價格實際上又是一種機(jī)會成本。在純市場經(jīng)濟(jì)條件下，當(dāng)?shù)?種資源的市場價格低于1/4時，可以買進(jìn)這種資源；相反當(dāng)市場價格高于影子價格時，就會賣出這種資源。隨著資源的買進(jìn)賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。（1）資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則26對偶問題運(yùn)籌學(xué)-ppt課件27五、

對偶單純形法由于單純表中同時反映原問題與對偶問題的最優(yōu)解，故可以從求對偶問題最優(yōu)解角度求解LP模型。例：minz=2x1+3x2maxz'=-2x1-3x2+0x3+0x4 s.tx1+x2

3標(biāo)準(zhǔn)化s.tx1+x2-x3=3 x1+2x2

4

x1+2x2-x4=4 x1

0,x2

0 xj

0,(j=1,2,3,4)maxz'=-2x1-3x2+0x3+0x4

s.t-x1-x2+x3=-3

-x1-2x2+x4=-4 xj

0,(j=1,2,3,4)五、對偶單純形法由于單純表中同時反映原問題與對偶問題的最優(yōu)28Cj→x1x2x3x4XBbCB-1 -1 1 0-1 -2 01-2 -3 0 0-3-4x3x400cj-zj-2-300-1/2 0 1 -1/21/2 1 0-1/2x3x2-12cj-zj-1/2 00-3/20-31 0 -2101 1-1x1x221cj-zj0 0 -1 -1-2-3列單純表計算：Cj→x1x2x3x4XBbCB-1 -1 29對偶單純形法步驟：1°把m階LP問題化成標(biāo)準(zhǔn)形（允許其右端常數(shù)為負(fù)）,

在其系數(shù)陣中找出或構(gòu)造一個m階排列陣作初始基,

建立初始單純形表。若所有檢驗數(shù)

j≤0，則轉(zhuǎn)2°;

2°最優(yōu)性檢驗：檢查表中解列各數(shù)值bi；若所有bi≥0,

則問題已得最優(yōu)解，停止計算;否則轉(zhuǎn)3°。3°無可行解判斷：只要存在一個br<0，它所在行中所有arj≥0，則原始問題無可行解，對偶問題無下界，停止；否則轉(zhuǎn)4°。對偶單純形法步驟：1°把m階LP問題化成標(biāo)準(zhǔn)形（允許其右端常304°確定主元：先確定離基變量，按

min{bi︱bi<0}=bl

確定第

l

行的基變量

xBl離基，第

l

行為主行；

后確定進(jìn)基變量，按最小比值規(guī)則：

min{

j/

alj︱alj<0}=

k

/

alk

確定進(jìn)基變量xk及主元alk。5°按主元alk對當(dāng)前表格進(jìn)行一次換基運(yùn)算，得到一個新單純形表，返2°

。4°確定主元：先確定離基變量，按31練習(xí)min

z

=3x1+2x2s.t.2x1+3x2≤18x1

-x2≥2x1+3x2≥10x1,x2≥0解max

z′=-3x1-2x2s.t.2x1+3x2+x3

=18x1

-x2

–x4

=2x1+3x2

–x5

=10x1,x2,x3,x4,x5≥0–x1+x2

+x4

=

–2–x1–3x2

+x5=

–1032第3章對偶原理練習(xí)minz=3x1+2x2s.t.2x1+3x2≤32maxz′=-3x1-2x2

2x1+3x2+x3

=18

-x1

+x2

+x4

=

-2

-x1-3x2

+x5

=

-10x1,x2,x3,x4,x5≥0

s.t.cj

基

解

x1x2x3x4x5

-3

-2

00

0

2

3

10

0x3x4

x5

18-2

-10

-1

1

01

0000

-1

-3

00

1

0

-3

-2

0

0

032/3min-3比值

33第3章對偶原理maxz′=-3x1-2x2s.t.cj基解33cj

基

解

x1x2x3x4