第8章動態(tài)規(guī)劃

動態(tài)規(guī)劃8.1多階段決策問題與動態(tài)規(guī)劃

8.2動態(tài)規(guī)劃的基本概念

8.3動態(tài)規(guī)劃的步驟

8.4動態(tài)規(guī)劃的應(yīng)用

1求解靜態(tài)規(guī)劃問題

2資源分配問題

3不確定性采購問題

4排序問題

動態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達到最優(yōu)。8.1多階段決策問題與動態(tài)規(guī)劃安全過河問題古代有3位商人各自帶了一個仆人外出來到了一個渡口,渡口只有一條小船每次只能乘2人,仆人私下約定只要岸上的仆人人數(shù)超過商人人數(shù),就可殺人越貨.但是過河的決策由商人制定.問商人如何安全的渡過河去?一、多階段決策問題1.時間階段的例子（機器負荷問題）

某廠有1000臺機器，現(xiàn)需作一個五年計劃，以決定每年安排多少臺機器投入高負荷生產(chǎn)（產(chǎn)量大但損耗也大）可使五年的總產(chǎn)量最大。12345S1=1000x1x2x5x4x3s5v1v2v3v4v5s2s3s48.1多階段決策問題與動態(tài)規(guī)劃2.空間階段的例子（最短路問題）

如圖為一線路網(wǎng)絡(luò)?，F(xiàn)要從A點鋪設(shè)一條管道到E點，圖中兩點間連線上數(shù)字表示兩點間距離。現(xiàn)需選一條由A到E的鋪管線路，使總距離最短。AEB1B2B3C1C2C3D1D229531225156468101312111410階段1階段2階段3階段4動態(tài)規(guī)劃解決問題的基本特征1.動態(tài)規(guī)劃一般解決最值（最優(yōu)，最大，最小，最長……）問題；2.動態(tài)規(guī)劃解決的問題一般是離散的，可以分解（劃分階段）的；3.動態(tài)規(guī)劃解決的問題必須包含最優(yōu)子結(jié)構(gòu)，即可以由（n－1）的最優(yōu)推導(dǎo)出n的最優(yōu)動態(tài)規(guī)劃模型的分類：以“時間”角度可分成：

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

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

單目標型和多目標型。1.基本概念階段（Stage）——分步求解的過程，用階段變量k表示，k=1，，n狀態(tài)（State）——每階段初可能的情形或位置，用狀態(tài)變量Sk表示。

按狀態(tài)的取值是離散或連續(xù)，將動態(tài)規(guī)劃問題分為離散型和連續(xù)型。決策（

Decision）——每階段狀態(tài)確定后的抉擇，即從該狀態(tài)演變到下階段某狀態(tài)的選擇，用決策變量xk表示。狀態(tài)轉(zhuǎn)移——由Sk轉(zhuǎn)變?yōu)镾k+1的規(guī)律，記Sk+1=T(Sk，xk)。策略（

Policy）——由各階段決策組成的序列，記P1n={x1，…，xn}，

稱Pkn={xk，…，xn}為階段k至n的后部子策略。

8.2

基本概念與方程當(dāng)前狀態(tài)以前狀態(tài)決策顯然,從上圖可以看出,當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。KSkSk+1XkVk過河:決策向量xk(I,J)初始狀態(tài)s1是T(3,3)結(jié)束狀態(tài)sn是T(0,0)可達狀態(tài)有哪些?(3,J)(2,2)(1,1)(0,J)0321123AJII表示留在左岸的商人人數(shù)J表示留在左岸的仆人人數(shù)階段指標——每階段選定決策xk后所產(chǎn)生的效益，記

vk=vk(Sk，xk)。指標函數(shù)——各階段的總效益，記相應(yīng)于Pkn的指標函數(shù)為vkn=vkn(Sk，Pkn)。其中最優(yōu)的稱最優(yōu)指標函數(shù)，記fk=fk（Sk

