第四章動態規劃
§1 引言
1.1 動態規劃的發展及研究內容
動態規劃（dynamic programming）是運籌學的乙個分支，是求解多階段決策問題的最優化方法。20世紀50年代初r. e.
bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優性原理（principle of optimality），把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法—動態規劃。2023年出版了他的名著《dynamic programming》，這是該領域的第一本著作。
動態規劃問世以來，在經濟管理、生產排程、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、裝置更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃（如線性規劃、非線性規劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。
應指出，動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊演算法（如線性規劃是一種演算法）。因而，它不象線性規劃那樣有乙個標準的數學表示式和明確定義的一組規則，而必須對具體問題進行具體分析處理。因此，在學習時，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創造性的技巧去求解。
例1 最短路線問題
下面是乙個線路網，連線上的數字表示兩點之間的距離（或費用）。試尋求一條由到距離最短（或費用最省）的路線。
例2 生產計畫問題
工廠生產某種產品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產能力為6（千件）。經調查，市場對該產品的需求量第
一、二、
三、四季度分別為2，3，2，4（千件）。如果工廠在第
一、二季度將全年的需求都生產出來，自然可以降低成本（少付固定成本費），但是對於第
三、四季度才能上市的產品需付儲存費，每季每千件的儲存費為0.5（千元）。還規定年初和年末這種產品均無庫存。
試制定乙個生產計畫，即安排每個季度的產量，使一年的總費用（生產成本和儲存費）最少。
1.2 決策過程的分類
根據過程的時間變數是離散的還是連續的，分為離散時間決策過程（discrete-time decision process）和連續時間決策過程（continuous-time decision process）；根據過程的演變是確定的還是隨機的，分為確定性決策過程（deterministic decision process）和隨機性決策過程（stochastic decision process），其中應用最廣的是確定性多階段決策過程。
§2 基本概念、基本方程和計算方法
2.1 動態規劃的基本概念和基本方程
乙個多階段決策過程最優化問題的動態規劃模型通常包含以下要素。
2.1.1 階段
階段(step)是對整個過程的自然劃分。通常根據時間順序或空間順序特徵來劃分階段，以便按階段的次序解優化問題。階段變數一般用表示。
在例1中由出發為，由出發為，依此下去從出發為，共個階段。在例2中按照第
一、二、
三、四季度分為，共四個階段。
2.1.2 狀態
狀態（state）表示每個階段開始時過程所處的自然狀況。它應能描述過程的特徵並且無後效性，即當某階段的狀態變數給定時，這個階段以後過程的演變與該階段以前各階段的狀態無關。通常還要求狀態是直接或間接可以觀測的。
描述狀態的變數稱狀態變數（state variable）。變數允許取值的範圍稱允許狀態集合(set of admissible states)。用表示第階段的狀態變數，它可以是乙個數或乙個向量。
用表示第階段的允許狀態集合。在例1中可取，或將定義為，則或，而。
個階段的決策過程有個狀態變數，表示演變的結果。在例1中取，或定義為，即。
根據過程演變的具體情況，狀態變數可以是離散的或連續的。為了計算的方便有時將連續變數離散化；為了分析的方便有時又將離散變數視為連續的。
狀態變數簡稱為狀態。
2.1.3 決策
當乙個階段的狀態確定後，可以作出各種選擇從而演變到下一階段的某個狀態，這種選擇手段稱為決策（decision），在最優控制問題中也稱為控制（control）。
描述決策的變數稱決策變數（decision variable），變數允許取值的範圍稱允許決策集合（set of admissible decisions）。用表示第階段處於狀態時的決策變數，它是的函式，用表示的允許決策集合。在例1中可取或，可記作，而。
決策變數簡稱決策。
2.1.4 策略
決策組成的序列稱為策略（policy）。由初始狀態開始的全過程的策略記作，即
.由第階段的狀態開始到終止狀態的後部子過程的策略記作，即
，.類似地，由第到第階段的子過程的策略記作
.可供選擇的策略有一定的範圍，稱為允許策略集合(set of admissible policies)，用表示。
2.1.5. 狀態轉移方程
在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用狀態轉移方程（equation of state transition）表示這種演變規律，寫作
1）在例1中狀態轉移方程為。
2.1.6. 指標函式和最優值函式
指標函式(objective function)是衡量過程優劣的數量指標，它是定義在全過程和所有後部子過程上的數量函式，用表示，。指標函式應具有可分離性，即可表為的函式，記為
並且函式對於變數是嚴格單調的。
過程在第階段的階段指標取決於狀態和決策，用表示。指標函式由組成，常見的形式有：
階段指標之和，即
，階段指標之積，即
，階段指標之極大（或極小），即
.這些形式下第到第階段子過程的指標函式為。
根據狀態轉移方程指標函式還可以表示為狀態和策略的函式，即。在給定時指標函式對的最優值稱為最優值函式（optimal value function），記為，即
，其中可根據具體情況取或。
2.1.7 最優策略和最優軌線
使指標函式達到最優值的策略是從開始的後部子過程的最優策略，記作。是全過程的最優策略，簡稱最優策略（optimal policy）。從初始狀態出發，過程按照和狀態轉移方程演變所經歷的狀態序列稱最優軌線（optimal trajectory）。
2.1.8 遞迴方程
如下方程稱為遞迴方程
2）在上述方程中，當為加法時取；當為乘法時，取。動態規劃遞迴方程是動態規劃的最優性原理的基礎，即：最優策略的子策略，構成最優子策略。
用狀態轉移方程（1）和遞迴方程（2）求解動態規劃的過程，是由逆推至，故這種解法稱為逆序解法。當然，對某些動態規劃問題，也可採用順序解法。這時，狀態轉移方程和遞迴方程分別為：
，縱上所述，如果乙個問題能用動態規劃方法求解，那麼，我們可以按下列步驟，首先建立起動態規劃的數學模型：
（）將過程劃分成恰當的階段。
（）正確選擇狀態變數，使它既能描述過程的狀態，又滿足無後效性，同時確定允許狀態集合。
（）選擇決策變數，確定允許決策集合。
（）寫出狀態轉移方程。
（）確定階段指標及指標函式的形式（階段指標之和，階段指標之積，階段指標之極大或極小等）。
（）寫出基本方程即最優值函式滿足的遞迴方程，以及端點條件。
§3 逆序解法的計算框圖
以自由終端、固定始端、指標函式取和的形式的逆序解法為例給出計算框圖，其它情況容易在這個基礎上修改得到。
一般化的自由終端條件為
3)其中為已知。固定始端條件可表示為。
如果狀態和決策是連續變數，用數值方法求解時需按照精度要求進行離散化。設狀態的允許集合為
.決策的允許集合為
.狀態轉移方程和階段指標應對的每個取值和的每個取值計算，即，。最優值函式應對的每個取值計算。基本方程可以表為
4）按照（3），（4）逆向計算出，為全過程的最優值。記狀態的最優決策為，由和按照狀態轉移方程計算出最優狀態，記作。並得到相應的最優決策，記作。於是最優策略為。
演算法程式的框圖如下。
圖的左邊部分是函式序列的遞推計算，可輸出全過程最優值，如果需要還可以輸出後部子過程最優值函式序列和最優決策序列。計算過程中存是備計算之用，在算完後可用將替換掉；存是備右邊部分讀之用。
圖的右邊部分是最優狀態和最優決策序列的正向計算，可輸出最優策略和最優軌線。
§4 動態規劃與靜態規劃的關係
動態規劃與靜態規劃（線性和非線性規劃等）研究的物件本質上都是在若干約束條件下的函式極值問題。兩種規劃在很多情況下原則上可以相互轉換。
動態規劃可以看作求決策使指標函式達到最優（最大或最小）的極值問題，狀態轉移方程、端點條件以及允許狀態集、允許決策集等是約束條件，原則上可以用非線性規劃方法求解。
一些靜態規劃只要適當引入階段變數、狀態、決策等就可以用動態規劃方法求解。下面用例子說明。
例3 用動態規劃解下列非線性規劃
；s.t. .
其中為任意的已知函式。
解按變數的序號劃分階段，看作段決策過程。設狀態為，取問題中的變數為決策。狀態轉移方程為
取為階段指標，最優值函式的基本方程為（注意到）；；
.按照逆序解法求出對應於每個取值的最優決策，計算至後即可利用狀態轉移方程得到最優狀態序列和最優決策序列。
與靜態規劃相比，動態規劃的優越性在於：
（）能夠得到全域性最優解。由於約束條件確定的約束集合往往很複雜，即使指標函式較簡單，用非線性規劃方法也很難求出全域性最優解。而動態規劃方法把全過程化為一系列結構相似的子問題，每個子問題的變數個數大大減少，約束集合也簡單得多，易於得到全域性最優解。
特別是對於約束集合、狀態轉移和指標函式不能用分析形式給出的優化問題，可以對每個子過程用列舉法求解，而約束條件越多，決策的搜尋範圍越小，求解也越容易。對於這類問題，動態規劃通常是求全域性最優解的唯一方法。
（）可以得到一族最優解。與非線性規劃只能得到全過程的乙個最優解不同，動態規劃得到的是全過程及所有後部子過程的各個狀態的一族最優解。有些實際問題需要這樣的解族，即使不需要，它們在分析最優策略和最優值對於狀態的穩定性時也是很有用的。
當最優策略由於某些原因不能實現時，這樣的解族可以用來尋找次優策略。
（）能夠利用經驗提高求解效率。如果實際問題本身就是動態的，由於動態規劃方法反映了過程逐段演變的前後聯絡和動態特徵，在計算中可以利用實際知識和經驗提高求解效率。如在策略迭代法中，實際經驗能夠幫助選擇較好的初始策略，提高收斂速度速度。
動態規劃練習
任務 請寫乙個程式 在文字檔案tan.in中讀入路程的總長度 旅館的數目和對旅館的描述 找出兩個旅行的方案 乙個最便宜的方案 就是付出的宿費最少的方案 如果有多個方案，選擇在旅館中度夜的次數最少的方案 乙個最短的方案 就是在旅館中度夜的次數最少的方案 如果有多個方案，選擇花費最少的方案 把結果，就是...
動態規劃講稿
第四章動態規劃 第一節動態規劃原理 一 基本概念 1 引例 例4 1 最短路程問題。某地區需要由發電廠至使用者端架設一條高壓輸電線路，途中經過三個城鎮 每個城鎮又各需建設乙個變電站。城鎮和各有二個站址可供選擇，城鎮有三個站址可供選擇，相互間地理位置如圖4 1所示，圖中各線段旁資料表示該段路徑相對長度...
動態規劃作業
作業1動態規劃練習 為保證某一裝置的正常運轉，需備有三種不同的零件e1 e2 e3 若增加備用零件的數量，可提高裝置正常運轉的可靠性，但增加了費用，而投資額僅為8000 元。已知備用零件數與它的可靠性和費用的關係如表1 所示。現要求在既不超出投資額的限制，又能盡量提高裝置運轉的可靠性的條件下，問各種...