動態(tài)規(guī)劃應用舉例ppt課件(編輯修改稿)
2025-06-02 12:08 本頁面
【文章內容簡介】 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)值是唯一的。 資源分配問題的應用很廣泛，例如： 4門功課，還剩 7天時間，每門功課至少復習 1天。若他已估計出各門功課的復習天數與能提高的分數之間的關系，問他應怎樣安排復習時間可使總的分數提高最多？ ：旅行者攜帶的背包中能裝的物品重量為 a，現(xiàn)他要從 n種物品中挑選若干數量裝入背包，問他應如何挑選可使所帶的物品總價值最大？ 一九九九年碩士研究生入學試題 某大學生正在計劃如何安排在 7天時間里復習完 4門考試課程。他要求每天只能安排一門課程復習，每門課程至少需要復習 1天，據他估計各門課程的復習時間與所能帶來的成績提高關系如下表。用動態(tài)規(guī)劃法求出使其總成績提高最多的復習天數安排計劃（資源分配問題） 4 3 5 24 5 6 45 6 8 78 7 8 83 4復 習 天 數 課 程341 212解： 階段 k： 將 7天分配給甲乙丙丁四門課程，劃分四個階段， k=1， 2， 3， 4 狀態(tài) sk： 分配給第 k門課程的天數， k=1,2,3,4 1?Xk?Sk 狀態(tài)轉移 : S k+1=SkXk 第 k階段初還剩的天數。 狀態(tài)集： S1={7},S2={3,4,5,6},S3={2,3,4,5}, S4={1,2,3,4} 決策 Xk： 階段指標 Vk: 第 k階段分配后提高的分數 指標函數： 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
教學課件相關推薦
鄂ICP備17016276號-1