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

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(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)化問題的實(shí)例2基本概念、基本方程和優(yōu)化原理3動(dòng)態(tài)編程的應(yīng)用(1)4動(dòng)態(tài)編程的應(yīng)用(2)、2、實(shí)例1多級(jí)資源分配問題,將數(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)化問題實(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)因此,問題是,通過獲取y,y1,y2,yn-1,g(y)h(x-y)g(y1)h(x1-y1)g(yn-1)h(xn-)滿足條件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í)決策過程優(yōu)化問題的示例,討論:1,a到e的最短路徑問題可以轉(zhuǎn)換為具有

3、4個(gè)特性但大小較小的子問題,分別是Di,Ci,Bi,a到e的最短路徑問題。步驟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的最短路徑問題。表10-2分析結(jié)果:通過C1時(shí),最短路的是C1-D2-e;如果通過C2,則段落為C2-D2-e。通過C3時(shí),最短路徑為C3-D1-E。1多階段決策流程優(yōu)化問題實(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的最短路徑問題:表

4、10-3分析結(jié)果:經(jīng)過B1后的B1-C2-D2-e;B2-C3-D1-e(如果通過B2);通過B3時(shí)為B3-C3-D1-e;通過B4后,移至B4-C3-D1-E。1多級(jí)決策過程優(yōu)化問題的示例,第10,1步:只有一個(gè)起點(diǎn)a,結(jié)尾有B1、B2、B3和B4。分析和討論從a到B1、B2、B3、B4的最短路徑問題:表10-4中的最后,從a到e的最短路徑是AB4C3D1E,1多級(jí)決策過程優(yōu)化問題的示例,11,以上計(jì)算過程和結(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ài)xk 1=Tk(xk,Qk),并獲得利潤Rk(xk,Qk)。我們的目標(biāo)是從每一階段的決策集中選擇決策,以最大限度地提高每一階段的總利潤。這種多階段問題稱為動(dòng)態(tài)編程。2基本概念,基本方程和優(yōu)化原理,13,多階段決策過程,動(dòng)態(tài)規(guī)劃的分類:離散決策離散概率連續(xù)決策連續(xù)概率類型,決策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開始到最后n步的決策序列,稱為k子策略。P1,n(s1)是整體過程策略。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開始,選擇從決策xk生成的階段k指標(biāo)。流程指標(biāo)函數(shù)Vk,n(sk,xk,xk 1,xn):選擇從狀態(tài)sk開始由決策xk,xk 1,xn生成的流程指標(biāo)。動(dòng)態(tài)編程需要過程指標(biāo)的可分離性。也就是說,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開始,所有策略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)的遞歸方程,通過編寫上述表達(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è)過程結(jié)束的整體最優(yōu)函數(shù)。最短路徑問題的步長(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)的最短距離。最短路徑問題是該定線需要f1(A)。,20,動(dòng)態(tài)編程的基本思路,離散決策動(dòng)態(tài)編程解決,最短路徑問題,逆序方法:(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 從邊界條件開始逐步遞歸優(yōu)化,在解決每個(gè)子問題時(shí),使用前面確定的子問題的最佳結(jié)果,最后一個(gè)子問題的最佳解決方案,即整個(gè)問題的最佳解決方案(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 * * 在此最佳策略中,無論特定狀態(tài)的先前狀態(tài)和決定如何,該狀態(tài)的所有后續(xù)決定都必須構(gòu)成最佳子策略。也就是說最佳策略的任意球子策略都是最佳的。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 1的狀態(tài)計(jì)劃將5臺(tái)設(shè)備分配給公司所屬的a、b、c三家工廠。各工廠取得該設(shè)備后,可預(yù)

11、測(cè)的利潤如表10-5所示,問如何將這5個(gè)設(shè)備分配給這3個(gè)工廠,以最大限度地提高所造成的總利潤。表10-5,3動(dòng)態(tài)編程應(yīng)用程序(1),41,解決:將問題按工廠分為3個(gè)階段,a,b,c三個(gè)工廠分別編號(hào)為1,2,3個(gè)工廠。Sk=設(shè)置從第一個(gè)工廠到第三個(gè)工廠的指定設(shè)備表數(shù)(k=1、2、3)。Xk=分配給第k個(gè)設(shè)備數(shù)。已知S1=5和具有和的定義。在此,從第三步開始計(jì)算。步驟3(1)、42、3步驟:將設(shè)備分配給3工廠時(shí),步驟3的指標(biāo)值(工廠3的收益)最大。也就是說,所需的值為0,1,2,3,4,5,因?yàn)榈谌A段是最后一個(gè)階段。數(shù)值計(jì)算見表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è)備分配給第三工廠)是最佳決定,此時(shí)步驟指標(biāo)值(利潤)為12,最佳3子流程最佳指標(biāo)值也為12。步驟2:將設(shè)備分配給2工廠和3工廠時(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工廠是有利的??梢栽诒?06中確認(rèn)=11 .也可以知道當(dāng)時(shí);那時(shí);那時(shí);那時(shí);2由于工廠不能劃分5臺(tái)設(shè)備,所以車廂是空的,沒有裝滿。獲取這些值中最大的值。范例=16

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(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)論