【正文】 xuxrxf ?? 動(dòng)態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 k=n－ 1時(shí) ， 動(dòng)態(tài)規(guī)劃的基本方程是 )}(),({)( 111111nnnnnunn xfuxroptxfn?? ??????所有的 fn(xn)都已經(jīng)求出，因此可以根據(jù) xn=Tn1(xn1,un1) 就階段 n1每個(gè)可能狀態(tài) xn1∈ Xn1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值 fn－ 1(xn－ 1) })()。({ 111111 Xxxuxf ?? 動(dòng)態(tài)規(guī)劃問題求解的一般步驟 逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 })()。({ 111111 ?????? ?? nnnnnn Xxxuxf ),( 111 ?? nnn uxr )( nn xf })()。1xuxu),( *1*11*2uxTx)()(*2*2*239。1????nnnnxuxu),( * 1* 11*??? nnnnuxTx))(***39。 試求 s到 t的最短路 。 },{)(11 cbasUu ?? },{)()( 22 fdaUa ?? },{()( 22 edbUbu ? },{)()( 22 fedcUcu ?? }{33 t?? 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 由于第 3階段末已到達(dá) t， 往后的距離自然是零 ， 因此 f4(t)=0 對(duì) 3階段所有可能的狀態(tài) X3={d, e, f}計(jì)算 f3( )如下 )}(),({min)( 4433333xfudrdf Uu ?? ? tdutftdr ????? )(5)}(),(min{343 )}(),({min)( 44333 33 xfueref Uu ?? ? teuter ????? )(7}0),(min{ 33 )}(),({min)( 4433333xfufrff Uu ?? ? tfutfr ????? )(4}0),(min{33 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 也可以用表格方法計(jì)算如下 t/t F3() U3() d e f 5+0 7+0 4+0 5 7 4 t t t r3(x3,u3)+f4(x4) f3(x3) u3(x3) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 a d b e t c f s 9 7 5 7 8 4 5 6 4 6 5 4 7 4 7 5 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 對(duì) 2階段所有可能的狀態(tài) X2={a, b, c}計(jì)算 f2( )如下 )}(),({min)( 3322)(222xfuaraf aUu ?? ? )}(),({min 3322},{2xfuarfdu ?? ? ?????????)(),()(),(min3232fffardfdarfau ???????????? )(84457min2 )}(),({min)(3322)(2 22 xfubrbf bUu ?? ? ?????????(),()(),(min3232efebrdfdbrdbu ??????????? )(107655min2 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 對(duì) 2階段所有可能的狀態(tài) X2={a, b, c}計(jì)算 f2( )如下 )}(),({min)( 3322)(222xfucrcf cUu ?? ? ??????????????)(),()(),()(),(min323232fffcrefecrdfdcrdcu ????????????????? )(9467554min 2 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 也可以用表格方法計(jì)算如下 d/d e/e f/f F2() U2() a b c 7+5 5+5 4+5 6+7 5+7 4+4 6+4 8 10 9 f d d f2(x2) u2(x2) r2(x2,u2)+f3(x3) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 a d b e t c f s 9 7 5 7 8 4 5 6 4 6 5 4 7 4 7 5 9 10 8 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 對(duì) 1階段所有可能的狀態(tài) X1={s}計(jì)算 f1( )如下 )}(),({min)( 2211)(111xfusrsf sUu ?? ? ??????????????)(),()(),()(),(min212121cfcsrbfbsrafasrcsu ????????????????? )(169710889min 1a/a b/b c/c F2() U2() s 9+8 8+10 7+9 16 c 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 順序求最優(yōu)策略 、 最優(yōu)路線和最優(yōu)目標(biāo)函數(shù)值 16)}({ 11*11???xfoptRXxsx ?*1csu ?)(*1 cx ?*2dcu ?)(*2 tx ?*4tdu ?)(*3 dx ?*3 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 定步數(shù)問題 逆序求條件最優(yōu)目標(biāo)函數(shù)集和條件最優(yōu)決策集 a d b e t c f s 9 7 5 7 8 4 5 6 4 6 5 4 7 4 7 5 9 10 8 16 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 不定步數(shù)問題 a c b d s t 6 9 5 2 4 4 8 4 2 3 圖 48 例 4－ 2 用 f(i)表示 I節(jié)點(diǎn)到 t節(jié)點(diǎn)的最短距離，則根據(jù)動(dòng)態(tài)規(guī)劃原理，應(yīng)該有： 0)( ?tf)}(),({min)( jfjirif j ?? 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 不定步數(shù)問題 a c b d s t 6 9 5 2 4 4 8 4 2 3 圖 48 例 4－ 2 可用迭代的方法來實(shí)現(xiàn)求解 。 否則重復(fù)上述過程 ， 直至最優(yōu) 。已知用于活動(dòng) k的資源為 uk時(shí)的收益是 gk(uk)， 問應(yīng)如何分配資源，使 n種生產(chǎn)活動(dòng)的總收益最大。 )()()(max 2211 nn ugugugZ ???? ?Muuuts n ???? ?21.. 0, 21 ?nuuu ? 資源分配問題 資源的多元分配 如果將 n種活動(dòng)作為一個(gè)互相銜接的整體 ， 對(duì)一種活動(dòng)的資源分配作為一個(gè)階段 ， 每個(gè)階段確定對(duì)一種活動(dòng)的資源投放量 。 狀態(tài)變量 xk的選取原則是要能夠據(jù)此確定決策 uk， 以及滿足狀態(tài)轉(zhuǎn)移方程所要求的無后效性 。 資源的多元分配 關(guān)于狀態(tài)變量 xk的約束條件是 0≤xk≤M 關(guān)于決策變量 uk的約束條件是 0≤uk≤xk 狀態(tài)轉(zhuǎn)移方程為 xk+1=xkuk 顯然它滿足無后效性要求 。 投放資金（萬元） 0 10 20 30 40 50 收 益 （萬元） A 0 15 20 25 28 30 B 0 0 10 25 45 70 C 0 10 20 30 40 50 資源的多元分配 解 該問題可以作為三段決策過程 。 xk表示給部門 k分配資金時(shí)擁有的資金數(shù) 。 狀態(tài)轉(zhuǎn)移方程是 xk+1=xkuk。 目標(biāo)函數(shù)是階段效應(yīng)求和 。 )}()({max)( 4433333xfugxf u ??0)(44 ?xf )}({max)( 33033 33 ugxf xu ??? )()(3333 ugxf ?從表可知 g3( )是單調(diào)遞增的函數(shù) ， 因此 ， 當(dāng) u3=x3時(shí)達(dá)到最大 。 x? 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 xu ? 0)0(,0)0()0( 333 ??? ugf 1)1(,10)1()1( 333 ??? ugf 2)2(,20)2()2(333 ??? ugf 3)3(,30)3()3( 333 ?? ugf 4)4(,40)4()4( 333 ??f 5)5(,50)5()5( 333 ?? ugf 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 xu ?x3 g3 f3 U3’ 0 0 0 0 1 10 10 1 2 20 20 2 3 30 30 3 4 40 40 4 5 50 50 5 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 k=2時(shí) ， 0≤x2≤5 0≤u2≤x2 )}()({max)( 332202322xfugxf xu ?? ??0/x2 1/x21 2/x22 3/x23 4/x24 5/x25 f2() U2’ 0 0+0 0 0 1 0+10 0+0 10 0 2 0+20 0+10 10+0 20 0 3 0+30 0+20 10+10 25+0 30 0 4 0+40 0+30 10+20 25+10 45+0 45 4 5 0+50 0+40 10+30 25+20 45+10 70+0 70 5 資源的多元分配 逆序求條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合 。 當(dāng) k=1時(shí) ， 有 x1=5， 0≤u1≤x1=5 )}()({max)5( 22115011xfugf u ?? ??0/5 1/4 2/3 3/2 4/1 5/0 f1() U1’ 5 0+70 15+45 20+30 25+20 28+10 30+0 70 0 資源的多元分配 順序求最優(yōu)目標(biāo)函數(shù)值和最優(yōu)策略 、 最優(yōu)路線 0/5 1/4 2/3 3/2 4/1 5/0 f1() U1’ 5 0+70 15+45 20+30 25+20 28+10 30+0 70 0 5*1 ?x0)5(*1 ?u 5*2 ?x5)5(*2 ?u 0*4 ?x0)0(*3 ?u 0*3 ?x70)}({ 11*11???xfoptRXx 資源的多段分配 將一種有消耗性的資源 ， 多階段地在多種不同的生產(chǎn)活動(dòng)中投放的問題稱為資源的多段分配問題 ， 下面討論其中包含有兩個(gè)生產(chǎn)活動(dòng)的簡單情況 。 計(jì)劃在 A， B兩個(gè)生產(chǎn)部門連續(xù)使用 n個(gè)階段 。 又資源在生產(chǎn)中將有部分消耗 ， 已知每生產(chǎn)一個(gè)階段后部門 A， B中的資源完好率分別為 a和 b， 0(a, b)1。 資源的多段分配 n段決策過程 狀態(tài)變量 xk為階段 k初擁有的資源量 ， 0≤xk≤M， x1=M 決策變量選為階段 k在部門 A的資源投放量 ， 即 uA=uk， 這里顯然有 uB=xk uk， 決策變量的約束條件是 0≤uk≤xk 即最多將所擁有的資源都投入部門 A， 其時(shí) uB=0 階段 k末部站 A的剩余資源 auk， 部門 B中則為 b(xkuk)， 因此狀態(tài)轉(zhuǎn)移方程 xk+1=T(xk, uk)是 xk+1=auk+b(xkuk) 滿足無后效性 階段效應(yīng) rk(xk, uk)即階段收益 rk(xk,