版權(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ī)劃,第一節(jié):現(xiàn)實(shí)中的動(dòng)態(tài)規(guī)劃問(wèn)題 第二節(jié):動(dòng)態(tài)規(guī)劃基本概念 第三節(jié):動(dòng)態(tài)規(guī)劃的基本方法 第四節(jié):動(dòng)態(tài)規(guī)劃的應(yīng)用,第六章 動(dòng)態(tài)規(guī)劃,多式聯(lián)運(yùn)是一種以實(shí)現(xiàn)貨物整體運(yùn)輸最優(yōu)化為目標(biāo)的聯(lián)合運(yùn)輸組織形式,它以集裝箱為媒介,把水路、公路、以及鐵路等多種運(yùn)輸方式有機(jī)地結(jié)合起來(lái),構(gòu)筑連續(xù)的、綜合性的一體化貨物運(yùn)輸網(wǎng)絡(luò)。在集裝箱多式聯(lián)運(yùn)系統(tǒng)中,各種運(yùn)輸方式的組織優(yōu)化直接關(guān)系到貨物運(yùn)輸?shù)馁M(fèi)用、時(shí)間和運(yùn)輸質(zhì)量。,第一節(jié)
2、:現(xiàn)實(shí)中的動(dòng)態(tài)規(guī)劃問(wèn)題,一、兩地之間集裝箱貨物運(yùn)輸有三種可選的運(yùn)輸方式(公路、鐵路、水路運(yùn)輸)二、集裝箱的中轉(zhuǎn)過(guò)程有很好的銜接三、集裝箱運(yùn)量不可以分割,在某兩個(gè)特定的地點(diǎn)之間,只能選擇一種運(yùn)輸方式四、集裝箱運(yùn)量對(duì)運(yùn)輸價(jià)格及運(yùn)輸時(shí)間沒(méi)有明顯的影響五、集裝箱運(yùn)輸能力幾乎不受限制六、運(yùn)輸時(shí)間須控制在合理范圍之內(nèi)(如集裝箱干線船的班期)。,通常情況下,多式聯(lián)運(yùn)組織優(yōu)化問(wèn)題具有如下幾個(gè)方面的特點(diǎn):,ZH物流公司是一家大型的集裝箱多式聯(lián)運(yùn)
3、經(jīng)營(yíng)企業(yè),在成都設(shè)有內(nèi)陸集裝箱貨運(yùn)站(CFS),經(jīng)營(yíng)成都——上海間集裝箱貨物運(yùn)輸服務(wù),其多式聯(lián)運(yùn)通道的主要節(jié)點(diǎn)城市為南京與鄭州。現(xiàn)有一個(gè)貨主需要將2個(gè)20英尺的集裝箱從成都運(yùn)往上海,運(yùn)輸路線為成都-鄭州-南京-上海,要求在貨物起運(yùn)后25-30小時(shí)之內(nèi)到達(dá)目的地。,第一節(jié):現(xiàn)實(shí)中的動(dòng)態(tài)規(guī)劃問(wèn)題,,如何制定運(yùn)輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運(yùn)輸總成本?,5,…,S’k+1,…,…,S2,多階段決策問(wèn)題 階段
4、、決策、策略動(dòng)態(tài)規(guī)劃的基本特性(多階段決策問(wèn)題的基本特性),第二節(jié) 動(dòng)態(tài)規(guī)劃基本概念,,,,,,,,,,,,Sk,Sk+1,Sn,T,S’n,Q = S1,反證法容易得證。,,若 {S1 , … , Sk , Sk+1 , … , Sn , T} 全程最優(yōu),則 {Sk+1 , … , Sn , T} 子程最優(yōu),動(dòng)態(tài)規(guī)劃方法的基本思路,最短路問(wèn)題,,,,,,,1,2,3,4,3,4,0
5、,4,7,6,11,7,8,11,階段,,,,,,,,,,,,,,,,,,,,,,,,,,,,—— 標(biāo)號(hào)法,三、決策 是指人們對(duì)某一階段活動(dòng)中各種不同的行為或方案或途徑等的一種選擇。 用xk表示第k段的決策,稱為第k段決策變量。由于決策隨狀態(tài)而變,所以決策變量xk是狀態(tài)變量sk的函數(shù),記為 xk= xk(sk),動(dòng)態(tài)規(guī)劃的基本概念一、階段 把所研究的問(wèn)題恰當(dāng)?shù)膭澐殖扇舾蓚€(gè)相互聯(lián)系的階段。用k
6、= 1,2,…,n 表示階段序號(hào),稱為階段變量。二、狀態(tài) 狀態(tài)表示某段的初始條件。用sk表示第k段的狀態(tài),稱為第k段狀態(tài)變量。,sk∈Sk,,k階段的允許決策集合,8,,四、狀態(tài)轉(zhuǎn)移方程 sk+1與sk,xk之間必須能夠建立一種明確的數(shù)量對(duì)應(yīng)關(guān)系,記為Tk(sk,xk), 即有 sk+1 = Tk(sk,xk) 這種明確的數(shù)量關(guān)系稱為狀態(tài)轉(zhuǎn)移方程。,,五、策
7、略 由各階段決策xk構(gòu)成的決策序列,稱為全過(guò)程策略,簡(jiǎn)稱策略,記為p1(s1),有 p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈Pk稱為第k子過(guò)程策略,簡(jiǎn)稱子策略。,∈P1,而,9,,六、指標(biāo)函數(shù) (1) 階段指標(biāo)函數(shù) 用vk(s
8、k,xk)表示第k段處于sk狀態(tài)且所作決策為xk時(shí)的指標(biāo),則它就是第k段指標(biāo)函數(shù),簡(jiǎn)記為vk。,∈P1,(2) 過(guò)程指標(biāo)函數(shù) 用fk(sk,xk)表示第k子過(guò)程的指標(biāo)函數(shù)。 它是各vk的累積效應(yīng)。 常用函數(shù):,積函數(shù),和函數(shù),七、最優(yōu)解 (1) 最優(yōu)指標(biāo)函數(shù) fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,…,n pk∈Pk (2) 最優(yōu)策略
9、 能使上式成立的子策略pk*稱為最優(yōu)子策略,記為 pk* (sk) = { xk*(sk),… ,xn*(sn)} 特別當(dāng)k=1時(shí),稱為最優(yōu)策略,記為 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)} (3) 最優(yōu)決策 構(gòu)成最優(yōu)策略的決策稱為最優(yōu)決策,記為xk*。 (4) 最優(yōu)值:最優(yōu)策略對(duì)
10、應(yīng)的最優(yōu)指標(biāo) f *1,11,第三節(jié) 動(dòng)態(tài)規(guī)劃的基本方法,一、最優(yōu)化原理 作為一個(gè)全過(guò)程最優(yōu)策略具有這樣的性質(zhì):無(wú)論過(guò)去的狀態(tài)和決策如何,對(duì)前面所形成的狀態(tài)而言,余下的諸決策必構(gòu)成最優(yōu)策略。 二、函數(shù)基本方程 f*n+1(sn+1) = 0 f*k(sk) = opt {vk(sk,xk)+fk+1*(sk+1)} xk∈Xk
11、 f*n+1(sn+1) = 1 f*k(sk) = opt {vk(sk,xk) ×fk+1*(sk+1)} xk∈Xk,,,和,積,k = n, n-1, …, 2, 1,k = n, n-1, …, 2, 1,12,第三節(jié) 動(dòng)態(tài)規(guī)劃的基本方法,三、基本步驟1°建立模型 (1) 劃分階段,設(shè)定 k
12、 (2) 設(shè)定狀態(tài)變量 sk (3) 設(shè)定決策變量 xk (4) 建立狀態(tài)轉(zhuǎn)移方程 (5) 確定指標(biāo)函數(shù) vk,fk* (6) 建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結(jié)論,,,s,a,b,c,f,e,d,h,g,t,,,,,,,,,,,,,,,,,2,5,1,12,14,6,10,13,,4,12,11,3,9,6,5,8,10,5,2,,,8,7,12,5,2,2
13、0,14,19,19,k=4,,=5,,,,k=3,,=8,,,,,,,,k=2,k=1,,,,,,,d1(s)=b,d1(s)=b,d2(b)=d,d3(d)=g,d4(g)=t,最優(yōu)策略: p1(s1)={s,b,d,g,t},最優(yōu)值: f*1(s)=19,14,第四節(jié) 動(dòng)態(tài)規(guī)劃的應(yīng)用,今有一輛載貨量為6t的載貨車,現(xiàn)有3種需要運(yùn)輸?shù)呢浳铮捎么溯d貨車裝運(yùn)。若已知這4種貨物每一種的質(zhì)量和運(yùn)輸例如表6-4所示。在載貨量許可的條件下,
14、每車裝載每一種貨物的件數(shù)不限,應(yīng)如何搭配這四種貨物,才能使每車裝載貨物的利潤(rùn)最大?,該問(wèn)題中的貨車可以看做是一個(gè)背包,需運(yùn)載的貨物為要裝入背包的物品。 該問(wèn)題可以看作是一個(gè)3階段的動(dòng)態(tài)規(guī)劃問(wèn)題。,步驟1,劃分階段。設(shè)每裝一種貨物為一個(gè)階段,k=1,2,3。步驟2,確定狀態(tài)變量。設(shè)狀態(tài)變量為 可用于裝載第k種至第n種貨物的裝載量。,,1)確定決策變量。設(shè)決策變量表示第k種貨物的裝載件數(shù) 2)狀態(tài)轉(zhuǎn)移方程為
溫馨提示
- 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ù)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 動(dòng)態(tài)規(guī)劃運(yùn)籌學(xué)
- 管理運(yùn)籌學(xué)--動(dòng)態(tài)規(guī)劃
- 運(yùn)籌學(xué)-第9章-動(dòng)態(tài)規(guī)劃
- 上海大學(xué)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃課件
- 運(yùn)籌學(xué)-第七章-動(dòng)態(tài)規(guī)劃
- 運(yùn)籌學(xué)5動(dòng)態(tài)
- 運(yùn)籌學(xué)-目標(biāo)規(guī)劃
- 運(yùn)籌學(xué)》習(xí)題答案運(yùn)籌學(xué)答案
- 運(yùn)籌學(xué)08-整數(shù)規(guī)劃
- 運(yùn)籌學(xué)非線性規(guī)劃
- 運(yùn)籌學(xué)
- 衛(wèi)生管理運(yùn)籌學(xué)線性規(guī)劃
- 運(yùn)籌學(xué)》習(xí)題答案運(yùn)籌學(xué)答案匯總
- 運(yùn)籌學(xué)習(xí)題答案運(yùn)籌學(xué)答案
- 858 運(yùn)籌學(xué)
- 《運(yùn)籌學(xué)1》
- 運(yùn)籌學(xué)線性規(guī)劃實(shí)驗(yàn)報(bào)告
- 運(yùn)籌學(xué)線性規(guī)劃實(shí)驗(yàn)報(bào)告
- 運(yùn)籌學(xué)課件
- 運(yùn)籌學(xué) 1
評(píng)論
0/150
提交評(píng)論