第四章動態規劃
第一節動態規劃原理
一、基本概念
1．引例
【例4－1】最短路程問題。某地區需要由發電廠至使用者端架設一條高壓輸電線路，途中經過三個城鎮、、，每個城鎮又各需建設乙個變電站。城鎮和各有二個站址可供選擇，城鎮有三個站址可供選擇，相互間地理位置如圖4－1所示，圖中各線段旁資料表示該段路徑相對長度。
問如何選址，才能使由到所用輸電線最短？
5a 3e
解：問題分4段。
本例是乙個四階段決策過程。
窮舉法：共有2×3×2×1＝12個不同方案，比較後可得最短路徑為：
最短路線總長為12。
記：第階段某位置到的最短距離，
：第階段某出發位置至第階段某終點位置的距離。
、、表示什麼？
目的：求，
需先求、，進一步，需先求、、，…
求解過程：
本例求解過程
時，時，
最短路徑為：
最短路徑為：
最短路徑為：
時，最短路徑為：
最短路徑為：
時，由到的最短距離為12，最短路徑為：。
將每段中各點至的最短距離標在該點旁邊，即可得圖4－2。
a(12
圖4－2各點至的最短路徑
下面對本例使用的動態規劃解法進行簡單的分析總結。
（1）與窮舉法相比，動態規劃方法有優點之一就是大大減少了計算工作量。本例中用動態規劃方法求解共用了14次相加計算、8次比較運算。事實上，問題規模越大，動態規劃方法比窮舉法節省的計算工作量越多。
（2）用動態規劃方法不僅求得了全過程的最優方案，而且得到了任一子過程的最優方案。對本例來說就是不僅求出了由a到e的最短路徑和距離，而且得到任意一點至e的最短路徑和距離。這一特點對許多實際問題都是非常有用的。
（3）動態規劃法雖然把整個過程分成若干階段，但每個階段的計算總是把當前效益與整體效益結合起來考慮，且以總體效益為準。
（4）多階段決策過程一般是不可逆的。但象例4－1這類問題，由於從a到e的最短路徑和距離與從e到a的最短路徑和距離相同，我們可以隨便選定一端為起點，另一端則為終點，尋找最優解時從終端向始端進行。象這樣可以把整個問題倒過來求解的過程稱為可逆過程。
（5）用動態規劃方法求解的多階段決策問題還有乙個重要特性，即無後效性。所謂無後效性是指對任意階段的任意乙個狀態來說，從此以後過程的發展只與現在的情況有關，與過去的情況無關。
2．基本概念和術語
1>階段：將問題分為若干互相聯絡的子過程，每個子過程稱為乙個階段，階段一般順序地用自然數1，2，…編號，通常用表示階段變數。
2>狀態、狀態變數：每一階段的出發位置稱為該階段的狀態。描述狀態的變數用表示，表示第段第個狀態，第段全體狀態集合為：
可以表示為
3>決策、決策變數：描述決策的變數稱為決策變數，表示第段狀態處於時的決策變數。
：允許決策集合，
4>策略：由每個階段的決策變數構成的決策變數序列稱為全過程策略，簡稱策略，用符號表示，即
子過程策略記為，即
從允許策略中找出效果最優的策略，稱為最優策略。
5>狀態轉移：確定的規則記為
稱之為狀態轉移方程。
6>指標函式、最優指標函式：
：最優指標函式；
：階段指標函式，它是，的函式。
二、動態規劃的最優化原理與基本方程
1．貝爾曼原理：乙個過程的最優策略具有以下性質：無論過去的狀態和決策如何，對前面的決策形成的當前狀態而言，餘下的諸決策必須構成最優策略。
2．動態規劃的基本方程
對一般的階段決策過程而言，第階段和第階段的之間有以下遞推關係：
結合，稱
為動態規劃的函式基本方程，簡稱動態規劃基本方程。
【例4－2】某工廠擬在今後三年內購買某種裝置五颱，考慮到裝置維護、資金貼現等各種因素後，預計第
一、第二、第三年初購買該裝置可獲純利如表4－1所示。問如何制定買計畫，才能使該廠獲得最大利潤？
表4-1 純利與購買裝置時間、台數的關係 （萬元）
解：為用動態規劃方法求解，應明確以下問題：
（1）以購買裝置時間為順序，將問題劃分為三個階段。
（2）引進4個狀態變數、、、，其中表示第年初至第三年末可（允許）購買裝置的台數，並且規定上一年末與下一年初為同一時刻。
（3）決策變數表示第年初購買裝置台數。
（4）狀態轉移方程為
（5）階段指標表示第年購買臺裝置所獲純利（萬元）；最優指標函式表示年初至第三年末購買臺裝置所能獲得的最大純利（萬元）。
（6）本題動態規劃函基本方程為
=3時，
所以=２時，對應＝０,１,２,３,4,５可分別計算如下
故 故故
故=１時，已知，故有
所以由此得最優購買方案為：
或最大純利為：
第二節函式迭代與策略迭代
確定性、固定階段決策問題；
確定性、無固定階段決策問題。
問題：設有個點1，2，…，。任意兩點、之間有一弧連線，其長度為（可以代表距離、費用等），。表示和之間沒有鏈結弧。試求任一點到的最短距離。
分析：設表示點到點的最短距離，則從必先到某，然後再經過某些點，最後到，因此得
問題是從不能推知的值，因此上式不是遞推公式，不能用第一節所講方法求解。
一、函式迭代法
１．基本思想
以步數作為階段數，
先求從到的一步最短路，
再求從到的兩步最短路，
……再求從到的 n-1步最短路，
能得到最優結果嗎？
一定能，最多不會超過步即可求得最短路徑和最短距離。
２．迭代步驟
設表示從出發，經步到的最短距離。
（1）當時，有
（2）按遞推關係求，即
（3）當時，停止迭代。此時，且不超過。
例１ 有四個城市，它們之間的相互位置和各個城市之間的距離如下圖所示。試求每個城市到城市4的最短路徑和距離。
4 21
1 5
4解：時，由，
得下表：
值時，由
得的值如表所示。
的值時，由
得的值如表所示。
的值由於已計算了3＝4－1＝n－1步，故可停止迭代。最優策略和最短距離如下表所示
最短距離和最優策略
最短距離為4
最短距離為2
最短距離為1
二、策略迭代法
1．基本思想
1>給乙個初始策略，即
，，然後按某種方法求出新策略：，，……直至求出最優策略。
2>從計算出由到的距離。
3>由再確定新的策略，就是使取最小值的那個。即若
則。4>重複這一過程，當對某一，
對所有均成立時，則就是最優策略。
2．迭代步驟
1>選擇乙個沒有迴路的初始策略
2>由策略計算，即由方程組
解出，其中為已知。
？？3>由求，若
則取。4>按（2）、（3）步反覆迭代，直至
則得。結論：有限步必可求得最優策略。
例２ 用策略迭代法求解例１。
解：1>先取一無迴路的初始策略，
2>求和。由得
由此可解出：
3>求計算過程及結果
3>再求和，顯然
由求的過程及結果列於下表
計算過程及結果
4>求和。易得
由可得，如下表所示。
計算過程及結果
再計算一步可發現與相同。因此，最優策略為：
結果與函式迭代法相同，最短路徑與最短距離均與例１相同，不再列出。
注意：在本例第二步中，與例１中相同。此後，函式迭代與策略迭代所得、均相同。
對一般情況，當初始策略選為時，兩種迭代方法本質上是一樣的。只是函式迭代法中，第步僅寫出沒寫出，因此，這種情況下函式迭代法比策略迭代法大約減少了一半計算工作量。另外，對一具體問題來說，函式迭代法的計算步驟與計算工作量是一定的，而策略迭代法的計算步驟與計算工作量與初始策略關係很大。
如能使離最優策略較近，則可大大減少計算工作量。
練習：全做
動態規劃練習
任務 請寫乙個程式 在文字檔案tan.in中讀入路程的總長度 旅館的數目和對旅館的描述 找出兩個旅行的方案 乙個最便宜的方案 就是付出的宿費最少的方案 如果有多個方案，選擇在旅館中度夜的次數最少的方案 乙個最短的方案 就是在旅館中度夜的次數最少的方案 如果有多個方案，選擇花費最少的方案 把結果，就是...
動態規劃作業
作業1動態規劃練習 為保證某一裝置的正常運轉，需備有三種不同的零件e1 e2 e3 若增加備用零件的數量，可提高裝置正常運轉的可靠性，但增加了費用，而投資額僅為8000 元。已知備用零件數與它的可靠性和費用的關係如表1 所示。現要求在既不超出投資額的限制，又能盡量提高裝置運轉的可靠性的條件下，問各種...
動態規劃作業
作業土規1101班劉邁克 2011306200521 1.運用動態規劃解決 為保證某一裝置的正常運轉，需備有三種不同的零件e1 e2 e3。若增加備用零件的數量，可提高裝置正常運轉的可靠性，但增加了費用，而投資額僅為8000元。已知備用零件數與它的可靠性和費用的關係如表所示。現要求在既不超出投資額的...