第3章：動態(tài)規(guī)劃

第三章：動態(tài)規(guī)劃3.1基本概念一、動態(tài)決策問題決策過程具有階段性和時序性(與時間有關(guān))的決策問題。即決策過程可劃分為明顯的階段。二、什么叫動態(tài)規(guī)劃(D.P.–DynamicProgram)

多階段決策問題最優(yōu)化的一種方法。廣泛應(yīng)用于工業(yè)技術(shù)、生產(chǎn)管理、企業(yè)管理、經(jīng)濟(jì)、軍事等領(lǐng)域。三、動態(tài)規(guī)劃(D.P.)的起源

1951年,(美)數(shù)學(xué)家R.Bellman等提出最優(yōu)化原理，從而建立動態(tài)規(guī)劃，名著《動態(tài)規(guī)劃》于1957年出版。四、動態(tài)決策問題分類1、按數(shù)據(jù)給出的形式分為：

離散型動態(tài)決策問題。

連續(xù)型動態(tài)決策問題。2、按決策過程演變的性質(zhì)分為：

確定型動態(tài)決策問題。

隨機(jī)型動態(tài)決策問題。1五、動態(tài)決策問題的基本要素AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、階段(stage)n：作出決策的若干輪次。n=1、2、3、4、5。2、狀態(tài)(state)Sn：每一階段的出發(fā)位置。構(gòu)成狀態(tài)集，記為Sn

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。階段的起點。3、決策(decision)Xn：從一個階段某狀態(tài)演變到下一個階段某狀態(tài)的選擇。構(gòu)成決策集，記為Dn(Sn)。

階段的終點。

D1(S1)={X1(A)}={B1,B2,B3}=S2，

D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，

D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，

D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，

D5(S5)={X5(E1),X5(E2)}={F;F}={F}。2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、策略(policy)：全過程中各個階段的決策Xn組成的有序總體{Xn}。如A

B2

C1

D1

E2

F

上例從A

F共有38種走法，即有38條路線，38個策略。5、子策略(sub-policy)

：剩下的n個階段構(gòu)成n子過程，相應(yīng)的決策系列叫n子策略。如

C1

D1

E2

F6、狀態(tài)轉(zhuǎn)移方程：前一階段的終點(決策)是后前一階段的起點(狀態(tài))。

Xn

=Sn+17、指標(biāo)函數(shù)：各個階段的數(shù)量指標(biāo)，記為rn(sn,xn)。如上例中，用dn(sn,xn)表示距離。d2(B3,C2)=1,d3(C2,D3)=6等。8、目標(biāo)函數(shù)：策略的數(shù)量指標(biāo)值，記為

Z=opt[r1(s1,x1)*

*rn(sn,xn)]。其中：opt為max或min，*為運(yùn)算符號。如上例中，Z=min[d1(s1,x1)+

+dn(sn,xn)]=min[d1+d2+…+

dn]3

3.2最優(yōu)化原理

一、R.Bellman最優(yōu)化原理：

作為整個過程的最優(yōu)策略，無任過去的狀態(tài)和決策如何，對前面的決策形成狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。即：若M是從A到B最優(yōu)路線上的任一點，則從M到B的路線也是最優(yōu)路線。A

MB

二、指標(biāo)遞推方程：

fn*(Sn)=opt[rn(sn,xn)*fn+1*(sn+1)]

xn∈Dn(Sn)

如上例：

fn*(Sn)=min[dn(sn,xn)+fn+1*(Sn+1)]，n=4、3、2、1

xn∈Dn(Sn)

f5*(S5)=min[r5(s5,x5)]

x5∈D5(S5)

三、求解過程：

用反向嵌套遞推法：從最后一個階段開始，依次對各子過程尋優(yōu)，直至獲得全過程的最優(yōu)，形成最優(yōu)策略，獲得最優(yōu)策略指標(biāo)值。4

3.3DP建模及求解一、建模條件：

決策過程本身具有時順序性或可以轉(zhuǎn)化為具有時序性的決策問題，均可建立動態(tài)規(guī)劃數(shù)學(xué)模型求解。

AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514二、典型動態(tài)決策問題建模及其求解

1、最短路線問題例1：求下列圖中A到F的最短路線及最短路線值。5AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、階段(stage)n：n=1、2、3、4、5。2、狀態(tài)(state)Sn：

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。3、決策(decision)Xn：決策集Dn(Sn)。

D1(S1)={X1(A)}={B1,B2,B3}=S2，

D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，

D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，

D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，

D5(S5)={X5(E1),X5(E2)}={F;F}={F}。4、狀態(tài)轉(zhuǎn)移方程：Xn

=Sn+15、指標(biāo)函數(shù)(距離)：dn(sn,xn)。d2(B3,C2)=1,d3(C2,D3)=6等。6、指標(biāo)遞推方程：fn*(Sn)=min[rn(sn,xn)+fn+1*(Sn+1)]，n=4、3、2、1

xn∈Dn(Sn)

f5*(S5)=min[r5(s5,x5)]

x5∈D5(S5)6AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E27AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141+4=55+7=12

///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16

///14C14+5=93+11=145+8=139C1

///1+11=127+8=1512C28AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+14=175+9=144+12=1614B2最短路線值為：f1*(s1)=14最短路線求解如下：911F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E21+4=55+7=12

///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16

///14C14+5=93+11=145+8=139C1

///1+11=127+8=1512C23+14=175+9=144+12=1614B210AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即：

A

B2

C1

D1

E2

