《動態(tài)規(guī)劃應用舉例》PPT課件

《《動態(tài)規(guī)劃應用舉例》PPT課件》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第二節(jié)動態(tài)規(guī)劃應用舉例本節(jié)將通過動態(tài)規(guī)劃的三種應用類型——資源分配問題、復合系統(tǒng)可靠性問題、設備更新問題，進一步介紹動態(tài)規(guī)劃的特點和處理方法。一、資源分配問題1.問題的一般提法設有某種資源，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品；若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)。問應如何分配，可使總收益最大？2.數(shù)學規(guī)劃模型模型的特點——變量分離。3.用動態(tài)規(guī)劃方法求解階段k狀態(tài)sk決策xk=1,…,n表示把資源分配給第k種產(chǎn)品的過程；表示在給第k種產(chǎn)品分配之前還剩有的資源量；表示分配給第k種產(chǎn)品的資源量；狀態(tài)轉移sk+1=sk-xk；階段指標vk指標函數(shù)vkn12S1=ax1x2

2、g1(x1)g2(x2)nxnsngn(xn)s2s3...例3某公司擬將某種高效設備5臺分配給所屬甲、乙、丙3廠。各廠獲此設備后可產(chǎn)生的效益如下表。問應如何分配，可使所產(chǎn)生的總效益最大？效益廠設備臺數(shù)甲乙丙000013542710639111141211125131112解：階段k狀態(tài)sk決策xk=1,2,3依次表示把設備分配給甲、乙、丙廠的過程；表示在第k階段初還剩有的可分臺數(shù)；表示第k階段分配的設備臺數(shù)；狀態(tài)轉移sk+1=sk-xk；階段指標vk指標函數(shù)vk3問題：本問題是屬于離散型還是屬于連續(xù)型？怎樣解？——離散型，用表格的方式求解。效益廠設備臺數(shù)甲乙丙00001354

3、2710639111141211125131112kSkxkvkvk+fk+1fk30123450123450461112120+04+06+011+012+012+0046111212012345kSkxkvkvk+fk+1fk0123452000+000-0000+4155+051-0000+6155+421010+0102-0000+11155+621010+431111+0142-1000+12155+1121010+631111+441111+0161-32-2000+12155+1221010+1131111+641111+451111+0212-3kSkxkvkv

4、k+fk+1fk15012345037912130+213+167+149+1012+513+0210-2-32-2-1最優(yōu)策略：P*13為0-2-3或2-2-1，即分給甲廠0臺、分給乙廠2臺、分給丙廠3臺，或分給甲廠2臺、分給乙廠2臺、分給丙廠1臺。最優(yōu)值：f1=21?？梢姡顑?yōu)解可以是不唯一的，但最優(yōu)值是唯一的。資源分配問題的應用很廣泛，例如：1.某學生正在備考4門功課，還剩7天時間，每門功課至少復習1天。若他已估計出各門功課的復習天數(shù)與能提高的分數(shù)之間的關系，問他應怎樣安排復習時間可使總的分數(shù)提高最多？2.背包問題：旅行者攜帶的背包中能裝的物品重量為a，現(xiàn)他要從n種物品中

5、挑選若干數(shù)量裝入背包，問他應如何挑選可使所帶的物品總價值最大？一九九九年碩士研究生入學試題某大學生正在計劃如何安排在7天時間里復習完4門考試課程。他要求每天只能安排一門課程復習，每門課程至少需要復習1天，據(jù)他估計各門課程的復習時間與所能帶來的成績提高關系如下表。用動態(tài)規(guī)劃法求出使其總成績提高最多的復習天數(shù)安排計劃（資源分配問題）解：階段k：將7天分配給甲乙丙丁四門課程，劃分四個階段，k=1，2，3，4狀態(tài)sk：分配給第k門課程的天數(shù)，k=1,2,3,41?Xk?Sk狀態(tài)轉移:Sk+1=Sk-Xk第k階段初還剩的天數(shù)。狀態(tài)集：S1={7},S2={3,4,5,6},S3={2,3

6、,4,5},S4={1,2,3,4}決策Xk：階段指標Vk:第k階段分配后提高的分數(shù)指標函數(shù)：Vk4=?Vi遞推方程：k=4,3,2,1f5(S5)=0fk(Sk)=max{vk(Sk,Xk)+fk+1(Sk+1)}1?xk?SkK=4,S4={1,2,3,4},1?X4?S4,S5=S4-X4,f5(S5)=0K=3,S3={2,3,4,5},1?X3?S3,S4=S3-X3K=2,S2={3,4,5,6},1?X2?S2,S3=S2-X2K=1,S1={7},1?X1?S1,S2=S1-X1最優(yōu)解為:S1=7X1*=1第1門復習1天S2=S1-X1*=7-1=6X2*=2第

7、2門復習2天S3=S2-X2*=6-2=4X3*=1第3門復習1天S4=S3-X3*=4-1=3X4*=3第4門復習3天最優(yōu)值為:f1(S1)=21總成績最多提高21分背包問題1.一般提法：旅行者攜帶的背包中能裝的物品重量為a，現(xiàn)他要從n種物品中挑選若干數(shù)量裝入背包，已知第i種物品的單件重量為ai，其價格是ci（xi），問他應如何挑選可使所帶的物品的總價值最大？2.模型：決策變量xi表示第i種物品裝入的件數(shù)（i=1~n）模型為：Maxz=∑Vi（xi）∑wi（xi）≤wxi≥0且為整數(shù)（i=