運(yùn)籌學(xué)與系統(tǒng)分析：第4章 動(dòng)態(tài)規(guī)劃

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

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

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

4、列構(gòu)成一個(gè)策略，用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）指標(biāo)函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)，分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)d(sk,uk):從狀態(tài)sk出發(fā)采取uk策略時(shí)的效益。 過程指標(biāo)函數(shù)V1,n(s1,p1,n):初始狀態(tài)s1時(shí)采用策略p1,n時(shí)原過程的指標(biāo)函數(shù)值。 后部子過程的指標(biāo)函數(shù)值Vk,n(sk,pk,n)：指第k階段，狀態(tài)為sk時(shí)采用策略pk,n時(shí)，后部子過程的指標(biāo)函數(shù)值。 最優(yōu)指標(biāo)函數(shù)fk(sk)：從第k階段的狀態(tài)s

5、k上采用最優(yōu)策略p*k,n到過程終止時(shí)的最佳效益值。動(dòng)態(tài)規(guī)劃的最優(yōu)解是最優(yōu)策略P1,n，最優(yōu)值是最優(yōu)指標(biāo)f1二、 動(dòng)態(tài)規(guī)劃的基本思想和最優(yōu)化原理例：例1的最短路問題AB2B1C4C3C2C1D3D2D1E2E1F452368775845344835621343解：用逆序遞推方法（逆序解法）求解（1）從k5開始，到終點(diǎn)的路長（2）k=4, 狀態(tài)有3個(gè)D1,D2,D3，到終點(diǎn)的最短路長相應(yīng)最優(yōu)策略u(píng)*4(D1)=E1, 路徑D1E1F相應(yīng)最優(yōu)策略u(píng)*4(D2)=E2, 路徑D2E2F相應(yīng)最優(yōu)策略u(píng)*4(D3)=E1, 路徑D3E1F類似地可得到k=3時(shí)，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時(shí)，f2(B1)=13, u*2(B1)=C2 f2(B2)=15, u*2(B2)=C3k=1時(shí)，只有一個(gè)狀態(tài)點(diǎn)A相應(yīng)最優(yōu)策略u(píng)*1(A)=B1, 最優(yōu)路徑AB1 C2 D2E2F最短路長17標(biāo)號(hào)法：利用上述逆序遞推方法計(jì)算完后，再利用如下圖直觀表示的方法。其中各點(diǎn)上數(shù)字表示該點(diǎn)到達(dá)終點(diǎn)的最短距離，這些數(shù)字對(duì)于許多實(shí)際問題而言是很有意義的。AB2B1C4C3C2C1D3D2D1E2E1F437553432143(4)(3)(7)(5)(5)(12)(10)(8)

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

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

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