第5章動(dòng)態(tài)規(guī)劃55

1、5.2 動(dòng)態(tài)規(guī)劃模型的建立動(dòng)態(tài)規(guī)劃模型的建立下面以資源分配問題為例介紹動(dòng)態(tài)規(guī)劃的建模下面以資源分配問題為例介紹動(dòng)態(tài)規(guī)劃的建模過程。過程。 資源分配就是將一定數(shù)量的一種或幾種資源資源分配就是將一定數(shù)量的一種或幾種資源恰當(dāng)?shù)胤峙浣o使用者，恰當(dāng)?shù)胤峙浣o使用者， 以獲取最大效益。以獲取最大效益。 資源可以是資源可以是資金、原材料、設(shè)備或勞動(dòng)力等。資金、原材料、設(shè)備或勞動(dòng)力等。例例5.2.1（資源分配問題）（資源分配問題） 某公司有資金某公司有資金10萬元，萬元， 若投若投資于項(xiàng)目資于項(xiàng)目 23332,gxxix1114 ,gxx2229,gxx(1,2,3)i i 的投資額為的投資額為 時(shí)，時(shí)， 其收

2、益分別為其收益分別為 問應(yīng)如何問應(yīng)如何分配投資數(shù)額才能使總收益最大？分配投資數(shù)額才能使總收益最大？分析：分析： 這是一個(gè)與時(shí)間無明顯關(guān)系的靜態(tài)最優(yōu)化問這是一個(gè)與時(shí)間無明顯關(guān)系的靜態(tài)最優(yōu)化問 題，題， 可列出其靜態(tài)模型?？闪谐銎潇o態(tài)模型。 目的是求目的是求 2123max492zxxx123100,1,2,3ixxxxi123,x x x使使 并且滿足約束條件并且滿足約束條件為了應(yīng)用動(dòng)態(tài)規(guī)劃方法求解，為了應(yīng)用動(dòng)態(tài)規(guī)劃方法求解， 我們可以人為地我們可以人為地 賦予它賦予它“時(shí)段時(shí)段”的概念。的概念。 將投資項(xiàng)目排序，將投資項(xiàng)目排序， 依次考慮依次考慮項(xiàng)目項(xiàng)目1、項(xiàng)目、項(xiàng)目2和項(xiàng)目和項(xiàng)目3的投資，的

3、投資， 即把問題劃分為三個(gè)即把問題劃分為三個(gè)階段，階段，每個(gè)階段只決定對一個(gè)項(xiàng)目應(yīng)投資的金額。每個(gè)階段只決定對一個(gè)項(xiàng)目應(yīng)投資的金額。 ,kx這樣問題轉(zhuǎn)化為一個(gè)三階段決策問題。這樣問題轉(zhuǎn)化為一個(gè)三階段決策問題。 題是如何正確選擇狀態(tài)變量，題是如何正確選擇狀態(tài)變量， 接下來的問接下來的問具有遞推關(guān)系。具有遞推關(guān)系。 使各后部子過程之間使各后部子過程之間通?？梢园褯Q策變量通?？梢园褯Q策變量 ,kkux,ksku態(tài)問題中的變量態(tài)問題中的變量 定為原靜定為原靜即令即令 1,2,3k 狀態(tài)變量和決策變量有密切關(guān)系，狀態(tài)變量和決策變量有密切關(guān)系， 為累計(jì)量或隨遞推過程變化的量。為累計(jì)量或隨遞推過程變化的量。

4、 即狀態(tài)變量一般即狀態(tài)變量一般段可供使用的資金定為狀態(tài)變量段可供使用的資金定為狀態(tài)變量 這里可以把每階這里可以把每階110.s 1u初始狀態(tài)初始狀態(tài) 為可分配用于第一種項(xiàng)目的最大資金，為可分配用于第一種項(xiàng)目的最大資金， 則當(dāng)?shù)谝粍t當(dāng)?shù)谝浑A段（階段（k=1）時(shí)，）時(shí)， 有有 11110sux第二階段（第二階段（k=2）時(shí)，）時(shí)， 狀態(tài)變量狀態(tài)變量 11kkkkkssuux21122ssuux2s其余兩個(gè)項(xiàng)目的資金，即其余兩個(gè)項(xiàng)目的資金，即 為余下可投資于為余下可投資于一般地，一般地， 第第k時(shí)段時(shí)段 于是本例中有：于是本例中有：階段階段k： ks:ks:kx1kkkssx3,31( )kiiiV

