動態(tài)規(guī)劃(運(yùn)籌學(xué)講義)課件

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

DynamicProgramming§1動態(tài)規(guī)劃問題實(shí)例

§2動態(tài)規(guī)劃的基本概念§3基本原理和基本方程§4動態(tài)規(guī)劃的應(yīng)用1

§1動態(tài)規(guī)劃問題實(shí)例許多問題用動態(tài)規(guī)劃研究求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問題，解析數(shù)學(xué)無用武之地，而動態(tài)規(guī)劃成為得力工具；某些情況下，用動態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計算機(jī)給出求其數(shù)值解的方法。動態(tài)規(guī)劃DP是運(yùn)籌學(xué)的一個分支，是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法（一種分析多階段決策過程的數(shù)學(xué)方法），這種方法可根據(jù)人們所采取的措施，一步步地控制過程的發(fā)展，以實(shí)現(xiàn)預(yù)定的要求。

1951年美國數(shù)學(xué)家R.E.Bellman等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的最優(yōu)化原理，把多階段過程轉(zhuǎn)化為一系列單階段問題逐個求解，并研究了許多實(shí)際問題而建立了動態(tài)規(guī)劃。2§1動態(tài)規(guī)劃問題實(shí)例多階段決策過程由問題的特征可將決策過程按時間、空間等方式分為若干互相聯(lián)系的不同階段，在每個階段有若干種不同方案可供選擇，進(jìn)行決策，每個階段的決策執(zhí)行將影響到下一階段的決策，決策者根據(jù)全局最優(yōu)在每一階段做出決策，從而使整個過程達(dá)到最優(yōu)3§1動態(tài)規(guī)劃問題實(shí)例例5.1最短路問題下圖為一城市若干單向道路組成的交通圖，兩點(diǎn)之間連線數(shù)字表示兩點(diǎn)間的距離，問應(yīng)該如何選擇路線，使A到G點(diǎn)路程最短A5631B1B2E1C2C3C43876C1E2E3D1D2D3F1F2G6835338422123363552634123456A→BiBi→CjCj→DkDk→ElEl→FmFm→G

(i=12)(j=1,…,3)(k=1,2,3)(l=1,2,3)(m=1,2,3)6階段圖8-14例5.2機(jī)器負(fù)荷分配問題

某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)．在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u的關(guān)系為g＝g(u),

這時機(jī)器的年完好率為a（0<a<1)．在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量v的關(guān)系為h＝h(v),

這時機(jī)器的年完好率為b（a<b<1）．假定開始生產(chǎn)時完好的機(jī)器數(shù)量為s1，要求制定一個五年計劃,在每年開始時決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。

狀態(tài)1

s1完好機(jī)器數(shù)階段1決策高負(fù)荷機(jī)器數(shù)狀態(tài)2s2階段2決策高負(fù)荷機(jī)器數(shù)狀態(tài)2s3階段3決策高負(fù)荷機(jī)器數(shù)狀態(tài)2s4階段4決策高負(fù)荷機(jī)器數(shù)狀態(tài)2s5階段5決策高負(fù)荷機(jī)器數(shù)s6圖8-25§2動態(tài)規(guī)劃的基本概念(1)階段（stage）和階段變量

把所研究多段決策問題，按時間和空間先后順序劃分為若干相互聯(lián)系的決策階段，以便按一定的次序求解每階段的解。描述階段的變量稱階段變量，常用k表示。(2)狀態(tài)（state）

狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk

表示。sk的所有可能取值集合稱為狀態(tài)集合，用Sk

表示.狀態(tài)既是前面階段所作決策的結(jié)果，又是本階段作出決策的出發(fā)點(diǎn)和依據(jù)。動態(tài)規(guī)劃中要求狀態(tài)必須具有無后效性，即如果某階段狀態(tài)給定后，這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展。這一性質(zhì)也稱馬爾科夫性(3)決策（decision）決策指決策者根據(jù)當(dāng)前的狀態(tài)，在若干種方案中作出選擇，達(dá)到下一階段狀態(tài)。表示決策的變量稱決策變量，第k階段的決策變量常用uk

