《運(yùn)籌學(xué) 北京郵電大學(xué)動態(tài)規(guī)劃1》由會員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué) 北京郵電大學(xué)動態(tài)規(guī)劃1（33頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第五章 動態(tài)規(guī)劃,不要過河拆橋,動態(tài)規(guī)劃,Dynamic programming,五十年代貝爾曼(,B.E.Bellman,),為代表的研究成果,屬于現(xiàn)代控制理論的一部分,以長遠(yuǎn)利益為目標(biāo)的一系列決策,最優(yōu)化原理，可歸結(jié)為一個遞推公式,5.1,動態(tài)規(guī)劃的最優(yōu)化原理及其算法,5.1.1 求解多階段決策過程的方法,例5.1.1 最短路問題,2,決策樹法,可以枚舉出20條路徑，其中最短的路徑長度為16,3,例,5.1.1,最短路問題,表現(xiàn)為明顯的階段性,一條從,A,到,B,的,最短路徑中的任何一段都是最短的,最

2、優(yōu)性原理,“最優(yōu)策略的一部分也是最優(yōu)的,”,每步的決策只與相鄰階段狀態(tài)有關(guān)，而與如何達(dá)到這一狀態(tài)無關(guān),因此我們可以從,B,向回搜索最短路,標(biāo)記法,如何找出最短路徑,4,5.1.2,動態(tài)規(guī)劃的基本概念及遞推公式,狀態(tài),(每階段初始的出發(fā)點(diǎn)),最短路問題中，各個節(jié)點(diǎn)就是狀態(tài),生產(chǎn)庫存問題中，庫存量是狀態(tài),物資分配問題中，剩余的物資量是狀態(tài),控制變量,(決策變量),最短路問題中，走哪條路,生產(chǎn)庫存問題中，各階段的產(chǎn)品生產(chǎn)量,物資分配問題中，分配給每個地區(qū)的物資量,階段的,編號,與遞推的,方向,一般采用反向遞推，所以階段的編號也是逆向的,當(dāng)然也可以正向遞推,5,動態(tài)規(guī)劃的步驟,1、確定問題的階段和編號

3、,2、確定狀態(tài)變量,用,S,k,表示第,k,階段的狀態(tài)變量及其值,3、確定決策變量,用,x,k,表示第,k,階段的決策變量，并以,x,k,*,表示該階段的最優(yōu)決策,4、狀態(tài)轉(zhuǎn)移方程,s,k,-1,=,g,(,s,k,x,k,),反向編號,s,k,+1,=,g,(,s,k,x,k,),正向編號,5、直接效果,直接一步轉(zhuǎn)移的效果,d,k,(,s,k,x,k,),6、,總效果函數(shù),指某階段某狀態(tài)下到終端狀態(tài)的總效果，它是一個遞推公式,6,動態(tài)規(guī)劃的步驟,h,k,是一般表達(dá)形式，求當(dāng)前階段當(dāng)前狀態(tài)下的階段最優(yōu)總效果,(1)如最短路問題，是累加形式，此時(shí)有,終端的邊際效果一般為,f,0,(,s,0,x,

4、0,)=0,(2),如串聯(lián)系統(tǒng)可靠性問題，是連乘形式，此時(shí)有,終端的邊際效果一般為,f,0,(,s,0,x,0,)=1,從第1階段開始，利用邊際效果和邊界條件，可以遞推到最后階段,7,5.2 動態(tài)規(guī)劃模型舉例,5.2.1 產(chǎn)品生產(chǎn)計(jì)劃安排問題,例1,某工廠生產(chǎn)某種產(chǎn)品的月生產(chǎn)能力為10件，已知今后四個月的產(chǎn)品成本及銷售量如表所示。如果本月產(chǎn)量超過銷售量時(shí)，可以存儲起來備以后各月銷售，一件產(chǎn)品的月存儲費(fèi)為2元，試安排月生產(chǎn)計(jì)劃并做到：,1、保證滿足每月的銷售量，并規(guī)定計(jì)劃期初和期末庫存為零；,2、在生產(chǎn)能力允許范圍內(nèi)，安排每月生產(chǎn)量計(jì)劃使產(chǎn)品總成本(即生產(chǎn)費(fèi)用加存儲費(fèi))最低。,8,例1 產(chǎn)品生產(chǎn)

5、計(jì)劃安排,設(shè),x,k,為第,k,階段生產(chǎn)量，則有直接成本,d,k,(,s,k,x,k,)=,c,k,x,k,+2,s,k,狀態(tài)轉(zhuǎn)移公式為,s,k,-1,=,s,k,+,x,k,-,y,k,總成本遞推公式,第一階段,：(即第4月份),由邊界條件和狀態(tài)轉(zhuǎn)移方程,s,0,=,s,1,+,x,1,y,1,=,s,1,+,x,1,6=0,得,s,1,+,x,1,=6,或,x,1,=6,s,1,0,估計(jì),第一階段，即第4月份初庫存的可能,狀態(tài)：,0,s,1,306712=5，,所以，,s,1,0,5,9,第一階段最優(yōu)決策表,第二階段,：最大可能庫存量 7 件,由狀態(tài)轉(zhuǎn)移方程：,s,1,=,s,2,+,x,