5、g x():kkfsk =1，2，3，4； 狀態(tài)變量狀態(tài)變量 第第k段可以投資于第段可以投資于第 k項(xiàng)到第項(xiàng)到第3個(gè)項(xiàng)目個(gè)項(xiàng)目的資金。的資金。決策變量決策變量 決定給第決定給第k個(gè)項(xiàng)目投資的資金。個(gè)項(xiàng)目投資的資金。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： 指標(biāo)函數(shù)：指標(biāo)函數(shù)： 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) 當(dāng)可投資金為當(dāng)可投資金為 時(shí)，時(shí)， 投資第投資第 k-3項(xiàng)所得的最大收益。項(xiàng)所得的最大收益。 基本方程為：基本方程為：1(10)f11044max,3,2,10kkkkkkkkxsfsgxfskfs用動(dòng)態(tài)規(guī)劃方法逐段求解，用動(dòng)態(tài)規(guī)劃方法逐段求解， 便可得到各項(xiàng)目最佳投便可得到各項(xiàng)目最佳投 資金額，資金額，

6、 就是所求的最大收益。就是所求的最大收益。 建立動(dòng)態(tài)規(guī)劃模型的步驟：建立動(dòng)態(tài)規(guī)劃模型的步驟： 劃分階段劃分階段： 按時(shí)間或空間的順序適當(dāng)?shù)貙⑦^程劃按時(shí)間或空間的順序適當(dāng)?shù)貙⑦^程劃劃成若干個(gè)相互聯(lián)系的階段；劃成若干個(gè)相互聯(lián)系的階段；確定狀態(tài)變量及其取值范圍確定狀態(tài)變量及其取值范圍：決策過程演變的狀態(tài)，又要滿足無后效性的要求，決策過程演變的狀態(tài)，又要滿足無后效性的要求，狀態(tài)變量要能描述狀態(tài)變量要能描述而且維數(shù)要盡可能地少。而且維數(shù)要盡可能地少。確定決策變量及其取值范圍確定決策變量及其取值范圍：1,kkkksTs ukkkuus建立狀態(tài)轉(zhuǎn)移方程建立狀態(tài)轉(zhuǎn)移方程：建立動(dòng)態(tài)規(guī)劃的基本方程建立動(dòng)態(tài)規(guī)劃的基

7、本方程。5.3 動(dòng)態(tài)規(guī)劃的求解動(dòng)態(tài)規(guī)劃的求解兩兩種種基基本本方方法法 逆序解法：逆序解法： 順序解法：順序解法： 尋優(yōu)的方向與多階段決策過程的尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)方向相反，從最后一階實(shí)際行進(jìn)方向相反，從最后一階段開始計(jì)算，逐段前推，求得全段開始計(jì)算，逐段前推，求得全過程的最優(yōu)策略過程的最優(yōu)策略 尋優(yōu)方向與多階段決策過程的實(shí)尋優(yōu)方向與多階段決策過程的實(shí)際行進(jìn)方向相同，從第一階段開際行進(jìn)方向相同，從第一階段開始計(jì)算，逐段向后遞推，計(jì)算后始計(jì)算，逐段向后遞推，計(jì)算后一階段要用到前一階段的尋優(yōu)結(jié)一階段要用到前一階段的尋優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果即為全果，最后一段計(jì)算的結(jié)果即為全過程的最

8、優(yōu)結(jié)果過程的最優(yōu)結(jié)果 1kkfs 0100,fsfA13137()fBu BA1ks因?yàn)槟嫘蚪夥ㄇ耙烟峒?，因?yàn)槟嫘蚪夥ㄇ耙烟峒埃?所以這里我們只討論順?biāo)赃@里我們只討論順 序解法，序解法， 仍以例仍以例5.1.1為例，為例， 因?yàn)樵搯栴}的始點(diǎn)因?yàn)樵搯栴}的始點(diǎn)A與終點(diǎn)與終點(diǎn) E都是固定的，都是固定的， 計(jì)算由計(jì)算由A點(diǎn)到點(diǎn)到E點(diǎn)的最短路徑與由點(diǎn)的最短路徑與由E點(diǎn)點(diǎn) 到到A點(diǎn)的最短路徑應(yīng)當(dāng)一樣，點(diǎn)的最短路徑應(yīng)當(dāng)一樣， 所以若用所以若用 表示從表示從 起點(diǎn)起點(diǎn)A到第到第k階段狀態(tài)階段狀態(tài) 的最短距離，的最短距離， 則可以從前向則可以從前向 后逐步求出起點(diǎn)后逐步求出起點(diǎn)A到各階段起點(diǎn)的最短距離，到各階

