動態(tài)規(guī)劃模型分享資料

1、1 動態(tài)規(guī)劃模型例1：最短線路問題0A6A 問題：現(xiàn)選擇一條從 到 的鋪管線路，使總距離最短？ 若用窮舉法要算23222148種不同線路，比較這48種結(jié)果即可得出，但當(dāng)段數(shù)增加，且各段選擇也增加時(shí)，窮舉法將變得非常龐大，以至利用計(jì)算機(jī)都十分困難。 2下面用動態(tài)規(guī)劃的方法計(jì)算最短線路問題的特性： 如果最短線路在第k站通過點(diǎn) ，則這一線路在由 出發(fā)到達(dá)終點(diǎn)的那一部分線路，對于從 點(diǎn)到達(dá)終點(diǎn)的所有可能選擇的不同線路來說，必定也是距離最短的。（反正法） kPkPkP 最短線路問題的這一特性啟示我們，從最后一段 開始，用從后向前逐步遞推的方法，求出各點(diǎn)到 的最短線路，最后求得從 到 的最短線路。 6A0

2、A6A3k6時(shí)： 設(shè) 表示由 到 的最短距離； )(56Af5A6A設(shè) 表示由 到 的最短距離； )(56Bf5B6A顯然 4)(56Af3)(56Bfk5時(shí)： 如果 表示由 到 的最短距離。 )(45Af4A6Amin)(45Af)(),()(),(56545654BfBAdAfAAd73543min（以下類似定義）（以下類似定義）4最短線路是 654AAA)(45Bf53245min)(),()(),(min5654556545BfBBdAfABd最短線路是 654ABB93646min)(),()(),(min)(565455654545BfBCdAfACdCf最短線路是 654ABC5

3、k4時(shí)： 75272min)(),()(),(min)(454344543434BfBAdAfAAdAf最短線路是 6543ABBA69251min)(),()(),(min)(454344543434CfCBdBfBBdBf最短線路是 6543ABBB689353min)(),()(),(min)(454344543434CfCCdBfBCdCf最短線路是 6543ABBCk3時(shí)： 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf最短線路是 65432ABBAA7106573min)(),()(),(min)(343233432323BfBBd

4、AfABdBf最短線路是 65432ABBAB98363min)(),()(),(min)(343233432323CfCCdBfBCdCf最短線路是 65432ABBBC8128468min)(),()(),(min)(343233432323CfCDdBfBDdDf最短線路是 65432ABBCDk2時(shí)： 1396103131min)(),()(),()(),(min)(23212232122321212CfCAdBfBAdAfAAdAf最短線路是 654321ABBABA91612697108min)(),()(),()(),(min)(23212232122321212DfDBdCfC

5、BdBfBBdBf最短線路是 出發(fā)點(diǎn)只有 0A18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf最短線路是 6543210ABBABAA最短距離為18。654321ABBBCB10說明 1)此例揭示了動態(tài)規(guī)劃的基本思想。 2)動態(tài)規(guī)劃方法比窮舉法（48種）大大節(jié)省了計(jì)算量。 3)計(jì)算結(jié)果不僅得到了 到 的最短線路和最短距離，而且得到了其它各點(diǎn)到 的最短線路和最短距離，這對于很多實(shí)際問題來說是很有用處的。 0A6A6A動態(tài)規(guī)劃法求解的數(shù)學(xué)描述 討論動態(tài)規(guī)劃中最優(yōu)目標(biāo)函數(shù)的建立，一般有下列術(shù)語和步驟： 、階段 用動態(tài)規(guī)劃求解多階段決策系統(tǒng)時(shí)，要根據(jù)

6、具體情況，將系統(tǒng)適當(dāng)?shù)胤殖扇舾蓚€(gè)階段，以便分若干個(gè)階段求解，描述階段的變量稱為階段變量。 11 上例分六個(gè)階段，是一個(gè)六階段的決策過程。例中由系統(tǒng)的最后階段向初始階段求最優(yōu)解的過程稱為動態(tài)規(guī)劃的逆推解法。 、狀態(tài)狀態(tài)表示系統(tǒng)在某一階段所處的位置或狀態(tài)。 上例中第一階段有一個(gè)狀態(tài)， ；即即0A第二階段有兩個(gè)狀態(tài)， ；即即,11BA 過程的狀態(tài)可用狀態(tài)變量 來描述，某個(gè)階段所有可能狀態(tài)的全體可用狀態(tài)集合來描述， kx01AS 如如,22223112DCBASBAS12、決策 某一階段的狀態(tài)確定之后，從該狀態(tài)演變到下一階段某一狀態(tài)所作的選擇稱為決策。描述決策的變量稱為決策變量 如上例中在第k階段用

