運(yùn)籌學(xué)chap6動(dòng)態(tài)規(guī)劃dynamicprogramming-在線瀏覽
2025-07-15 15:06本頁(yè)面
【正文】 F2 G ? ? ? ? ? ?? ? ? ? 936 46m i n,m i n262351613535 ???????????????????FfFEdFfFEdEfu5(E3)= F2 E3 F2 G k=6, F1 G, f6(F1)=4 F2 G,f6(F2)=3 36 k=4， f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D1 f3(C4)=12 u3(C4)=D3 k=3, = min f1(A)= min d1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2) 5+13 3+16 =18 k=1, u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 37 增加研制費(fèi) （ 萬(wàn)元 ） 新產(chǎn)品成功的概率 甲 乙 丙 0 1 2 例 3：有一工廠研制甲、乙、丙三種新產(chǎn)品，估計(jì)這三種新研制成功的概率分別為： 、 、 。據(jù)估計(jì)，把增加的研制費(fèi)用于各種新產(chǎn)品研制時(shí)，研制成功的概率見(jiàn)下表。應(yīng)怎樣分配。一個(gè)階段表示需要做出一次決策的子問(wèn)題，建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問(wèn)題具有同一模式。 可劃分為 3個(gè)階段求解，對(duì)甲產(chǎn)品增加研制費(fèi)記為第1階段，對(duì)乙產(chǎn)品增加研制費(fèi)記為第 2階段，對(duì)丙產(chǎn)品增加研制費(fèi)記為第 3階段， k=1， 2， 3。狀態(tài)必須包含表示系統(tǒng)情況和確定決策所需要的全部信息，使其能反映過(guò)程的演變特征。確定狀態(tài)變量之后，根據(jù)具體問(wèn)題的性質(zhì)，找出狀態(tài)變量在各階段的取值范圍。 把給第 K種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量 uk, 顯然， uk不能超過(guò)當(dāng)時(shí)擁有的金額 sk 即： uk≤sk 41 ? 4. 建立狀態(tài)轉(zhuǎn)移方程 根據(jù)狀態(tài)變量和決策變量的含義，寫(xiě)出狀態(tài) 轉(zhuǎn)移方程。 ? 由于開(kāi)始時(shí)可用的金額為 2萬(wàn)元，而最后將全部用完，有 S1=2,S4=0 43 ? ，建立動(dòng)態(tài)規(guī)劃的基本方程 選取指標(biāo)函數(shù)，根據(jù)指標(biāo)函數(shù)建立最優(yōu)指標(biāo)函數(shù)遞推關(guān)系 ,即基本方程。 基本方程為 ? ???????? ??)(1)(1,2,3,)(),(m a x)(4411必然事件sfksfuspsf kkkkkkk44 第三階段 )}(),(m a x {)( 4433333 sfuspsf ?? 04 ?s 33 us ?? s3=0 ? s3=1 ? s3=2 } a x {)}0()0,0(m a x {)0( 433 ????? fpf 0*3 ?u} a x {)}0()1,1(m a x {)1( 433 ????? fpf 1*3 ?u} a x {)}0()2,2(m a x {)2( 433 ????? fpf *3 ?u第二階段 )}(),(m a x {)( 22322222 usfuspsf ???} a x {)}0()0,0(m a x {)0( 322 ????? fpf 0*2 ?u? s2=0 ? s2=1 ? s2=2 a x)11()1,1( )01()0,1(m a x)1(32322 ??????? ????????? ?? ??? fp fpf 0*2 ?um a x)22()2,2()12()1,2()02()0,2(m a x)2(3232322 ????????????????????????????????fpfpfpf 1*2 ?u第一階段 )}(),(m a x {)( 11111111 usfuspsf ???m a x)22()2,2()12()1,2()02()0,2(m a x)2(2121211 ????????????????????????????????fpfpfpf 0*1 ?u只有 S1=2 s2=s1u1* =20=2 s3=s2u2* =21=1 最優(yōu)解 011 從最后一個(gè)階段開(kāi)始，逐階段向前，直至第一階段，即可求出全過(guò)程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。 一維動(dòng)態(tài)規(guī)劃求解方法 逆推法 45 順推法 s3=s4+1=1 s2=s3+1=2 最優(yōu)解 011 由第一階段開(kāi)始，逐階段向后，直至最后一個(gè)階段，同樣可求出最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。 第一階段 ? s2=0 ? s2=1 ? s2=2 )}(),(m a x {)( 1012121 sfuspsf ?? 1 ?s} a x {)}2()2,0(m a x {)0( 011 ????? fpf 2*1 ?u} a x {)}2()1,1(m a x {)1( 011 ????? fpf 1*1 ?u} a x {)}2()0,2(m a x {)2( 011 ????? fpf 0*1 ?u1*2 ?u第二階段 ? s3=0 ? s3=1 ? s3=2 )}(),(m a x {)( 2123232 sfuspsf ??m a x)2()2,0()1()1,0()0()0,0(m a x)0(1212122 ?????????????????????????????fpfpfpf 1*2 ?u a x)2()1,1( )1()0,1(m a x)1(12122 ???????????????????fpfpf} a x {)}2()0,2(m a x {)2( 122 ???? fpf 0*2 ?u22 uss ??第三階段 )}(),(m a x {)( 3234343 sfuspsf ?? 343 uss ?? 04?sm a x)2()2,0()1()1,0()0()0,0(m a x)0(2323233 ?????????????????????????????fpfpfpf 1*3 ?u? ???????? ???1)(3,2,1,)(),(m a x)(10111sfksfuspsf kkkkkkk46 有一個(gè)徒步旅行者，其可攜帶物品重量的限度為 a 公斤，設(shè)有n 種物品可供他選擇裝入包中。 47 設(shè) xj 為第 j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問(wèn)題的數(shù)學(xué)模型如下： ?????????????)...(m a xnjxaxaxcZjnijjjnjjj?21 01且為整數(shù)用 動(dòng)態(tài)規(guī)劃方法求解 ，令 fk(y) 為 總重量不超過(guò) y 公斤，包中只裝有前 k 種物品時(shí)的最大使用價(jià)值。 所以問(wèn)題就是求 fn(a) 48 其遞推關(guān)系式為： ? ?nkxayfxcyf kkkkkayxkkk????? ???2 10其中)(m a x)(當(dāng) k=1 時(shí)，有： 的最大整數(shù)表示不超過(guò)其中1111111 )(ayayaycxcyf??????????????????49 例 3：求下面背包問(wèn)題的最優(yōu)解 ??????????且為整數(shù)0,55231258m a x321321321xxxxxxxxxZ 物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 解 ： a＝ 5 ，問(wèn)題是求 f3(5) ? ? )55(12m a x)5( 323503333xfxfxax?????整數(shù)50 ? ?)( ma x)( 323503 55125333xfxfxax?????整數(shù)? ?)( m a x 323550551233xfxxx????整數(shù)＝? ? )( m ax 32310 55123xfxx ??，＝＝?????? ???? )( )()( ),(m a x 10223301250xxff＝物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 51 ? ?? ?? ???????????????????????? 5 5 )( 2)1()0(1112122,10212250212502222222222)1(10),3(5),5(0m a x)25(m a x)25(m a x)25(5m a x)5(xxxxxxxaxfffxfxxfxxfxf＝＝＝，＝整數(shù)整數(shù)物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 ?????? ???? )()()()(m a x)(1022333012505x xf, f＝f52 ? ?? ?? ?)0( )0(0m a x )20(5 m a x )20(5 m a x )20(5 m a x)0(1 )0( 12120212 200212 0022222222ffxfxxfxxfxfxxxxxax????????????????????＝＝＝＝整數(shù)整數(shù) 物品 (xi ) x1 x2 x3 重量（ ai） 3 2 5 使用價(jià)值 8 5 12 ?????????? )1()0(22333)0(12)5(0m a x)5(x xf, f＝f53 )0(0308)0()0(0318)1()1(833
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1