北航計(jì)算機(jī)研究生課程_算法設(shè)計(jì)與分析_Assignment_1_第1頁
北航計(jì)算機(jī)研究生課程_算法設(shè)計(jì)與分析_Assignment_1_第2頁
北航計(jì)算機(jī)研究生課程_算法設(shè)計(jì)與分析_Assignment_1_第3頁
北航計(jì)算機(jī)研究生課程_算法設(shè)計(jì)與分析_Assignment_1_第4頁
北航計(jì)算機(jī)研究生課程_算法設(shè)計(jì)與分析_Assignment_1_第5頁
已閱讀5頁，還剩11頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、一、 解：設(shè)第k月的需求量為Nk(k=1,2,3,4) 狀態(tài)變量Xk:第k月初的庫存量，X1=X5=Q0<XkwNk+ +N4決策變量Uk：第k月的生產(chǎn)量,max0, Nk-Xk< Uk< min6, Nk+-+N4 - Xk狀態(tài)轉(zhuǎn) 移方程：Xk+i = Uk + XkNk第 k 月的成本 Vk = 0.5*(Xk - Nk)Uk=O3 + Uk + 0.5*(Uk + Xk - Nk)0設(shè)Fk(Xk)是由第k月初的庫存量Xk開始到第4月份結(jié)束這段時(shí)間的最優(yōu)成本則 Fk(Xk) = minVk + F+i(X k+i)1< k< 4=min 3 + Uk + 0.

2、5*(Uk + Xk - Nk) +kF(Uk + Xk - Nk) UK 0min 0.5*(Xk - Nk) + Fk+i(Xk - Nk)Uk=OF5(X5)=0四個(gè)月的最優(yōu)成本為Fi(X1)=F(0)詳細(xì)計(jì)算步驟如下：(i) k=4 時(shí)0WX4W4, max0, 4 - X4<U4Wmin6, 4-X4X4U4X5V4F5(X5)V4 + F5(X5)0407。7=F4(0)130606=F4(1)220505=F4(2)310404=F4(3)400000=F4 (4)即對(duì)于狀態(tài)X4的每個(gè)取值，都有唯一確定的決策變量U4使得F"X4)最優(yōu)k=3時(shí)0<X3<

3、6, max0, 2 - X3 p U3<min6, 6-X3X3U3X4V3F4(X4)V3 + 丘(X4)0205712316.5612.5428513539.5413.56411011= F3(0)1104711215.5A11.5327512438.5412.55410。10=F3(1)200077=F3 114.5610.522611337.5411.5449093010.5A6.5=Fs （3）125510236.5410.53488402156=F3（4）135.549.5247075031.545.5=F3 （5）1466604302=F3（6）（3） k=2 時(shí)0VX2

4、W9, max0, 3 X2vU2cmin6, 9-X2X2U2X3V2F3 （X3）V2 + F3 （X3）03061117417.51017.5529716=F2（0）6310.56.51712051116316.51016.5428715=F2（1）539.56.516641161721041115215.51015.5327714=F2（2）438.56.51554106166511.55.51730001111= F2（3）114.51014.5226713337.56.5144496155510.55.51666122144010.51010.5=F2（4）125713236.56

5、.513348614459.55.5155611213502178=F2 (5)135.56.512247613358.55.5144610126031.56.58=F2 (6)146612257.55.513369211704268=F2 (7)156.55.5122682108052.55.58=F2(8)167A9906325=Fz(9)(4) k=1 時(shí)X1=0, max0, 2< U1< min6, 11X1U1X2V1F2(X2)V1 + E(X2)020521316.51521.5428142253|9.5M120.5=Fi(0)641110.521.5由以上計(jì)算可得

