資源描述：
《《動態(tài)規(guī)劃應(yīng)用舉例》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第二節(jié)動態(tài)規(guī)劃應(yīng)用舉例本節(jié)將通過動態(tài)規(guī)劃的三種應(yīng)用類型——資源分配問題、復(fù)合系統(tǒng)可靠性問題、設(shè)備更新問題，進一步介紹動態(tài)規(guī)劃的特點和處理方法。一、資源分配問題1.問題的一般提法設(shè)有某種資源，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品；若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)。問應(yīng)如何分配，可使總收益最大？2.數(shù)學(xué)規(guī)劃模型模型的特點——變量分離。3.用動態(tài)規(guī)劃方法求解階段k狀態(tài)sk決策xk=1,…,n表示把資源分配給第k種產(chǎn)品的過程；表示在給第k種產(chǎn)品分配之前還剩有的資源量；表示分配給第k種產(chǎn)品的資源量；狀態(tài)轉(zhuǎn)移sk+1=sk-xk；階段指標(biāo)vk指標(biāo)函數(shù)vkn12S1=ax1x2
2、g1(x1)g2(x2)nxnsngn(xn)s2s3...例3某公司擬將某種高效設(shè)備5臺分配給所屬甲、乙、丙3廠。各廠獲此設(shè)備后可產(chǎn)生的效益如下表。問應(yīng)如何分配，可使所產(chǎn)生的總效益最大？效益廠設(shè)備臺數(shù)甲乙丙000013542710639111141211125131112解：階段k狀態(tài)sk決策xk=1,2,3依次表示把設(shè)備分配給甲、乙、丙廠的過程；表示在第k階段初還剩有的可分臺數(shù)；表示第k階段分配的設(shè)備臺數(shù)；狀態(tài)轉(zhuǎn)移sk+1=sk-xk；階段指標(biāo)vk指標(biāo)函數(shù)vk3問題：本問題是屬于離散型還是屬于連續(xù)型？怎樣解？——離散型，用表格的方式求解。效益廠設(shè)備臺數(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)值是唯一的。資源分配問題的應(yīng)用很廣泛，例如：1.某學(xué)生正在備考4門功課，還剩7天時間，每門功課至少復(fù)習(xí)1天。若他已估計出各門功課的復(fù)習(xí)天數(shù)與能提高的分?jǐn)?shù)之間的關(guān)系，問他應(yīng)怎樣安排復(fù)習(xí)時間可使總的分?jǐn)?shù)提高最多？2.背包問題：旅行者攜帶的背包中能裝的物品重量為a，現(xiàn)他要從n種物品中
5、挑選若干數(shù)量裝入背包，問他應(yīng)如何挑選可使所帶的物品總價值最大？一九九九年碩士研究生入學(xué)試題某大學(xué)生正在計劃如何安排在7天時間里復(fù)習(xí)完4門考試課程。他要求每天只能安排一門課程復(fù)習(xí)，每門課程至少需要復(fù)習(xí)1天，據(jù)他估計各門課程的復(fù)習(xí)時間與所能帶來的成績提高關(guān)系如下表。用動態(tài)規(guī)劃法求出使其總成績提高最多的復(fù)習(xí)天數(shù)安排計劃（資源分配問題）解：階段k：將7天分配給甲乙丙丁四門課程，劃分四個階段，k=1，2，3，4狀態(tài)sk：分配給第k門課程的天數(shù)，k=1,2,3,41?Xk?Sk狀態(tài)轉(zhuǎn)移: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：階段指標(biāo)Vk:第k階段分配后提高的分?jǐn)?shù)指標(biāo)函數(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門復(fù)習(xí)1天S2=S1-X1*=7-1=6X2*=2第
7、2門復(fù)習(xí)2天S3=S2-X2*=6-2=4X3*=1第3門復(fù)習(xí)1天S4=S3-X3*=4-1=3X4*=3第4門復(fù)習(xí)3天最優(yōu)值為:f1(S1)=21總成績最多提高21分背包問題1.一般提法：旅行者攜帶的背包中能裝的物品重量為a，現(xiàn)他要從n種物品中挑選若干數(shù)量裝入背包，已知第i種物品的單件重量為ai，其價格是ci（xi），問他應(yīng)如何挑選可使所帶的物品的總價值最大？2.模型：決策變量xi表示第i種物品裝入的件數(shù)（i=1~n）模型為：Maxz=∑Vi（xi）∑wi（xi）≤wxi≥0且為整數(shù)（i=
