第七章 運(yùn)籌學(xué) 動(dòng)態(tài)規(guī)劃.ppt

1、第六章 動(dòng)態(tài)規(guī)劃,多階段的決策問(wèn)題 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃基本方程 離散確定型動(dòng)態(tài)規(guī)劃模型的求解 連續(xù)確定型動(dòng)態(tài)規(guī)劃模型的求解 一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃求解法 背包問(wèn)題,教學(xué)目的與要求:使學(xué)生學(xué)會(huì)利用多階段問(wèn)題的決策思想處理一些簡(jiǎn)單的實(shí)際問(wèn)題,并會(huì)用WinQSB求解動(dòng)態(tài)規(guī)劃. 重點(diǎn)與難點(diǎn):重點(diǎn)是離散型資源分配問(wèn)題;難點(diǎn)是動(dòng)態(tài)規(guī)劃建模和求解方法. 教學(xué)方法:從多階段最短路引入基本概念和數(shù)學(xué)模型,再講解離散型DP和連續(xù)型DP. 思考題,討論題,作業(yè):本章習(xí)題. 參考資料:見前言. 學(xué)時(shí)分配:6學(xué)時(shí).,前言:動(dòng)態(tài)規(guī)劃是最優(yōu)化的一個(gè)分支,它是解決多階段決策過(guò)程最優(yōu)化的一種方法.動(dòng)態(tài)規(guī)劃的創(chuàng)始人是美國(guó)數(shù)

2、學(xué)家貝爾曼(R.Bellman).它在四十年代后期和五十年代初期在美國(guó)蘭德公司工作,針對(duì)一些多階段決策問(wèn)題提出了解決這類問(wèn)題的最優(yōu)化原理,并在1957年出版了動(dòng)態(tài)規(guī)劃的第一本書Dynamic programming.在企業(yè)管理方面,動(dòng)態(tài)規(guī)劃可以解決庫(kù)存問(wèn)題,資源分配問(wèn)題,設(shè)備更新問(wèn)題,運(yùn)輸問(wèn)題,生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題.它的弱點(diǎn)是,根據(jù)最優(yōu)化原理建立的動(dòng)態(tài)規(guī)劃基本方程,尚無(wú)統(tǒng)一的解法,而要根據(jù)其數(shù)學(xué)結(jié)構(gòu)靈活處理;此外,變量個(gè)數(shù)不能太多,否則計(jì)算量太大,這稱為維數(shù)問(wèn)題.,第一節(jié) 多階段決策問(wèn)題及實(shí)例,所謂多階段決策問(wèn)題,是指一個(gè)大問(wèn)題可以劃分為若干個(gè)階段,每個(gè)階段形成一個(gè)子問(wèn)題,各個(gè)階段是互相聯(lián)系的

3、,每個(gè)階段都要作出決策,并且一個(gè)階段的決策確定以后會(huì)影響下一階段的決策,從而影響整個(gè)過(guò)程的活動(dòng)路線.各個(gè)階段所確定的決策構(gòu)成一個(gè)決策序列,稱為一個(gè)策略,對(duì)于不同的策略其效果不同(效果可以用數(shù)量來(lái)衡量).多階段決策問(wèn)題就是選擇一個(gè)最優(yōu)策略,使在給定的標(biāo)準(zhǔn)下達(dá)到最好的效果.,典型例題:,例1 多階段網(wǎng)絡(luò)的最短路,狀態(tài)1,狀態(tài)2,狀態(tài)3,狀態(tài)4,終點(diǎn),例題特點(diǎn):, 階段:如圖的階段,分為四段;, 狀態(tài):頂點(diǎn);, 決策:選弧;, 轉(zhuǎn)移:從一個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn);, 目標(biāo):路長(zhǎng)最短.,例2 資源分配問(wèn)題,設(shè)有數(shù)量x的某種資源,將它投入兩種生產(chǎn)A,B.若以y投入生產(chǎn)A,剩下的x-y投入生產(chǎn)B,則收入函數(shù)為