6、，4個(gè)月的總最優(yōu)成本為Fi(O) = 20.5千元)從k=1回溯，可得最優(yōu)結(jié)果中各階段的狀態(tài)變量Xk和決策變量Uk如下表:月份k產(chǎn)量Uk月初庫存量Xk需求量Nk每月成本Vk15029.52033036021140440二、解:1、變量設(shè)定階段k：已遍歷過k個(gè)結(jié)點(diǎn)，k=1,2 6,7OK=1表示剛從V1出發(fā)，k=7表示已回到起點(diǎn)V1狀態(tài)變量Xk=(i, Sk)已遍歷k 個(gè)結(jié)點(diǎn)，當(dāng)前位于i結(jié)點(diǎn)，還未遍歷的結(jié)點(diǎn)集合為 Sko 則 X 仁(1, 234,5,6), X6=(,),X7=(1,)決策變量Uk=(i, j)：已遍歷k個(gè)結(jié)點(diǎn)，當(dāng)前位于i結(jié)點(diǎn)，下一個(gè)結(jié)點(diǎn)選擇j。狀態(tài)轉(zhuǎn)移方 程：Xk+i = T

7、(XK Uk) = (j, Sk-j)第k階段的指標(biāo)函數(shù)Vk=Di,j。最優(yōu)指標(biāo)函數(shù)Fk(Xk) = Fk(, Sk)：已遍歷k個(gè)結(jié)點(diǎn)，當(dāng)前從i結(jié)點(diǎn)出發(fā)，訪問Sk中的結(jié) 點(diǎn)一次且僅一次，最后返回起點(diǎn) V1的最短距離。則 Fk(, Sk) = min Di,j + F+i(j, Sk-j)1< k< 6F7(X7) = F(1,)=02、分析:(1) k=6 時(shí)，F(xiàn)6(,)=minDi,1 + F7(X7) = Di,1i=2,3,4,5,6X6=(,)U6=(i, j)X7=(1,)V6=Di,jF7(1,)V6 + F7(X7)(2,)(2. 1)(1,)r 120：12=F6(

8、2,)：(3,)1)(1.)23023=F6(3,)(4.)« 1)(1,)34034二F6(4,)(5,)(5, 1)(1.)；450：45=F6(5,)(6,)(6, 1)(1,)56056=F6(6,)即k=6時(shí)，對(duì)于每一種狀態(tài)X6,都有唯一的決策U6(2) k=5 時(shí)，F(xiàn)5(, S5) = minDi,j + F6(j )i=2,3,4,5,6X5=(i,S5)U5=(iJ)X6=(j,)V5=DiJF6(j,)V5 + F6(X6)(2,6)(2,6)(6,)215677=F5(2,6):(2,5(2,5)(5,)254570=F5(2,5)(2,4(2,4)(4,)303

9、464=F5(2,4)(2,3(2,3)(3,)1823仁 F5(2,3)(3,6)(3,6)(6,)15567 仁 F5(3,6)(3,5)(3,5)(5,)104555=F5(3,5)(3,4)(3,4)(4,)53439=F5(3,4)(3,2)(3,2)(2,)1912仁 F5(3,2)(4,6)(4.6)(6,)165672=F5(4,6)(4,5)(4.5)(5,)84553=F5(4,5)(4,3)(4,3)(3.)42327=F5(4.3)(4,2)(4,2)(2,)321244=F5(4,2)(5.6)(5,6)(6,)185674=F5(5,6)(5,4)(5,4)(4,)

10、103444=F5(5,4)(5,3)(5,3)(3,)112334=F5(5,3)(5,2)(5.2)(2,)271239=F5(5,2)(6.5)(6.5)(5,)124557=F5(6,5)(6,4)(6.4)(4,)203454=F5(6,4)(6,3)(6,3)(3,)162339=F5(6,3)(6,2)(6,2)2212:34=F5(6,2):即卜=時(shí)，對(duì)于每一種狀態(tài)X5,都有唯一決策U5(3) k=4 時(shí)，F(xiàn)4(i,S4) = min(Di,j + F5(j,S5)i=2,3,4,5,6X4=(i,S4)U4=(i,j)X5=(j,S5)|V4=DiJF5(j,S5)V4 +

11、F5(j,S5)(2,3,4)(2,3)(3,4)183957=F4(2,3,4)(2,4)(4,3)302757=F4(2,3,4)(2,4,5)(2,4)(4,5)305383(2,5)(5,4)2544:69=F4(2,4,5)(2,5,6)(2,5)(5,6)257499(2,6)(6,5)215778=F4(235,6)(2,3,5)(2,3)(3,5)185573(2,5)(5,3)253459=F4(2,3,5)(2,3,6)(2,3)(3,6)187189(2,6)(6,3)213960=F4(2,3,6)(2,4,6)(2,4)(4,6)3072102(2,6)(6,4)21

12、5475=F4(2,4,6)(3,2,4)(3,2)(2,4)196483(3,4)(4,2)544:49=F4(3,2,4)(3,2,5)(3,2)(2,5)197089(3,5)(5,2)103949=F4(3,2,5)(3,2,6)(3,2)(2,6)19177(3,6)(6,2)1534:49=F4(3,2,6)(3,4,5)(3,4)(4,5)55358(3,5)(5,4)1044:54=F4(3,4,5)(3,4,6)(3,4)(4,6)57277(3,6)(6,4)155469=F4(3,4,6)(3,5,6)(3,5)(5,6)107484(3,6)(6,5)r 1557r 7

13、2=F4(3,5,6)(4,2,3)(4,2)(2,3)324173(4,3)(3,2)43134=F4(4,2,3)(4,2,5)(4,2)(2,5)I?70102(4,5)(5,2)83947=F4(4,2,5)(4,2,6)(4,2)(2,6)3277109(4.6)(6,2)r 1634:50=F4(4,2,6) I(4,3,5)(4,3)(3,5)455(4,5)(5,3)83442=F4(4,3,5)(4,3,6)(4,3)(3,6)47175(4,6)(6,3)r 1639:55=F4(4,3,6) I(4,5,6)(4,5)(5,6)87482co 9石oCM 00CM 00

14、co 產(chǎn)9 00CM 6u LOLO 產(chǎn)ug) LO0s寺X6 COCMr：6 COCMw0so6 CO6 COCMin LOwcoLD寺9CMTCM1CMcoio T-T- 00T-o TcoT-CM CM9CM CMCM CMCM99CMCXIo T-y-Az*s / A、寸r>CM.z-sx-寸cssx “A'、Z*L A、 9c 這X-*>. 一-、寸c9，人、 寸 *-v-*c3x-z-sZ*-1， 寸c sszXx-sX-sZ*-*s L。、寸c9LO9COeCMc ssCMc 這9c 3CMc 9CO1r 史9r>ssCOc 9cor3CMc ssCMc

15、 史LOcCMCMc9COc 心IDc ssCOc9， ， LO *-v-*c立6 rCM c9coc9CMc9c9CM r9CDc9coc9G9co c96 c9r>9CDc9CM r>9coc9CMc9C9CMc9u?c9coc9C9coc9tno9C9in c9CMCMcoL000§CM COgT-o)00 00inCMco6 9LO 9gCMIOcoCOCM9 LD69gco 1-wL0 CMCOV-wRcoLOCM&w9 CM&6 T-LDc II co Z)cocCMcCMincCMco<%CMo6 r> CMcocinGCM6 c

16、3cCMiov> CM6 r> CMCMGCOr>COco cooco9lnGoCMH六寸巴 hll+sauEWLLfX (寸)(3,5)(5,2,4)105464(3,2,4,6)(3,2)(2,4,6)197594(3,4)(4,2,6)55055=F3(3,2,4,6)(3,6)(6,2,4)156479(3,25,6)(3,2)5,6)197897(3,5)(5,2,6)105262=F3(3,2,5,6)(3,6)(6,2,5)155166(3,4,5,6)(3,4)(4,5,6)57378(3,5)(5,4,6)107282(3,6)(6,4,5)15567 仁

