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

動(dòng)態(tài)規(guī)劃(Dynamicprogramming)動(dòng)態(tài)規(guī)劃的根本思想最短路徑問(wèn)題投資分配問(wèn)題背包問(wèn)題?動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法。由美國(guó)數(shù)學(xué)家貝爾曼〔Ballman〕等人在20世紀(jì)50年代提出。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類問(wèn)題的“最優(yōu)化原理〞，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多實(shí)際問(wèn)題。?動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)方案和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。?動(dòng)態(tài)規(guī)劃模型的分類：以“時(shí)間〞角度可分成：離散型和連續(xù)型。從信息確定與否可分成：確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成：?jiǎn)文繕?biāo)型和多目標(biāo)型。?7-1動(dòng)態(tài)規(guī)劃的根本原理多階段決策過(guò)程最優(yōu)化多階段決策過(guò)程是指這樣一類特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成假設(shè)干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱為序貫決策問(wèn)題。?例7-1生產(chǎn)與存儲(chǔ)問(wèn)題某工廠每月需供給市場(chǎng)一定數(shù)量的產(chǎn)品。供給需求所剩余產(chǎn)品應(yīng)存入倉(cāng)庫(kù)，一般地說(shuō)，某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)本錢(qián)，但超產(chǎn)局部存入倉(cāng)庫(kù)會(huì)增加庫(kù)存費(fèi)用，要確定一個(gè)每月的生產(chǎn)方案，在滿足需求條件下，使一年的生產(chǎn)與存儲(chǔ)費(fèi)用之和最小。?例7-2投資決策問(wèn)題某公司現(xiàn)有資金Q億元，在今后5年內(nèi)考慮給A、B、C、D四個(gè)工程投資，這些工程的投資期限、回報(bào)率均不一樣，問(wèn)應(yīng)如何確定這些工程每年的投資額，使到第五年末擁有資金的本利總額最大。?例7-3設(shè)備更新問(wèn)題企業(yè)在使用設(shè)備時(shí)都要考慮設(shè)備的更新問(wèn)題，因?yàn)樵O(shè)備越陳舊所需的維修費(fèi)用越多，但購(gòu)置新設(shè)備那么要一次性支出較大的費(fèi)用。?現(xiàn)在某企業(yè)要決定一臺(tái)設(shè)備未來(lái)8年的更新方案，已預(yù)測(cè)到第j年購(gòu)置設(shè)備的價(jià)格為Kj，Gj為設(shè)備經(jīng)過(guò)j年后的殘值，Cj為設(shè)備連續(xù)使用j-1年后在第j年的維修費(fèi)用(j=1,2…8)，問(wèn)應(yīng)在哪年更新設(shè)備可使總費(fèi)用最小。?動(dòng)態(tài)規(guī)劃的根本概念階段；狀態(tài)；決策和策略；狀態(tài)轉(zhuǎn)移；指標(biāo)函數(shù)。?例7-4〔不定階段最短路線問(wèn)題〕如圖是一個(gè)五座城市的及其相連道路的交通圖，線上的數(shù)字是對(duì)應(yīng)的路長(zhǎng)。問(wèn)：應(yīng)如何選擇行駛路線，才能使從A、B、C、D各城市到E城市的行駛路程最短？?AEDCB252755610.53?從圖中可以看出，任意兩座城市之間都有道路相通。我們把從一座城市直達(dá)另一座城市作為一個(gè)階段。例從A城市到E城市的階段數(shù)，少那么一個(gè)〔例從A城市直達(dá)E城市〕，多那么無(wú)限〔例從A城市通過(guò)其他B、C、D三城市循環(huán)到E城市〕。為防止循環(huán)，加上約束條件：每個(gè)城市至多經(jīng)過(guò)一次。?于是從A城市到達(dá)E城市的階段數(shù)有以下四種情形：1.從A城市直達(dá)E城市，一個(gè)階段。?于是從A城市到達(dá)E城市的階段數(shù)有以下四種情形：1.從A城市直達(dá)E城市，一個(gè)階段。2.從A城市通過(guò)其他B、C、D三城市之一到E城市，二個(gè)階段。?于是從A城市到達(dá)E城市的階段數(shù)有以下四種情形：3.從A城市通過(guò)其他B、C、D三城市之二到E城市，三個(gè)階段。?于是從A城市到達(dá)E城市的階段數(shù)有以下四種情形：3.從A城市通過(guò)其他B、C、D三城市之二到E城市，三個(gè)階段。4.從A城市通過(guò)其他B、C、D三城市各一次到E城市，四個(gè)階段。?例7-5〔一定階段最短路問(wèn)題〕W先生每天駕車去公司上班。如圖，W先生的住所位于A，公司位于F，圖中的直線段代表公路，穿插點(diǎn)代表路口，直線段上的數(shù)字代表兩路口之間的平均行駛時(shí)間?，F(xiàn)在W先生的問(wèn)題是要確定一條最省時(shí)的上班路線。?A3B14C13D14532B22C23D2E11234C34D35E22F?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?1階段〔Stage〕將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成假設(shè)干個(gè)相互聯(lián)系的階段，以便按次序去求每階段的解，常用k表示階段變量。我們把從A到F看成一個(gè)五階段問(wèn)題。?2狀態(tài)〔State〕各階段開(kāi)場(chǎng)時(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)給定以后，在這階段以后的過(guò)程的開(kāi)展不受這段以前各段狀態(tài)的影響。即：過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前狀態(tài)去影響它未來(lái)的開(kāi)展，這稱為無(wú)后效性。如果所選定的變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃模型。?3決策和策略〔DecisionandPolicy〕當(dāng)各段的狀態(tài)確定以后，就可以做出不同的決定〔或選擇〕，從而確定下一階段的狀態(tài)，這種決定稱為決策。決策變量用dk(Sk)表示，允許決策集合用Dk(Sk)表示。?各個(gè)階段決策確定后，整個(gè)問(wèn)題的決策序列就構(gòu)成一個(gè)策略，用p1,n(d1,d2,…dn)表示。對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定的范圍，稱為允許策略集合，用P表示。使整個(gè)問(wèn)題到達(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ī)劃的根本思想：從過(guò)程的最后一段開(kāi)場(chǎng)，用逆序遞推方法求解，逐步求出各段各點(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)=E1?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?如果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)=E2?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?如果S4=D3，那么下一步只能取E2，故f4(D3)=r(D3,E2)+f5(E2)=5+2=7最短路線：D3——E2——F最優(yōu)解：d4*(D3)=E2?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF??當(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)=D2?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?如果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)=D2?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?如果S3=C3，那么下一步只能取D3，故f3(C3)=r(C3,D3)+f4(D3)=〔4+7〕=11最短路線：C3——D3——E2——F最優(yōu)解：d3*(C3)=D3?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF??當(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)=C1?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?如果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)=C2?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF??當(dāng)K=1時(shí)，五個(gè)階段的原問(wèn)題，初始狀態(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.?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF??AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?AB1B2C1C2C3D1D2D3E1E2F41544445333332222ABCDEF?動(dòng)態(tài)規(guī)劃的函數(shù)方程〔DP〕建立DP函數(shù)方程是指確定過(guò)程的階段及階段數(shù)，規(guī)定狀態(tài)變量