動態規劃動態規劃問題實例動態規劃的基本概念與原理動態規劃應用舉例引言動態規劃是解決多階段決策過程最優化的一種方法。該方法是由美國數學家貝爾曼（R.E.Bellman)等人在20世紀50年代初提出的。并成功地解決了生產管理、工程技術等方面的許多問題，從而建立了運籌學的一個新的分支，即動態規劃。Bellman在1957年出版了《DynamicProgramming》一書，是動態規劃領域中的第一本著作。§1動態規劃問題實例例1給定一個線路網絡，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要從A向F鋪設一條輸油管道，各點間連線上的數字表示距離，問應選擇什么路線，可使總距離最短？動態規劃是解決多階段決策問題的一種方法。所謂多階段決策問題是指這樣的決策問題：其過程可分為若干個相互聯系的階段，每一階段都對應著一組可供選擇的決策，每一決策的選定即依賴于當前面臨的狀態，又影響以后總體的效果。ABCDE狀態A狀態B狀態C狀態D狀態E狀態F決策A決策D決策E當每一階段的決策選定以后，就構成一個決策序列，稱為一個決策B決策C策略，它對應著一個確定的效果。多階段決策問題就是尋找使此效果最好的策略。§2

動態規劃的基本概念與原理一。基本概念階段：是指問題需要做出決策的步數。階段總數常記為n，相應的是n個階段的決策問題。階段的序號常記為k，稱為階段變量，k=1,2,…,n.k即可以是順序編號也可以是逆序編號，常用順序編號。狀態：各階段開始時的客觀條件，第k階段的狀態常用狀態變量表示，狀態變量取值的集合成為狀態集合，用表示。例如，例1中，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態1狀態2狀態3狀態4狀態5狀態6決策：是指從某階段的某個狀態出發，在若干個不同方案中做出的選擇。表示決策的變量，稱為決策變量，用表示例如：表示走到C階段,當處于C2路口時，下一步奔D1.

