動(dòng)態(tài)規(guī)劃相關(guān)知識(shí)

動(dòng)態(tài)規(guī)劃(Dynamicprogramming)動(dòng)態(tài)規(guī)劃的基本思想最短路徑問題投資分配問題背包問題

動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。由美國(guó)數(shù)學(xué)家貝爾曼（Ballman）等人在20世紀(jì)50年代提出。他們針對(duì)多階段決策問題的特點(diǎn)，提出了解決這類問題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問題。動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問題、資源分配問題、生產(chǎn)計(jì)劃和庫存問題、投資問題、裝載問題、排序問題及生產(chǎn)過程的最優(yōu)控制等。動(dòng)態(tài)規(guī)劃模型的分類：以“時(shí)間”角度可分成：

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

確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成：

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

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

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

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

動(dòng)態(tài)規(guī)劃中的狀態(tài)具有如下性質(zhì)：

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

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

各個(gè)階段決策確定后，整個(gè)問題的決策序列就構(gòu)成一個(gè)策略，用p1,n(d1,d2,…dn)表示。對(duì)每個(gè)實(shí)際問題，可供選擇的策略有一定的范圍，稱為允許策略集合，用P表示。使整個(gè)問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。4狀態(tài)轉(zhuǎn)移方程

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

Sk，dk）確定，稱為狀態(tài)轉(zhuǎn)移方程。5指標(biāo)函數(shù)

用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)。最優(yōu)指標(biāo)函數(shù)記為fk(Sk)。

動(dòng)態(tài)規(guī)劃的基本思想：

從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)E最短路線，最后求出A點(diǎn)到E點(diǎn)的最短路線。AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當(dāng)K=5時(shí)，此時(shí)d5(S5)=F，其初始狀態(tài)E1或E2，故f5(E1)=4,f5(E2)=2用d5*(S5)表示最優(yōu)決策。AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當(dāng)K=4時(shí)，有兩個(gè)階段，初始狀態(tài)S4可以是D1、D2或D3。如果S4=D1，則下一步只能取E1，故f4(D1)=r(D1,E1)+f5(E1)=2+4=6最短路線：D1——E1——F最優(yōu)解：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最優(yōu)解：d4*(D2)=E2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S4=D3，則下一步只能取E2，故f4(D3)=r(D3,E2)+f5(E2)=5+2=7最短路線：D3——E2——F最優(yōu)解：d4*(D3)=E2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當(dāng)K=3時(shí)，還有三個(gè)階段，初始狀態(tài)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最優(yōu)解：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最優(yōu)解：d3*(C2)=D2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF如果S3=C3，則下一步只能取D3，故f3(C3)=r(C3,D3)+f4(D3)=（4+7）=11最短路線：C3——D3——E2——F最優(yōu)解：d3*(C3)=D3AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當(dāng)K=2時(shí)，還有四個(gè)階段，初始狀態(tài)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最優(yōu)解：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最優(yōu)解：d2*(B2)=C2AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF當(dāng)K=1時(shí)，五個(gè)階段的原問題，初始狀態(tài)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最優(yōu)解：d1*(A)=B2，最短用時(shí)14.AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF動(dòng)態(tài)規(guī)劃的函數(shù)方程（DP）

建立DP函數(shù)方程是指確定過程的階段及階段數(shù)，規(guī)定狀態(tài)變量和決策變量的取法，給出各階段的狀態(tài)集合，允許決策集合，狀態(tài)轉(zhuǎn)移方程和指標(biāo)函數(shù)等。在上面的計(jì)算過程中，利用了第k階段與第k+1階段的關(guān)系：fk(Sk)=Minr(Sk,dk(Sk))+fk+1(Sk+1)

dk(Sk)k=1,2,3,4,5f6(S6)=0

這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。貝爾曼(Ballman)最優(yōu)化原理

作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)，即無論過去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。這就是說，不管引導(dǎo)到這個(gè)現(xiàn)時(shí)狀態(tài)的頭一個(gè)狀態(tài)和決策是什么，所有的未來決策應(yīng)是最優(yōu)的。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問題化成N個(gè)一維優(yōu)化問題求解。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問題化成N個(gè)一維優(yōu)化問題求解。DP方程中附加某些約束條件，可使求解更加容易。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問題化成N個(gè)一維優(yōu)化問題求解。DP方程中附加某些約束條件，可使求解更加容易。求得最優(yōu)解以后，可得所有子問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒有統(tǒng)一處理方法。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒有統(tǒng)一處理方法。狀態(tài)變量維數(shù)不能太高，一般要求小于6。

謝謝大家！9、春去春又回，新桃換舊符。在那桃花盛開的地方，在這醉人芬芳的季節(jié)，愿你生活像春天一樣陽光，心情像桃花一樣美麗，日子像桃子一樣甜蜜。3月-253月-25Sunday,March9,2025