【正文】 90 ? 解 把 12支巡邏隊伍往 4部位看成依次分 4個階段（用 k表示， k=1,2,3,4) ? (1)逆序解法 ? 每 個階段初擁有的可派遣的巡邏隊數(shù)是前面階段決策的結(jié)果，用狀態(tài)變量 來表示。各階段的決策變量就是對各部位派出的巡邏隊數(shù)，用 表示 ，顯然個階段允許的決策集合為 ? 英每階段初擁有可派遣的巡邏隊數(shù)等于上階段初擁有的數(shù)量減去上階段排出的數(shù)，故狀態(tài)轉(zhuǎn)移律為 ? 若用 表示階段 派出的巡邏隊數(shù)為 時，該階段的部位的預(yù)期損失值，因此指標(biāo)函數(shù)可寫為 kxku? ?( ) | 2 4 1 , 2 , 3 , 4k k k kD x u u k? ? ? ?1k k kx x u? ??1 , 2 , 3k ?()kkpx k ku44, 4 1 , 41( ) ( ) ( )k i i k k i i k k ki k i kV p u p u p u p u V ?? ? ?? ? ? ? ???91 ? 設(shè)用 表示 階段狀態(tài)為 ，以此出發(fā)采用最優(yōu)子策略到過程結(jié)束時的預(yù)期損失值，因此有 ? 先考慮給 D部位派巡邏隊，即 ，上式可寫為 ? 因問題中只有 4個要害部門，故第 5階段初擁有的未派出的巡邏隊數(shù)隊前4個部位的預(yù)期損失不再起影響，故邊界條件 ，因此有 ? 因 ，又 的可能值為 ， 故由表 1的數(shù)據(jù)可得表 2的結(jié)果。 ()kkfx kkx? ?11()( ) m i n ( ) ( )k k kk k k k k ku D xf x p u f x?????4k?? ?4 4 4 4 5 5()( ) ( ) ( )m i nk k ku D xf x p u f x???55( ) 0fx???4 4 4 4()( ) ( )m i nk k ku D xf x p u????44( ) 2 , 3 , 4Dx ? 4x426x??92 表 2 2 3 4 2 34 _ _ 34 2 3 34 31 _ 31 3 4 34 31 25 25 4 5 34 31 25 25 4 6 34 31 25 25 4 4u4x44()pu44()fx*4u93 再聯(lián)合考慮對 C、 D兩個部位派巡邏隊，即 ，這是有 因有 ，又 ， 故可得表 3的結(jié)果 3k???3 3 33 3 3 3 4 4()( ) ( ) ( )m i nu D xf x p u f x?????33( ) 2 , 3 , 4Dx ?348x?? 表 3 2 3 4 4 24+34 58 2 5 24+31 22+34 55 2 6 24+25 22+31 21+34 49 2 7 24+25 22+25 21+31 47 3 8 24+25 22+25 31+25 46 4 3u3x3 3 4 3 3( ) ( )p u f x u??33()fx*3u94 ? 下面考慮對 B、 C、 D三個部位派巡邏隊，即 ，這時有 ? 同樣有 又 ，故計算得表 4。 2k???2 2 22 2 2 2 3 3()( ) ( ) ( )m inu D xf x p u f x?????22( ) 2 , 3 , 4Dx ? 28 1 0x?? 表 4 2 3 4 8 38+49 35+55 31+58 87 2 9 38+47 35+49 31+55 84 3 10 38+46 35+47 31+49 80 4 2u2x22()fx*2u2 2 3 2 2( ) ( )p u f x u??95 ? 最后考慮對 A、 B、 C、 D四個部位派巡邏隊，即 時，有 ? 因 有 故計算得表 5 1k???1 1 11 1 1 1 2 2()( ) ( ) ( )m inu D xf x p u f x?????11( ) 2 , 3 , 4Dx ?1 12x ? 2 3 4 12 18+80 14+84 10+87 97 4 1u1x11()fx*1u1 1 2 1 1( ) ( )p u f x u??96 ? 由表 5知，最優(yōu)策略是： A部位 4支， B部位 2支， C部位 2支， D部位 4支，總預(yù)期損失為 97單位。 97 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃問題實例 ? 動態(tài)規(guī)劃的基本概念與原理 ? 動態(tài)規(guī)劃應(yīng)用舉例 98 例 Wyndor Glass Company Problem 12m a x 3 5Z x x??12121242 1 2..3 2 1 8,0xxstxxxx?????????? ??使用動態(tài)規(guī)劃進(jìn)行求解 99 1 2 一、動態(tài)規(guī)劃問題建模 這個問題需要對兩個相關(guān)活動 (activity)確定其活動水平 (level of activity)，因此我們可以將這兩個活動看作動態(tài)規(guī)劃中的階段。 決策變量 ：第 k 個活動的活動水平（ level ofactivity ） kx狀態(tài)變量 ：可用于第 k階段生產(chǎn)的資源量（右端項）。即 ks1 2 3( , , )k k k ks R R R?100 狀態(tài)轉(zhuǎn)移方程： 12 11 1 122 2132 31 1 14123 18 3R R x xRRR R x x? ? ? ??? ???? ? ? ? ??階段指標(biāo)函數(shù) ：第 k 階段確定 時所產(chǎn)生的利潤即 )(kk xg kx最優(yōu)指標(biāo)函數(shù) ：第 k 階段狀態(tài)為 且采取最佳投資 策略，從第 k 個活動以及以后的最大總利潤。 )( kk sf ks 逆序法基本遞推方程： ? ?1133( ) m a x ( ) ( ) 2 , 1( ) 0kk k k k k kxf s g x f s kfs??? ? ? ??????kkcx101 二、動態(tài)規(guī)劃問題求解 （ 1） k=2 時 232222 1 2 2 2 3 2 2 3 1 3 2 3 3 30 m i n ( , )22( , , ) m a x { 5 ( , , ) }RRxf R R R x f R R R????33( ) 0fs ?因為 2322232222 1 2 2 2 3 2 20 m i n ( , )22( , , ) m a x { 5 } 5 m i n { , }22RRxRRf R R R x????故有 2 1 2 2 2 3 2( , , )s R R R? 2 1 2 2 2 3 2( , , )f R R R *2x32225 m in { , }22RR1 2 2 2 3 20 , 0 , 0R R R? ? ? 2322m in ( , )22RRk=2 時決策表 102 （ 2） k=1 時 131 1 11 1 1 2 1 3 1 1 2 1 2 2 2 3 20 m i n ( , )3( , , ) m a x { 3 ( , , ) }RxRf R R R x f R R R????因為初時狀態(tài)確定 1 1 2 1 3 1( , , ) ( 4 , 1 2 , 1 8 )R R R ?且 111 1 2 1 1 1 2 1 3 1 1041 2 1 104( 4 , 1 2 , 1 8 ) m a x { 3 ( , , ) }m a x { 3 ( 4 , 1 2 , 1 8 ) }xxf x f R x R R xx f x x????? ? ? ?? ? ? ?12 11 1 122 2132 31 1 14123 18 3R R x xRRR R x x? ? ? ??? ???? ? ? ? ??103 111 1 2 1 1 1 2 1 3 1 1041 2 1 104( 4 , 1 2 , 1 8 ) m a x { 3 ( , , ) }m a x { 3 ( 4 , 1 2 , 1 8 ) }xxf x f R x R R xx f x x????? ? ? ?? ? ? ?2 1 2 2 2 3 2( , , )s R R R? 2 1 2 2 2 3 2( , , )f R R R *2x32225 m in { , }22RR1 2 2 2 3 20 , 0 , 0R R R? ? ? 2322m in ( , )22RRk=2 時決策表 111041812m a x { 3 5 m i n { , } }23xxx?????104 111 1 2 1 1 1 2 1 3 1 1041 2 1 104( 4 , 1 2 , 1 8 ) m a x { 3 ( , , ) }m a x { 3 ( 4 , 1 2 , 1 8 ) }xxf x f R x R R xx f x x????? ? ? ?? ? ? ?111041812m a x { 3 5 m i n { , } }23xxx?????在可行區(qū)間 上 104x??11116 0 21812m in{ , } 323 9 2 42if xxx if x???? ?? ?? ? ???111104113 30 0 2( 4 , 12 , 18 ) m a x 945 2 42xxxfxx??? ? ???? ?? ? ???105 因為 1 102m a x { 3 3 0 }x x?? ?11249m a x { 4 5 }2x x?? ?和 都在 x1=2時獲得最大值 36 2 1 1 1 2 1 3 1( , , )s R R R? 1 1 1 2 1 3 1( , , )f R R R *1x? ?4,12,18k=1 時決策表 111104113 30 0 2( 4 , 12 , 18 ) m a x 945 2 42xxxfxx??? ? ???? ?? ? ???所以 11* 2 , ( 4 , 1 2 , 1 8 ) 3 6xf??106 36 2 1 1 1 2 1 3 1( , , )s R R R? 1 1 1 2 1 3 1( , , )f R R R *1x? ?4,12,18k=1 時決策表 2 1 2 2 2 3 2( , , )s R R R? 2 1 2 2 2 3 2( , , )f R R R *2x32225 m in { , }22RR1 2 2 2 3 20 , 0 , 0R R R? ? ? 2322m in ( , )22RRk=2 時決策表 12 11 1