(sk)表示。決策變量的取值會受到狀態(tài)變量的制約，被限制在某一范圍之內(nèi),稱此范圍為允許決策集合，常用Dk

(sk)

表示，顯然uk

(sk)∈Dk

(sk)6§2動態(tài)規(guī)劃的基本概念(4)策略（policy）各階段決策決定后，整個問題的決策序列就構(gòu)成一個策略。設(shè)u1

(s1),u2

(s2),…,un

(sn)分別為各階段的決策，用決策排列序列

p1

n(s1)＝｛u1

(s1),u2

(s2),…,un

(sn)｝表示，簡記p1

n。p1

n(s1)

允許取值的范圍稱為允許策略集合,用P1

n表示,p1

n(s1)∈P1

n。由過程的第k階段開始到終止?fàn)顟B(tài)的過程為后部子過程(k子過程),相應(yīng)策略

pk

n(sk)＝｛uk

(sk),uk+1

(sk+1),…,un

(sn)｝稱為k子過程策略簡記pk

n(5)狀態(tài)轉(zhuǎn)移方程

若給定第k階段的狀態(tài)為sk，當(dāng)采取決策變uk

(sk),則第k+1段的狀態(tài)sk+1也就完全確定。上述過程可用

sk+1＝Tk[sk,(uk)]（8.1）

表示，上式刻畫k段到k+1段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)

用來衡量所選策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)?？煞譃殡A段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)兩種。階段指標(biāo)函數(shù)是對某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量，用vk(sk,uk

(sk))表示;過程指標(biāo)函數(shù)是指過程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，用

Vk,n＝Vk,n(sk,

uk,

sk+1,

uk+1,

…,sn,un)＝Vk,n(sk,

pk

n)7動態(tài)規(guī)劃模型要求指標(biāo)函數(shù)滿足可分離性，即

φ

(sk,

uk,

sk+1,

uk+1,

…,sn,un)＝φ(sk,

uk,

Vk+1,n(sk+1,

uk+1,

…,sn,un))常見的指標(biāo)函數(shù)形式為

1）全過程和任一后部子過程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之和(第一類)2）全過程和任一后部子過程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之積(第二類)最優(yōu)指標(biāo)函數(shù)fk(sk,)表示從第k階段狀態(tài)sk

，采用最優(yōu)策略p*k

n到過程終止時的最佳效益值

當(dāng)k=1時，

fk

(s1)就是從初始狀態(tài)到全過程結(jié)束的整體最優(yōu)函數(shù)

(8.2)8§3動態(tài)規(guī)劃基本原理和基本方程下面結(jié)合例5.1最短路問題介紹動態(tài)規(guī)劃的基本原理。求A到G的最短路的一種簡單方法是窮舉法：找出從A到G的所有路線和長度并加以比較，從而找出最短路。這種方法計算量非常大。下面介紹動態(tài)規(guī)劃方法，采用逆序遞推方法求解f

(?)表示點(diǎn)?到

G最短路的距離第一步k=6開始狀態(tài)變量s6

可取F1,

F2,指標(biāo)函數(shù)f6

(s6)為F1和F2表到G路長的距離：f6

(F1)=4；f6

(F2)=3第二步k=5，狀態(tài)變量s5

可取E1,

E2和E3。f5

(s5)是從s5經(jīng)過一個中途點(diǎn)F到G點(diǎn)最短路的兩級決策問題，從E1到G有兩條路線，取最短路線長這說明E1到G最短距離為7，路徑為E1→F1→G。相應(yīng)決策u*5

(E1)=F1u*5

(E2)=F2u*5

(E3)=F29第三步k=4狀態(tài)變量s4

可取D1,

D2和D3u*4

(D1)=E2u*4

(D2)=E2u*4

(D3)=E2類似地可算得

k=3

f(C1)=13

u*3

