動態規劃（動態模擬 Programming，DP）是分析解決多階段決策過程最優化問題的一種方法。它主要求解以時間化分階段的動態過程的優化問題，對于靜態問題，也可以用它來解決。動態規劃是考察問題的一種途徑，而不是具體的算法。
動態規劃起源于20世紀40年代人們對于水利資源多級分配、庫存多級存儲等問題的研究，美國數學家理查德·貝爾曼（R.Bellman）逐漸發現了多階段決策問題的背后結構，并指出逆序歸納法到底是如何求解多階段決策問題的。1949年，他提出了著名的最優化原理（principle of optimality），次年，貝爾曼經過反復斟酌確定了“動態規劃”這一名稱。1957年，貝爾曼出版了他的書籍《動態規劃》（Dynamic Programming），并在1961年、1962年相繼再版此書，進一步闡明了動態規劃的理論和方法。
動態規劃有求解更容易、效率更高等優勢，但是，它也存在著應用條件苛刻、通用性不足的限制。動態規劃的求解常用到階段、狀態、決策、策略、效果函數等一系列基本概念，一般步驟可分為6步，核心思路為構建基本方程。動態規劃具有順序解法、逆序解法等基本求解方法。
動態規劃的常見類型有多維動態規劃、隨機動態規劃。變分法是另一種求最優結果的方法，對于復雜的變分問題，也可以利用動態中華人民共和國城鄉規劃法進行求解。動態規劃問題有許多經典的案例，如背包問題、機器負荷分配問題。動態規劃在現實世界的許多領域得到了廣泛的應用，例如生產調度、資源分配、設備更新、信息處理、模式識別等，成為了運籌學中的活躍分支。
定義
動態規劃是分析解決多階段決策過程最優化問題的一種方法，為運籌學的一個重要分支。而多階段決策是指這樣一類特殊的活動過程，它們可以按時間順序分解成若干相互聯系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題。動態規劃主要求解以時間化分階段的動態過程的優化問題，對于靜態問題，也可以它來解決。它是考察問題的一種途徑，而不是具體的算法。
歷史
20世紀40年代，人們開始研究水力資源的多級分配和庫存的多級存儲問題。美國數學家理查德·貝爾曼（R.Bellman）逐漸發現了多階段決策問題的背后結構，并指出逆序歸納法到底是如何求解多階段決策問題的。1949年，他提出了著名的最優化原理（principle of optimality），即把多階段過程轉化為一系列單階段問題，利用各階段之間的關系逐個求解，開始了動態規劃的研究。1950年，他經過反復斟酌確定了“動態規劃”這一名稱。1957年，貝爾曼出版了他的書籍《動態規劃》（Dynamic Programming），并在1961年、1962年相繼出版第2版和第3版，進一步闡明了動態規劃的理論和方法。
特性
優點
（1）求解更容易、效率更高。動態規劃方法是一種逐步改善法，它把原問題化成一系列結構相似的最優化子問題，而每個子問題的變量個數比原問題少得多，約束集合也簡單得多，故比較易于確定最優解。
（2）解的信息更豐富。非線性規劃（或線性規劃）的方法是對問題的整體進行一次性求解的，因此只能得到全過程的解；而動態規劃方法是將過程分解成多個階段進行求解的，因此不僅可以得到全過程的解，還可以得到所有子過程的解。
（3）對于處理變量為整數的最優化問題有特別的功效。相反，變量的某些約束，例如整數或非負等，對于其他優化技術的應用都將產生困難。實質上，所有其他優化技術，各類約束都能引出嚴重的麻煩問題。例如，對問題變量加上只能取整數的限制，就不能用經典的方法來解決。然而，在動態規劃中，要求某些或全部變量為整數，還將大大地簡化計算過程。
（4）確定出絕對（全局）極大或極小，而不是相對（局部）的極值。這一點幾乎超過了所有現存的計算方法，特別是經典最優化方法。
局限性
（1）沒有一個統一的標準模型。由于實際問題不同，其動態規劃模型也各有差異，模型構建存在一定困難。
（2）應用條件苛刻、通用性不足。由于構造動態規劃模型狀態變量必須滿足“無后效性”條件，這一條件不僅依賴于狀態轉移律，還依賴于允許決策集合和指標函數的結構，不少實際問題在取其自然特征作為狀態變量時并不滿足這一條件，這就降低了動態規劃的通用性。
（3）狀態變量存在“維數障礙”。最優指標函數是狀態變量的函數，當狀態變量的維數增加時，最優指標函數的計算量將成指數倍增長，因此無論是手工計算還是電算，“維數障礙”都是無法完全克服的。
相關概念
階段
階段：對整個過程的自然劃分。通常根據時間順序或空間順序特征來劃分階段，以便按階段的次序解優化問題。
階段變量一般用表示。由于在求解多階段決策問題時，一般采用反向遞推，所以階段的編號也是逆向的，也可以正向遞推。
狀態
狀態：描述了研究過程所處的狀況，即每一階段開始時所處的狀態。在最短路徑問題中，狀態既是某一階段某一支路的始點，又是下一階段某一支路的終點。通常，一個階段有一個或若干個狀態。動態規劃中的狀態必須滿足無后效性，它是指如果某一階段的狀態給定后，則在這階段以后過程的發展不受這階段以前各狀態的影響。也就是說，過去的歷史只能通過當前的狀態去影響它未來的發展，當前的狀態是以往歷史的全部總結。
描述狀態的變量稱為狀態變量。狀態變量允許取值的范圍稱作允許狀態集合。用表示第階段的狀態變量它可以是一個數或一個向量。用表示第階段的允許狀態集合。個階段的決策過程有個狀態變量，表示演變的結果。根據過程演變的具體情況，狀態變量可以是離散的或連續的。為了計算的方便，有時將連續變量離散化；為了分析的方便，有時又將離散變量視為連續的。
決策
決策：當多階段決策過程處于某一階段某一狀態時，可以作出不同的決定，從而決定下一階段的狀態，這種決定稱為決策。
描述決策狀態的變量為決策變量，某一階段某一狀態所作出的決策用決策變量表示，第階段狀態的允許決策集合用表示，第階段各狀態的允許決策集合用表示，所有各階段各狀態的允許決策集合用表示，則有。
策略
策略：按順序排列的決策組合的集合，通常指某一階段某一狀態到終點的順序排列的決策組合的集合。
用表示從第階段狀態出發到終點的一個子策略。從第階段狀態出發到終點的允許策略集合為，則。
狀態轉移方程
狀態轉移方程：表示從某一階段某一狀態到下一個階段另一狀態的演變過程。它反映相鄰兩個階段的狀態和決策變量之間的相互關系。如果給定某一階段的某一狀態及其在該狀態下的決策變量，就可以確定下一階段的某一特定狀態（按逆向劃分階段）。這種相鄰兩個階段的狀態轉移關系稱為狀態轉移方程，記為：。
效果函數
直接效果函數：表示在某一階段某一狀態下，采取某一決策后到下一階段某一狀態的直接效果值。它是狀態變量和決策變量的函數，記為：。
總效果（指標）函數：表示在某一階段某一狀態下，采取某一策略后到終點的總效果值。它是狀態變量和一系列決策變量的函數，即為從第階段狀態出發到終點的子策略的函數，記為：。
最優效果（指標）函數：表示在某一階段某一狀態下，采取最優策略后到終點的最優效果值。
記為：，其中 是最優化“最優化”的縮寫。
方法模型
最優化原理
最優化原理可以表述為：“一個過程的最優策略具有這樣的性質，即無論初始狀態和初始決策如何，對于先前決策所形成的狀態而言，其以后的所有決策必構成最優策略。”
例如，將這一基本原理應用于最短路線問題時可表述為：一方面，一條路線如果是最短路線，則對于該線上的任何一點來說，最短路線以此點為起點的剩余部分，必然是從此點到終點的最短路線；另一方面，無論是從哪一階段的哪一種狀態出發，到終點的最短路線只與此狀態有關，而與以前的狀態路線無關，即并不受從點是如何到達這點的決策的影響。
最優化原理可以用反證法來證明。假定是由始點到終點的最短路線上的一點，如果存在另一條最短路將與終點相連，則這條最短路線與以前的部分必構成全程的最短路線，這就與原策略為最短路線的假定相矛盾。所以，對于一個過程的最優策略而言，不管其初始狀態和決策如何，其后的任一決策都構成最優策略。這也是動態規劃可以采用逆序遞推法尋優的依據。
基本方程
作為整個過程的最優策略具有這樣的性質：即無論過去的狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。作為全過程的最優策略，其后部子策略也必須是最優的。因此，動態規劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結合起來考慮的一種方法。
動態規劃基本方程式為：
其中可根據題意而取或。稱為階段指標函數，它是由狀態和決策變量確定的，在不同的問題中，階段指標函數的含義是不同的，它可能是距離、利潤、成本、產品的產量或資源消耗等。則稱為最優指標函數，它表示從第階段的起到終點為止的最短距離、最大利潤或最低成本等。是將階段的指標與子過程的最優指標聚合起來的運算，對每一個來說，可以取不同的運算，但在大多數實際問題中，一般是全取加法或全取乘法。在動態規劃的基本方程中，由于狀態轉移的無后效性，所以，該式被稱為狀態轉移律或狀態轉移方程，其具體形式由具體問題而決定。基本方程中的遞推關系式中并不是新的自變量，只有為自變量。
求解步驟
（1）將實際問題的全過程根據時間或空間順序恰當地劃分成若干階段，用表示階段變量。一個階段表示需要作出一次決策的子問題，各子問題應具有同一模式。
（2）正確選擇狀態變量，使它既能描述過程的狀態演變特征，又要滿足無后效性。同時，還必須具有可知性，即，規定的各階段狀態變量的值，通過直接或間接的方式可以得知。
（3）確定決策變量、允許決策集合和相鄰兩階段的狀態轉移律：。
（4）根據題意寫出總效果（指標）函數以及最優效果（指標）函數。
（6）根據問題的各種性質，結合其他數學技巧，求解方程。
基本解法
動態的求解方法多樣。順序解法和逆序解法為兩種基本方法，順序解法的尋優方向與過程的行進方向相同，逆序解法的方向相反。此外，一些決策問題中，階段變量不易確定，可考慮更一般的方法——函數迭代法。而滿足同一種條件決策過程的方法還有策略迭代法。
順推解法
順推解法：由前向后推算最優解的方法。運用順推法求解時，需根據實際決策從最初階段開始，即邊界條件從開始，由前向后進行順推，逐步求得各個階段的最優決策和相應的最優值，最后求得最優后部指標即最后階段的最優指標，從而得到整個問題的最優解。
該方法的基本方程為：
或寫成：
順推法的求解過程就是根據邊界條件，從開始由前向后進行順推，根據基本方程求出各個階段的，最后求得的就是整個動態規劃問題的最優解。
逆推解法
逆推法：由后向前推算最優解的方法。運用逆推法求解時，需根據實際決策從最后階段開始，即邊界條件從開始，由后向前進行逆推，逐步求得各個階段的最優決策和相應的最優值，最后求得最優后部指標即最初階段的最優指標，從而得到整個問題的最優解。
該方法的基本方程為：
或寫成：
逆推法的求解過程就是根據邊界條件，從開始，由后向前進行逆推，根據基本方程求出各個階段的，最后求得的就是整個動態規劃問題的最優解。
函數迭代法
另一類動態規劃問題的階段數目是不能事先予定的，而要通過最優指標函數值的計算來確定，其最優策略是由個最優決策組成的，因此也要通過最優指標函數值的計算來確定。這種動態規劃問題，一般叫做確定性不定期決策過程最優化問題，可以使用函數迭代法和策略迭代法來求解。
問題：設有個點。任意兩點，之間有一弧連結，其長度為（可以代表距離、費用等），，其中表示和之間沒有連結弧，試求任一點到的最短路線。
設表示點到點的最短矩離，則由最優化原理可列出基本方程：
函數迭代法：基本思想是以階段數作為參數，先求不同參數下的最優解（值），再從這些最優解中選出最優者，從而確定了最優階段數，更進一步講，從到的步數雖然不定，但不會超過步，否則將會出現回路，不是最短路。每一條從到的步最短路都可以求出。令，就可以求出所有最短路，把它們加以比較，從中選出最優者，最后確定了最優階段數（步數）和最優策略及最短路。迭代步驟可具體為：設表示從開始，經過步到的最短距離，所以時有：
按下列遞推關系求。
當時，停止迭代。這時滿足，且不超過。
策略迭代法
策略迭代法：基本思想是先給出初始策略（即），然后按某種方法求出新策略直至求出最優策略。若對某一，對所有成立，則稱策略收斂，而且就是最優策略，這里的表示第步從出發應該到達的下一點。由可以計算出從到的距離，根據距離修改策略，直至求出最優策略。
迭代步驟：
（1）選擇一個沒有回路的初始策略。
（2）由策略求出指標函數，即由方程組
解出，其中為已知。
（3）由求。
就是使取最小值的那個，即它是的解。
（4）按（2）、（3）步反復迭代，直至時，就是最優策略，記作。
常見類型
多維動態規劃
多維動態規劃：有個或個以上的狀態變量，或者在每一階段要選擇個或個以上的決策變量的動態規劃模型。當動態規劃維數超過維時，所需計算機的存貯量和計算量太大，常無法求解，所以，各種改進算法被相繼提出，如：動態規劃逐次逼進法、狀態增量動態規劃、導數動態規則、離散微分動態規劃等。
例如：設有兩種原料，數量分別為和，需要用于生產種產品，對第種產品來說，當使用第一種原料數為，使用第二種原料數為時，其收益為。需要尋求一個最佳策略，即如何分配這兩種原料于種產品才能使總收益為最大。
求解思路：如果用線性規劃求解，則其數學模型為：
在約束條件
下使目標函數為最大，可以看出，它有兩個約束條件，如果用動態規劃方法求解，其狀態變量和決策變量都是二維的。
設級的輸入狀態變量為，表示分配用于生產第種產品到第種產品的第一種原料總數量，表示分配用于生產第種產品到第種產品的第二種原料總數量，級的決策變量為。因此有狀態傳遞方程為：
由最優化原理，可以建立動態規劃遞推方程為：
。
隨機動態規劃
隨機動態規劃：如果一個動態規劃的狀態轉移律是不確定的，即對給定的狀態和策略，下一階段的狀態不是確定的，而是一個已知概率分布的隨機變量，那么這個動態規劃稱為隨機動態規劃。在隨機動態規劃中，由于下一階段的狀態不確定，只能根據各階段的期望值進行優化處理。
這時，基本方程應表示為：
。
例如：某科研單位為某廠承擔一種新產品試制任務，雙方簽訂的合同規定須在三個月內由科研部門向廠方交出一臺合格樣品，否則應向廠方交付元的賠償費。該科研單位的已有資科表明，進行試制時合格的概率為，并知投產一批的固定成本為元，而每臺產品的試制費用為元。若投產一批后均不合格，可繼續試制，但每投產試制一批的周期為一個月。廠方已按合同付給研究單位一筆費用。問：研究單位應確定怎樣一個試制計劃，可使總的研制費用的期望值最小。
求解思路：可按一月為一個階段把整個合同期分為三個階段，分別以表示。設狀態變量為，并且假定尚沒有一臺合格品產生時為，至少得到一臺合格品時為 。決策變量設為，它表示第批投產試制臺新產品。這樣，充許決策集合當時為，當時。于是，狀態轉移律是以如下分布表示的隨機變量,。以表示第階段的研制費用支出，則。用表示第階段以后的總研制費用的最小期望值，則有，于是可以建立如下基本方程：
。
類似理論
變分法
變分法是另一種求最優結果的方法，它與動態規劃之間有明顯的差別。用變分法時，最優函數（極值）是滿足邊界條件的一個或多個微分方程的確定解，不需逐點計算，而是一次求得，或者用近似解的序列逼近總函數。用動態規劃方法時，不是一次就求出整個最優函數，而是逐點移動，沿著極值曲線，從前一個點加上已知導數情況，計算下一個點。盡管有這些差別，兩種方法之間是有著密切聯系的。事實上，變分問題的解，常常是難以求得的，存在很多實際困難，常通過動態規劃的思想進行求解。
聯系
性能指標函數為：
求滿足式的約束條件，使為最小的，可采用求最優化方法引入輔助變量（或稱約瑟夫·拉格朗日乘子），構造新泛函，然后求新泛函的無條件極值，得到的歐拉方程為
變分法求最優控制的必要條件是歐拉方程。在動態規劃哈密頓一卡爾·雅可比方程中的，與經典變分法中求最優化引入的輔助變量是相對應的。所以，動態規劃是最優問題的一種現代變分法，它包含了經典變分法的內容。
案例分析
動態規劃主要求解多決策過程的最優化問題，包括最短路線問題、資源分配問題、生產—庫存問題等經典案例。其中，確定性的定期多階段決策問題包括旅行售貨員問題、多階段生產分配問題、可靠性問題；確定性的不定期多階段決策問題包括最優線路問題、有限資源分配問題。目前，動態規劃在現實世界的許多領域得到了廣泛的應用，例如生產調度、資源分配、設備更新、工業控制和多級工藝設備的優化設計以及信息處理、模式識別等，成為了運籌學中的活躍分支。
背包問題
背包問題是一個經典的最優化問題，即原問題的最優解一定包含子問題的最優解，下面可以遞歸地定義最優解的值。
問題：對于每個物品，可以有兩個選擇，放入或者不放入背包，有個物品，故而需要做出個選擇。設表示做出第次選擇后，所選物品放入一個容量為的背包獲得的最大價值，其中表示第件物品的重量，表示第件物品的價值。對于第件物品，有兩種選擇，放或者不放。
（1）如果放入第件物品，則。這表示，前次選擇后，所選物品放入容量為的背包所獲得的最大價值為，加上當前所選的第個物品的價值即為。
（2）如果不放入第件物品，則有，這表示當不選第件物品時，就轉化為前次選擇后所選物品占容量為時的最大價值為。
綜上所述，。
機器負荷分配問題
問題：設有某種機器，可以在高、低兩種不同的負荷下進行生產，產量函數分別為，機器的年折損完好率分別為和。假定，開始生產時，完好的機器數量為，要求制定一個年生產計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同負荷下生產的數量，使在年內產品的總產量達到最高。這就是機器負荷分配問題，也可以看作是帶回收的資源分配問題。
解：將問題劃分為個階段，每一年為一個階段，。狀態變量選為第階段初擁有的完好機器數，顯然。決策變量選為第階段安排在高負荷下生產的機器數，則第階段在低負荷下生產的機器數為，決策變量的約束條件是：。由于在高負荷下生產的機器年折損完好率是，在低負荷下生產的機器年折損完好率是，因此，狀態轉移方程是：。階段指標函數即為階段產量。若用表示由出發采用最優分配方案到結束時這段期間的產品產量，則有：
。
最短路線問題
最短路線問題是指給定始點及終點，并知道由始點到終點的各種可能的途徑，問題是要找一條由始點到終點的最短的路線。例如，運輸部門要選擇一條費用最低的運輸路線；建筑公司要輔設一條使兩點之間總距離最短的公路；旅行者希望找到一條由出發地至目的地的距離最短的行進路線等。而且，有些與運輸根本沒有關系的問題也可以化為求最短路線的模型，用動態規劃方法來求解。
問題：如下圖所示，給定一個線路網絡，兩點之間連線上的數字表示兩點間的距離（或費用），試求一條由到的鋪管線路，使總距離為最短（或總費用最小）。
解：由圖可知，從點到點可以分為個階段。從到為第一階段，從到為第二階段，從到為第三階段，從到為第四階段。在第一階段，為起點，終點有、、三個，因而這時走的路線有三個選擇，一是走到，二是走到，三是走到。若選擇走到，則就是在第一階段的決策結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，從點出發，對應于點就有一個可供選擇的終點集合，若選擇由走至，則就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可以看到：各個階段的決策不同，鋪管路線就不同。當某階段的始點給定時，它直接影響著后面各階段的行進路線和整個路線的長短，而后面各階段的路線的發展不受這點以前各階段路線的影響。對于這樣的問題，可以用窮舉法來解決。即把由到所有可能的每一條路線的距離都算出來，然后互相比較找出最短者，相應地可以得出最短路線。這樣，由到的個階段中，若第一階段選擇，則一共有條不同的路線，若第一階段選擇或，則一共有條不同的路線，比較這些不同路線的距離值，就可以找出最短路線為：，相應最短距離為。
參考資料 >
什么是動態規劃(Dynamic Programming)?動態規劃的意義是什么?.CSDN博客.2024-04-16