6、2,12,0,及,x,2,10，,可知,s,2,2,7，min,x,2,=5,由階段效果遞推公式有：,f,2,(2,10)=,d,2,(2,10)+,f,1,*(0,6)=2,2+8010+456=1260,得第二,階段最優(yōu)決策表，如下,10,第二階段最優(yōu)決策表,第三階段,：最大可能庫存量 4 件,由狀態(tài)轉(zhuǎn)移方程：,s,2,=,s,3,+,x,3,7,2,及,x,3,10，,可知,s,3,0,4，min,x,3,=5,由階段效果遞推公式有：,f,3,(1,10)=,d,3,(1,10)+,f,2,*(4,8)=2,1+,7210+1104=1826,得第三,階段最優(yōu)決策表，如下,11,第三階段

7、最優(yōu)決策表,第四階段,：初始庫存量,s,4,=0,由狀態(tài)轉(zhuǎn)移方程：,s,3,=,s,4,+,x,4,6,0,可知,x,4,6，,由階段效果遞推公式有：,f,4,(0,6)=,d,4,(0,6)+,f,3,*(0,10)=,706+1902=2322,得第四,階段最優(yōu)決策表，如下,回,溯,得,此,表,12,例,2,生產(chǎn)庫存管理問題,(,連續(xù)變量,),設(shè)某廠計(jì)劃全年生產(chǎn)某種產(chǎn)品,A。,其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品,A,的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)有倉庫可存放產(chǎn)品，存儲費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最

8、小。,解,：四個季度為四個階段，采用階段編號與季度順序一致。,設(shè),s,k,為第,k,季初的庫存量，則邊界條件為,s,1,=,s,5,=0,設(shè),x,k,為第,k,季的,生產(chǎn),量，,設(shè),y,k,為第,k,季的訂貨量；,s,k,，,x,k,，,y,k,都取實(shí)數(shù)，狀態(tài)轉(zhuǎn)移方程為,s,k,+1,=,s,k,+,x,k,-,y,k,仍采用反向遞推，但注意階段編號是正向的,目標(biāo)函數(shù)為,13,例,2,生產(chǎn)庫存管理問題,(,連續(xù)變量,),第一步,：(第四季度)總效果,f,4,(,s,4,x,4,)=0.005,x,4,2,+,s,4,由邊界條件有：,s,5,=,s,4,+,x,4,y,4,=0，,解得：,x,4

9、,*=1200,s,4,將,x,4,*,代入,f,4,(,s,4,x,4,),得：,f,4,*(,s,4,)=0.005(1200,s,4,),2,+,s,4,=7200 11,s,4,+0.005,s,4,2,第二步,：(第三、四季度)總效果,f,3,(,s,3,x,3,)=0.005,x,3,2,+,s,3,+,f,4,*(,s,4,),將,s,4,=,s,3,+,x,3,500,代入,f,3,(,s,3,x,3,),得：,14,例,2,生產(chǎn)庫存管理問題,(,連續(xù)變量,),第三步,：(第二、三、四季度)總效果,f,2,(,s,2,x,2,)=0.005,x,2,2,+,s,2,+,f,3,

10、*(,s,3,),將,s,3,=,s,2,+,x,2,700,代入,f,2,(,s,2,x,2,),得：,注意,：階段最優(yōu)總效果僅是當(dāng)前狀態(tài)的函數(shù)，與其后的決策無關(guān),15,例,2,生產(chǎn)庫存管理問題,(,連續(xù)變量,),第四步,：(第一、二、三、四季度)總效果,f,1,(,s,1,x,1,)=0.005,x,1,2,+,s,1,+,f,2,*(,s,2,),將,s,2,=,s,1,+,x,1,600=,x,1,600,代入,f,1,(,s,1,x,1,),得：,由此,回溯,：得最優(yōu)生產(chǎn)庫存方案,x,1,*=600，,s,2,*=0；,x,2,*=700，,s,3,*=0；,x,3,*=800，,s

11、,4,*=300；,x,4,*=900。,16,5.2.2,資源分配問題,例3,某公司有9個推銷員在全國三個不同市場推銷貨物，這三個市場里推銷人員數(shù)與收益的關(guān)系如下表，試作出使總收益最大的分配方案。,解,：設(shè)分配人員的順序?yàn)槭袌?,2,3，采用反向階段編號。,設(shè),s,k,為第,k,階段尚未分配的人員數(shù)，邊界條件為,s,3,=9,設(shè),x,k,為第,k,階段分配的推銷人員數(shù)；,仍采用反向遞推，,狀態(tài)轉(zhuǎn)移方程為,s,k,1,=,s,k,x,k,目標(biāo)函數(shù)為,17,例3,第一階段：給第三市場分配,s,1,有,09種可能，第一階段最優(yōu)決策表如下：,為什么與,例1,的第一階段的表有差別？,因?yàn)椴淮嬖谶吔鐥l件

