運籌學與系統(tǒng)分析：第4章 動態(tài)規(guī)劃

1、第四章 動態(tài)規(guī)劃（Dynamic Programming） 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。用于解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)計劃與庫存、投資、裝載、排序、生產(chǎn)過程最優(yōu)控制等。動態(tài)規(guī)劃模型分類：離散確定型離散隨機型連續(xù)確定型連續(xù)隨機型（最基本） 多階段決策過程，是按時間順序分解成若干相互聯(lián)系的階段（時段），每個階段都要做出決策，形成一個決策序列。 多階段決策過程最優(yōu)化的目標是要達到活動過程的總體最優(yōu)。每階段決策時不僅要考慮本階段最優(yōu)，還應考慮對最終目標的影響。 動態(tài)規(guī)劃就是符合這種要求的一種決策方法。4.1 多階段決策過程的最優(yōu)化多階段決策問題舉例：例1：最短路線問題。

2、如下圖，給定一個線路網(wǎng)絡圖，要從A地向F地鋪設一條輸油管道，各點間連線上的數(shù)字表示距離，問應選擇什么路線，可使總距離最短？AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343例2：投資決策問題。某公司有資金10萬元，若投資項目i (i=1,2,3)的投資額為xi，其收益分別是g1(x1)=4x1, g2(x2)=9x2,g3(x3)=2x32, 問應如何分配投資數(shù)額才能使總收益最大？解：求x1,x2,x3，使本例可轉(zhuǎn)化為3階段的決策問題。4.2 動態(tài)規(guī)劃的基本概念和基本原理一、動態(tài)規(guī)劃的基本概念（1）階段：將問題按時間或空間特征分解成若干相互聯(lián)系的階

3、段，常用k表示階段變量。例1中A到F有5個階段。（2）狀態(tài)：各階段開始時的條件為狀態(tài)。常用sk表示狀態(tài)，Sk表示狀態(tài)集合。例1中，第1階段狀態(tài)為A，第2階段有兩個狀態(tài)B1,B2，以此類推。 無后效性：某階段狀態(tài)確定后，其后面階段狀態(tài)的變化不受其前面各階段狀態(tài)的影響。 動態(tài)規(guī)劃模型的狀態(tài)變量必須具有無后效性。（3）決策和策略：當某階段的狀態(tài)取定后，可以作不同的決策（或選擇），稱為決策，從而確定下一階段的狀態(tài)。通常用uk(sk)表示第k階段當狀態(tài)為sk時的決策變量。Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。 例如，例1中D2(B1)=C1,C2,C3 各階段策略確定后，整個問題的決策序

4、列構(gòu)成一個策略，用p1,nu1(s1),u2(s2),un(sn)表示。（4）狀態(tài)轉(zhuǎn)移方程：若給定第k階段的狀態(tài)sk，且其決策為uk(sk)，則第k+1階段的狀態(tài)sk+1可用狀態(tài)轉(zhuǎn)移方程確定（5）指標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標，分為階段指標函數(shù)和過程指標函數(shù)。 階段指標函數(shù)d(sk,uk):從狀態(tài)sk出發(fā)采取uk策略時的效益。 過程指標函數(shù)V1,n(s1,p1,n):初始狀態(tài)s1時采用策略p1,n時原過程的指標函數(shù)值。 后部子過程的指標函數(shù)值Vk,n(sk,pk,n)：指第k階段，狀態(tài)為sk時采用策略pk,n時，后部子過程的指標函數(shù)值。 最優(yōu)指標函數(shù)fk(sk)：從第k階段的狀態(tài)s

5、k上采用最優(yōu)策略p*k,n到過程終止時的最佳效益值。動態(tài)規(guī)劃的最優(yōu)解是最優(yōu)策略P1,n，最優(yōu)值是最優(yōu)指標f1二、 動態(tài)規(guī)劃的基本思想和最優(yōu)化原理例：例1的最短路問題AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343解：用逆序遞推方法（逆序解法）求解（1）從k5開始，到終點的路長（2）k=4, 狀態(tài)有3個D1,D2,D3，到終點的最短路長相應最優(yōu)策略u*4(D1)=E1, 路徑D1E1F相應最優(yōu)策略u*4(D2)=E2, 路徑D2E2F相應最優(yōu)策略u*4(D3)=E1, 路徑D3E1F類似地可得到k=3時，f3(C1)=12, u*3(C1)=D1

