運籌學(xué)之動態(tài)規(guī)劃(new2009)

動態(tài)規(guī)劃Dynamicprogramming驛站馬車問題19世紀(jì)中葉，密蘇里州的一個尋寶者決定去加州西部淘金。旅程需要乘坐驛站馬車，途徑那些有遭遇強盜襲擊的危險的無人鄉(xiāng)村。雖然他的出發(fā)點和目的地已定，但他有相當(dāng)多的選擇從哪個州中穿過。下圖顯示了可能路線，每個州都用字母表示，旅行方向在圖中是從左到右的。因此從他的出發(fā)點A州（密蘇里州）到目的地J州（加利福尼亞州），就需要4個階段（驛站馬車行駛）。于是，淘金者決定購買保險，每條路線的保單成本并不一樣，淘金者決定選一條保單費用最便宜的路線。（每段保單的費用也如圖所示）AFCDGIJHEB24374632441514633334驛站馬車問題驛站馬車問題考慮：尋找每個連續(xù)階段費用最省的方案？ABFIJ(13)另一條ADFIJ(11)解決方案：找出所有路線（18條)動態(tài)規(guī)劃：從原問題的很小的一個部分開始，給這個較小的問題尋找最優(yōu)解，然后逐漸擴大問題，從前面的問題中找出目前最優(yōu)解，然后取得全部問題的最優(yōu)解。從小問題開始，假設(shè)淘金者幾乎完成了他的旅行，只剩下最后一個階段了。然后依次重復(fù)，通過每次增加一個階段來不斷來擴大問題。建模令決策變量xn（n=1，2，3，4）為階段n（要進行的n段驛站馬車運行）的直接目的地。這樣選擇路線是A→X1→

X2→

X3→

X4,其中X4=J。保單成本用cij表示。設(shè)fn（s，xn）為剩余階段整體最優(yōu)成本，已知淘金者在s州，準(zhǔn)備開始第n階段并選擇xn作為直接目的地。最小化fn（s，xn），并設(shè)f*（s）為相應(yīng)的fn（s，xn）的最小值。f*（s）=Minfn（s，xn）=fn（s，x*），其中fn（s，xn）=中間成本（階段n）+最小未來成本（階段n+1至終點）=csx+f*n+1（xn）。

而csx

的值由當(dāng)前州（i=s)和直接目的地（j=xn）中的cij已給出。所以在第四階段末將達到最終目的地J州，所以f*5（J）=0求解N=4當(dāng)淘金者只有一步要走時，他后來的路線完全由他目前所在的州（HorJ）和最終目的x4=J所決定。sf*4（s）x*4H3JI4JN=3淘金者還有2步走，假設(shè)淘金者在F州，他必須往下走到H州或J州，直接成本分別是CFH=6和CFI=3。假設(shè)他選H州，他到達之后，最小額外成本是f*4（H)=3,所以這個決策成本是6+3=9.如果他選的是I州，全部成本是3+4=7，所以，最優(yōu)選擇是后者，x*3=I同樣，在其他兩個可能有兩步要走要走的州s=E和s=G開始，有類此計算。N=3x3sf3（s，x3）=csx3+f*4（x3）f*3（s）X*3HIE484HF977IH676HN=2此時，淘金者有三步要走，這里f2(s,x2)=csx2+f*3(x2)假設(shè)淘金者正在C州，他接著必須走到E州、F州或G州，直接成本是cCE=3,cCF=2或cCG=4，到達之后，第三階段最小成本如n=3的表，分別為x2=E:f2(C,E)=cCE+f*3(E)=3+4=7x2=F:f2(C,F)=cCF+f*3(F)=2+7=9x2=G:f2(C,G)=cCG+f*3(G)=4+6=10顯然，C到終點最小成本是f*2(C)=7,直接目的應(yīng)為x*2=E同理從B或D開始計算，有類似計算N=2x2Sf2（s，x2）=csx2+f*3（x2）f*2（s）X*2EFGB11111211E或FC79107ED88118E或FN=1淘金者走第一步的問題包含了全部要走的4個階段。但目前只有一個可能開始的周s=A.x1=B:f1(A,B)=cAB+f*3(B)=2+11=13x1=C:f1(A,C)=cAC+f*3(C)=4+7=11x1=D:f1(A,D)=cAD+f*3(D)=3+8=11由此可知A到終點最小成本是f*1(A)=11,直接目的應(yīng)為x*1=C或DN=1X1Sf1（s，x1）=csx1+f*2（x1）f*1（s）X*1BCDA13111111C或DAFCDGIJHEB24374632441514633334結(jié)論動態(tài)規(guī)劃問題的特征問題可以分為幾個階段，每一個階段都有一個策略決策（xn）。每個階段都有一些與那個階段的開始有關(guān)的狀態(tài)（sn）。每個階段策略決策的結(jié)果都是從當(dāng)前狀態(tài)變到下一階段開始的狀態(tài)。設(shè)計求解過程是為整個問題找到一個最優(yōu)策略最優(yōu)性原理：已知目前狀態(tài)，對于剩余階段的最優(yōu)解策略與先前階段采用的策略無關(guān)。即最優(yōu)決策要依據(jù)當(dāng)前狀態(tài)，而不是如何到那里。求解過程通過為最后階段找到最優(yōu)解開始。如果知道n+1階段的最優(yōu)策略，就可以確定第n階段的最優(yōu)策略，因此可以得到一種遞推關(guān)系。（當(dāng)?shù)趎階段從s狀態(tài)開始時找出的最優(yōu)最優(yōu)決策策略，就需要找到xn的最小值，于是通過使用xn的值求得相關(guān)的最小成本，然后遵循你在n+1階段時開始于xn狀態(tài)的最優(yōu)策略。

