動(dòng)態(tài)規(guī)劃運(yùn)籌學(xué)

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)移方程為