）=optvkn。問題：動態(tài)規(guī)劃的最優(yōu)解和最優(yōu)值各是什么？——最優(yōu)解：最優(yōu)策略P1n

，

最優(yōu)值：最優(yōu)指標f1。多階段決策過程

d1d2dNs1s2s3

sNsN+112N

V1V2VN

N階段決策系統(tǒng)示意圖2.基本原理與基本方程（1）基本原理以最短路為例說明（2）基本方程根據(jù)最優(yōu)性原理，可建立從后向前逆推求解的遞推公式——基本方程：通常動態(tài)規(guī)劃問題的最優(yōu)值函數(shù)滿足遞推關(guān)系式.。

邊界條件

動態(tài)規(guī)劃求解的一般步驟：

-確定過程的分段，構(gòu)造狀態(tài)變量；

-設(shè)置決策變量，寫出狀態(tài)轉(zhuǎn)移；

-列出階段指標和指標函數(shù)；

-寫出基本方程，由此逐段遞推求解。KSkSk+1XkVk8.3動態(tài)規(guī)劃的求解方法例1

用動態(tài)規(guī)劃方法求解前面的最短路問題。AEB1B2B3C1C2C3D1D2295312251564681013121114101.離散型求解方法

標號法求解在每個節(jié)點上標出從該節(jié)點到終點的最短距離AEB1B2B3C1C2C3D1D229531225156468101312111410始端終端0528712201419191234逆序解法AEB1B2B3C1C2C3D1D229531225156468101312111410請在每個節(jié)點上標出從該節(jié)點到始點的最短距離順序解法解：設(shè)階段k=1，2，3，4依次表示4個階段選路的過程；

狀態(tài)sk表示k階段初可能處的位置；決策xk表示k階段初可能選擇的路；階段指標vk表示k階段與所選擇的路段相應(yīng)的路長；指標函數(shù)vk4=表示k至4階段的總路長；

用表格方式求解逆推AEB1B2B3C1C2C3D1D2295312251564681013121114104kSkxkvkvkn=vk+fk+1

fk3C1C2C38712C1D1EC2D2EC3D2EkSkxkvkvkn=vk+fk+1

fkAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B320B1C1D1E14B2C1D1E19B3C2D2EkSkxkvkvkn=vk+fk+1

fkAEB1B2B3C1C2C3D1D2295312251564681013121114101A19AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）2.連續(xù)型（用公式遞推求解）例2

用動態(tài)規(guī)劃方法求解前面的機器負荷問題。某種機器可以在高、低兩種負荷下進行生產(chǎn)。高負荷年產(chǎn)量8，年完好率0.7；低負荷年產(chǎn)量5，年完好率0.9?，F(xiàn)有完好機器1000臺，需制定一個5年計劃，以決定每年安排多少臺機器投入高、低負荷生產(chǎn)，使5年的總產(chǎn)量最大。12345S1=1000x1x2x5x4x3s5v1v2v3v4v5s2s3s4階段指標vk=8xk+5(sk-xk)表示第k年的產(chǎn)量；指標函數(shù)vkn=表示第k至5年的總產(chǎn)量；解：設(shè)階段k=1，…，5表示第k年安排機器的過程；狀態(tài)sk表示第k年初的完好機器臺數(shù)；決策xk表示第k年投入高負荷的機器臺數(shù)；則投入低負荷的臺數(shù)為sk-xk

；狀態(tài)轉(zhuǎn)移sk+1=0.7xk+0.9(sk-xk)；f5(S5

)是關(guān)于x5的單調(diào)增函數(shù)x5*=S5

f5

(S5

)=8S55年的最大總產(chǎn)量為23.72×1000=23720。逆推解法的特點:12345S1x1x2x5x4x3s5v1v2v3v4v5s2s3s4始端已知終端邊界值取0或11.已知初始狀態(tài)s12.最優(yōu)值函數(shù)fk(sk)表示第k階段的初始狀態(tài)為sk,從k階段到n階段的最優(yōu)值.該問題的最優(yōu)值f1(s1)3.邊界條件是fn+1=0或者14.遞推關(guān)系是fk(sk)=opt(vk+fk+1)8.4