1、階段k：表示決策順序的離散的量，階段可以按時間或空間劃分。

2、狀態(tài)sk：能確定地表示決策過程當(dāng)前特征的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

3、決策xk：從某一狀態(tài)向下一狀態(tài)過渡時所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體。

4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。

5、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。

基本概念

6、階段指標(biāo)函數(shù)vk(sk,xk)：從狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)。過程指標(biāo)函數(shù)Vk,n(sk,xk,xk+1,…,xn)：從狀態(tài)sk出發(fā)，選擇決策xk,xk+1,…,xn所產(chǎn)生的過程指標(biāo)。動態(tài)規(guī)劃要求過程指標(biāo)具有可分離性，即Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,…,xn)稱指標(biāo)具有可加性，或Vk,n(sk,xk,xk+1,…,xn)=vk(sk,xk)×Vk+1(sk+1,xk+1,…,xn)稱指標(biāo)具有可乘性。二、基本方程：最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對所有的策略Pk,n，過程指標(biāo)Vk,n的最優(yōu)值，即

基本概念、基本方程

對于可加性指標(biāo)函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為

以上式子稱為動態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)=0。

基本方程作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的任意子策略都是最優(yōu)的。最優(yōu)化原理練習(xí)下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。BACBDBCDEC412312312322164724838675611063751N=4第四階段：兩個始點D1和D2，終點只有一個；分析得知：從D1和D2到E的最短路徑唯一。

階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D210*6106EE

第三階段：有三個始點C1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2

的最短路徑問題：

分析得知：如果經(jīng)過C1，則最短路為C1-D2-E；如果經(jīng)過C2，則最短路為C2-D2-E；如果經(jīng)過C3，則最短路為C3-D1-E。

N=3

階段3本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3

的最短路徑問題：

分析得知：如果經(jīng)過B1，則走B1-C2-D2-E；如果經(jīng)過B2，則走B2-C3-D1-E；如果經(jīng)過B3，則走B3-C3-D1-E；如果經(jīng)過B4，則走B4-C3-D1-E。

N=2

階段2本階段始點（狀態(tài)）

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3第一階段：只有1個始點A，終點有B1,B2,B3,B4

。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：

最后，可以得到：從A到E的最短路徑為A

B4

C3

D1

EN=1

階段1本階段始點(狀態(tài))

本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414C2動態(tài)規(guī)劃的求解方法一、逆推法1.基本公式已知初始狀態(tài)為。并假定最優(yōu)值函數(shù)表示第k階段的初始狀態(tài)為，從k階段到n所得到的最大效益。從n階段開始，則有得到最優(yōu)解和最優(yōu)值在n－1階段有其中得到最優(yōu)解和最優(yōu)值在第k階段有其中得到最優(yōu)解和最優(yōu)值如此類推，直到第1階段有其中得到最優(yōu)解和最優(yōu)值由于初始狀態(tài)s1已知，故是可以確定的,和從而和是可以確定的，于是和也就可以確定。這樣按照上述遞推過程相反的順序推算下去，就可逐步確定出每階段的決策與收益。實例解：令二、順推法1.基本公式從第一階段開始，則有得到最優(yōu)解和最優(yōu)值其中在第二階段有其中得到最優(yōu)解和最優(yōu)值如此類推，直到第n階段有其中得到最優(yōu)解和最優(yōu)值由于終止?fàn)顟B(tài)sn＋1已知，故xn=xn(Sn+1)和fn(Sn+1)是可以確定的這樣按照上述遞推過程相反的順序推算下去，就可逐步確定出每階段的決策與收益。2.實例解：范圍資源分配問題

某公司擬將某種設(shè)備5臺，分配給所屬的甲、乙、丙三個工廠。各工廠獲得此設(shè)備后，預(yù)測可創(chuàng)造的利潤如表所示，問這5臺設(shè)備應(yīng)如何分配給這3個工廠，使得所創(chuàng)造的總利潤為最大？

盈利工廠設(shè)備臺數(shù)

甲廠

乙廠

丙廠000013542710639111141211125131112

動態(tài)規(guī)劃的應(yīng)用解：將問題按工廠分為三個階段，甲、乙、丙三個廠分別編號為1、2、3廠。設(shè)

sk=分配給第k個廠至第3個廠的設(shè)備臺數(shù)（k=1、2、3）。

xk=分配給第k個設(shè)備臺數(shù)。已知s1=5,

并有

從與的定義，可知

以下我們從第三階段開始計算。動態(tài)規(guī)劃的應(yīng)用

第三階段:

顯然將臺設(shè)備都分配給第3工廠時，也就是時，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

由于第3階段是最后的階段，故有其中可取值為0,1,2,3,4,5。其數(shù)值計算見下表。

動態(tài)規(guī)劃的應(yīng)用

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－12125

動態(tài)規(guī)劃的應(yīng)用

其中表示取3子過程上最優(yōu)指標(biāo)值時的決策，例如在表中可知當(dāng)=4時，有有此時，即當(dāng)時，此時?。ò?臺設(shè)備分配給第3廠）是最優(yōu)決策，此時階段指標(biāo)值（盈利）為12，最優(yōu)3子過程最優(yōu)指標(biāo)值也為12。第二階段：

當(dāng)把臺設(shè)備分配給第2工廠和第3工廠時，則對每個值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過程最優(yōu)指標(biāo)函數(shù)值為

動態(tài)規(guī)劃的應(yīng)用因為上式也可寫成其數(shù)值計算如表所示。

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

212

動態(tài)規(guī)劃的應(yīng)用