暑期集訓授課人：馬翠DynamicProgramming動態規劃動態規劃概述動態規劃基本概念動態規劃基本思想及原理動態規劃模型的建立與求解應用實例主要內容動態規劃

動態規劃（DynamicProgramming）是1951年由美國數學家貝爾曼（RichardBellman）提出，是求解多階段決策問題的優化方法。

動態規劃針對多階段決策的過程，把多階段決策問題轉化為一系列單階段最優化問題，從而逐個求解。

Bellman在1957年出版的《DynamicProgramming》是動態規劃領域的第一本著作。一、動態規劃概述多階段決策過程

多階段決策過程可以在各個階段進行決策，去控制過程發展的多段過程；其發展是通過一系列的狀態轉移來實現的；系統在某一階段的狀態轉移不但與系統當前的狀態和決策有關，而且還與系統過去的歷史狀態和決策有關。動態規劃本質上是多階段決策過程。

（2）在每一個階段都需要做出決策，從而使整個過程達到最好的效果。

（1）根據過程的特性可以將過程按空間、時間等標志分為若干個互相聯系又互相區別的階段。多階段決策過程特點：

（4）當各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線。

（3）在處理各階段決策的選取上，不僅只依賴于當前面臨的狀態，而且還要注意對以后的發展。即是從全局考慮解決局部（階段）的問題。多階段決策問題

多階段決策問題是把一個問題看作是一個前后關聯具有鏈狀結構的多階段過程，也稱為序貫決策過程。12n狀態決策狀態決策狀態狀態決策狀態多階段決策問題示意圖

多階段決策問題和我們前面遇到的決策問題不同，它是和時間有關的。與時間有關的活動過程稱為動態過程，其優化方法稱為動態規劃。

多階段決策問題是一種特殊的動態決策問題，在多階段決策過程中,系統的動態過程可以按照時間進程分為狀態相互聯系而又相互區別的各個階段，每個階段都要進行決策,目的是使整個過程的決策達到最優效果。多階段決策問題的典型例子

最短路徑問題：從A

地到E

地要鋪設一條煤氣管道，其中需經過三級中間站，兩點之間連線上的數字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？

AB1B2B3C1C2C3D1D2E24374632426534633334

背包問題：有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn

類似問題：工廠里的下料問題、運輸中的貨物裝載問題、人造衛星內的物品裝載問題等。

生產決策問題：企業在生產過程中，由于需求是隨時間變化的，因此企業為了獲得全年的最佳生產效益，就要在整個生產過程中逐月或逐季度地根據庫存和需求決定生產計劃。

機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產的數量，使在五年內產品的總產量達到最高。

航天飛機飛行控制問題：由于航天飛機的運動環境是不斷變化的，因此就要根據航天飛機飛行在不同環境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態），使之能最省燃料和完成飛行任務（如軟著陸）。引例（最短路問題）AB1B2B3C1C2C3D1D2E24374632426534633334

問題：上圖是一個線路網絡，兩點之間連線上的數字表示兩點間的距離（或費用），要將貨物從A地運往E地，中間通過B、C、D三個區域，在區域內有多條路徑可走，現求一條由A到E的線路，使總距離最短。

將該問題劃分為4個階段的決策問題，即第一階段為從A到Bj(j=1,2,3)，有三種決策方案可供選擇；第二階段為從Bj到Ci(i,j=1,2,3)，均有三種方案可供選擇；第三階段為從Cj到Di(j=1,2,3,i=1,2)，有兩種方案可供選擇；第四階段為從Dj到E，只有一種方案選擇。如果用完全枚舉法，則可供選擇的路線有3×3×2×1=18（條），將其一一比較可找出最短路線：A→B3→C2→D2→E，其長度為12。

問題分析：

由于我們考慮的是從全局上解決求A到E的最短路問題，而不是就某一階段解決最短路線，因此可考慮從最后一階段開始計算，由后向前逐步推至A點。

第四階段，由D1、D2到E只有一條路線，其長度AB1B2B3C1C2C3D1D2E24374632426534633334

決策點為D1

決策點為D1決策點為D2第三階段，由Cj到Di分別均有兩種選擇第二階段，由Bj到Ci分別均有三種選擇決策點為C2

決策點為C1或C2決策點為C2

第一階段，由A到Bj，有三種選擇，即：決策點為B3

f1(A)=12說明從A到E的最短距離為12，最短路線的確定可按計算順序反推而得。即A→B3→C2→D2→E

上述最短路線問題的計算過程，也可借助于圖形直觀的表示出來：

