動態(tài)規(guī)劃應(yīng)用舉例ppt課件(編輯修改稿)
2025-06-02 12:08 本頁面
【文章內(nèi)容簡介】 0+12 1 5 5+12 2 10 10+11 3 11 11+6 4 11 11+4 5 11 11+0 21 23 k Sk xk vk vk+fk+1 fk ?P1 5 012345 0 3 7 9 1213 0+21 3+16 7+14 9+10 12+5 13+0 21 023 221 最優(yōu)策略： P*13 為 023或 221， 即分給甲廠 0臺、分給乙廠 2臺、分給丙廠 3臺， 或分給甲廠 2臺、分給乙廠 2臺、分給丙廠 1臺。 最優(yōu)值： f1=21。 可見，最優(yōu)解可以是不唯一的，但最優(yōu)值是唯一的。 資源分配問題的應(yīng)用很廣泛，例如： 4門功課，還剩 7天時間，每門功課至少復(fù)習(xí) 1天。若他已估計(jì)出各門功課的復(fù)習(xí)天數(shù)與能提高的分?jǐn)?shù)之間的關(guān)系，問他應(yīng)怎樣安排復(fù)習(xí)時間可使總的分?jǐn)?shù)提高最多？ ：旅行者攜帶的背包中能裝的物品重量為 a，現(xiàn)他要從 n種物品中挑選若干數(shù)量裝入背包，問他應(yīng)如何挑選可使所帶的物品總價(jià)值最大？ 一九九九年碩士研究生入學(xué)試題 某大學(xué)生正在計(jì)劃如何安排在 7天時間里復(fù)習(xí)完 4門考試課程。他要求每天只能安排一門課程復(fù)習(xí)，每門課程至少需要復(fù)習(xí) 1天，據(jù)他估計(jì)各門課程的復(fù)習(xí)時間與所能帶來的成績提高關(guān)系如下表。用動態(tài)規(guī)劃法求出使其總成績提高最多的復(fù)習(xí)天數(shù)安排計(jì)劃（資源分配問題） 4 3 5 24 5 6 45 6 8 78 7 8 83 4復(fù) 習(xí) 天 數(shù) 課 程341 212解： 階段 k： 將 7天分配給甲乙丙丁四門課程，劃分四個階段， k=1， 2， 3， 4 狀態(tài) sk： 分配給第 k門課程的天數(shù)， k=1,2,3,4 1?Xk?Sk 狀態(tài)轉(zhuǎn)移 : S k+1=SkXk 第 k階段初還剩的天數(shù)。 狀態(tài)集： S1={7},S2={3,4,5,6},S3={2,3,4,5}, S4={1,2,3,4} 決策 Xk： 階段指標(biāo) Vk: 第 k階段分配后提高的分?jǐn)?shù) 指標(biāo)函數(shù)： Vk4=?Vi 遞推方程： k=4,3,2,1 f 5(S5)=0 fk(Sk)=max { vk(Sk,Xk)+f k+1(S k+1)} 1? xk ?Sk K=4, S4={1,2,3,4}, 1?X4?S4, S5=S4X4 ,f5(S5)=0 S 4 X 4 V 4 (S 4 ) S 5 f 5 (S 5 ) V 4 (x 4 )+f 5 (S 5 ) f 4 (S 4 ) X 4*1 1 2 0 0 2 2 12 2 4 0 0 4 4 23 3 7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1