第8章 動(dòng)態(tài)規(guī)劃11-5-8_第1頁(yè)
第8章 動(dòng)態(tài)規(guī)劃11-5-8_第2頁(yè)
第8章 動(dòng)態(tài)規(guī)劃11-5-8_第3頁(yè)
第8章 動(dòng)態(tài)規(guī)劃11-5-8_第4頁(yè)
第8章 動(dòng)態(tài)規(guī)劃11-5-8_第5頁(yè)
已閱讀5頁(yè),還剩31頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第八章動(dòng)態(tài)規(guī)劃北京物資學(xué)院運(yùn)籌學(xué)教學(xué)課件北京物資學(xué)院信息學(xué)院2011-5-8動(dòng)態(tài)規(guī)劃多階段決策問(wèn)題最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃模型的建立與求解多階段決策問(wèn)題

動(dòng)態(tài)規(guī)劃是一種研究多階段決策問(wèn)題的理論和方法。

多階段決策問(wèn)題是指一類活動(dòng)過(guò)程,它可以分為若干個(gè)相互聯(lián)系的階段,在每個(gè)階段都需要作出決策。這個(gè)決策不僅決定這一階段的效益,而且決定下一階段的初始狀態(tài)。

策略:每個(gè)階段的決策確定以后,就得到一個(gè)決策序列,稱為策略。多階段決策問(wèn)題就是求一個(gè)策略,使各階段的總效益達(dá)到最優(yōu)。例1最短路問(wèn)題設(shè)有一個(gè)旅行者從下圖中的A點(diǎn)出發(fā),途中要經(jīng)過(guò)B、C、D等處,最后到達(dá)終點(diǎn)E。從A到E有很多條路線可以選擇,各點(diǎn)之間的距離如圖所示,問(wèn)該旅行者應(yīng)該選擇哪一條路線,才能使從A到達(dá)E的總行程最短?AB1B2B3C3C2C1D1D2E25375632451514633334狀態(tài)A決策階段1狀態(tài)B1階段2決策狀態(tài)D1狀態(tài)C3階段3決策階段4決策狀態(tài)E行程1行程2行程3行程4例2多階段資源分配問(wèn)題

設(shè)有某種機(jī)器設(shè)備,可用于完成兩類工作A和B。若第k年初完好機(jī)器的數(shù)量為sk,若以數(shù)量xk用于工作A,余下的sk-xk用于工作B,則該年的預(yù)期收入為g(xk)+h(sk-xk),其中g(shù)(xk)

和h(sk-xk)