7、表示處于 狀態(tài)時(shí)的決策變量。 )(kkxukx決策變量限制的范圍稱為允許決策集合。 用 表示第k階段從 出發(fā)的決策集合。 )(kkxDkx、策略 由每階段的決策 (i1,2,n)組成的決策函數(shù)序列稱為全過程策略或簡稱策略，用p表示， )(iixu)(,),(),()(22111nnxuxuxuxP即即13 由系統(tǒng)的第k個(gè)階段開始到終點(diǎn)的決策過程稱為全過程的后部子過程，相應(yīng)的策略稱為后部子過程策略。 用 表示k子過程策略， )(kkxP)(,),(),()(11nnkkkkkkxuxuxuxP即即 對于每一個(gè)實(shí)際的多階段決策過程，可供選擇的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。 允許策

8、略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。 、狀態(tài)轉(zhuǎn)移 某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。 14 設(shè)第k個(gè)階段的狀態(tài)變量為 ，決策變量為 ，則第k+1個(gè)階段的狀態(tài) 用 表示從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱它為狀態(tài)轉(zhuǎn)移方程。kx)(kkxu1kx),(1kkkkuxTx、階段效益 系統(tǒng)某階段的狀態(tài)一經(jīng)確定，執(zhí)行某一決策所得的效益稱為階段效益，它是整個(gè)系統(tǒng)效益的一部分，是 階段狀態(tài)和 階段決策的函數(shù)，記為 kxku),(kkkuxW、指標(biāo)函數(shù) 指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生的效益的數(shù)量表示，根據(jù)不同的實(shí)際問題，效益可以是利潤、距離、產(chǎn)量或資源的耗量等。 15 指標(biāo)

9、函數(shù)可以定義在全過程上，也可以定義在后部子過程上。指標(biāo)函數(shù)往往是各階段效益的某種和式，取最優(yōu)策略時(shí)的指標(biāo)函數(shù)稱為最優(yōu)策略指標(biāo)。 如上例中， 表示從 出發(fā)到終點(diǎn) 的最優(yōu)策略指標(biāo)。 )(45Af4A6A上例中 顯然為零，稱它為邊值條件。 )(66Af 而動態(tài)規(guī)劃的求解就是對kn,n-1,2,1逐級求出最優(yōu)策略指標(biāo)的過程。 、動態(tài)規(guī)劃的基本方程)(),(min)(11kkkkkukkxfuxWxfk16例2：機(jī)器負(fù)荷分配問題 某種機(jī)器可以在高低兩種負(fù)荷下生產(chǎn)，年產(chǎn)量與年初投入生產(chǎn)的機(jī)器數(shù)有關(guān)。在高負(fù)荷下生產(chǎn)時(shí)，年產(chǎn)量 ，式中 為投入生產(chǎn)的機(jī)器數(shù)，年終的完好機(jī)器數(shù)為 ，稱系數(shù)0.7為機(jī)器完好率。在低負(fù)

10、荷下生產(chǎn)時(shí)，年產(chǎn)量 ，式中 為投入生產(chǎn)的機(jī)器數(shù)，機(jī)器完好率為0.9，設(shè)開始時(shí)，完好的機(jī)器數(shù)為 臺，要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)決定如何重新分配完好機(jī)器在兩種不同負(fù)荷下工作的數(shù)量，使五年的總產(chǎn)量最高。 118us 1u17 . 0 u225us 2u10001x17解：此問題與上例類似。 設(shè)階段變量k表示年度； 狀態(tài)變量 是第k年初擁有的完好機(jī)器數(shù)（也是第k-1年度末完好機(jī)器數(shù)）。 kx 決策變量 規(guī)定為第k年度中分配在高負(fù)荷下生產(chǎn)的機(jī)器數(shù)。 ku 于是 是該年度分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)。 kkux k=2 k=3 k=4 k=5 1k1x2x3x4x5x 1u2u3u4u5u18記 表