F112、資源分配問題某種資源總量為a，用于生產(chǎn)n種產(chǎn)品，若分配數(shù)量Xi用于生產(chǎn)第i種產(chǎn)品，收益為gi(Xi)。問：如何分配才使總收益最大?例1.某有色金屬公司擬拔出50萬元對所屬三家冶煉廠進(jìn)行技術(shù)改造。若以十萬元為最小分割單位，各廠收益與投資的關(guān)系如下表示：公司經(jīng)理從定量決策的需要出發(fā)，要求系統(tǒng)分析組求出：對三個工廠如何分配這50萬元，才能使總收益達(dá)到最大?121、階段n：

123(工廠)2、狀態(tài)Sn：

S1，S2=S1-

X1，

S3=S2-

X2，

(可供分配的資源量)={5}，={0,1,

,5}，={0,1,

,5}，

3、決策變量Xn：X1，X2,X3=S3(分配的資源量)={0,1,

,5}，={0,1,

,5}，={0,1,

,5}4、狀態(tài)轉(zhuǎn)移方程：Sn+1=

Sn

-

Xn

5、指標(biāo)函數(shù)(收益)gn(xn)：g1(x1)=g2(x2)=g3(x3)=

{0,4.5,7,9,10.5,12}，{0,2,4.5,7.5,11,15}，{0,5,7,8,10,13}6、指標(biāo)遞推方程：fn*(Sn)=max[gn(xn)+fn+1*(Sn+1)]，n=2、10≤xn≤Sn

f3*(S3)=max[g3(x3)]，

0≤x3≤S3工廠1工廠2工廠313S2=S1-x1=5-1=4S3=S2-x2=4-3=1最優(yōu)策略為：P*={x1*，x2*，x3*}={1，3，1}Z*=17萬元S3=S2-x2S2=S1-x1143、背包問題

例.設(shè)有3種物品，每種數(shù)量無限，其重量和價值如下表?，F(xiàn)有一只可裝載重量為W=5公斤的背包，試問:各種物品應(yīng)各取多少件放入背包，才能使背包中的物品價值最高？這個問題可以整數(shù)規(guī)劃數(shù)學(xué)模型來描述：設(shè)第i種物品取xi件放入背包，背包中物品總價值記為Z，則有數(shù)學(xué)模型：

MaxZ=65x1+80x2+30x3s.t.2x1+3x2+x3≤5xj≥0，j=1,2,3；且為整數(shù)下面用動態(tài)規(guī)劃求解：

15①、階段n：123(物品)②、狀態(tài)Sn：S1={5}，

S2=S1－W1·X1，

S3=S2－W2·X2

(背包可裝入的重量)={1,3,5}={0,1,2,3,5}③、決策Xn：0≤X1≤S1/W10≤X2≤S2/W20≤X3≤S3/W3(裝入的物品件數(shù))X1={0,1,2}X2={0,1}X3={0,1,2,3,5}④、狀態(tài)轉(zhuǎn)移方程：

Sn+1=Sn－Wn·Xn

⑤、階段指標(biāo)函數(shù)(價值)：

r1(x1)=65·x1,r2(x2)=80·x2,r3(x3)=30·x3

⑥、遞推方程：

物品A物品B物品C下面利用表格進(jìn)行計算，從最后一個階段開始：

16n=3時：此時X3≤S3/W3=S3，為整數(shù)X3S3f3(S3)=r3(X3)f3*(S3)X3*0123500

001030

301203060

60230306090

903503060901501505n=2時：此時X2≤S2/W2=S2/3，為整數(shù)，S3=S2－W2·X2

X2S2f2(S2)=r2(X2)+f3*(S3)f2*(S2)X2*0110+30=30

30030+90=9080+0=8090050+150=15080+60=1401500n=1時：此時X1≤S1/W1=S1/2，為整數(shù)，S2=S1－W1·X1

X1S1f1(S1)=r1(X1)+f2*(S2)f1*(S1)X1*01250+150=15065+90=155130+30=1601602S2=S1－W1X1*=5－2×2=1S3=S2－W2X2*=1－3×0=1最優(yōu)策略為：X*={x1*，x2*，x3*}={2，0，1}，Z*=f1*(S1)=160即應(yīng)取第一種物品2件，第二種物品0件，第三種物品1件放入背包，才能使背包中的所有物品總價值最高為160元。

174、生產(chǎn)問題

例.某廠生產(chǎn)一種產(chǎn)品，該產(chǎn)品在未來三個月中的需要量分別為3，4，3萬件，若生產(chǎn)準(zhǔn)備費(fèi)為

3萬元/次，每件成本為1元，每件每月存儲費(fèi)為0.7元，假定1月初和4月初存貨為0，且每月產(chǎn)量不限。試求：該廠未來三個月內(nèi)的最優(yōu)生產(chǎn)計劃？

1月3月4月2月需求量：D1=3D2=4D3=3①、階段(月)n：1234②、狀態(tài)Sn：S1={0}，

S2=S1+X1－D1，

S3=S2+X2－D2S4=S3+X3－D3=0

(月初庫存

)={0,1,2,3,4,5,6,7},={0,1,2,3}③、決策Xn：X1=

X2

=

X3=(生產(chǎn)量

){3,4,5,6,7,8,9,10};{0,1,2,3,4,5,6,7};{0,1,2,3}④、狀態(tài)轉(zhuǎn)移方程：

Sn+1=Sn+Xn－Dn

⑤、階段指標(biāo)函數(shù)(成本)：成本=生產(chǎn)費(fèi)用＋存儲費(fèi)用

rn(Xn)=3＋1·Xn，

Xn＞00，Xn＝0＋0.7Sn⑥、遞推方程：

18n=3時：

此時

S3+X3－D3=0，即X3=3－S3

n=2時：

因為0≤S3≤3，而S3=S2+X2－D2

，即0≤S2+X2－4≤3

，所以4-S2≤X2≤7－S2X3S3f3(S3)=r3(X3)f3*(S3)X3*01230

6+0=6631

5+0.7=5.7

5.722

4+