是已知函數(shù),并且g(0)=h(0)=0。又機(jī)器設(shè)備在使用中會(huì)有損壞,設(shè)機(jī)器用于工作A時(shí),一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的a倍(0<a<1),若用于工作B時(shí),一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的b倍(0<b<1),即下一年初能繼續(xù)用于完成這兩項(xiàng)工作的機(jī)器數(shù)為sk+1=axk+b(sk-xk)。設(shè)第一年初完好的機(jī)器數(shù)為s1,問(wèn)在連續(xù)三年內(nèi),每年應(yīng)如何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù),才能使三年的總收益達(dá)到最大。狀態(tài)S1決策第一年階段1狀態(tài)S2第二年階段2決策狀態(tài)S4狀態(tài)S3第三年階段3決策收益1收益2收益3最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃問(wèn)題的解題思路動(dòng)態(tài)規(guī)劃的基本概念最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃模型的分類動(dòng)態(tài)規(guī)劃問(wèn)題的解題思路思路:將一個(gè)n階段的決策問(wèn)題轉(zhuǎn)化為依次求n個(gè)具有遞推關(guān)系的單階段決策問(wèn)題,從而簡(jiǎn)化計(jì)算。在例1中,這種轉(zhuǎn)化的實(shí)現(xiàn)是從終點(diǎn)E出發(fā)一步步進(jìn)行反推(逆序算法)(1)考慮一個(gè)階段的選擇。到達(dá)E之前,上一步必然到達(dá)D1或D2,D1到E的最優(yōu)策略是:D1E,距離d(D1,E)=3,記f(D1)=3.D2到E的最優(yōu)策略是:D2E,距離d(D2,E)=4,記f(D2)=4.1AB1B2B3C3C2C1D1D2E2537563245154633334(2)聯(lián)合考慮兩個(gè)階段的最優(yōu)選擇。當(dāng)旅行者離終點(diǎn)還有兩站時(shí),他必然處在C1,C2或C3的某一點(diǎn)上。C1到終點(diǎn)的路有兩條:C1D1E,C1D2E,旅行者從這兩條路線中選最短的一條,并且不管是經(jīng)過(guò)D1或D2,到達(dá)該點(diǎn)后,他應(yīng)循著從D1或D2到E的最短路線繼續(xù)走。因此從C1到E的最短路程為:即從C1到E的最短路線為C1D1E,記如果從C2出發(fā)如果從C3出發(fā)(3)再聯(lián)合起來(lái)考慮三個(gè)階段的最優(yōu)選擇。從B1點(diǎn)出發(fā)的最優(yōu)選擇為從B2點(diǎn)出發(fā)的最優(yōu)選擇為從B3點(diǎn)出發(fā)的最優(yōu)選擇為(4)四個(gè)階段聯(lián)合考慮時(shí)從A到E的最優(yōu)選擇。從A到E的最短路線為AB3C2D2E,距離為11。1AB1B2B3C3C2C1D1D2E253756324515463333434476117811以上計(jì)算過(guò)程可以在圖上通過(guò)標(biāo)號(hào)法實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的基本概念1.階段(stage):指一個(gè)問(wèn)題需要作出決策的步數(shù)。

通常用k表示問(wèn)題的階段數(shù)。階段一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分的。2.狀態(tài)(state):表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件,它描述了研究問(wèn)題過(guò)程的狀況,是動(dòng)態(tài)規(guī)劃中最關(guān)鍵的一個(gè)參數(shù)。它既反映前面各個(gè)階段決策的結(jié)局,又是本階段決策的出發(fā)點(diǎn)和依據(jù)。它是動(dòng)態(tài)規(guī)劃問(wèn)題各個(gè)階段信息的傳遞點(diǎn)和結(jié)合點(diǎn)。通常一個(gè)階段有多個(gè)狀態(tài)。如例1中第一階段有1個(gè)狀態(tài),A.第三階段有三個(gè)狀態(tài)C1,C2,C3。狀態(tài)變量:描述狀態(tài)的變量??梢允菙?shù)、數(shù)組或向量。通常用Sk表示k階段的狀態(tài)集。如例1中S3={C1,C2,C3}.狀態(tài)的性質(zhì):無(wú)后效性。3.決策(decision)

是指某階段初從給定的狀態(tài)出發(fā),決策者在面臨的若干種不同方案中做出的選擇。決策變量xk(sk)表示第k階段狀態(tài)為sk時(shí)對(duì)方案的選擇。用Dk(sk)表示在第k階段狀態(tài)為sk時(shí)決策允許的取值范圍,稱為允許決策集合。即xk(sk)Dk(sk)。

D2(B1)={C1,C2,C3}

xk*(sk)表示第k階段狀態(tài)為sk時(shí)的最優(yōu)決策。決策的性質(zhì):第k階段某一狀態(tài)下的決策直接決定第k+1階段的狀態(tài)。4.策略(policy)和子策略(subpolicy):策略:多階段決策過(guò)程中,由各階段決策組成的序列總體稱作一個(gè)策略(全過(guò)程策略)。

{x1(s1),x2(s2),…,xn(sn)}從過(guò)程的某一階段開(kāi)始到過(guò)程最終階段結(jié)束的決策序列稱為問(wèn)題的子過(guò)程策略或子策略。從k階段起的子策略可以寫(xiě)為{xk(sk),xk+1(sk+1),…,xn(sn)}每一階段有若干狀態(tài),每個(gè)狀態(tài)又有若干不同的決策,從而形成許多可供選擇的策略(子策略),能使預(yù)期目標(biāo)達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略(子策略)。