圖中各點上方框內的數，表示該點到E的最短距離。圖中紅色箭頭線表示從A到E的最短路線。AB1B2B3C1C2C3D1D2E2437463242653463333434676991112啟示：①對一個問題是否用上述方法求解，其關鍵在于能否將問題轉化為相互聯系的決策過程相同的多階段決策問題。②在處理各階段決策的選取上，不僅只依賴于當前面臨的狀態，而且還要注意對以后的發展。即是從全局考慮解決局部（階段）的問題。③決策過程與階段發展過程逆向而行。④各階段選取的決策，一般與“時序”有關，決策依賴于當前的狀態，又隨即引起狀態的轉移，整個決策序列就是在變化的狀態中產生出來，故有“動態”含義。因此，這種方法稱為動態規劃方法。AB1B2B3C1C2C3D1D2E24374632426534633334

動態規劃把一個問題的過程，恰當地分為若干個相互聯系的階段，以便于按一定的次序去求解。描述階段的變量稱為階段變量,常用k表示。階段的劃分，一般是根據時間和空間的自然特征來進行的，但要便于問題轉化為多階段決策。1、階段（stage）二、動態規劃基本概念2、狀態（state）

狀態表示每個階段開始時所處的自然狀況或客觀條件。

描述狀態的變量稱為狀態變量，它可用一個數、一組數或一向量（多維情形）來描述，第k階段的狀態變量常用sk表示，通常一個階段有若干個狀態。

第k階段的狀態就是該階段所有始點的集合，用Sk表示。在第1階段狀態變量s1是確定的，稱初始狀態。如引例中:

能用動態規劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即狀態具有無后效性的多階段決策過程。

無后效性(馬爾可夫性)：是指如果某階段狀態給定后，則在這個階段以后過程的發展不受這個階段以前各段狀態的影響；構造動態規劃模型時，要充分注意是否滿足無后效性的要求；狀態變量要滿足無后效性的要求；如果狀態變量不能滿足無后效性的要求，應適當改變狀態的定義或規定方法。

決策：在某一階段，當狀態給定后，往往可以作出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。決策變量：描述決策的變量。dk(sk)：第k階段的決策變量（狀態變量sk的函數）。

允許決策集合：決策變量的取值范圍。常用Dk(sk)表示。顯然dk(sk)∈Dk(sk)。3、決策（decision）

如在引例的第二階段中，若從B1出發，D2(B1)={B1C1,B1C2,B1C3}，如果決定選取B1C2，則d2(B1)=B1C2。問題的全過程：從第一階段開始到最后階段終止的整個決策過程；k子過程：從第k階段開始到最后階段終止的決策過程；全過程策略：在全過程上，各階段的決策按順序排列組成的決策序列P1n={d1(s1),d2(s2),…,dn(sn),}簡稱策略；k子過程策略：在k子過程上的決策序列Pkn={dk(sk),dk+1(sk+1),…,dn(sn)}，簡稱（后部）子策略。4、策略（policy）

可供選擇策略的范圍，稱為允許策略集，用P表示。

動態規劃方法就是要從允許策略集P中找出最優策略P1n*={dk*

(sk),dk+1*

(sk+1),…,dn*(sn)}

若第k階段的狀態變量值為sk，當決策變量dk(sk)的取值決定后，下一階段狀態變量sk+1的值也就完全確定。即sk+1的值對應于sk和dk(sk)的值。這種對應關系記為sk+1＝Tk(sk,dk(sk))，稱為狀態轉移方程。狀態轉移方程描述了由一個階段的狀態到下一階段的狀態的演變規律。5、狀態轉移方程6、指標函數和最優指標函數

指標函數分為階段指標函數和過程指標函數。階段指標函數是對某一階段的狀態和決策產生的效益值的度量，用vk(sk,dk(sk))表示，在不同的問題中，其含義不同。它可以是距離、利潤、成本等；

在引例中，用vk(sk,dk(sk))表示在第k階段由點sk到點sk+1（由決策變量dk(sk)決定）的距離。如v2(B3,B3C1)=6。

過程指標函數是指過程所包含的各階段的狀態和決策所產生的總效益值，記為

動態規劃所要求的過程指標函數應具有可分離性，即可表達為它所包含的各階段指標函數的函數形式。常見的過程指標函數的形式：①各階段指標函數的和②各階段指標函數的積

最優指標函數：表示從第k階段的狀態sk開始采用最優子策略P*kn，到第n階段終止時所得到的指標函數值，記為：

在引例中，指標函數Vkn表示在第k階段由點sk至終點E的距離。fk(sk)表示第k階段點sk到終點E的最短距離。f2(B1)=11表示從第2階段中的點B1到點E的最短距離。7、基本方程（遞推關系式）遞推方程邊界條件引例：

通常動態規劃問題的最優值函數滿足遞推關系式。設過程指標函數為各階段指標函數的和的形式，即，則有

