廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃_第1頁(yè)
廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃_第2頁(yè)
廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃_第3頁(yè)
廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃_第4頁(yè)
廣東工業(yè)大學(xué) 管理運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃_第5頁(yè)
已閱讀5頁(yè),還剩98頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、第1、10章動(dòng)態(tài)編程,1多級(jí)決策流程優(yōu)化問(wèn)題的實(shí)例2基本概念、基本方程和優(yōu)化原理3動(dòng)態(tài)編程的應(yīng)用(1)4動(dòng)態(tài)編程的應(yīng)用(2)、2、實(shí)例1多級(jí)資源分配問(wèn)題,將數(shù)量為x的特定資源投入到兩種生產(chǎn)方法a和b中:將數(shù)量y投入到生產(chǎn)方法a中,剩下的投入到生產(chǎn)方法b中,收入g其中g(shù)(y)和h(y)是已知函數(shù),g(0)=h(0)=0;另外,假設(shè)您可以用y和x-y分別投入兩種生產(chǎn)方法a,b可以用a和b的回收率回收再生產(chǎn)。尋找步驟n后的最大總收入。1多階段決策流程優(yōu)化問(wèn)題實(shí)例,3,實(shí)例1繼續(xù)(1),分別以y和x-y的形式投入生產(chǎn)方法a和b,在步驟1中投入生產(chǎn)后回收的資源合計(jì)為x1=ay b(x-y),x1投入生產(chǎn)

2、方法a和b,則收入g(y1) h(x1)因此,問(wèn)題是,通過(guò)獲取y,y1,y2,yn-1,g(y)h(x-y)g(y1)h(x1-y1)g(yn-1)h(xn-)滿(mǎn)足條件x1=ayb(x-y)x2=ay1b(x1-y1)xn-1=ayn-2b(xn-2-yn-2)yi和Xi不是負(fù)值求從a到e的最短路徑。b,c,b,d,d,e,c,k值增加時(shí),所需的添加和比較次數(shù)會(huì)快速增加。例如,當(dāng)k=20時(shí),加法比較為4.2550833962771015次,1.3726007547297717114次。計(jì)算1億次/秒需要大約508天。7,1多級(jí)決策過(guò)程優(yōu)化問(wèn)題的示例,討論:1,a到e的最短路徑問(wèn)題可以轉(zhuǎn)換為具有

3、4個(gè)特性但大小較小的子問(wèn)題,分別是Di,Ci,Bi,a到e的最短路徑問(wèn)題。步驟4:兩個(gè)起點(diǎn)D1和D2,只有一個(gè)終點(diǎn);表10-1分析發(fā)現(xiàn)D1和D2到e的最短路徑是唯一的。步驟、8和3:有三個(gè)起點(diǎn):C1、C2、C3、D1和D2,分別分析和討論C1、C2和C3中D1和D2的最短路徑問(wèn)題。表10-2分析結(jié)果:通過(guò)C1時(shí),最短路的是C1-D2-e;如果通過(guò)C2,則段落為C2-D2-e。通過(guò)C3時(shí),最短路徑為C3-D1-E。1多階段決策流程優(yōu)化問(wèn)題實(shí)例,第9,2階段:4個(gè)起點(diǎn)B1、B2、B3、B4,終點(diǎn)C1、C2、C3。分析和討論起點(diǎn)和終點(diǎn),分別從B1、B2、B3、B4到C1、C2和C3的最短路徑問(wèn)題:表

4、10-3分析結(jié)果:經(jīng)過(guò)B1后的B1-C2-D2-e;B2-C3-D1-e(如果通過(guò)B2);通過(guò)B3時(shí)為B3-C3-D1-e;通過(guò)B4后,移至B4-C3-D1-E。1多級(jí)決策過(guò)程優(yōu)化問(wèn)題的示例,第10,1步:只有一個(gè)起點(diǎn)a,結(jié)尾有B1、B2、B3和B4。分析和討論從a到B1、B2、B3、B4的最短路徑問(wèn)題:表10-4中的最后,從a到e的最短路徑是AB4C3D1E,1多級(jí)決策過(guò)程優(yōu)化問(wèn)題的示例,11,以上計(jì)算過(guò)程和結(jié)果如圖2所示,上述方法不僅可以獲得從a到d的最短路徑,還可以獲得從圖中任意點(diǎn)到e的最短路徑只用了22次加法,計(jì)算效率遠(yuǎn)高于宮法。b,c,b,d,d,e,c,對(duì)于每個(gè)階段k的每個(gè)狀態(tài),如

