網(wǎng)絡(luò)優(yōu)化-第4章動(dòng)態(tài)規(guī)劃-預(yù)覽頁(yè)
【正文】 ?因?yàn)? )。(m i n)。(*,11,1,)(1,111,1)(,)(1,111,1,1,111,1,11,1,11,11,1,nnnkknkxPpkkxPpnkknkxPpkknkknkkknnpxVpxVpxVpxVpxVpxVpxVpxVknknkkkknknk??????????????????所以 , 是最優(yōu)策略 ),( **2*1* ,1 nn uuup ??證畢 9 “全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：不管該最優(yōu)策略上某狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，余下的諸決策必定構(gòu)成最優(yōu)子策略 . ”即：最優(yōu)策略的任一后部子策略都是最優(yōu)的 . 最優(yōu)化原理 這只是最優(yōu)性定理的一個(gè)推論 ， 即最優(yōu)策略的必要條件 . 10 建立動(dòng)態(tài)規(guī)劃模型的基本過(guò)程是： （ 1） 正確劃分階段 ， 選擇階段變量 k. （ 2） 對(duì)每個(gè)階段 ， 正確選擇狀態(tài)變量 xk. 選擇狀態(tài)變量時(shí)應(yīng)當(dāng)注意兩點(diǎn)：一是要能夠正確描述受控過(guò)程的演變特性 ， 二是要滿足無(wú)后效性 . （ 3） 對(duì)每個(gè)階段 ， 正確選擇決策變量 uk . （ 4） 列出相鄰階段的狀態(tài)轉(zhuǎn)移方程： xk+1= Tk(xk, uk). （ 5） 列出按階段可分的準(zhǔn)則函數(shù) V1,n . 假設(shè)問(wèn)題的目標(biāo)是極小化 4． 2 動(dòng)態(tài)規(guī)劃基本方程 11 逆序遞推 k=1 k=n k k=2 1x2x 3x 1?kx 1?nxkx nx)( 11 xf1u 2uku nu)( 22 xf )( kk xf )( nn xf )](),([m i n)]。0)0()0( 33 ?? gf 。000)0()0()]0()([m a x)0( 3223220212???????? ?? fgufugf u。10}08,36,55,72,80m a x {)}0()4(),1()3(),2()2(),3()1(),4()0(m a x {)]4()([m a x)4(323232323223224022??????????????????fgfgfgfgfgufugfu17 資源分配問(wèn)題 k=1時(shí)： )]()([m a x)]()([m a x)( 11211022110111111uxfugxfugxf xuxu ????? ????.12}07,37,56,84,100m a x {)}0()4(),1()3(),2()2(),3()1(),4()0(m a x {)]4()([m a x)4(212121212112114011??????????????????fgfgfgfgfgufugfu最優(yōu)解 ,最大利潤(rùn)為 . 1,2,1 *3*2*1 ??? uuu 12)4(1* ?? fz推廣 1： 二維（或多維）資源分配問(wèn)題 推廣 2：非線性整數(shù)規(guī)劃問(wèn)題 ， 如： ???????????Zxxxxxxtsxxxxxxz321321321232221,4..5342m i nM=4, N=3 12111 )( uuug ??22222 32)( uuug ??32333 54)( uuug ??18 例 （ Singlelevel Uncapacitated Lotsizing） 某工廠生產(chǎn)某種產(chǎn)品用以滿足市場(chǎng)需求 ,且已知在時(shí)段 t中的市場(chǎng)需求為 dt . 在某時(shí)段 t, 如果開(kāi)工生產(chǎn) , 則生產(chǎn)開(kāi)工所需的生產(chǎn)準(zhǔn)備費(fèi)為 st , 單件產(chǎn)品的生產(chǎn)費(fèi)為 ct . 在某時(shí)段 t期末 , 如果有產(chǎn)品庫(kù)存 , 單件產(chǎn)品的庫(kù)存費(fèi)為 ht . 假設(shè)初始庫(kù)存為 0, 不考慮能力限制 , 工廠應(yīng)如何安排生產(chǎn) , 可以保證按時(shí)滿足生產(chǎn) , 且使總費(fèi)用最小 ? （ Wagner – Whitin， 1958） 單產(chǎn)品、無(wú)能力限制的批量問(wèn)題 假設(shè)在時(shí)段 t, 產(chǎn)品的生產(chǎn)量為 xt , 期末產(chǎn)品的庫(kù)存為It (I0 =0)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1