動態規劃(Dynamicprogramming)動態規劃的基本思想最短路徑問題投資分配問題背包問題

動態規劃是解決多階段決策過程最優化問題的一種方法。由美國數學家貝爾曼（Ballman）等人在20世紀50年代提出。他們針對多階段決策問題的特點，提出了解決這類問題的“最優化原理”，并成功地解決了生產管理、工程技術等方面的許多實際問題。動態規劃是現代企業管理中的一種重要決策方法，可用于最優路徑問題、資源分配問題、生產計劃和庫存問題、投資問題、裝載問題、排序問題及生產過程的最優控制等。動態規劃模型的分類：以“時間”角度可分成：

離散型和連續型。從信息確定與否可分成：

確定型和隨機型。從目標函數的個數可分成：

單目標型和多目標型。7-1動態規劃的基本原理多階段決策過程最優化多階段決策過程是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題。例7-1生產與存儲問題某工廠每月需供應市場一定數量的產品。供應需求所剩余產品應存入倉庫，一般地說，某月適當增加產量可降低生產成本，但超產部分存入倉庫會增加庫存費用，要確定一個每月的生產計劃，在滿足需求條件下，使一年的生產與存儲費用之和最小。例7-2投資決策問題某公司現有資金Q億元，在今后5年內考慮給A、B、C、D四個項目投資，這些項目的投資期限、回報率均不相同，問應如何確定這些項目每年的投資額，使到第五年末擁有資金的本利總額最大。例7-3設備更新問題企業在使用設備時都要考慮設備的更新問題，因為設備越陳舊所需的維修費用越多，但購買新設備則要一次性支出較大的費用?，F在某企業要決定一臺設備未來8年的更新計劃，已預測到第j年購買設備的價格為Kj，Gj為設備經過j年后的殘值，Cj為設備連續使用j-1年后在第j年的維修費用(j=1,2…8)，問應在哪年更新設備可使總費用最小。動態規劃的基本概念階段；狀態；決策和策略；狀態轉移；指標函數。例7-4（不定階段最短路線問題）如圖是一個五座城市的及其相連道路的交通圖，線上的數字是對應的路長。問：應如何選擇行駛路線，才能使從A、B、C、D各城市到E城市的行駛路程最短？AEDCB252755610.53從圖中可以看出，任意兩座城市之間都有道路相通。我們把從一座城市直達另一座城市作為一個階段。例從A城市到E城市的階段數，少則一個（例從A城市直達E城市），多則無限（例從A城市通過其他B、C、D三城市循環到E城市）。為避免循環，加上約束條件：每個城市至多經過一次。于是從A城市到達E城市的階段數有下列四種情形：1.從A城市直達E城市，一個階段。于是從A城市到達E城市的階段數有下列四種情形：1.從A城市直達E城市，一個階段。2.從A城市通過其他B、C、D三城市之一到E城市，二個階段。于是從A城市到達E城市的階段數有下列四種情形：3.從A城市通過其他B、C、D三城市之二到E城市，三個階段。于是從A城市到達E城市的階段數有下列四種情形：3.從A城市通過其他B、C、D三城市之二到E城市，三個階段。4.從A城市通過其他B、C、D三城市各一次到E城市，四個階段。例7-5（一定階段最短路問題）

W先生每天駕車去公司上班。如圖，W先生的住所位于A，公司位于F，圖中的直線段代表公路，交叉點代表路口，直線段上的數字代表兩路口之間的平均行駛時間?，F在W先生的問題是要確定一條最省時的上班路線。A3B14C13D14532B22C23D2E11234C34D35E22FAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF1階段（Stage）

將所給問題的過程，按時間或空間特征分解成若干個相互聯系的階段，以便按次序去求每階段的解，常用k表示階段變量。我們把從A到F看成一個五階段問題。2狀態（State）

各階段開始時的客觀條件叫做狀態。描述各階段狀態的變量稱為狀態變量，常用sk表示第k階段的狀態變量，狀態變量的取值集合稱為狀態集合，用Sk表示。

動態規劃中的狀態具有如下性質：