5、果在決策集Qk(xk)、Qk(xk)中選擇決策qkQk(xk),則狀態(tài)xk將轉(zhuǎn)換為新?tīng)顟B(tài)xk 1=Tk(xk,Qk),并獲得利潤(rùn)Rk(xk,Qk)。我們的目標(biāo)是從每一階段的決策集中選擇決策,以最大限度地提高每一階段的總利潤(rùn)。這種多階段問(wèn)題稱(chēng)為動(dòng)態(tài)編程。2基本概念,基本方程和優(yōu)化原理,13,多階段決策過(guò)程,動(dòng)態(tài)規(guī)劃的分類(lèi):離散決策離散概率連續(xù)決策連續(xù)概率類(lèi)型,決策1,決策2,決策n,14,狀態(tài)可以是數(shù)量或文字,數(shù)量狀態(tài)可以是連續(xù)的或不連續(xù)的。3,決定xk:從一個(gè)狀態(tài)切換到下一個(gè)狀態(tài)時(shí)所做的選擇。決定是該狀態(tài)的函數(shù),以xk(sk)表示。決策允許集Dk(sk):狀態(tài)sk中決策的完全允許。4,poli

6、cy Pk,n(sk):從步驟k開(kāi)始到最后n步的決策序列,稱(chēng)為k子策略。P1,n(s1)是整體過(guò)程策略。5,狀態(tài)轉(zhuǎn)移方程sk 1=Tk(sk,xk):狀態(tài)及其狀態(tài)的決策和下一狀態(tài)之間的函數(shù)關(guān)系。2基本概念,基本方程和優(yōu)化原理,17,6,階段索引函數(shù)vk(sk,xk):從狀態(tài)sk開(kāi)始,選擇從決策xk生成的階段k指標(biāo)。流程指標(biāo)函數(shù)Vk,n(sk,xk,xk 1,xn):選擇從狀態(tài)sk開(kāi)始由決策xk,xk 1,xn生成的流程指標(biāo)。動(dòng)態(tài)編程需要過(guò)程指標(biāo)的可分離性。也就是說(shuō),vk,n (sk,xk,xk 1,xn)=vk (sk,xk) vk1 (sk 1,xk 1,xn)是指標(biāo)相加或vk,n()最佳指

7、數(shù)函數(shù)fk(sk):從狀態(tài)sk開(kāi)始,所有策略Pk,n,流程指標(biāo)Vk,n的最佳值為2基本概念,基本方程和優(yōu)化原理,18,可加指數(shù)函數(shù)的常識(shí)是自下而上的“opt”是“max”或“min”對(duì)于乘法指數(shù)函數(shù),常識(shí)是動(dòng)態(tài)編程最佳指標(biāo)的遞歸方程,通過(guò)編寫(xiě)上述表達(dá)式,是動(dòng)態(tài)編程的基本方程。端子條件:為了使上述遞歸方程具有遞歸起點(diǎn),必須設(shè)置最佳指標(biāo)的端子條件,通常在最后狀態(tài)n 1下的最佳指數(shù)fn 1(sn 1)=0。2基本概念,基本方程和優(yōu)化原理,19,特別是f1(s1),是從初始狀態(tài)s1到整個(gè)過(guò)程結(jié)束的整體最優(yōu)函數(shù)。最短路徑問(wèn)題的步長(zhǎng)指標(biāo)函數(shù)是兩點(diǎn)之間的距離。后子程序pk,n的指數(shù)函數(shù)Vk,n(sk,pk,

8、n)是k步長(zhǎng)從點(diǎn)sk到端點(diǎn)的距離,fk(sk)是到端點(diǎn)的最短距離。最短路徑問(wèn)題是該定線(xiàn)需要f1(A)。,20,動(dòng)態(tài)編程的基本思路,離散決策動(dòng)態(tài)編程解決,最短路徑問(wèn)題,逆序方法:(10),(4),(3),(7),(5),(5),(5) k=4s 4=D1、D2、D3、x * 4 (D1)=E1、x * 4 (D2)=E2、x * 4 (D3)=E1、23 k=1 S1=a,x * 1 (a)=B1,26,x * 3 (C4)=D3,k=2 S2=B1,B2,x * 2 (B1) x * 4 (D2)=E2,x * 4 (D3)=E1,29,k=5 S5=E1,e2f 5 (E1)=d (E1,F(xiàn)

9、) x * 1(A)=b1x * 2(B1)=c2x * 3(C2)=d2x * 4(D2)=e2x * 5(E2)=f,F(xiàn)1 從邊界條件開(kāi)始逐步遞歸優(yōu)化,在解決每個(gè)子問(wèn)題時(shí),使用前面確定的子問(wèn)題的最佳結(jié)果,最后一個(gè)子問(wèn)題的最佳解決方案,即整個(gè)問(wèn)題的最佳解決方案(3)段的最佳決定選擇,通常與段的最佳選擇不同,整體考慮,動(dòng)態(tài)編程方法的基本思路,32,動(dòng)態(tài)編程方法:(1)逆序法,(2)順序法Fk(sk 1)是從起點(diǎn)a到階段k狀態(tài)sk 1的最短距離k=0f0(a)=0k=1 f1(B1)=4x * 1(B1)=af1(B2)=5x * 1 k=3 F3(D1)=11x * 3(D1)=C1/C2 F