12、,s,0,=0,18,例3,第二階段：給第二市場分配,s,2,有,09種可能，第二階段最優(yōu)決策表如下：,19,例3,第三階段：給第一市場分配,由邊界條件,s,3,=9，,第三階段最優(yōu)決策表如下：,得決策過程：,x,3,*=2,x,2,*=0,x,1,*=7,f,3,*=218,即 市場1 分配 2人，市場2 不分配，市場3 分配 7人,最優(yōu)解與分配的順序有關(guān)嗎,？,20,5.2.2,資源分配問題,例4,項(xiàng)目選擇問題,某工廠預(yù)計(jì)明年有,A,B,C,D,四個新建項(xiàng)目，每個項(xiàng)目的投資額,w,k,及其投資后的收益,v,k,如右表所示。投資總額為30萬元，問如何選擇項(xiàng)目才能使總收益最大。,上述問題的靜態(tài)

13、規(guī)劃模型如下：,這是一類,0-1規(guī)劃問題,該問題是經(jīng)典的,旅行背包問題,(,Knapsack),該問題是,NP-complete,21,例,4,項(xiàng)目選擇問題,解,：設(shè)項(xiàng)目選擇的順序?yàn)?A,B,C,D;,1、,階段,k,=1,2,3,4,分別,對應(yīng),D,C,B,A,項(xiàng)目的選擇過程,2、第,k,階段的狀態(tài),s,k,，,代表第,k,階段初尚未分配的投資額,3、第,k,階段的決策變量,x,k,，,代表第,k,階段分配的投資額,4、,狀態(tài)轉(zhuǎn)移方程為,s,k,1,=,s,k,w,k,x,k,5、,直接效益,d,k,(,s,k,x,k,)=,v,k,或,0,6、總效益遞推公式,該問題的難點(diǎn)在于各階段的狀態(tài)的

14、確定，當(dāng)階段增加時(shí)，狀態(tài)數(shù)成指數(shù)增長。下面利用決策樹來確定各階段的可能狀態(tài)。,22,23,例,4,第一階段(項(xiàng)目,D,),的選擇過程,s,1,8,時(shí),，,x,1,只能取0；,w,1,=8,v,1,=5,24,例,4,第二階段(項(xiàng)目,C,),的選擇過程,25,例,4,第三階段(項(xiàng)目,B,),的選擇過程,第四階段(項(xiàng)目,A,),的選擇過程,26,5.2.3,串聯(lián)系統(tǒng)可靠性問題,例5,有,A,B,C,三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計(jì)結(jié)果表明，機(jī)器,A,B,C,產(chǎn)生次品的概率分別為,p,A,=30%,P,B,=40%,P,C,=20%,而產(chǎn)品必須經(jīng)過三部機(jī)器順序加工才能

15、完成。為了降低產(chǎn)品的次品率，決定撥款,5 萬元進(jìn)行技術(shù)改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)?，F(xiàn)提出如下四種改進(jìn)方案：,方案1:不撥款，機(jī)器保持原狀；,方案2:加裝監(jiān)視設(shè)備，每部機(jī)器需款 1 萬元；,方案3:加裝設(shè)備，每部機(jī)器需款 2 萬元；,方案4:同時(shí)加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款 3 萬元；,采用各方案后，各部機(jī)器的次品率如下表。,27,例,5,串聯(lián)機(jī)器可靠性問題,解,：為三臺機(jī)器分配改造撥款，設(shè)撥款順序?yàn)?A,B,C,，,階段序號反向編號為,k,，,即第一階段計(jì)算給機(jī)器,C,撥款的效果。,設(shè),s,k,為第,k,階段剩余款，則邊界條件為,s,3,=5,；,設(shè),x,k,為第,k,階段的

16、,撥款額,；,狀態(tài)轉(zhuǎn)移方程為,s,k,-1,=,s,k,-,x,k,；,目標(biāo)函數(shù)為,max,R,=(1-,P,A,)(1-,P,B,)(1-,P,C,),仍采用反向遞推,第一階段,：對機(jī)器,C,撥款的效果,R,1,(,s,1,x,1,)=,d,1,(,s,1,x,1,),R,0,(,s,0,x,0,)=,d,1,(,s,1,x,1,),28,第二階段最優(yōu)決策表,第二階段,：對機(jī)器,B,C,撥款的效果,由于機(jī)器,A,最多只需,3,萬元，故,s,2,2,遞推公式：,R,2,(,s,2,x,2,)=,d,2,(,s,2,x,2,),R,1,(,s,1,x,1,*),例：,R,2,(3,2)=,d,2,(3,2),R,1,(1,1)=(1-0.2),0.9=0.72,得,第二階段最優(yōu)決策表,29,第二階段最優(yōu)決策表,第三階段,：對機(jī)器,A,B,C,撥款的效果,邊界條件：,s,3,=5,遞推公式：,R,3,(,s,3,x,3,)=,d,3,(,s,3,x,3,),R,2,(,s,2,x,2,*),例：,R,3,(5,3)=,d,3,(5,3),R,2,(2,2)=(1-0.05),0.64=0.