動態規劃
動態規劃（dynamic programming），簡稱DP.
動態規劃的基本概念
動態規劃的發展及研究內容
動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最最佳化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的最佳化問題時，提出了著名的最最佳化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程最佳化問題的新方法——動態規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作。
動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的套用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。
雖然動態規劃主要用於求解以時間劃分階段的動態過程的最佳化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。
多階段決策問題
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯繫的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
決策過程的分類
根據過程的時間變數是離散的還是連續的，分為離散時間決策過程(discrete-time decision process)，即多階段決策過程和連續時間決策過程(continuous-time decision process)；根據過程的演變是確定的還是隨機的，分為確定性決策過程 (deterministic decision process)和隨機性決策過程(stochastic decision process)，其中套用最廣的是確定性多階段決策過程。
動態規劃模型的基本要素
一個多階段決策過程最最佳化問題的動態規劃模型通常包含以下要素：
1.階段
階段(step)是對整個過程的自然劃分。通常根據時間順序或空間特徵來劃分階段，以便按階段的次序解最佳化問題。階段變數一般用k= 1,2,..,n表示。在例1中由A出發為k=1，由Bi(i=1,2)出發為k=2，依此下去從Di(i=1,2,3)出發為k=4，共n=4個階段。在例2中按照第一、二、三、四季度分為k=1,2,3,4，共4個階段。
2.狀態
狀態(state)表示每個階段開始時過程所處的自然狀況。它應該能夠描述過程的特徵並且具有無後向性，即當某階段的狀態給定時，這個階段以後過程的演變與該階段以前各階段的狀態無關，即每個狀態都是過去歷史的一個完整總結。通常還要求狀態是直接或間接可以觀測的。
描述狀態的變數稱狀態變數(state variable)。變數允許取值的範圍稱允許狀態集合 (set of admissible states)。用xk表示第k階段的狀態變數，它可以是一個數或一個向量。用Xk表示第k階段的允許狀態集合。在例1中x2可取B1，B2，X2={B1,B2}。
n個階段的決策過程有n+1個狀態變數，xn+1表示xn演變的結果，在例1中x5取E。
根據過程演變的具體情況，狀態變數可以是離散的或連續的。為了計算的方便有時將連續變數離散化；為了分析的方便有時又將離散變數視為連續的。
狀態變數簡稱為狀態。
3.決策
當一個階段的狀態確定後，可以作出各種選擇從而演變到下一階段的某個狀態，這種選擇手段稱為決策(decision)，在最優控制問題中也稱為控制(control)。
描述決策的變數稱決策變數(decision variable)。變數允許取值的範圍稱允許決策集合 (set of admissible decisions)。用uk(xk)表示第k階段處於狀態xk時的決策變數，它是xk的函式，用Uk(xk)表示了xk的允許決策集合。在例1中u2(B1)可取C1,C2,C3。
決策變數簡稱決策。
4.策略
決策組成的序列稱為策略(policy)。由初始狀態x1開始的全過程的策略記作p1n(x1)，即p1n(x1)={u1(x1),u2 (x2),...，un(xn)}。由第k階段的狀態xk開始到終止狀態的後部子過程的策略記作PKN(xk)，即pkn(xk)={uk(xk),uk +1(xk+1),...，un(xn)}。類似地，由第k到第j階段的子過程的策略記作pkj(xk)={uk(xk),uk+1(xk+ 1),...，uj(xj)}。對於每一個階段k的某一給定的狀態xk，可供選擇的策略pkj(xk)有一定的範圍，稱為允許策略集合 (set of admissible policies)，用P1n(x1),Pkn(xk),Pkj(xk)表示。
5.狀態轉移方程
在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用狀態轉移方程(equation of state)表示這種演變規律，寫作
在例1中狀態轉移方程為：xk+1=uk(xk)
6.指標函式和最優值函式
指標函式(objective function)是衡量過程優劣的數量指標，它是關於策略的數量函式，從階段k到階段n的指標函式用Vkn(xk,pkn(xk))表示，k=1,2,...,n。
能夠用動態規劃解決的問題的指標函式應具有可分離性，即Vkn可表為xk,uk,Vk+1 n 的函式，記為：
其中函式是一個關於變數Vk+1 n單調遞增的函式。這一性質保證了最最佳化原理(principle of optimality)的成立，是動態規劃的適用前提。
過程在第j 階段的階段指標取決於狀態xj和決策uj，用vj(xj,uj)表示。階段k到階段n的指標由vj(j=k,k+1,..n)組成，常見的形式有：
階段指標之和，即
階段指標之積，即
階段指標之極大(或極小)，即
這些形式下第k到第j階段子過程的指標函式為Vkj(xk,uk,xk+1,...,xj+1)。可以發現，上述(3)-(5)三個指標函式的形式都滿足最優性原理。在例1中指標函式為(3)的形式，其中vj(xj,uj)是邊<xj,uj(xj)>的權（邊的長度）,uj(xj)表示從xj出髮根據決策uj(xj)下一步所到達的節點。
根據狀態轉移方程，指標函式Vkn還可以表示為狀態xk和策略pkn的函式，即Vkn(xk,pkn)。在xk給定時指標函式Vkn對pkn的最優值稱為最優值函式(optimal value function)，記作fk(xk)，即
其中opt可根據具體情況取max或min。上式的意義是，對於某個階段k的某個狀態xk，從該階段k到最終目標階段n的最優指標函式值等於從xk出發取遍所有能策略pkn所得到的最優指標值中最優的一個。
7.最優策略和最優軌線
使指標函式Vkn達到最優值的策略是從k開始的後部子過程的最優策略，記作pkn*={uk*,..un*},p1n*又是全過程的最優策略，簡稱最優策略(optimal policy)。從初始狀態x1(=x1*)出發，過程按照p1n*和狀態轉移方程演變所經歷的狀態序列{x1*, x2*,..,xn+1*}稱最優軌線(optimal trajectory)。
