運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(二)(名校講義).ppt_第1頁(yè)
運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(二)(名校講義).ppt_第2頁(yè)
運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(二)(名校講義).ppt_第3頁(yè)
運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(二)(名校講義).ppt_第4頁(yè)
運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(二)(名校講義).ppt_第5頁(yè)
已閱讀5頁(yè),還剩14頁(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)介

1、第十九講 動(dòng)態(tài)規(guī)劃(二),1 具有隱含階段和無(wú)限階段問(wèn)題的算法 2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(1),一、具有隱含階段(即階段有限,但不明顯) 動(dòng)態(tài)規(guī)劃法的一個(gè)重要環(huán)節(jié)是需有階段劃分,其中,轉(zhuǎn)移函數(shù)往往是從一個(gè)階段轉(zhuǎn)移到另一個(gè)階段。例如:xk+1=g(xk,uk,k), 表明從kk+1的轉(zhuǎn)變關(guān)系。顯然,這有明顯的階段劃分。 然而,轉(zhuǎn)移函數(shù)亦可定義為一個(gè)集合轉(zhuǎn)移到另一個(gè)集合,該轉(zhuǎn)移函數(shù)特點(diǎn)示于圖3-10。,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(2),非交叉集合的函數(shù)轉(zhuǎn)移,有明顯的劃分,簡(jiǎn)圖示于圖3-11。,例3-6敷設(shè)管道問(wèn)題(設(shè)無(wú)回路) 已

2、知從A到M的管道鋪設(shè)的可行路線及其費(fèi)用于圖3-12。 求從A到M的最低費(fèi)用鋪設(shè)線路。,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(3),解本問(wèn)題無(wú)明顯階段劃分,可令: 每個(gè)節(jié)點(diǎn)表示“狀態(tài)”。 節(jié)點(diǎn)鏈(管道)的選擇為決策變量。 其求解步驟如下: (i) I(M)=0(終端條件) (ii) 從M上推,找直接聯(lián)結(jié)的狀態(tài)點(diǎn),共有3個(gè)點(diǎn):J、K、L。它們到達(dá)終點(diǎn)的最小費(fèi)用為: I(J)=min2+ I(K),4+ I(M),2+ I(L)尚不確定 I(K)=min4+ I(M)=4 I(L)=min3+ I(M)=3 于是: I(J)=min2+4,4,2+3=4,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(4),

3、(iii)再?gòu)腏、K、L向前推 I(H)=min3+ I(K),3+ I(J)=min3+4,3+4=7 I(I)=min2+ I(L)=min2+3=5 全部計(jì)算結(jié)果示如圖3-13中。,圖中數(shù)字表示從該點(diǎn)到終點(diǎn)M鋪設(shè)管道的最低費(fèi)用。例如,A至M的最低費(fèi)用為14,其路線為:ABEGILM。,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(5),例3-7挑硬幣問(wèn)題 N個(gè)硬幣,有一枚較重,其它等重。現(xiàn)要求用等臂天平來(lái)選 出重幣。希確定出一定能找出這枚重幣的最少稱重次數(shù)。 解令:硬幣數(shù)為狀態(tài)變量x I(x)表示使用最優(yōu)策略在批量為x個(gè)硬幣中一定能找出重幣 中所需最少稱量次數(shù)。 u為決策變量,放在天平每邊的硬幣

4、數(shù)。 現(xiàn)分析每次u的最佳選擇。顯然,從x個(gè)硬幣中選出2u個(gè)硬 幣分放天平2邊,必有下述2種可能: 1)天平平衡,說(shuō)明重幣在剩余的(x2u)個(gè)硬幣中。 2)天平不平衡,說(shuō)明重幣在天平重的一邊的u個(gè)硬幣中。,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(6),因此,u的選擇應(yīng)符合下式: I(x)=1+ maxI(u),I(x2u) I(1)=0 (1) 式中加1,是因?yàn)镮(1)=0,而把x分成u及x2u,且找出硬 幣所在區(qū)需秤一次。 式(1)表明,需從I(u)和I(x2u)中選取最大者再取極小, 故應(yīng)選u使之I(u)盡量與I(x2u)相等,即: ux2u u x 故應(yīng)選u= 或 +1。,1 具有隱含階段和

5、無(wú)限階段問(wèn)題的算法(7),根據(jù)此法,對(duì)任何N都可用遞推公式求出。其公式為: 3k1x3k I(x)=k 即: k為log3x的最小整數(shù):x與I(x)的對(duì)應(yīng)見(jiàn)表3-8。,1 具有隱含階段和無(wú)限階段問(wèn)題的算法(8),表3-8 x與I(x)對(duì)應(yīng)表,二、無(wú)限階段過(guò)程(有明顯階段,但是階段數(shù)無(wú)限)(略),2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (1),解 顯然,該問(wèn)題從幾何圖形上無(wú)明顯階段劃分,路線中經(jīng)過(guò)幾點(diǎn)亦無(wú)限制,如果采用動(dòng)態(tài)規(guī)劃算法,必須加以處理。,本節(jié)不想從理論上推導(dǎo)這些方法,只準(zhǔn)備結(jié)合例題介紹這 些方法的步驟。 例3-9已知5個(gè)地區(qū)(點(diǎn))之間的距離示于圖3-14中。求任 一點(diǎn)到終點(diǎn)的最