4、g(y)+h(x-y),如果生產(chǎn)后可以回收再生產(chǎn),其回收率分別為0a,b1,則在第一階段生產(chǎn)后回收的總資源為 再將 投入生產(chǎn)A,B,若以 分別投入生產(chǎn)A,B則又可得收入 因此兩階段的總收入為,如果上面的過(guò)程進(jìn)行了n個(gè)階段,而且我們希望選擇 使n個(gè)階段的總收入最大,問(wèn)題變?yōu)?例題特點(diǎn):, 階段:年(月), 狀態(tài):資金數(shù), 決策:分配給A的資金數(shù), 轉(zhuǎn)移:, 效益:n個(gè)階段的總收入最大,第二節(jié) 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃基本方程,一. 動(dòng)態(tài)規(guī)劃的基本概念,階段(stage):是指一個(gè)問(wèn)題需要作出決策的步驟,用k表示階段數(shù),k稱為階段變量.通常以時(shí)間作為階段變量.,狀態(tài)(state):狀態(tài)表示在任一階段所

5、處的位置,通常一個(gè)階段有若干個(gè)狀態(tài),描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量,第k階段的狀態(tài)變量用 表示.狀態(tài)變量取值的全體稱為狀態(tài)空間或狀態(tài)集合.,在例1中各階段的狀態(tài)變量集合如下:,注意:狀態(tài)變量是動(dòng)態(tài)規(guī)劃中最關(guān)鍵的一個(gè)參數(shù),它既反映前面各階段決策的結(jié)局,又是本階段作出決策的出發(fā)點(diǎn),狀態(tài)是動(dòng)態(tài)規(guī)劃問(wèn)題各階段信息的傳遞點(diǎn)和結(jié)合點(diǎn).,決策(decision):決策是指某階段狀態(tài)給定后,從該階段演變到下一階段某狀態(tài)的選擇.決策變量 表示第k階段狀態(tài)為 時(shí)對(duì)方案的選擇. 表示k階段狀態(tài)為 時(shí)決策允許的取值集合.例如:例1中,策略(policy)和子策略(subpolicy):動(dòng)態(tài)規(guī)劃問(wèn)題各階段決策組成的序列

6、總體稱為一個(gè)策略.,是n個(gè)階段DP的一個(gè)策略.,狀態(tài)轉(zhuǎn)移律:從 的某一狀態(tài)值出發(fā),當(dāng)決策變量 的取值決定后,下一階段狀態(tài)變量 的取值也隨之確定.這種從上一階段的某一狀態(tài)值到下一階段某一狀態(tài)值的轉(zhuǎn)移規(guī)律稱為狀態(tài)轉(zhuǎn)變移律.可表示為,指標(biāo)函數(shù)(index function):指標(biāo)函數(shù)是用來(lái)衡量實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo).它是從狀態(tài) 出發(fā)至過(guò)程最終,當(dāng)采取某種策略時(shí),按預(yù)定標(biāo)準(zhǔn)得到的效益值,這個(gè)值既與 有關(guān),又與 以后所選取的策略有關(guān),它是兩者的函數(shù),稱為過(guò)程指標(biāo)函數(shù),記為 特別地,僅第k階段的指標(biāo)函數(shù),可記為,最優(yōu)指標(biāo)函數(shù):是指對(duì)某一確定狀態(tài)選取最優(yōu)策略后得到的指標(biāo)函數(shù)值,也就是對(duì)應(yīng)某一最優(yōu)子策略的

7、某種效益度量,這個(gè)度量值可以是成本,產(chǎn)量,距離等等.對(duì)應(yīng)于從狀態(tài) 出發(fā)的最優(yōu)子策略的效益值記為,其中optimization是最優(yōu)化的意思,在具體問(wèn)題中,可以是最小化(min)也可以是最大化(max).,二.最優(yōu)化原理與動(dòng)態(tài)規(guī)劃基本方程,貝爾曼(R.Bellman)最優(yōu)化原理:作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì),無(wú)論過(guò)去的狀態(tài)和決策如何,對(duì)先前決策所形成的狀態(tài)而言,余下的諸決策必構(gòu)成最優(yōu)策略.,根據(jù)這一原理,計(jì)算動(dòng)態(tài)規(guī)劃問(wèn)題的遞推關(guān)系式(逆序法)稱為動(dòng)態(tài)規(guī)劃基本方程:,其中, 稱為邊界條件.,用動(dòng)態(tài)規(guī)劃求解例1:,動(dòng)態(tài)規(guī)劃基本方程為:,2,5,1,12,14,10,6,10,4,13,11,

