馬賽克飾面

[拼音]：dongtai guihua

[英文]：dynamic programming

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

發展簡況

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

多段決策過程

又稱為多步決策過程(或系統)，是一種適合採用動態規劃的過程(或系統)。多段決策過程包括階段、狀態、決策、策略和目標函式 5個要素。

（1）階段:把所要求解的過程劃分成若干相互聯絡的階段,並用k表示階段變數。

（2）狀態:表示某一階段出發位置的狀態，它既是上一階段的輸出又是本階段的輸入，並用向量xk表示第k階段的狀態，稱為狀態變數。

（3）決策:指給定k階段的狀態後,從該狀態轉移到下一階段某一狀態的選擇。用Uk表示第k階段當狀態處於Xk時的決策變數。對於系統的每一個狀態，都可以從若干種可能的決策（或控制）中任選一種。選定決策並加以實施，即可引起系統狀態的變化。系統的下一階段狀態由現在的狀態和決策確定，與過去的歷史無關，即系統是無記憶的。

（4）策略：由過程中每一階段所選決策構成的整個序列，又稱為方案。

（5）目標函式：策略的目標是使狀態變數的某個特定函式的值為最大（或最小）。這個特定函式就是目標函式。使目標函式值為最大（或最小）的策略稱為最優策略。圖1中求最短路徑的例子說明了多段決策過程及其構成要素。圖中S是出發點，G是目的地，各邊上的數字表示兩點間的距離。求從S到G的最短路徑和距離數。首先，可將圖1劃分成四個階段，然後逆向依次尋求使總的距離為最小的最短路徑。先從第一階段開始,從C1到G只有一條路線,同樣從C2到G也只有一條路線。到了第二階段，從B1到G有經過C1或C2兩條路線，經選擇後由B1經C2到G距離最小。如此繼續進行下去，就把一個最短路徑問題變成了多段決策問題（圖2）。最後求得最短路徑為SA2B1C2G。

基本原理

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

最優化原理

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

嵌入原理

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

貝爾曼方程

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

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

表示以xk+1為初始狀態的後N-(k+1)段分過程的最優效能目標，xk+1=f(xk，uk)是基於第k段的狀態 xk和決策uk而得到的第k+1段的狀態向量，

[·]表示選擇決策uk使[·]取極小值。這是一個逆向遞推方程。採用迭代法按k=N-1,N-2,…,1,0順序求解貝爾曼方程，即可得到N段決策過程的最優策略{uk，k=0,2,N-1}和最優軌線{xk，k=0,N },而最優效能值為J壨(x0)。

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

經迭代計算後，得

………………………

這就是所求的最短距離。從S到G的最短路徑是SA2B1C2G。而A2B1C2G，B1C2G，C2G 則分別是從A2，B1,C2到G 的最短路徑。

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

特點和應用範圍

若多階段決策過程為連續型，則動態規劃與變分法處理的問題有共同之處。動態規劃原理可用來將變分法問題歸結為多階段決策過程，用動態規劃的貝爾曼方程求解。在最優控制理論中動態規劃方法比極大值原理更為適用。但動態規劃還缺少嚴格的邏輯基礎。60年代，В．Г．沃爾昌斯基對動態規劃方法作了數學論證。動態規劃方法有五個特點：

（1）在策略變數較多時，與策略窮舉法相比可降低維數；

（2）在給定的定義域或限制條件下很難用微分方法求極值的函式，可用動態規劃方法求極值；

（3）對於不能用解析形式表達的函式,可給出遞推關係求數值解；

（4）動態規劃方法可以解決古典方法不能處理的問題，如兩點邊值問題和隱變分問題等；

（5）許多數學規劃問題均可用動態規劃方法來解決，例如，含有隨時間或空間變化的因素的經濟問題。投資問題、庫存問題、生產計劃、資源分配、裝置更新、最優搜尋、馬爾可夫決策過程，以及最優控制和自適應控制等問題，均可用動態規劃方法來處理。

參考書目

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

S.E. Dreyfus，DynamicProgrammingandthe 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.