10、3(D2)=12x * 3(D2)=c2f3 F3(D3)=11x * * 在此最佳策略中,無(wú)論特定狀態(tài)的先前狀態(tài)和決定如何,該狀態(tài)的所有后續(xù)決定都必須構(gòu)成最佳子策略。也就是說(shuō)最佳策略的任意球子策略都是最佳的。37,順序法,逆序適用的條件:(1)給出初始狀態(tài),逆序法(2)可以使用退出狀態(tài),順序法(3)可以使用初始狀態(tài)和退出狀態(tài),可以使用,劃分38,1,建模(1)階段sk 1=Tk(sk,xk)sk=Tk(sk 1,Xk)(3)指數(shù)函數(shù)fk(sk):步驟k,從sk到端點(diǎn)的最佳收益值fk(sk 1):從開(kāi)始到步驟k 1的狀態(tài)計(jì)劃將5臺(tái)設(shè)備分配給公司所屬的a、b、c三家工廠(chǎng)。各工廠(chǎng)取得該設(shè)備后,可預(yù)

11、測(cè)的利潤(rùn)如表10-5所示,問(wèn)如何將這5個(gè)設(shè)備分配給這3個(gè)工廠(chǎng),以最大限度地提高所造成的總利潤(rùn)。表10-5,3動(dòng)態(tài)編程應(yīng)用程序(1),41,解決:將問(wèn)題按工廠(chǎng)分為3個(gè)階段,a,b,c三個(gè)工廠(chǎng)分別編號(hào)為1,2,3個(gè)工廠(chǎng)。Sk=設(shè)置從第一個(gè)工廠(chǎng)到第三個(gè)工廠(chǎng)的指定設(shè)備表數(shù)(k=1、2、3)。Xk=分配給第k個(gè)設(shè)備數(shù)。已知S1=5和具有和的定義。在此,從第三步開(kāi)始計(jì)算。步驟3(1)、42、3步驟:將設(shè)備分配給3工廠(chǎng)時(shí),步驟3的指標(biāo)值(工廠(chǎng)3的收益)最大。也就是說(shuō),所需的值為0,1,2,3,4,5,因?yàn)榈谌A段是最后一個(gè)階段。數(shù)值計(jì)算見(jiàn)表106。3動(dòng)態(tài)編程的應(yīng)用(1),43,表106,3動(dòng)態(tài)編程的應(yīng)用(1

12、),44。其中表示采取3個(gè)子流程的最佳指標(biāo)值時(shí)的決定。例如,如表10-6所示,=4,此時(shí)(將4臺(tái)設(shè)備分配給第三工廠(chǎng))是最佳決定,此時(shí)步驟指標(biāo)值(利潤(rùn))為12,最佳3子流程最佳指標(biāo)值也為12。步驟2:將設(shè)備分配給2工廠(chǎng)和3工廠(chǎng)時(shí),每個(gè)值的最佳分配方案是最大收益,即最佳2子流程最佳指數(shù)函數(shù)值,3動(dòng)態(tài)編程的應(yīng)用(1),45。這是因?yàn)榭梢杂?jì)算值,例如表107。表107,3動(dòng)態(tài)編程應(yīng)用程序(1),46,這里,如表105所示,將一臺(tái)設(shè)備移交給b工廠(chǎng)是有利的。可以在表106中確認(rèn)=11 .也可以知道當(dāng)時(shí);那時(shí);那時(shí);那時(shí);2由于工廠(chǎng)不能劃分5臺(tái)設(shè)備,所以車(chē)廂是空的,沒(méi)有裝滿(mǎn)。獲取這些值中最大的值。范例=16

13、。在這一行,我們?cè)谧畲蟮闹瞪霞铀絹?lái)表示差異。也可以看出,此時(shí)最好的決定是1或2。3動(dòng)態(tài)編程的應(yīng)用(1),47,步驟1:1,2,3將設(shè)備分配給工廠(chǎng)時(shí),最大收益是優(yōu)選值0,1,2,3,4,5。值計(jì)算參照表108中的表10-8,然后按計(jì)算表的順序計(jì)算。1.據(jù)了解,調(diào)查表107是已知的,然后得到的。被分配到0家工廠(chǎng),2家b工廠(chǎng),3家c工廠(chǎng)。2.根據(jù),表107分配給,3動(dòng)態(tài)編程應(yīng)用程序(1),48,知道,因?yàn)樗玫搅耍矗?個(gè)a工廠(chǎng),2個(gè)b工廠(chǎng),1個(gè)c工廠(chǎng)。兩種分配方案都能獲得最高總利潤(rùn)21萬(wàn)元。3動(dòng)態(tài)編程應(yīng)用(1),49,2,背包問(wèn)題各有無(wú)限數(shù)量的n個(gè)項(xiàng)目。我的I項(xiàng)是每件重量wi公斤,每件價(jià)值ci元。現(xiàn)

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 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ì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。