17、F3(3,4,5,6)(4,2,3,5)(4,2)(2,3,5)325991(4,3)(3,2,5)44953(4,5)(5,2,3)84250=F3(4,2,3,5)(4,2,3,6)(4,2)(2,3,6)326092(4,3)(3,2,6)44953=F3(4,2,3,6)(4,6)(6,2,3)164763(4,25,6)(4,2)(2,5,6)3278110(4,5)(5,2,6)85260=F3(4,2,5,6)(4,6)(6,2,5)165167(4,3,5,6)(4,3)(3,5,6)47276(4,5)(5,3,6)85765(4,6)(6,3,5)164662=F3(4,3

18、,5,6)(5,2,3,4)(5,2)(2,3,4)275784(5,3)(3,2,4)114960(5,4)(4,2,3)103444=F3(5,2,3,4)(5,2,3,6)(5,2)(2,3,6)276087(5,3)(3,2,6)114960=F3(5,2,3,6)(5,6)(6,2,3)184765(5,2,4,6)(5,2)(2,4,6)2775102(5,4)(4,2,6)105060=F3(5,2,4,6)(5,6)(6,2,4)186482(5,3,4,6)(5,3)(3,4,6)116980(5,4)(4,3,6)105565=F3(5,3,4,6)(5,6)(6,3,4)