動態(tài)規(guī)劃應(yīng)用舉例

本節(jié)將通過動態(tài)規(guī)劃的四種應(yīng)用類型——靜態(tài)規(guī)劃問題的動態(tài)規(guī)劃求解、資源分配問題、復(fù)合系統(tǒng)可靠性問題、設(shè)備更新問題，進一步介紹動態(tài)規(guī)劃的特點和處理方法。123S1x1x2x3v1v2v3s2s3s4三階段決策問題狀態(tài)變量Sk:s1,s2,s3,s4決策變量為xi:x1,x2,x3例子:一、靜態(tài)規(guī)劃問題的動態(tài)規(guī)劃求解123S1x1x2x3v1v2v3s2s3s44假定s1=4,用逆推法可分析每個階段的狀態(tài)轉(zhuǎn)移:第3階段:s3=x3第2階段:s2=x2+s3第1階段:s1=x1+s2遞推方程:每個階段上決策變量的取值范圍?123S1x1x2x3v1v2v3s2s3s4k123sk431x*k121fk441123S1x1x2x3v1v2v3s2s3s44假定s4=4,用順推法可分析每個階段的狀態(tài)轉(zhuǎn)移:第1階段:s2=x1第2階段:s3=x2+s2第3階段:s4=x3+s3遞推方程:每個階段上決策變量的取值范圍?已知終止狀態(tài)sn+1怎么求解動態(tài)規(guī)劃?k123sk-+1134x*k121fk144二、資源分配問題1.問題的一般提法

設(shè)有某種資源，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品；若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)。問應(yīng)如何分配，可使總收益最大？2.數(shù)學(xué)規(guī)劃模型模型的特點——變量分離。3.用動態(tài)規(guī)劃方法求解階段k狀態(tài)sk決策xk=1,…,n表示把資源分配給第k種產(chǎn)品的過程；表示在給第k種產(chǎn)品分配之前還剩有的資源量；表示分配給第k種產(chǎn)品的資源量；狀態(tài)轉(zhuǎn)移sk+1=sk-xk；階段指標vk指標函數(shù)vkn

12S1=ax1x2g1(x1)g2(x2)

nxnsngn(xn)s2s3...例3某公司擬將某種高效設(shè)備5臺分配給所屬甲、乙、丙3廠。各廠獲此設(shè)備后可產(chǎn)生的效益如下表。問應(yīng)如何分配，可使所產(chǎn)生的總效益最大？效益廠設(shè)備臺數(shù)甲乙丙000013542710639111141211125131112解：階段k狀態(tài)sk決策xk=1,2,3依次表示把設(shè)備分配給甲、乙、丙廠的過程；表示在第k階段初還剩有的可分臺數(shù)；表示第k階段分配的設(shè)備臺數(shù)；狀態(tài)轉(zhuǎn)移sk+1=sk-xk；階段指標vk指標函數(shù)vk3

問題：本問題是屬于離散型還是屬于連續(xù)型？怎樣解？——離散型，用表格的方式求解。效益廠設(shè)備臺數(shù)甲乙丙000013542710639111141211125131112kSkxkvkvk+fk+1

fk30123450123450461112120+04+06+011+012+012+0046111212012345kSkxkvkvk+fk+1

fk0123452000+000-0

000+4155+051-0

000+6155+421010+0102-0

000+11155+621010+431111+0142-1

000+12155+1121010+631111+441111+0161-32-2

000+12155+1221010+1131111+641111+451111+0212-3kSkxkvkvk+fk+1