5.狀態(tài)轉(zhuǎn)移方程從第k階段的狀態(tài)sk到第k+1階段的狀態(tài)sk+1的演變過(guò)程的解析表達(dá)式。記為:或簡(jiǎn)寫(xiě)為

狀態(tài)轉(zhuǎn)移方程6.指標(biāo)函數(shù)階段的指標(biāo)函數(shù):用來(lái)衡量每一階段決策效果優(yōu)劣的數(shù)量指標(biāo)。階段指標(biāo)函數(shù)是狀態(tài)變量和決策變量的函數(shù),即vk(sk,xk)。過(guò)程的指標(biāo)函數(shù):從第k階段的狀態(tài)sk

出發(fā)到過(guò)程的最后階段結(jié)束,當(dāng)采取某種子策略時(shí),按預(yù)定標(biāo)準(zhǔn)得到的效益值,稱為過(guò)程指標(biāo)函數(shù)。過(guò)程指標(biāo)函數(shù)值取決于從第k階段到最后階段所采取的子策略,它是sk和子策略的函數(shù)值。記作根據(jù)實(shí)際問(wèn)題的性質(zhì),過(guò)程指標(biāo)函數(shù)可以是各個(gè)階段指標(biāo)函數(shù)的和或積。最優(yōu)指標(biāo)函數(shù):從狀態(tài)sk出發(fā),選取最優(yōu)子策略所得到的指標(biāo)函數(shù)值稱為最優(yōu)指標(biāo)函數(shù)值,記作fk(sk).

Opt代表最優(yōu)化,可以是min或max狀態(tài)s1決策x1(s1)階段1T(S1,x1)狀態(tài)s2階段2T(S2,x2)決策x2(s2)階段nT(Sn,xn)狀態(tài)sn決策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型最優(yōu)化原理:作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì),即無(wú)論過(guò)去的狀態(tài)和決策如何,對(duì)先前決策所形成的狀態(tài)而言,余下的諸決策必構(gòu)成最優(yōu)策略。作為全過(guò)程的最優(yōu)策略的組成部分的任一后部子策略一定是從該狀態(tài)出發(fā)至終點(diǎn)的最優(yōu)子策略。逆序解法:逆著階段順序的方向,由后向前推算。求解思路:從最后一個(gè)階段開(kāi)始,逆著過(guò)程的進(jìn)展方向依次求出各階段的各個(gè)狀態(tài)對(duì)應(yīng)的最優(yōu)子策略。每一階段的求解過(guò)程都是在其后部子過(guò)程最優(yōu)子策略的基礎(chǔ)上,再考慮本階段的指標(biāo)函數(shù),求出本階段的最優(yōu)策略。直到求出整個(gè)過(guò)程的最優(yōu)策略為止?;具f推方程據(jù)最優(yōu)性原理,階段k的階段指標(biāo)值vk(sk)加上(或乘以)從下一階段k+1開(kāi)始到過(guò)程結(jié)束采取最優(yōu)策略取得的最優(yōu)指標(biāo)函數(shù)值fk+1(sk+1)

,再?gòu)闹羞x出最優(yōu),便是階段k從狀態(tài)sk出發(fā)到全過(guò)程結(jié)束的最優(yōu)指標(biāo)函數(shù)值。狀態(tài)s1決策x1(s1)階段1T(S1,x1)狀態(tài)s2階段2T(S2,x2)決策x2(s2)階段nT(Sn,xn)狀態(tài)sn決策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)尋求最優(yōu)解的方向遞推方程邊界條件動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型:建模步驟(小結(jié))劃分階段,確定階段變量k。確定狀態(tài)變量sk。確定決策變量xk和允許決策集合Dk(xk)寫(xiě)出狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,

