動態規劃

　　研究多段（多步）決策過程最優化問題的一種數學方法，英文縮寫DP，是最優控制和運籌學的重要數學工具。為瞭尋找系統最優決策，可將系統運行過程劃分為若幹相繼的階段（或若幹步），並在每個階段（或每一步）都作出決策。這種決策過程就稱為多段（多步）決策過程。多段決策過程的每一階段的輸出狀態就是下一階段的輸入狀態。某一階段所作出的最優決策，對於下一階段未必是最有利的。多段決策過程的最優化問題必須從系統整體出發，要求各階段選定的決策序列所構成的策略最終能使目標函數達到極值值。

　　發展簡況　20世紀40年代，人們開始研究水力資源的多級分配和庫存的多級存儲問題。50年代初,美國數學傢R.貝爾曼首先提出動態規劃的概念，1957年發表《動態規劃》一書。在1961、1962年相繼出版的第二版和第三版中，又進一步闡明瞭動態規劃的理論和方法。

　　多段決策過程　又稱為多步決策過程(或系統)，是一種適合采用動態規劃的過程(或系統)。多段決策過程包括階段、狀態、決策、策略和目標函數 5個要素。①階段:把所要求解的過程劃分成若幹相互聯系的階段,並用k表示階段變量。②狀態:表示某一階段出發位置的狀態，它既是上一階段的輸出又是本階段的輸入，並用向量x_k表示第k階段的狀態，稱為狀態變量。③決策:指給定k階段的狀態後,從該狀態轉移到下一階段某一狀態的選擇。用U_k表示第k階段當狀態處於X_k時的決策變量。對於系統的每一個狀態，都可以從若幹種可能的決策（或控制）中任選一種。選定決策並加以實施，即可引起系統狀態的變化。系統的下一階段狀態由現在的狀態和決策確定，與過去的歷史無關，即系統是無記憶的。④策略：由過程中每一階段所選決策構成的整個序列，又稱為方案。⑤目標函數：策略的目標是使狀態變量的某個特定函數的值為最大（或最小）。這個特定函數就是目標函數。使目標函數值為最大（或最小）的策略稱為最優策略。圖1中求最短路徑的例子說明瞭多段決策過程及其構成要素。圖中S是出發點，G是目的地，各邊上的數字表示兩點間的距離。求從S到G的最短路徑和距離數。首先，可將圖1劃分成四個階段，然後逆向依次尋求使總的距離為最小的最短路徑。先從第一階段開始,從C₁到G隻有一條路線,同樣從C₂到G也隻有一條路線。到瞭第二階段，從B₁到G有經過C₁或C₂兩條路線，經選擇後由B₁經C₂到G距離最小。如此繼續進行下去，就把一個最短路徑問題變成瞭多段決策問題（圖2）。最後求得最短路徑為SA₂B₁C₂G。

　　基本原理　動態規劃的理論基礎是最優化原理和嵌入原理。

　　最優化原理　一個最優策略，具有如下性質：不論初始狀態和初始決策（第一步決策）如何，以第一步決策所形成的階段和狀態作為初始條件來考慮時，餘下的決策對餘下的問題而言也必構成最優策略。最優化原理體現瞭動態規劃方法的基本思想。

　　嵌入原理　一個具有已知初始狀態和固定步數的過程總可以看作是初始狀態和步數均不確定的一族過程中的一個特殊情況。這種把所研究的過程嵌入一個過程族的原理稱為嵌入原理。通過研究過程族的最優策略族的共同性質得出一般通解，此通解自然也適用於原來的特殊問題。動態規劃的基本方法就是根據嵌入原理把一個多步決策問題化為一系列較簡單的一步決策問題，可顯著降低數學處理上的難度。

　　貝爾曼方程　應用最優化原理和嵌入原理可推導出動態規劃的基本方程，稱為貝爾曼方程。它具有下面的形式：

式中N表示多段決策過程的總段數,F(x_k，u_k)為標量函數，表示由第k段到第k+1段的過程中基於狀態x_k和決策u_k的性能損失，

表示以 x_k+1為初始狀態的後 N-( k+1)段分過程的最優性能目標， x_k+1= f( x_k，u_k)是基於第 k段的狀態 x_k和決策 u_k而得到的第 k+1段的狀態向量， [·]表示選擇決策 u_k使[·]取極小值。這是一個逆向遞推方程。采用迭代法按 k= N-1, N-2,…,1,0順序求解貝爾曼方程，即可得到 N段決策過程的最優策略{ u_k，k=0,1,2,…, N-1}和最優軌線{ x_k，k=0,1,2,…, N },而最優性能值為 J _N ^*( x ₀)。

　　對於圖1中的例子，貝爾曼方程的形式如下：

經迭代計算後，得

………………………

這就是所求的最短距離。從S到G的最短路徑是SA₂B₁C₂G。而A₂B₁C₂G，B₁C₂G，C₂G 則分別是從A₂，B₁,C₂到G 的最短路徑。

　　貝爾曼方程是關於未知函數（目標函數）的函數方程組。應用最優化原理和嵌入原理建立函數方程組的方法稱為函數方程法。在實際運用中要按照具體問題尋求特殊解法。動態規劃理論開拓瞭函數方程理論中許多新的領域。

　　特點和應用范圍　若多階段決策過程為連續型，則動態規劃與變分法處理的問題有共同之處。動態規劃原理可用來將變分法問題歸結為多階段決策過程，用動態規劃的貝爾曼方程求解。在最優控制理論中動態規劃方法比極大值原理更為適用。但動態規劃還缺少嚴格的邏輯基礎。60年代，В．Г．沃爾昌斯基對動態規劃方法作瞭數學論證。動態規劃方法有五個特點：①在策略變量較多時，與策略窮舉法相比可降低維數；②在給定的定義域或限制條件下很難用微分方法求極值的函數，可用動態規劃方法求極值；③對於不能用解析形式表達的函數,可給出遞推關系求數值解；④動態規劃方法可以解決古典方法不能處理的問題，如兩點邊值問題和隱變分問題等；⑤許多數學規劃問題均可用動態規劃方法來解決，例如，含有隨時間或空間變化的因素的經濟問題。投資問題、庫存問題、生產計劃、資源分配、設備更新、最優搜索、馬爾可夫決策過程，以及最優控制和自適應控制等問題，均可用動態規劃方法來處理。

　　

參考書目

　R.E. Bellman，Dynamic Programming，princeton Univ.Press,Princeton,N.J.,1957.

　S.E. Dreyfus，Dynamic Programming and the Calculus of Variations，Academic Press, New York,1965.

　S.E.Dreyfus and A.M.Law, The Art and Theory of Dynamic Programming， Academic Press，New York，1977.