9、段起點(diǎn)的最短距離， 最后求出最后求出從從A點(diǎn)到點(diǎn)到 E點(diǎn)的最短距離及最短路線，點(diǎn)的最短距離及最短路線， 計(jì)算過程如下：計(jì)算過程如下： k=0時(shí)，時(shí)， 即為邊界條件。即為邊界條件。 k=1時(shí)，按時(shí)，按 12fs的定義有：的定義有： 12125,(),fBu BA11113,(),fBu BA1111212112(,)()()min(,)()d B Cf Bf Cd B Cf Bk=2時(shí)，時(shí)， AB1B2B3C1C2C3D1D2E359677523835433496圖圖5.1.2 12112212223213(,)()(,)()()min(,)()d B Cf Bd B Cf Bf Cd B Cf

10、 B63min105537221()u CB211()u CB73min10952312233313(,)()()min(,)()d B Cf Bf Cd B Cf B25min787232()u CB11112112313113(,)()(,)()()min(,)()d C Df Cd CDf CfDd C Df Ck=3時(shí)，時(shí)， 2C3C311()u DC3 10min134967或或 或或 122.ABCDE42( )uED4 13min153 122314332(,)()( )min(,)()d D EfDfEd D EfD322()u DCk=4時(shí)，時(shí)， 4( )15fE 按定義可知

11、按定義可知 為所求的最短路長，為所求的最短路長， 而最短路而最短路徑則為徑則為 5 10min12399712112212323213(,)()(,)()()min(,)()d C Df Cd CDf CfDd C Df CAB1B2B3C1C2C3D1D2E36775234336圖圖5.3.1 與前節(jié)逆序解法結(jié)論相同，全部計(jì)算情況如圖與前節(jié)逆序解法結(jié)論相同，全部計(jì)算情況如圖5.3.1 (5)(9)(10)(7)(3)(7)(12)(13)(15)(0)圖中每節(jié)點(diǎn)上方括號(hào)內(nèi)的數(shù)表示該點(diǎn)到圖中每節(jié)點(diǎn)上方括號(hào)內(nèi)的數(shù)表示該點(diǎn)到A點(diǎn)的最短點(diǎn)的最短 距離。距離。上述解法可寫成如下遞推方程：上述解法可寫成

12、如下遞推方程：,.kkkksTs u11101()min(,)(),1,2,3,4( )0kkkkkkkkufsv sufskfs這里這里 順序解法和逆序解法的區(qū)別順序解法和逆序解法的區(qū)別 ：1狀態(tài)轉(zhuǎn)移方式不同狀態(tài)轉(zhuǎn)移方式不同逆逆序序解解法法狀態(tài)狀態(tài)轉(zhuǎn)移轉(zhuǎn)移方程方程順順序序解解法法1,kkkksTsu1,kkkksTs u順序轉(zhuǎn)移方程順序轉(zhuǎn)移方程 逆序轉(zhuǎn)移方程逆序轉(zhuǎn)移方程 n ns1nsnu(,)nnnv s un1k 1s1(,)kkkvsu1u2sku121(,)v s uks1ksns1nsnu1(,)nnnvsu圖圖5.3.3 順序解法順序解法1k 1s狀態(tài)(,)kkkvs u1u決策

13、2sku111( ,)v s u效益ks1ks圖圖5.3.2 逆序解法逆序解法2指標(biāo)函數(shù)的定義不同指標(biāo)函數(shù)的定義不同逆序解法：逆序解法： 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) 逆序解法：逆序解法： 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) 1()nnfsks1():kkfs1ks11( )f s():kkfs第第k階段從狀態(tài)階段從狀態(tài) 出發(fā)，到終點(diǎn)后部子過程最優(yōu)效益值。出發(fā)，到終點(diǎn)后部子過程最優(yōu)效益值。 第第k階段時(shí)從起階段時(shí)從起 點(diǎn)到狀態(tài)點(diǎn)到狀態(tài) 的前部子過程最優(yōu)效益的前部子過程最優(yōu)效益值。值。整體最優(yōu)函數(shù)值：整體最優(yōu)函數(shù)值： 整體最優(yōu)函數(shù)值：整體最優(yōu)函數(shù)值： 11()11()(,)(),1,1()0kkkkkkkkk

14、kuDsnnfsoptv s ufskn nfs3基本方程形式不同基本方程形式不同 逆序解法：逆序解法： 順序解法：順序解法： 指標(biāo)函數(shù)為指標(biāo)函數(shù)為階段指標(biāo)和階段指標(biāo)和形式形式 1,11,kkjjjjVvsu111()01()(,)(),1,2,( )0kkkkkkkkkkuDsfsoptv sufsknfs,nk njjjj kVvs u指標(biāo)函數(shù)為指標(biāo)函數(shù)為階段指標(biāo)積階段指標(biāo)積形式形式 逆序解法：逆序解法： 順序解法：順序解法： 111()01()(,)(),1,2,( )1kkkkkkkkkkuDsfsoptv sufsknfs1,11,kkjjjjVvsu11()11()(,)(),1,

