動態(tài)規(guī)劃運籌學

1、第六章 動態(tài)規(guī)劃,第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題 第二節(jié)：動態(tài)規(guī)劃基本概念 第三節(jié)：動態(tài)規(guī)劃的基本方法 第四節(jié)：動態(tài)規(guī)劃的應用,第六章 動態(tài)規(guī)劃,多式聯(lián)運是一種以實現(xiàn)貨物整體運輸最優(yōu)化為目標的聯(lián)合運輸組織形式，它以集裝箱為媒介，把水路、公路、以及鐵路等多種運輸方式有機地結合起來，構筑連續(xù)的、綜合性的一體化貨物運輸網絡。在集裝箱多式聯(lián)運系統(tǒng)中，各種運輸方式的組織優(yōu)化直接關系到貨物運輸?shù)馁M用、時間和運輸質量。,第一節(jié)

2、：現(xiàn)實中的動態(tài)規(guī)劃問題,一、兩地之間集裝箱貨物運輸有三種可選的運輸方式（公路、鐵路、水路運輸）二、集裝箱的中轉過程有很好的銜接三、集裝箱運量不可以分割，在某兩個特定的地點之間，只能選擇一種運輸方式四、集裝箱運量對運輸價格及運輸時間沒有明顯的影響五、集裝箱運輸能力幾乎不受限制六、運輸時間須控制在合理范圍之內（如集裝箱干線船的班期）。,通常情況下，多式聯(lián)運組織優(yōu)化問題具有如下幾個方面的特點：,ZH物流公司是一家大型的集裝箱多式聯(lián)運

3、經營企業(yè)，在成都設有內陸集裝箱貨運站（CFS），經營成都——上海間集裝箱貨物運輸服務，其多式聯(lián)運通道的主要節(jié)點城市為南京與鄭州。現(xiàn)有一個貨主需要將2個20英尺的集裝箱從成都運往上海，運輸路線為成都-鄭州-南京-上海，要求在貨物起運后25-30小時之內到達目的地。,第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題,,如何制定運輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運輸總成本？,5,…,S’k+1,…,…,S2,多階段決策問題 階段

4、、決策、策略動態(tài)規(guī)劃的基本特性（多階段決策問題的基本特性）,第二節(jié) 動態(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),動態(tài)規(guī)劃方法的基本思路,最短路問題,,,,,,,1,2,3,4,3,4,0

5、,4,7,6,11,7,8,11,階段,,,,,,,,,,,,,,,,,,,,,,,,,,,,—— 標號法,三、決策 是指人們對某一階段活動中各種不同的行為或方案或途徑等的一種選擇。 用xk表示第k段的決策，稱為第k段決策變量。由于決策隨狀態(tài)而變,所以決策變量xk是狀態(tài)變量sk的函數(shù),記為 xk= xk(sk),動態(tài)規(guī)劃的基本概念一、階段 把所研究的問題恰當?shù)膭澐殖扇舾蓚€相互聯(lián)系的階段。用k

6、= 1，2，…，n 表示階段序號，稱為階段變量。二、狀態(tài) 狀態(tài)表示某段的初始條件。用sk表示第k段的狀態(tài)，稱為第k段狀態(tài)變量。,sk∈Sk,,k階段的允許決策集合,8,,四、狀態(tài)轉移方程 sk+1與sk,xk之間必須能夠建立一種明確的數(shù)量對應關系，記為Tk(sk,xk), 即有 sk+1 = Tk(sk,xk) 這種明確的數(shù)量關系稱為狀態(tài)轉移方程。,,五、策

7、略 由各階段決策xk構成的決策序列,稱為全過程策略,簡稱策略,記為p1(s1),有 p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈Pk稱為第k子過程策略，簡稱子策略。,∈P1,而,9,,六、指標函數(shù) (1) 階段指標函數(shù) 用vk(s

8、k,xk)表示第k段處于sk狀態(tài)且所作決策為xk時的指標，則它就是第k段指標函數(shù)，簡記為vk。,∈P1,(2) 過程指標函數(shù) 用fk(sk,xk)表示第k子過程的指標函數(shù)。 它是各vk的累積效應。 常用函數(shù)：,積函數(shù),和函數(shù),七、最優(yōu)解 (1) 最優(yōu)指標函數(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)} 特別當k=1時,稱為最優(yōu)策略，記為 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)} (3) 最優(yōu)決策 構成最優(yōu)策略的決策稱為最優(yōu)決策，記為xk*。 (4) 最優(yōu)值：最優(yōu)策略對

10、應的最優(yōu)指標 f *1,11,第三節(jié) 動態(tài)規(guī)劃的基本方法,一、最優(yōu)化原理 作為一個全過程最優(yōu)策略具有這樣的性質：無論過去的狀態(tài)和決策如何，對前面所形成的狀態(tài)而言，余下的諸決策必構成最優(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é) 動態(tài)規(guī)劃的基本方法,三、基本步驟1°建立模型 (1) 劃分階段，設定 k

12、 (2) 設定狀態(tài)變量 sk (3) 設定決策變量 xk (4) 建立狀態(tài)轉移方程 (5) 確定指標函數(shù) vk，fk* (6) 建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結論,,,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é) 動態(tài)規(guī)劃的應用,今有一輛載貨量為6t的載貨車，現(xiàn)有3種需要運輸?shù)呢浳?，均可用此載貨車裝運。若已知這4種貨物每一種的質量和運輸例如表6-4所示。在載貨量許可的條件下，

14、每車裝載每一種貨物的件數(shù)不限，應如何搭配這四種貨物，才能使每車裝載貨物的利潤最大？,該問題中的貨車可以看做是一個背包，需運載的貨物為要裝入背包的物品。 該問題可以看作是一個3階段的動態(tài)規(guī)劃問題。,步驟1，劃分階段。設每裝一種貨物為一個階段，k=1,2,3。步驟2，確定狀態(tài)變量。設狀態(tài)變量為 可用于裝載第k種至第n種貨物的裝載量。,,1）確定決策變量。設決策變量表示第k種貨物的裝載件數(shù) 2）狀態(tài)轉移方程為