xk

)寫(xiě)出指標(biāo)函數(shù)的基本遞推方程明確邊界條件

動(dòng)態(tài)規(guī)劃模型的分類按過(guò)程演變特征:確定性動(dòng)態(tài)規(guī)劃隨機(jī)性動(dòng)態(tài)規(guī)劃根據(jù)狀態(tài)變量:離散型動(dòng)態(tài)規(guī)劃連續(xù)型動(dòng)態(tài)規(guī)劃

過(guò)程變量確定隨機(jī)離散離散確定型離散隨機(jī)型連續(xù)連續(xù)確定型連續(xù)隨機(jī)型動(dòng)態(tài)規(guī)劃模型的建立與求解例3:某一警衛(wèi)部門(mén)共有9支巡邏隊(duì),負(fù)責(zé)3個(gè)要害部位A、B、C的警衛(wèi)巡邏。每個(gè)部位可分別派出2--4支巡邏隊(duì),并且由于派出巡邏隊(duì)數(shù)的不同,各部位預(yù)期在一段時(shí)間內(nèi)可能造成的損失有差別,具體數(shù)字見(jiàn)下表1,問(wèn)警衛(wèi)部門(mén)應(yīng)往各部位分別派多少支巡邏隊(duì),才能使總的預(yù)期損失為最少?213110422351432438182CBA預(yù)期損失部位巡邏隊(duì)數(shù)表1解:把9支巡邏隊(duì)派往3個(gè)部位看成依次分三個(gè)階段(用k表示,k=1,2,3)。狀態(tài)變量sk:每個(gè)階段初擁有的可派遣的巡邏隊(duì)數(shù)。決策變量xk:每個(gè)階段對(duì)相應(yīng)部位派出的巡邏隊(duì)數(shù)。狀態(tài)轉(zhuǎn)移方程:決策變量x1x2x3狀態(tài)變量允許集95,6,72,3,4,5決策變量允許集2,3,42,3,42,3,4狀態(tài)變量S1S2S3狀態(tài)轉(zhuǎn)移方程S1=9S2=S1-x1S3=S2-x2階段123若用pk(xk)表示k階段派出巡邏隊(duì)數(shù)為xk時(shí),該階段的部位預(yù)期損失值,則過(guò)程的指標(biāo)函數(shù)可寫(xiě)成因此有k=3時(shí),考慮對(duì)C部位派巡邏隊(duì)k=4時(shí),k=2時(shí),聯(lián)合考慮對(duì)B,C兩個(gè)部位派巡邏隊(duì)k=1時(shí),對(duì)A,B,C三個(gè)部位派巡邏隊(duì)例4.投資問(wèn)題現(xiàn)有資金5萬(wàn)元,可對(duì)三個(gè)項(xiàng)目進(jìn)行投資,投資額均為整數(shù)(單位為萬(wàn)元),其中第二項(xiàng)目投資不得超過(guò)3萬(wàn)元,第一和第三項(xiàng)目投資不得超過(guò)4萬(wàn)元,第三項(xiàng)目投資至少要1萬(wàn)元,每個(gè)項(xiàng)目投資五年后,預(yù)計(jì)可獲得的收益由下表給出,問(wèn)如何投資可望獲得最大的利潤(rùn)?

投資額收益項(xiàng)目01234項(xiàng)目10361012項(xiàng)目2051012項(xiàng)目3481115解:這個(gè)問(wèn)題用動(dòng)態(tài)規(guī)劃求解,可分為3個(gè)階段,k=1,2,3.狀態(tài)變量Sk:

第k階段初擁有的資金額。(可用于第k,k+1,..3項(xiàng)目的投資額)決策變量xk(Sk

):對(duì)第

k

個(gè)項(xiàng)目的投資額.狀態(tài)轉(zhuǎn)移方程:Sk+1

=Sk

-xk決策變量x1x2x3狀態(tài)變量允許集51,2,3,4,51,2,3,4,5決策變量允

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論