時的允許決策集合記為，例如：狀態轉移方程：是從上一階段的某一狀態值轉變為下一階段某一狀態值的轉移規律，用表示。決策變量允許的取值范圍稱為允許決策集合，第k階段狀態為策略(Strategy)由過程的第一階段開始到最后一階段為止稱為問題的全過程，由各階段的決策構成的策略序列稱為全過程策略，記為P1n。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=1k=2k=3k=4k=5k=6策略狀態指標函數：分階段指標函數和過程指標函數。階段指標函數是指第k階段從狀態出發，采取決策時的效益，用表示。而過程指標函數從第k階段的某狀態出發，采取子策略時所得到的階段效益之和：最優指標函數：表示從第k階段狀態為時采用最佳策略到過程終止時的最佳效益。記為其中opt可根據具體情況取max或min。基本方程：此為逐段遞推求和的依據，一般為：式中opt可根據題意取max或min.例如，例1的基本方程為：最優性原理動態規劃最優化原理：不管該最優策略上某狀態以前的狀態和決策如何，對該狀態而言，余下的諸決策必定構成最優子策略。即最優策略的任意后部子策略也是最優的。ABC將多階段的決策過程劃分為不同階段，恰當地選取狀態變量、決策變量并定義最優指標函數，正確寫出基本的遞推關系和恰當的邊界條件。求解時從邊界條件開始，逆過程進行方向逐段遞推尋優，在對每一個子問題進行求解時，都要使用前面已求出的子問題的最優結果，最后一個子問題的最優解就是整個問題的最優解。動態規劃方法每一階段最優決策選取是從全局考慮的，與該階段的最優決策一般是不同的。動態規劃方法的基本思想動態規劃應用舉例例1最短路線問題AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143逆序遞推方程：（1）k=5時，狀態它們到F點的距離即為最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時，狀態它們到F點需經過中途點E，需一一分析從E到F的最短路：先說從D1到F的最短路有兩種選擇：經過E1,E2,比較最短。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說明由D1到F的最短距離為7，其路徑為相應的決策為：這說明由D2到F的最短距離為5，其路徑為相應的決策為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應的決策為：（3）k=3時，狀態這說明由C1到F的最短距離為12，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143},,,{43213CCCCS=AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應的決策為即由C3到F的最短距離為8，相應的決策為即由C4到F的最短距離為9，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時，狀態這說明由B1到F的最短距離為13，相應的決策為即由B2到F的最短距離為15，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1時，只有一個狀態點A,則即由A到F的最短距離為17，相應的決策為所以最優路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計算順序反推可得最優決策序列：.)(1*1BAu=順序遞推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段行走方向AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1時注意到：所以K=2時AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=3時AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或類似地，可算出：最優策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或最短路徑：最短路長：注：順序解法與逆序解法無本質區別，一般來說，當初始狀態給定時用逆序解法，當終止狀態給定時用順序解法。若問題給定了一個初始狀態與一個終止狀態，則兩種方法均可使用。建立動態規劃模型的步驟分析問題。識別問題的多階段特征，按照時間或者空間的先后順序將過程適當地分為滿足遞推關系的若干階段，對非時序的靜態問題需要人為地賦予“時段”的概念；正確選擇具有以下兩個特征的狀態變量及其取值范圍

(1)可知性。過程演變的各階段狀態變量取值能直接或者間接地被確定。

(2)能確切描述過程的演變，且滿足無后效性確定決策變量及其取值范圍根據狀態變量和決策變量的含義，正確寫出狀態轉移方程sk+1=T(sk,xk)

根據問題，明確指標函數Fkn，最優指標函數fk(sk)

及k階段指標dk(sk,xk)

的含義，并正確列出最優指標函數的遞推關系及邊界條件檢查所建立的動態規劃模型是否正確表達了原問題的要求和各種限制條件建立動態規劃模型的步驟例2資源分配問題（離散型）例：設有6百萬元資金用于4個工廠的擴建，已知每個工廠的利潤增長額同投資額的大小有關，見下表。問應如何確定對這四個工廠的投資額，使總利潤增長額最大？

投資額

(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）解：把對四個工廠的投資依次看成4個階段的決策過程，確定對第k個工廠的投資額看成第k個階段的決策，k=1,2,3,4。圖示如下：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態狀態變量：可用于第k,k+1,…n個工廠的投資額。決策變量：第k階段對第k個工廠的投資額。允許決策集：狀態轉移方程：其中階段指標函數：第k階段投資元時所產生的利潤。（見上表）最優指標函數：第k階段狀態為且采取最佳投資策略，從第k個工廠以及以后的最大總利潤。

逆序法基本遞推方程：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態

投資額

(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）解：（1）k=4時考慮：若到最后一個，第4個工廠投資時，還有資金，若投資于第4個工廠的資金為，則最大利潤為工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態

投資額

(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）（注意到此時=0）自然問：現在還有多少錢？即=？=0，100，200，300，400，500，600都有可能。下面分情況討論：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態

投資額

(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）時，時，其他種情況類似討論，我們把所有的結果匯總成一個表2。

投資額

(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600

表2

k=4時決策表

投資額

(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）（2）k=3時到第三個工廠投資時，可利用的資金還有，若向第三個工廠投資（萬元），則自此即以后最大利潤為：

表1利潤增長額

（百元）

投資額

(j)工廠(i)010020030040050060030183961789095同樣問：=？，即現在還有多少錢？它是允許決策集上界。同理僅舉一例：

投資額

(j)工廠(i)010020030040050060030183961789095

表1利潤增長額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600

表2

k=4時決策表

投資額

(j)工廠(i)010020030040050060030183961789095

表1利潤增長額（百元）所有情況討論結果匯總成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300

表3

k=3時決策表（3）k=2時僅舉一例：

投資額

(j)工廠(i)010020030040050060020254557657073

表1利潤增長額（百元）010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300

表3

k=3時決策表關于的其它取值情況及相應的最優決策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表（4）k=1時，此時

投資額

(j)工廠(i)010020030040050060010204260758590

表1利潤增長額（百元）010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表匯一表格：0100200300400500600600134134134133138113901340或100或200

表5k=1時決策表此時對應最大值134的有三個值：

所對應的最優策略分別為：時，由狀態轉移方程知：所對應的010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表

對應的

再由狀態轉移方程

對應的

010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300

表3

k=3時決策表

所對應的

再由狀態轉移方程

對應的

01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600

表2

k=4時決策表

對應的

從而得一最優策略同理還有另外三個最優策略:所有解總利潤最大增長額為（百元）加上剛才一組資源分配問題（連續型）：設備負荷分配問題。例（何堅勇/P-256）某公司有500輛運輸卡車，在超負荷運輸（即每天滿載行駛500km以上）情況下，年利潤為25萬元/輛，這時卡車的年損壞率為0.3；在低負荷下運輸（即每天行駛300km以下）情況下，年利潤為16萬元/輛。年損壞率為0.1。現要制定一個5年計劃，問每年年初應如何分配完好車輛，在兩種不同的負荷下運輸的卡車數量，使在5年內的總利潤最大？解：這是一個以時間為特征的多階段決策問題。第1年第2年第3年第4年投x1輛超負荷車狀態狀態狀態投x2輛超負荷車投x3輛超負荷車投x4輛超負荷車第5年投x4輛超負荷車狀態狀態階段：將5年運輸計劃看成5個階段的決策問題。k=1,2,3,4,5狀態變量：第k階段初完好卡車數量，其中決策變量：表示第k階段分配給超負荷運輸的卡車數量。

顯然，分配給低負荷的卡車數為注：這里視，為連續變量。若=0.6表示有一輛卡車在第k年度有60℅的時間處于完好狀態。=0.7表示有一輛卡車在第k年度有70℅時間在超負荷運輸等等。狀態轉移方程：

階段指標函數：表示第k年度利潤。最優指標函數：第k年度初完好車輛數為時，采用最優策略到第5年末所產生的最大利潤。逆序遞推式為：1）k=5時（注意到此時=0）此時2）k=4時同理，只有當時，函數才能達到極大值。故有3）k=3時不難得到4）k=2時可見，只有當時，函數才能達到極大值。故有5）k=1時同理，只有當時，函數才能達到極大值。故有（萬元）所對應的最優策略分別為：時，由狀態轉移方程由且再由且第一年初：500輛車全部用于低負荷運輸。第二年初：還有450輛完好的車，也全部用于低負荷運輸。第三年初：還有405輛完好的車，全部用于超負荷運輸。第四年初：還有238.5輛完好的車，全部用于超負荷運輸。第五年初：還有198.45輛完好的車，全部用于超負荷運輸。到第五年末，即第六年初，還剩余138.15輛完好的車。實現最大利潤（億元）背包問題

一般的提法為：一旅行者攜帶背包去登山。已知他所能承受的背包重量的極限為a(千克)，現有n種物品可供他選擇裝入背包。第i種物品的單位重量為(千克)，其價值（可以是表明本物品對登山者的重要性指標）是攜帶數量的函數（i=1，2，…n）.問旅行者應如何選擇攜帶物品的件數，以使總價值最大？此模型解決的是運輸工具包括衛星的最優裝載問題。其數學模型為：設為第i種物品裝入的件數，則背包問題可歸結為如下形式的整數規劃模型：下面從一個例子來分析動態規劃建模。例7/P211

有一輛最大貨運量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應單位價值如表7-4所示。應如何裝載可使總價值最大？貨物編號i123單位重量（t）345單位價值ci456表7-4設第種貨物裝載的件數為則問題可表為：階段k:

將可裝入物品按1，2，3的順序排序，每段裝入一種物品，共劃分3個階段，即k=1,2,3.接下來用順序法求解狀態變量：在第k段開始時，背包中允許裝入前k種物品的總重量。（）決策變量：裝入第k種物品的件數。狀態轉移方程：最優指標函數：在背包中允許裝入物品的總重量不超過kg，采取最優策略只裝前k種物品時的最大使用價值貨物1貨物2貨物3由此可得動態規劃的順序遞推方程為：貨物1貨物2貨物3K=1時貨物1貨物2貨物3K=1時注意到：例如：時，其它計算結果見表7-5：01230123456789104×04×0

4×0

4×0

4×14×0

4×1

4×0

4×1

4×04×14×24×04×14×24×04×14×24×04×14×24×34×04×14×24×3000444888121200011122233表7-5貨物1貨物2貨物3K=2時其中例如：時，01230123456789104×04×0

4×0

4×0

4×14×0

4×1

4×0

4×1

4×04×14×24×04×14×24×04×14×24×04×14×24×34×04×14×24×3000444888121200011122233表7-5其它計算結果見表7-6：0120123456789105×0＋0

…

…

……5×0＋4

5×1＋0

…5×0＋125×1＋85×2＋00513011表7-6貨物1貨物2貨物3K=3時0120123456789105×0＋0

…

…

……5×0＋4

5×1＋0

…5×0＋125×1＋85×2＋00513011表7-6從再由狀態轉移方程0120123456789105×0＋0

…

…

……5×0＋4

5×1＋0

…5×0＋125×1＋85×2＋00513011表7-6貨物1貨物2貨物3再由狀態轉移方程最大裝載價值為01230123456789104×04×0

4×0

4×0

4×14×0

4×1

4×0

4×1

4×04×14×24×04×14×24×04×14×24×04×14×24×34×04×14×24×3000444888121200011122233表7-57.9(3)/P-239用動態規劃方法求解：解：Sk+1：可用于第1到第k個項目的投資額

Sk＝Sk+1－akxk

人為的劃分三個階段：k=1,2,3

階段指標函數及其他分配情況如下圖：123k=1k=2k=3解：Sk：可用于第k到第3個項目的投資額

Sk+1＝Sk－akxk

人為的劃分三個階段：k=1,2,3

階段指標函數及其他分配情況如下圖：123k=3k=2k=3例5貨郎擔問題貨郎擔問題也叫推銷商問題（travelingsalesmanproblem）,其一般提法為：有n個城市，用1，2，…，n表示，城i,j之間的距離為，有一個貨郎從城1出發到其他城市一次且僅一次，最后回到城市1，怎樣選擇行走路線使總路程最短？123645789101112452368775845348435623113345一。動態規劃解階段變量k：按所經過的城市個數劃分階段k,k=1,2,…,n-1.狀態變量：設第k階段到達城市i時途中所經過的k個城市集合為S，則其中123645789101112452368775845348435623113345例如：，表示推銷商從城1出發途徑城市{2,3,4}到達城市5時，須先途經城市{2,4}到達城市3，再奔城市5。決策變量：第k階段到達城市i的最短路線上鄰接i的前一個城市。1236457891011124523687758453484356