6、短路線。,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (2),設(shè)各點(diǎn)之間的距離為cij,令f(i)為由i點(diǎn)出發(fā)到終點(diǎn)N的最短 距離,則知: f(i)=mincij+f(j) i=1,2,N1 f(N)=0 (cNN=0) 顯然,上述表達(dá)式在計(jì)算時(shí)會(huì)出現(xiàn)循環(huán)現(xiàn)象,不能采用簡(jiǎn) 單的遞推迭代,與第三節(jié)一樣,此處亦可采用函數(shù)迭代法 與策略迭代法。 一、函數(shù)迭代法 以段數(shù)(本例為到達(dá)終點(diǎn)容許經(jīng)過(guò)最多的點(diǎn)步數(shù))為參變 數(shù)。計(jì)算中,逐步求出只容許1步,然后只容許2步,直 至只容許N1步到達(dá)N點(diǎn)的最短路徑。具體步驟如下:,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (3),先選一個(gè)初始函數(shù)f1(i),

7、令每個(gè)點(diǎn)只許一步到達(dá)終點(diǎn)。即: f1(i)=ciN i=1,2,N1 f1(N)=0 i=N 遞推:令fk(i)表示k步內(nèi)到達(dá)的最短路徑。則: fk(i)= i=1,2,N1 fk(N)=0 結(jié)合本例計(jì)算。 1)只容許走一步到達(dá)=5點(diǎn)的各點(diǎn)對(duì)應(yīng)最短路線為: f1(i)=ci5 2)最多走兩步到達(dá)5點(diǎn)的各點(diǎn)對(duì)應(yīng)最短路線為: 設(shè)i=1,則f2(1)=,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (4),=minc11+f1(1),c12+f1(2),c13+f1(3),c14+f1(4),c15+f1(5) =min0+2,6+7,5+5,2+3,2+0 =2 同理,i=2,3,4時(shí)可得:f2

8、(2)=5.5,f2(3)=4,f2(4)=3。 3)f3(i)= 4)f4(i)= 由于f3=f4,故結(jié)束。具體結(jié)果示于表3-9。 不難看出: (i) fk(i)單調(diào)下降,且收斂于一固定值(即最優(yōu)解) (ii) fk(i)不超過(guò)N1步可收斂于f(i)(即最優(yōu)解),2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (5),表3-9 例3-9的函數(shù)迭代結(jié)果,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (6),二、策略迭代法 先給出初始策略u(píng)0(i),i=1,2,N1。然后逐步求新 策略,當(dāng)uk(i)=uk1(i)時(shí),即結(jié)束。其步驟為: 選一無(wú)回路的初始策略u(píng)0(i) ,i=1,2,N1,表 示

9、在此策略下i點(diǎn)應(yīng)到達(dá)的下一點(diǎn)。 由策略u(píng)k(i),求指標(biāo)值函數(shù)fk(i)。 fk(i)= i=1,2,N1;k=0,1,2 fk(N)=0 由fk(i),求策略u(píng)k+1(i),令 uk+1(i)=,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (7),返回,反復(fù)迭代,直到uk (i)= uk1(i)為止。此時(shí),uk (i), fk1(i)即為最優(yōu)策略及最優(yōu)目標(biāo)值。 用該法計(jì)算例3-9如下: 1)設(shè)初始無(wú)回路策略u(píng)0(i)為: u0(1)=5,u0(2)=4,u0(3)=5,u0(4)=3 2)由u0(i)計(jì)算f0(i) f0(i)= ,f0(5)=0 應(yīng)先算f0(1)和f0(3) f0(1)

10、= =c1,5+f0(5)=2 f0(3)=c3,5+f0(5)=5 f0(4)=c4,3+f0(3)=1+5=6 f0(2)=c2,4+f0(4)=5+6=11,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (8),3)由f0(i)求出u1(i),即: u1(i)= (令u(i)=j) j=1,2,N1 當(dāng)i=1,則: u1(1) =arg c11+f0(1),c12+f0(2),c13+f0(3),c14+f0(4),c15+f0(5) =arg 0+2,6+11,5+5,2+6,2+0 =arg2=5 同理可求得: u1(2)=3,u1(3)=5,u1(4)=5,2 不定期階段決策問(wèn)題的求解函數(shù)迭代與策略迭代 (9),即:u1(i)=5,3,5,5 然后,以這些策略求出f1(i

溫馨提示

  • 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)論