(C1)=D1;f(C2)=10

u*3

(C2)=D1

f(C3)=9

u*3

(C3)=D2;f

(C4)=11

u*3

(C4)=D3

k=2f(B1)=min{1+13,3+10,6+9}=13

u*2

(B1)=C2;

f(B2)=min{8+10,7+9,6+11}=16

u*2

(B2)=C3

k=1f(A)=min{5+13,3+16}=18

u*1

(A)=B1

即從A到G的最短路為：A→B1

→C2

→D1→E2→F2→G最短距離為18計算過程可見P117表4-5101.基本原理和基本方程最優(yōu)化原理：一個過程的最優(yōu)策略具有這樣的性質(zhì),即無論過去的狀態(tài)和決策如何，相對于前面決策所形成的狀態(tài)而言,其以后的所有決策必構(gòu)成最優(yōu)策略。簡言值，一個最優(yōu)策略的子策略必須最優(yōu)。例8.1的求解應(yīng)用了這一原理，計算過程可以看出，在求解的各階段，都利用了第k階段和第k+1階段如下關(guān)系：這種遞推關(guān)系為動態(tài)規(guī)劃的基本方程，(8.3b)為邊界條件。設(shè)最優(yōu)解存在，且目標(biāo)函數(shù)為和的形式（第一類形式）一般的動態(tài)規(guī)劃的基本方程為：Opt可根據(jù)題意取min或max

11

動態(tài)規(guī)劃的基本思想如下：（1）動態(tài)規(guī)劃方法的關(guān)鍵在于正確寫出基本遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件，因此必須將多階段決策過程劃分為n個相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)，從而把問題化為一族同類型的子問題，然后逐個求解（2）求解時從邊界條件開始，逆（或順）過程逐段遞推尋優(yōu)。在每一個子問題求解中，均利用了它前面子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是這個問題的最優(yōu)解。（3）動態(tài)規(guī)劃方法既把當(dāng)前階段與未來階段分開，又把當(dāng)前效益和未來效率結(jié)合，因此每段的最優(yōu)決策選取是從全局來考慮。（4）在求這個問題的最優(yōu)解時，由于初始狀態(tài)是已知，而每階段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各各階段狀態(tài)可逐次變換得到，從而確定最優(yōu)路線。12

2.動態(tài)規(guī)劃的建模步驟：（1）恰當(dāng)?shù)貙⒍嚯A段決策過程劃分為n個相互聯(lián)系的階段。（2）正確地選取狀態(tài)變量sk。

能描述過程的演變特征;滿足無后效性。并確定初始狀態(tài)s1的值。（3）確定決策變量uk以及各階段的允許決策集合Dk(sk)；（4）給出狀態(tài)轉(zhuǎn)移方程：sk+1＝Tk[sk,(uk)]

；

（5）根據(jù)題意列出階段效益函數(shù)vk(sk,

uk),過程指標(biāo)函數(shù)的形式

Vk,n(sk,

pk

n)和最優(yōu)指標(biāo)函數(shù)fk

(sk)

；（6）列出基本（遞推）方程，注明邊界條件。13

3.動態(tài)規(guī)劃順序解法的基本方程：(8.4a)和(8.4b)兩式為動態(tài)規(guī)劃的逆序解法的基本方程，當(dāng)決策過程可逆時，動態(tài)規(guī)劃可以用順序解法，尋優(yōu)的方向與過程與行進(jìn)方向相同。動態(tài)規(guī)劃順序解法階段劃分和狀態(tài)變量的設(shè)置與逆序解法相同，第k階段的狀態(tài)變量sk，改變決策變量uk的定義uk(sk+1)＝sk，決策可能集合為uk

(sk+1)∈Dk

(sk+1

)

狀態(tài)轉(zhuǎn)移方程為：sk＝Tk[sk+1,

uk(sk+1)]?；痉匠虨椋篺k－1

(sk)表示第k-1