11、示第k年到第五年末的最高總產(chǎn)量)(kkxfk5時(shí))(58max)(55505555uxuxfxu5550835max55xuxxu最優(yōu)點(diǎn)最優(yōu)點(diǎn)5*5xu 這說明第5年初要把全部完好機(jī)器投入高負(fù)荷下生產(chǎn)。 k4時(shí)4444452 . 09 . 0)(9 . 07 . 0uxuxux因因?yàn)闉?()(58max)(5544404444xfuxuxfxu所所以以)2 . 09 . 0(835max4444044uxuxxu1944406 .134 . 12 .12max44xuxxu最優(yōu)點(diǎn)最優(yōu)點(diǎn)4*4xu k3時(shí)3333342 . 09 . 0)(9 . 07 . 0uxuxux因因?yàn)闉?()(58ma

12、x)(4433303333xfuxuxfxu所以所以)2 . 09 . 0(6 .1335max3333033uxuxxu33305 .1728. 024.17max33xuxxu最優(yōu)點(diǎn)最優(yōu)點(diǎn)3*3xu 20k2時(shí)2222232 . 09 . 0)(9 . 07 . 0uxuxux因因?yàn)闉?()(58max)(3322202222xfuxuxfxu所所以以)2 . 09 . 0(5 .1735max2222022uxuxxu22208 .205 . 075.20max22xuxxu最優(yōu)點(diǎn)最優(yōu)點(diǎn)0*2uk1時(shí)10001x因?yàn)橐驗(yàn)?111122 . 09 . 0)(9 . 07 . 0uxuxux

13、)()(58max)1000(221110111xfuxufxu所所以以)2 . 09 . 0(8 .2035max1111011uxuxxu21)2 . 09 . 0(8 .2035max1111011uxuxxu16. 172.23max11011uxxu2370010007 .237 .231x最優(yōu)點(diǎn)最優(yōu)點(diǎn)0*1u 由此知五年最高總產(chǎn)量為23700再由上遞推知 10001x0*1u9002x0*2u8103x810*3u5674x567*4u3975x397*5u22高負(fù)荷生產(chǎn)的完好機(jī)器的最優(yōu)組合簡記：397,567,810, 0, 0,*5*2*1uuu 這表明在前兩年年初全部完好機(jī)器

14、投入低負(fù)荷生產(chǎn)，后三年年初全部完好機(jī)器投入高負(fù)荷生產(chǎn)。 第五年末的完好機(jī)器數(shù)為 0.7397278臺 在此例中，我們僅考慮最高產(chǎn)量，而未考慮五年計(jì)劃后的完好機(jī)器數(shù)。 問題1：若計(jì)劃為n個(gè)年度，怎樣決策？ 問題2：若要求在第5年末完好的機(jī)器數(shù)為500臺，如何決策使5年總產(chǎn)量最高？ 23這類問題稱為固定終端問題1x2x3x4x5x5006x1u2u3u4u5u由上討論知：狀態(tài)轉(zhuǎn)移方程仍為 ) 1 (2 . 09 . 0)(9 . 07 . 01kkkkkkuxuxux 表示第k年初開始到第5年末的最高產(chǎn)量，稱為最優(yōu)值函數(shù)，其遞推關(guān)系為 )(kkxf)2()2 . 09 . 0()(58(max)(

15、10kkkkkkxukkuxfuxuxfkkk=1,2,3,4,50)(66xf24其中 為第k段的效益值，即第k年的產(chǎn)量。 )(58),(kkkkkkuxuuxy 表示第6年的產(chǎn)量不計(jì)算在總產(chǎn)量之內(nèi)，故為零。 0)(66xf由假設(shè) ， 5006x又根據(jù)(1)得 5562 . 09 . 0uxx一般地，當(dāng) 確定后，選擇 來確定 ，現(xiàn)在 已經(jīng)給定，故 已經(jīng)沒有選擇余地，它由 和 確定。 5x5u6x6x5u6x5x于是25005 . 455 . 45655xxxu25由(2)可知035max)(5505555uxxfxu)25005 . 4(3555xx75005 .185x)2 . 09 . 0(35max)(4454404444uxfuxxfxu7500)2 . 09 . 0(5 .1835max4444044uxuxxu.max750070652144044uxxu75007 .214x最優(yōu)值 0*4u267500)2 . 09 . 0(7 .2135max)(333303333uxuxxfxu75005 .243x最優(yōu)值 0*3u類似地得到 75007 .21)(222xxf0*2u750