15、1()1kkkkkkkkkkuDsnnfsoptvs ufskn nfs,nk njjjj kVvs u當(dāng)動(dòng)態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連當(dāng)動(dòng)態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量時(shí)，續(xù)變量時(shí)， 則可靈活選取求解方法，則可靈活選取求解方法， 法、非線性規(guī)劃方法、經(jīng)典解析方法或者其它數(shù)法、非線性規(guī)劃方法、經(jīng)典解析方法或者其它數(shù)如線性規(guī)劃方如線性規(guī)劃方值方法等。值方法等。如例如例5.2.1，狀態(tài)變量和決策變量均取，狀態(tài)變量和決策變量均取連續(xù)值。連續(xù)值。這里我們分別采用逆序解法和順序解法這里我們分別采用逆序解法和順序解法來求解。來求解。1用逆序解法求解用逆序解法求解由前面分析知，由前面分析知，

16、 該問題為三階段決策問題該問題為三階段決策問題:ks:kx第第k段可以投資于第段可以投資于第 k項(xiàng)到第項(xiàng)到第3個(gè)項(xiàng)目的資金個(gè)項(xiàng)目的資金決定給第決定給第k個(gè)項(xiàng)目投資的資金個(gè)項(xiàng)目投資的資金 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: 110max,3,2,1kkkkkkkkxsfsgxfsk440fs332233330max 22xsfsxsks():kkfs3,31( )kiiiVg x1kkkssx指標(biāo)函數(shù)指標(biāo)函數(shù): 最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) 當(dāng)可投資金為當(dāng)可投資金為 時(shí)，投資第時(shí)，投資第k-3 項(xiàng)所得的最大收益，基本方程：項(xiàng)所得的最大收益，基本方程：k=3時(shí)，時(shí)， 22222222(0)29 299 2fs

17、sfsss222222223322200max 9( )max 92()xsxsfsxf sxsxk=2時(shí)，時(shí)， 20,s2294xs2222222(,)92()h sxxsx220,dhdx229,4xs222240,d hdx若令若令 并令并令 得到得到 且有且有 故故 為極小點(diǎn)，為極小點(diǎn)， 因而極大值只可能在因而極大值只可能在 端點(diǎn)取得，即端點(diǎn)取得，即 此時(shí)此時(shí) 29 2s 211100109 2,ssx11111010111010max 49()max 959xxxsxsxs211,ssx 11112010max 49xfsxs222()9,fss 11111220max 4()xsf

18、sxfs29 2s *22.xs*20 x或或 k=1時(shí)，時(shí)， 若若 時(shí)，時(shí)， 注意到注意到 所以所以 但是但是 這與這與 矛盾，矛盾， 因而舍去。因而舍去。 111xs若若 212110,d hdx 2111111( ,)42()h s xxsx111.xs110,dhdx 121112010max 42xfsxs12111010max 42()xxsx2222()2,fss29 2,s 則則 令令 由由 可得可得 因?yàn)橐驗(yàn)?所以 為極小點(diǎn)。為極小點(diǎn)。 比較比較0,10兩個(gè)端點(diǎn)兩個(gè)端點(diǎn) , 1(10)40.f10 x 時(shí)，時(shí)， 110 x 1(10)200;f時(shí)，時(shí)， *20,x29 2,s

19、 *21110010ssx*10.x 故故 再由狀態(tài)轉(zhuǎn)移方程順推再由狀態(tài)轉(zhuǎn)移方程順推 因因 故故 *3310.xs*32210010.ssx因而因而 故最優(yōu)投資方案為全部投資于第三個(gè)項(xiàng)目，可得最故最優(yōu)投資方案為全部投資于第三個(gè)項(xiàng)目，可得最 大收益大收益200萬元。萬元。 2用順序解法求解用順序解法求解 階段劃分和決策變量的設(shè)置同逆序解法。階段劃分和決策變量的設(shè)置同逆序解法。 狀態(tài)變量狀態(tài)變量 1110max,1,2,3kkkkkkkkxsfsgxfsk 010fs121211010max()( )xsfsg xfs1:ks1kkkssx1():kkfs1ks可以投資于第可以投資于第1到第到第k個(gè)項(xiàng)目的資金個(gè)項(xiàng)目的資金