當某階段狀態給定以后，在這階段以后的過程的發展不受這段以前各段狀態的影響。即：過程的過去歷史只能通過當前狀態去影響它未來的發展，這稱為無后效性。如果所選定的變量不具備無后效性，就不能作為狀態變量來構造動態規劃模型。3決策和策略（DecisionandPolicy）

當各段的狀態確定以后，就可以做出不同的決定（或選擇），從而確定下一階段的狀態，這種決定稱為決策。決策變量用dk(Sk)表示，允許決策集合用Dk(Sk)表示。

各個階段決策確定后，整個問題的決策序列就構成一個策略，用p1,n(d1,d2,…dn)表示。對每個實際問題，可供選擇的策略有一定的范圍，稱為允許策略集合，用P表示。使整個問題達到最優效果的策略就是最優策略。4狀態轉移方程

動態規劃中本階段的狀態往往是上一階段的決策結果。如果給定了第k段的狀態Sk，本階段決策為dk(Sk)，則第k+1段的狀態Sk+1由公式：Sk+1=Tk（

Sk，dk）確定，稱為狀態轉移方程。5指標函數

用于衡量所選定策略優劣的數量指標稱為指標函數。最優指標函數記為fk(Sk)。

動態規劃的基本思想：

從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點E最短路線，最后求出A點到E點的最短路線。AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當K=5時，此時d5(S5)=F，其初始狀態E1或E2，故f5(E1)=4,f5(E2)=2用d5*(S5)表示最優決策。AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當K=4時，有兩個階段，初始狀態S4可以是D1、D2或D3。如果S4=D1，則下一步只能取E1，故f4(D1)=r(D1,E1)+f5(E1)=2+4=6最短路線：D1——E1——F最優解：d4*(D1)=E1AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S4=D2，則下一步能取E1或E2，故f4(D2)=Minr(D2,E1)+f5(E1)

r(D2,E2)+f5(E2)=Min（4+4，3+2）=5最短路線：D2——E2——F最優解：d4*(D2)=E2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S4=D3，則下一步只能取E2，故f4(D3)=r(D3,E2)+f5(E2)=5+2=7最短路線：D3——E2——F最優解：d4*(D3)=E2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當K=3時，還有三個階段，初始狀態S3可以是C1、C2或C3。如果S3=C1，則下一步能取D1或D2，故f3(C1)=Minr(C1,D1)+f4(D1)

r(C1,D2)+f4(D2)=Min（3+6，3+5）=8最短路線：C1——D2——E2——F最優解：d3*(C1)=D2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S3=C2，則下一步能取D2或D3，故f3(C2)=Minr(C2,D2)+f4(D2)r(C2,D3)+f4(D3)=Min（3+5，2+7）=8最短路線：C2——D2——E2——F最優解：d3*(C2)=D2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S3=C3，則下一步只能取D3，故f3(C3)=r(C3,D3)+f4(D3)=（4+7）=11最短路線：C3——D3——E2——F最優解：d3*(C3)=D3AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當K=2時，還有四個階段，初始狀態S2可以是B1或B2。如果S2=B1，則下一步能取C1或C2，故f2(B1)=Minr(B1,C1)+f3(C1)

r(B1,C2)+f3(C2)=Min（4+8，5+8）=12最短路線：B1——C1——D2——E2——F最優解：d2*(B1)=C1AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S2=B2，則下一步能取C2或C3，故f2(B2)=Minr(B2,C2)+f3(C2)

r(B2,C3)+f3(C3)=Min（2+8，1+11）=10最短路線：B2——C2——D2——E2——F最優解：d2*(B2)=C2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當K=1時，五個階段的原問題，初始狀態S1是A。則下一步能取B1或B2，故f1(A)=Minr(A,B1)+f2(B1)

r(A,B2)+f2(B2)=Min（3+12，4+10）=14最短路線：A——B2——C2——D2——E2——F最優解：d1*(A)=B2，最短用時14.AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF動態規劃的函數方程（DP）

建立DP函數方程是指確定過程的階段及階段數，規定狀態變量和