19、184765=F3(5,3,4,6)(6,2,3,4)(6,2)(2,3,4)225779(6,3)(3,2,4)164965(6,4)(4,2,3)203454=F3(6,2,3,4)(6,2,3,5)(6,2)(2,3,5)225981(6,3)(3,2,5)164965(6,5)(5,2,3)124254=F3(6,2,3,5)(6,2,4,5)(6,2)(2,4,5)226991(6,4)(4,2,5)204767(6,5)(5,2,4)125466=F3(6,2,4,5)(6,3,4,5)(6,3)(3,4,5)165470(6,4)(4,3,5)204262(6,5)(5,3,4)

20、123749=F3(6,3,4,5)(5) k=2 時(shí)，F(xiàn)2(i,S2) = minDi,j + F3(j,S3)i=2,3,4,5,6X2=(i,S2)U2=(iJ)X3=(j,S3)V2=Di,jF3(j,S3)V2 + F3(j,S3)(2,3,4,5,6)(2,3)；(3,4,5,6)r 187189(2,4)(4,3,5,6)306292(2,5)(5,3,4,6)256590(2,6)(6,3,4,5)：214970=F2(2,3,4,5,6):(3,2,4,5,6)(3,2)(2,4,5,6)197796(3,4)(4,2,5,6)56065=F2(3,2J4,5,6)(3,5)

21、：(5,2,4.6)r 106070(3,6)(6,2,4,5)156681(4,2,3,5,6)(4,2)(2,3,5,6)326799(4,3)：(3,2,5,6)46266=F2(4,2,3,5,6) 1(4,5)(5,2,3,6)86068(4,6)(6,2,3,5)165470(5,2,3,4,6)(5,2)：(2,3,4.6)276895(5,3)(3,2,4,6)115566(5,4)(4,2,3,6)105363=F2(5,2,3,4,6)(5,6)：(6,2,3,4)M85472(6,2,3,4,5)(6,2)(2,3,4,5)226284(6,3)(3,2,4,5)I 16

22、5268(6,4)M2,3,5)：205070(6,5)(5,2,3,4)124456=F2(6,2,3,4,5)(6) k=1 時(shí)，F(xiàn)1(1,S1) = minD1J4-F2(j,S2)X 仁(1,S1)X2=(j,S2)V1=D1JF2(j,S2)V1 + F2(j,S2)(1,2,3,4,5,6)(1,2)1(2,3,4,5,6)107080=F1(1,2,3,4,5,6)(1,3)(3,2,4,5,6)206585(1,4)(4,2,3,5,6)306696(1,5) n(5,2,3,4,6)4063103(1,6)(6,2,3,4,5)50561063、偽代碼和時(shí)間復(fù)雜度為方便計(jì)算，結(jié)點(diǎn)編號(hào)改為0到5. 用一二維

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論