fk15012345037912130+213+167+149+1012+513+0210-2-32-2-1最優(yōu)策略：P*13為0-2-3或2-2-1，即分給甲廠0臺、分給乙廠2臺、分給丙廠3臺，或分給甲廠2臺、分給乙廠2臺、分給丙廠1臺。最優(yōu)值：f1=21?？梢?，最優(yōu)解可以是不唯一的，但最優(yōu)值是唯一的。資源分配問題的應(yīng)用很廣泛，例如：

1.某學(xué)生正在備考4門功課，還剩7天時間，每門功課至少復(fù)習(xí)1天。若他已估計出各門功課的復(fù)習(xí)天數(shù)與能提高的分數(shù)之間的關(guān)系，問他應(yīng)怎樣安排復(fù)習(xí)時間可使總的分數(shù)提高最多？

2.背包問題：旅行者攜帶的背包中能裝的物品重量為a，現(xiàn)他要從n種物品中挑選若干數(shù)量裝入背包，問他應(yīng)如何挑選可使所帶的物品總價值最大？其中,ci(xi)表示攜帶數(shù)量為xi的價值函數(shù);Wi表示第i種物品的單件重量1n2s1x1x2xnSn+1s2v1=c1(x1)vn=cn(xn)v2=c2(x2)sn三、復(fù)合系統(tǒng)工作可靠性問題1.問題的一般提法

設(shè)某工作系統(tǒng)由n個部件串接而成，為提高系統(tǒng)的可靠性，在每個部件上裝有備用件。已知部件i上裝有xi個備用件時，其正常工作的概率為pi(xi)；每個部件i的備用件重量為wi，系統(tǒng)要求總重量不超過W。問應(yīng)如何安排備用件可使系統(tǒng)可靠性最高？串接:122.數(shù)學(xué)規(guī)劃模型模型的特點——變量分離。3.用動態(tài)規(guī)劃方法求解12S1=Wx1x2p1(x1)p2(x2)

nxnsnpn(xn)s2s3...階段k狀態(tài)sk決策xk=1,…,n表示安排第k個部件備用件的過程；表示在給第k個部件安排之前還剩有的容許重量；表示第k個部件上安排的備用件數(shù)量；狀態(tài)轉(zhuǎn)移sk+1=sk-wkxk；階段指標vk指標函數(shù)vkn

可靠性問題的應(yīng)用很廣泛，例如：

1.某重要的科研攻關(guān)項目正在由3個課題組以3種不同的方式進行，各組已估計出失敗的概率。為減少失敗的概率，選派了2名高級專家去充實科研力量。若可估計出各組增加專家后的失敗概率，問應(yīng)如何分派專家可使總的失敗概率最小？

2.已知x1+x2+…+xn=c，求z=x1x2…xn的最大值。四、設(shè)備更新問題例4

某運輸公司購進一批卡車投入運營，公司每年初需對卡車作出更新或繼續(xù)使用的決定。假設(shè)第k年中，rk(tk)表示車齡為tk的車使用一年的收入，uk(tk)表示車齡為tk的車使用一年的維修費用，ck(tk)表示車齡為tk的車更新成新車的費用。現(xiàn)公司需制定一個10年計劃，以決定如何安排使10年的總收入最大。12S1=？x1x210x10s10v1v2v10s2…問題：狀態(tài)和決策怎樣設(shè)置？——決策是更新與否，可用0-1變量表示；狀態(tài)可設(shè)為車齡。階段k狀態(tài)sk決策xk=1,…,10表示第k年的決策過程；=tk表示第k年的車齡；狀態(tài)轉(zhuǎn)移tk+1=tk+1(1-xk)階段指標vk指標函數(shù)vkn

=rk[tk

]-uk[tk]-ck(tk)(1-xk)(1-xk)xk四、其他——隨機型問題舉例例5

某瓷廠接受訂制一個瓷瓶的任務(wù)。瓷瓶用電爐燒制。據(jù)技術(shù)分析估計，每個瓷瓶出爐后的合格率為0.5，各瓶合格與否相互獨立