8、12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C

9、1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)

10、=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12

11、,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19

12、,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B2） B2 （B2，C1） C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,

13、C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,

14、f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 從A到E的最短路徑為19，路線為AB 2C1 D1 E,第三節(jié) 離散確定型動(dòng)態(tài)規(guī)劃模型的求解,例2 資源分配問(wèn)題:某公司有五套先進(jìn)設(shè)備,需分配給下屬的甲,乙,丙三個(gè)工廠,各工廠得此設(shè)備后每年為公司上繳的利潤(rùn)如下表,問(wèn)如何分配可使公司獲得最大利潤(rùn)?,解:將問(wèn)題按三個(gè)工廠分為三個(gè)階段,即k=1,2,3.,根據(jù)最優(yōu)化原理得出動(dòng)態(tài)規(guī)劃

15、基本方程:,動(dòng)態(tài)規(guī)劃的求解方法通常是采取逆序解法,即從第三階段向前推導(dǎo).,最優(yōu)方案一:甲廠0臺(tái),乙廠2臺(tái),丙廠3臺(tái); 最優(yōu)方案二:甲廠2臺(tái),乙廠2臺(tái),丙廠1臺(tái). 最大盈利值為21萬(wàn)元.,第四節(jié) 連續(xù)確定型動(dòng)態(tài)規(guī)劃模型的求解,例3 (p208例5),解:階段變量是以年作為化分單位,k=1,2,3. 狀態(tài)變量 為k 年初可用于工作的完好機(jī)器數(shù).決策變量 為第k年用于完成A項(xiàng)任務(wù)的機(jī)器數(shù),則 為用于完成B項(xiàng)任務(wù)的機(jī)器數(shù).狀態(tài)轉(zhuǎn)移方程是 動(dòng)態(tài)規(guī)劃 基本方程及邊界條件為,當(dāng)k=3時(shí),當(dāng)k=2時(shí),當(dāng)k=1時(shí),第五節(jié) 一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法,用動(dòng)態(tài)規(guī)劃解數(shù)學(xué)規(guī)劃的方法是:把依次決定各個(gè)變量的取值看成

16、是一個(gè)多階段決策問(wèn)題,因而模型中含有幾個(gè)變量,就分為幾個(gè)階段,用狀態(tài)變量表示數(shù)學(xué)規(guī)劃中約束條件右邊常數(shù)項(xiàng),它表示可分配的資源數(shù).,例3 某投資者有40萬(wàn)元的固定資本,他可以在三種不同的投資機(jī)會(huì)中投資(股票,銀行,土地)投資額為x,y,z.假定他做過(guò)預(yù)測(cè),知道每項(xiàng)投資可獲得的效益分別為 問(wèn)如何分配投資額,才能獲得最大效益.,解:依題意,列出數(shù)學(xué)模型,設(shè),為決策變量,階段變量為k,k=1,2,3.,為狀態(tài)變量,即投放到第k個(gè)項(xiàng)目上的資金數(shù).狀態(tài) 轉(zhuǎn)移律為,效益函數(shù)為,.動(dòng)態(tài)規(guī)劃基本方程為,K=3,這是單增的線性函數(shù),它在區(qū)間右端點(diǎn)取得 最大值,顯然,時(shí),上式有最大值,.,K=2,設(shè),求其極大值,為極小值點(diǎn),則,當(dāng)k=1時(shí),若,=,為一常數(shù),不存在極值,舍去.若,設(shè),1600.,例4 用動(dòng)態(tài)規(guī)劃求解非線性規(guī)劃,解:把確定 的值看作