段時從起點(diǎn)(第1段)到狀態(tài)sk的前k-1部子過程最優(yōu)效益(指標(biāo)函數(shù))值。fn

(sn+1)

即為所求的整體最優(yōu)函數(shù)值。注意：當(dāng)初始狀態(tài)s0給定時，用逆序解法比較好，當(dāng)終止?fàn)顟B(tài)sn+1給定時，用順序解法比較好。如果給定了一個初始狀態(tài)與一個終止?fàn)顟B(tài)，則兩種方法均可使用。14逆序遞推求解和順序遞推求解圖：狀態(tài)s1v1(s1,u1)階段1決策u1s2階段k…決策ukskvk(sk,uk)sk+1…階段n決策unsnvn(sn,un)sn+1V1n(s1,p1n)f1(s1)Vkn(sk,pkn)fk(sk)Vnn(sn,pnn)fn(sn)逆序解法圖狀態(tài)s1v1(s1,u1)階段1決策u1s2階段k…決策ukskvk(sk+1,uk)sk+1…階段n決策unsnvn(sn+1,un)sn+1V11(s2,p11)f1(s1)V1k(sk+1,p1k)fk(sk+1)V1n(sn+1,p1n)fn(sn+1)順序解法圖其中15用順序解法求例5.1的最短路在例5.1中，當(dāng)k=0時，f0(s1)=f0(A)=0，這是邊界條件。當(dāng)k=1時，f1(s2)的定義有

f1(B1)=5,u1(B1)=A;f1(B2)=3;u1(B2)=A當(dāng)k=2時

f2(C1)=d(B1,C1)+f1(B1)=1+5=6,u*2(C1)=B1u*2(C2)=B1

f2(C4)=d(B2,C4)+f1(B2)=6+3=9,u2(C4)=B2當(dāng)k=3時u*3(D1)=C2u*2(C3)=B216當(dāng)k=3時u*3(D3)=C3或C4類似地可算得

k=4

f(E1)=13

u*4

(E1)=D1;f(E2)=13

u*4

(E2)=D1

f(E3)=15

u*4

(E3)=D2;

k=5f(F1)=16

u*5

(F1)=E1;

f(F2)=15

u*5

(F2)=E2

k=6f(G)=min{4+16,3+15}=18

u*6

(G)=F2

即從A到G的最短路為：A→B1

→C2

→D1→E2→F2→G最短距離為18u*3(D2)=C2或C3174.第二類指標(biāo)函數(shù)的基本方程：對于第二類指標(biāo)函數(shù)

逆序解法的基本方程為：Sk+1＝Tk[sk

,

uk(sk)]順序解法的基本方程為：sk＝Tk[sk+1,

uk(sk+1)]18§4動態(tài)規(guī)劃的應(yīng)用一、最短路問題（逆序解法）根據(jù)空間分為n個階段。狀態(tài)為第k階段所有開始點(diǎn)集合決策為從各狀態(tài)點(diǎn)出發(fā)走向下一階段位置點(diǎn)階段效益為相鄰一段路長的距離目標(biāo)函數(shù)為階段效益之和最優(yōu)函數(shù)fk(sk)是由sk到終點(diǎn)的最短距離基本方程為19二、資源分配問題（逆序解法）所謂資源分配問題，是將一種或幾種總量一定的資源（例如資金，機(jī)器、設(shè)備、原材料、物質(zhì)和勞動力等）恰當(dāng)?shù)胤峙浣o若干使用者，以獲得最大收益。例5.2機(jī)器負(fù)荷分配問題某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)．在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u的關(guān)系為g＝g(u)＝cu,

這時機(jī)器的年完好率為a（0<a<1)．在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量v的關(guān)系為h＝h(v)＝dv,(0<d<c)這時機(jī)器的年完好率為b(a<b<1)。假定開始生產(chǎn)時完好的機(jī)器數(shù)量為s1＝1000

臺，要求制定一個五年計劃,在每年開始時決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。

解將問題按年度分為5個階段，階段變量k=1,2,3,4,5。