遞推方程和邊界條件一起稱為動態規劃的基本方程。可根據邊界條件，從k=n開始，由后向前逆推，逐步求得各階段的最優決策和相應的最優值，最后求出f1(s1)時，就得到整個問題的最優解。一般而言，指標函數是各階段的和時，其邊界條件為0；指標函數是各階段的乘積時，其邊界條件為1。三、動態規劃基本思想及原理

動態規劃方法的關鍵在于正確地寫出基本方程，因此首先必須將問題的過程劃分為多個相互聯系的多階段決策過程，恰當地選取狀態變量和決策變量及定義最優指標函數，從而把問題化成一族同類型的子問題。然后從邊界條件開始，逆過程行進方向，逐段遞推尋優。1、基本思想

在每個子問題求解時，均利用它前面已求出的子問題的最優化結果依次進行，最后一個子問題所得的最優解，就是整個問題的最優解。

在多階段決策過程中，動態規劃方法是既把當前的一段和未來的各段分開，又把當前效益和未來效益結合起來考慮的一種最優化方法。因此，每階段決策的選取是從全局來考慮，與該段的最優選擇一般是不同的。

動態規劃方法的基本思想體現了多階段性、無后效性、遞歸性、總體優化性。2、最優化原理

動態規劃方法基于R·Bellman等人提出的最優化原理：“作為整個過程的最優策略具有這樣的性質，即無論過去的狀態和決策如何，對于先前的決策所形成的狀態而言，余下的諸決策必須構成最優策略。”簡言之，“一個最優策略的子策略總是最優的”。

最優化原理僅是策略最優性的必要條件，而基本方程是策略最優性的充要條件。由此可見，基本方程是動態規劃理論與方法的基礎。

動態規劃是用來解決多階段決策過程最優化的一種數量方法。其特點在于，它可以把一個n維決策問題變換為n個一維最優化問題，從而一個一個地去解決。需指出：動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態規劃的原理和方法，建立相應的模型，然后再用動態規劃方法去求解。動態規劃特點：動態規劃優點：①許多問題用動態規劃研究求解比線性規劃、非線性規劃更有效，特別是離散性問題，解析數學無用武之地，而動態規劃成為得力工具；②某些情況下，用動態規劃處理不僅能作定性描述分析，且可利用計算機給出求其數值解的方法。①沒有統一的處理方法，求解時要根據問題的性質，結合多種數學技巧。因此，實踐經驗及創造性思維將起重要的引導作用。②“維數障礙”：當變量個數太多時，由于計算機內存和速度的限制導致問題無法解決。有些問題由于涉及的函數沒有理想的性質使問題只能用動態規劃描述，而不能用動態規劃方法求解。動態規劃缺點：四、動態規劃模型的建立與求解1、構成動態規劃模型的條件

建立動態規劃模型，就是分析問題并建立問題的動態規劃基本方程。為此，必須滿足以下條件：（1）將問題的過程劃分成恰當的階段；

（2）正確選擇狀態變量sk，使它既能描述過程的演變，又要滿足無后效性；

（3）確定決策變量dk(sk)及每階段的允許決策集合Dk(sk)；

（4）正確寫出狀態轉移方程；（5）正確寫出指標函數Vkn的關系式，它應具有以下三個性質；

A.是定義在全過程和所有后部子過程上的數量函數；

B.具有可分離性，并滿足遞推關系，即

Vkn(sk,dk(sk),…,sn+1)=f(sk,dk(sk),Vk+1,n)

C.函數f(sk,dk,Vk+1,n)對于Vk+1,n要求嚴格單調。2、建立動態規劃模型的步驟

（1）劃分階段劃分階段是運用動態規劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯系的階段。對于靜態問題要人為地賦予“時間”概念，以便劃分階段。

（2）正確選擇狀態變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態變量的取值能夠確定。一般地，狀態變量的選擇是從過程演變的特點中尋找。

（3）確定決策變量及允許決策集合通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。

（4）確定狀態轉移方程根據k階段狀態變量和決策變量，寫出k+1階段狀態變量，狀態轉移方程應當具有遞推關系。（5）確定階段指標函數和最優指標函數，建立動態規劃基本方程。3、求解動態規劃模型的方法

在已知初始狀態s1下，求解動態規劃模型時采用逆序解法（逆向遞歸），如下圖：階段1s1d1(s1)v1(s1,d1)…階段kskdk(sk)vk(sk,dk)階段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)階段nsndn(sn)vn(sn,dn)…Vknfk(sk)=optVkn尋優方向

引例的求解，就是把A看作始端，E為終端，規定從A到E為過程的行進方向，而尋優則是從E到A逆過程進行，所以是采用了逆序法。

例1(最短路徑問題)從A

地到D

地要鋪設一條煤氣管道,其中需經過兩級中間站，兩點之間的連線上的數字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？

AB1B2C1C2C3D24333321114

解：1、建立動態規劃模型