6、f3(C2)=10, u*3(C2)=D2 f3(C3)=8, u*3(C3)=D2 f3(C4)=9, u*3(C4)=D3k=2時，f2(B1)=13, u*2(B1)=C2 f2(B2)=15, u*2(B2)=C3k=1時，只有一個狀態(tài)點A相應最優(yōu)策略u*1(A)=B1, 最優(yōu)路徑AB1 C2 D2E2F最短路長17標號法：利用上述逆序遞推方法計算完后，再利用如下圖直觀表示的方法。其中各點上數(shù)字表示該點到達終點的最短距離，這些數(shù)字對于許多實際問題而言是很有意義的。AB2B1C4C3C2C1D3D2D1E2E1F437553432143(4)(3)(7)(5)(5)(12)(10)(8)

7、(9)(15)(13)(17)分析：求解各階段，都利用了如下第k與k+1階段的關系此遞推關系稱為動態(tài)規(guī)劃基本方程，f6(s6)=0為邊界條件?？偨Y(jié)：（1）動態(tài)規(guī)劃恰當?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標函數(shù)，將問題化成一族同類型的子問題，逐個求解。（2）求解時從邊界條件開始，逆（或順）過程行進方向，逐段遞推尋優(yōu)。每個子問題的求解都用到它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。（3）動態(tài)規(guī)劃把當前階段與未來各段分開，又把當前效益與未來效益結(jié)合起來考慮的一種最優(yōu)方法。4.3 動態(tài)規(guī)劃模型的建立與求解一、動態(tài)規(guī)劃模型的建立 動態(tài)規(guī)劃方法的關鍵在于識別問題的多階段

8、特征，正確選擇狀態(tài)變量，使各階段狀態(tài)變量具有遞推的狀態(tài)轉(zhuǎn)移關系sk+1=Tk(sk,uk)例：上述例2的投資決策問題。某公司有資金10萬元，若投資項目i (i=1,2,3)的投資額為xi，其收益分別是g1(x1)=4x1, g2(x2)=9x2,g3(x3)=2x32, 問應如何分配投資數(shù)額才能使總收益最大？解：人為地賦予“階段”的概念。將投資項目排序，依次對項目1、2、3進行投資，分為3個階段，每階段只決定對一個項目應投資的金額。 狀態(tài)變量：設每階段可供使用的資金為狀態(tài)變量sk, s1=10 決策變量：設項目投資額為決策變量，即uk=xk, k=1,2,3k=1時:k=2時:一般地，第k階段

9、:于是有：狀態(tài)變量sk：第k階段可以投資于第k項目至第3項目的資金決策變量xk：決定給第k個項目投資的資金狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk指標函數(shù)：最優(yōu)指標函數(shù)fk(sk):當可投資金為sk時，投資第k項至第3項所 得最大收益建立起動態(tài)規(guī)劃基本方程為： 用動態(tài)規(guī)劃方法逐段求解，可得各項目最佳投資金額，以及投資的最大收益為f1(10) （求解過程略）二、順序解法 與逆序解法相反，從第1階段開始向后遞推，后一階段要用到前一階段的求優(yōu)結(jié)果。例：用順序解法解例1的最短路問題AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343k=0時，f0(s1)= f0(A)=0，這是邊界條件解：設fk(sk+1)為從A點到第k階段狀態(tài)sk+1的最短距離k=1時，按f1(s2)的定義有k=2時,類似地可得到k=3時，f3(D1)=11, u3(D1)=C1或C2f3(D2)=12, u3(D2)=C2f3(D3)=14, u3(D3)=C3k=4時，f4(E1)=14, u4(E1)=D1f4(E2)=14, u4(E3)=D2k=5時，f5(F)=17, u5(F)=E2最短路長17，