狀態(tài)sk為第k年初擁有完好機(jī)器的臺數(shù)；

決策變量uk為第k年初投入高負(fù)荷運(yùn)行機(jī)器的臺數(shù)，允許決策集合

Dk(sk)＝{uk

|0≤uk≤sk

}。

狀態(tài)轉(zhuǎn)移方程

第k年年初投入高負(fù)荷機(jī)器數(shù)uk

年末完好的機(jī)器數(shù)為auk

年初投入低負(fù)荷機(jī)器數(shù)sk

－uk

，年末完好的機(jī)器數(shù)為b(sk

－uk)

20狀態(tài)轉(zhuǎn)移方程為

sk+1=auk

+b(sk－uk)

=

bsk

+

(a－b)

uk

階段效益為第k年的年產(chǎn)量

vk(sk,uk)

=g(uk)

+h(sk－uk)

=cuk

+d(sk－uk)

=dsk

+

(c－d)

uk

目標(biāo)函數(shù)基本方程為若取a=0.7，b=0.9，

c=8，

d

=5逆序推算得

k=5時，

k=4時，21依次類推得計算結(jié)果見P11922例5.3一維資源分配問題

總量為a某種資源，用于n個方面（生產(chǎn)n種產(chǎn)品，分配給n個部門、投資n個項(xiàng)目等），以生產(chǎn)n種產(chǎn)品為例，若分配數(shù)量為xi的資源用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)，問應(yīng)如何分配這種資源，是生產(chǎn)n種產(chǎn)品的總收益最大？

一般此問題可構(gòu)建靜態(tài)的規(guī)劃數(shù)學(xué)模型：解通常將資源分配給若干個使用者作為階段，第k階段為分配給第k個使用者，即生產(chǎn)第k種產(chǎn)品；

狀態(tài)變量sk為第k年階段開始留存的資源數(shù)量，用于后面產(chǎn)品的生產(chǎn)；決策變量uk表示分配給生產(chǎn)第k種產(chǎn)品的資源數(shù)量，即uk=xk；允許決策集合：Dk(sk)＝{uk

|0≤uk≤sk}

對于離散問題，gi(xi)較難表達(dá)，通常只能用分段函數(shù)，當(dāng)n較大時，計算較麻煩，可以將這類問題看成一個多階段決策問題，用動態(tài)規(guī)劃求解23

階段效益為第k種產(chǎn)品生產(chǎn)的收益vk(sk,uk)=g(uk)

目標(biāo)函數(shù)；

基本方程最優(yōu)值函數(shù)fk(sk為)

將資源sk分配給第k種產(chǎn)品到第n中產(chǎn)品生產(chǎn)所得到最大收益，遞推方程基本方程最優(yōu)值函數(shù)fk(sk)

為將資源sk分配給第k種產(chǎn)品到第n中產(chǎn)品生產(chǎn)所得到最大收益，遞推方程狀態(tài)轉(zhuǎn)移方程：第k+1種產(chǎn)品生產(chǎn)生時留存的資源數(shù)量sk+1sk+1=sk－uk24例5.4假設(shè)有5臺設(shè)備分配給所下的1、2、3三個車間使用，各車間在分得不同數(shù)量的設(shè)備后所創(chuàng)造的經(jīng)濟(jì)效益gj(xi)（萬元）如下表所示，問應(yīng)該如何分配這5臺設(shè)備，使總收益最大？27

臺數(shù)車間012345x103791213gj(xi)萬元20510111111304611121225解分為三個階段，k=1,2,3表示三個車間分配設(shè)備的順序，第一階段分配給1車間，第二階段分配給2車間，第三階段分配給3車間，1、

k=3時，第三階段開始，狀態(tài)變量s3為所有存留的設(shè)備臺數(shù)，s3的取值范圍為：s3=0,1,2,3,4,5。對于s3的每一個取值，決策變量u3=x3

的取值為：x3=0,1,…,s3。據(jù)此列表求解

x3s3g