（1）問題劃分為三個階段k=1，2，3。即：

A→B，B→C，C→D；

（3）決策變量dk表示第k階段選擇的路線，例如其中第二階段的允許決策集為:

D2(B1)={B1C1,B1C2,B1C3}如果決定選擇B1C1，則d2(s2)

={B1C1}；（2）狀態變量sk表示第k階段初的位置，其中S1={A}，S2={B1,B2}，S3={C1,C2,C3}；AB1B2C1C2C3D24333321114（4）狀態轉移方程sk+1=T(sk,dk(sk))；（5）指標函數fk(sk)=v(sk,dk(sk))表示在第k階段由Sk點到Sk+1點的距離；（6）基本方程為

第一階段（C→D）：C

有三條路線到終點D

。AB1B2C1C2C3D24333321114DC1C2C3顯然有f1

(C1

)

=1；

f1(C2

)

=3；

f1

(C3

)

=4

2、用逆序算法求解第二階段（B→C）：B到C

有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)(最短路線為B2→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2第三階段（

A→B

）：A到B有兩條路線。(最短路線為A→B1→C1→D)C3AB1B2C1C2D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D,

路長為6AB1B2C1C2C3D24333321114DC1C2C3B1B2A

實例一（生產存貯問題）某工廠與購貨單位簽訂的供貨合同如下表。該廠每月最大產量為4百件，倉庫的存貨能力為3百件。已知每1百件貨物的生產費為1萬元。在生產的月份，每批產品的生產準備費為4千元，倉庫保管費為每1百件貨物每月1千元。假定1月初開始時及6月底交貨后倉庫中都無存貨。問該廠應該如何安排每月的生產與庫存，才能既滿足交貨合同的要求，又使總費用最小？五、應用實例月份123456交貨量（百件）125321

解：1、建立動態規劃模型（1）階段劃分：k=1，2，3，4，5，6；（2）狀態變量sk表示第k月初的庫存量，s1=0；（3）決策變量dk

(sk)表示第k月的計劃生產量，

ck表示第k月的合同交貨量。其中該廠每月最大產量為4百件，倉庫的存貨能力為3百件。（4）狀態轉移方程：（5）第k月的總費用包括生產費和庫存費（6）基本遞推方程當k=6時,s7=s6+d6(s6)-1=0,所以s6+d6(s6)=1

f6(s6)=min{v6(s6,d6(s6))}

當s6=0,d6(s6)=1,f6(s6)=14

當s6=1,d6(s6)=0,f6(s6)=1當k=5時，s6=s5+d5(s5)-2,所以2、用逆序算法求解當s5=0,當s5=1,當s5=2,當s5=3,d5(s5)=0,s6=1

k=4,3,2,1時類似求解，所求最優決策結果如下表：k月初存貨量sk最優生產量dk(sk)交貨量ck104123023145403350326101

實例二(背包問題)某工廠生產三種產品，各種產品重量與利潤的關系下表所示。現將此三種產品運往市場出售，運輸能力總重量不超過6噸，問如何安排使運輸總利潤最大？種類重量（噸/件）利潤（元/件）12802418033130

解：其實本例是一個整數規劃問題，其整數規劃模型如下1、建立動態規劃模型（1）階段劃分：k=1,2,3，把裝載一種產品看成一個階段;（3）決策變量dk(sk)表示第k階段裝載第k種貨物的件數;（2）狀態變量sk表示第k階段初可用于裝載產品的總容量，s1=6;（4）狀態轉移方程：（6）基本遞推方程（5）指標函數：vk(sk,dk(sk))表示裝載第k種貨物dk(sk)件所得的利潤，即v1(s1,d1(s1))=80d1(s1),

v2(s2,d3(s3))=180d2(s2),v3(s3,d3(s3))=130d3(s3)其中其中ak表示第k種貨物的單件重量;2、用逆序法求解其結果如下表：s3d3(s3)f3(s3)d3*(s3)000*01000200030101301401013015010130160120130260*2當k=3,其計算結果如下表:s2d2(s2)s3f3(s3)f2(s2)d2*(s2)00000010100020200030313013004014013000+130180+0*1501511301800+130180+01601622601800+260*180+00當k=2,其計算結果如下表s1d1(s1)s2f2(s2)f1(s1)d1*(s1)601236420260180000+260*80+180*160+0240+001按計算次序反推，得到最優解有兩個：（1）x1=0,x2=0,x3=2；（2）x1=1,x2=1,x3=0當k=1,

實例三（一維資源分配問題）某公司擬將3千萬元資金用于改造擴建所屬的3個工廠，每個工廠的利潤增長額與所分配到的投資額有關。各工廠在獲得不同的投資額時所能增加的利潤如下表。問應如何分配這些資金，使公司總的利潤增長額最大？