管理運籌學(xué)動態(tài)規(guī)劃課件

第六章動態(tài)規(guī)劃第六章動態(tài)規(guī)劃第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題第二節(jié)：動態(tài)規(guī)劃基本概念第三節(jié)：動態(tài)規(guī)劃的基本方法第四節(jié)：配載問題第五節(jié)：生產(chǎn)和庫存控制問題第六節(jié)：資源分配問題第七節(jié)：動態(tài)規(guī)劃應(yīng)用第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題

多式聯(lián)運是一種以實現(xiàn)貨物整體運輸最優(yōu)化為目標的聯(lián)合運輸組織形式，它以集裝箱為媒介，把水路、公路、以及鐵路等多種運輸方式有機地結(jié)合起來，構(gòu)筑連續(xù)的、綜合性的一體化貨物運輸網(wǎng)絡(luò)。在集裝箱多式聯(lián)運系統(tǒng)中，各種運輸方式的組織優(yōu)化直接關(guān)系到貨物運輸?shù)馁M用、時間和運輸質(zhì)量。第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題一、兩地之間集裝箱貨物運輸有三種可選的運輸方式（公路、鐵路、水路運輸）二、集裝箱的中轉(zhuǎn)過程有很好的銜接三、集裝箱運量不可以分割，在某兩個特定的地點之間，只能選擇一種運輸方式四、集裝箱運量對運輸價格及運輸時間沒有明顯的影響五、集裝箱運輸能力幾乎不受限制六、運輸時間須控制在合理范圍之內(nèi)（如集裝箱干線船的班期）。通常情況下，多式聯(lián)運組織優(yōu)化問題具有如下幾個方面的特點：多式聯(lián)運是一種以實現(xiàn)貨物整體運輸最優(yōu)化為ZH物流公司是一家大型的集裝箱多式聯(lián)運經(jīng)營企業(yè)，在成都設(shè)有內(nèi)陸集裝箱貨運站（CFS），經(jīng)營成都——上海間集裝箱貨物運輸服務(wù)，其多式聯(lián)運通道的主要節(jié)點城市為南京與鄭州。現(xiàn)有一個貨主需要將2個20英尺的集裝箱從成都運往上海，運輸路線為成都-鄭州-南京-上海，要求在貨物起運后25-30小時之內(nèi)到達目的地。第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題成都-鄭州鄭州-南京南京-上海公路運輸1474704349鐵路運輸1353695303水路運輸//392運輸方式鐵路運輸公路運輸水路運輸運載工具速度(km/h)7010036運輸方式鐵路運輸公路運輸水路運輸中轉(zhuǎn)時間(h)7318如何制定運輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運輸總成本？ZH物流公司是一家大型的集裝箱多式5

…S’k+1……S2多階段決策問題

階段、決策、策略動態(tài)規(guī)劃的基本特性（多階段決策問題的基本特性）第二節(jié)動態(tài)規(guī)劃基本概念SkSk+1SnTS’nQ

=

S1反證法容易得證。若{S1,

…

,Sk,Sk+1,

…

,Sn,

T}

全程最優(yōu)則

{Sk+1,

…

,Sn,

T}

子程最優(yōu)5…S’k+1……S2多階段決策問題第二節(jié)動態(tài)規(guī)劃基本概動態(tài)規(guī)劃方法的基本思路最短路問題1234340476117811階段A124374632441514633334A3B1QA2B2B3TC1

C2——標號法動態(tài)規(guī)劃方法的基本思路最短路問題12343404761178三、決策

是指人們對某一階段活動中各種不同的行為或方案或途徑等的一種選擇。用xk表示第k段的決策，稱為第k段決策變量。由于決策隨狀態(tài)而變,所以決策變量xk是狀態(tài)變量sk的函數(shù),記為xk=

xk(sk)動態(tài)規(guī)劃的基本概念一、階段

把所研究的問題恰當?shù)膭澐殖扇舾蓚€相互聯(lián)系的階段。用k=1，2，…，n表示階段序號，稱為階段變量。二、狀態(tài)

狀態(tài)表示某段的初始條件。用sk表示第k段的狀態(tài)，稱為第k段狀態(tài)變量。sk∈Skk階段的允許決策集合三、決策動態(tài)規(guī)劃的基本概念sk∈Skk階段的允許決策集合8

四、狀態(tài)轉(zhuǎn)移方程

sk+1與sk,xk之間必須能夠建立一種明確的數(shù)量對應(yīng)關(guān)系，記為Tk(sk,xk),即有

sk+1=Tk(sk,xk)

這種明確的數(shù)量關(guān)系稱為狀態(tài)轉(zhuǎn)移方程。

五、策略

由各階段決策xk構(gòu)成的決策序列,稱為全過程策略,簡稱策略,記為p1(s1),有

p1(s1)

={x1(s1),x2(s2),…,xn(sn)}

pk(sk)

={xk(sk),xk+1(sk+1),…,xn(sn)}∈Pk稱為第k子過程策略，簡稱子策略?！蔖1而8四、狀態(tài)轉(zhuǎn)移方程五、策略∈P1而9

六、指標函數(shù)

(1)階段指標函數(shù)

用vk(sk,xk)表示第k段處于sk狀態(tài)且所作決策為xk時的指標，則它就是第k段指標函數(shù)，簡記為vk?！蔖1

(2)過程指標函數(shù)

用fk(sk,xk)表示第k子過程的指標函數(shù)。它是各vk的累積效應(yīng)。

常用函數(shù)：fk(sk,xk)=

vi(si,xi)ni=kfk(sk,xk)=

vi(si,xi)ni=k積函數(shù)和函數(shù)9六、指標函數(shù)∈P1(2)過程指標函數(shù)fk(s

七、最優(yōu)解

(1)

最優(yōu)指標函數(shù)

fk*(sk)

=opt{fk(sk,pk(sk))},

k=1,2,…,npk∈Pk

(2)

最優(yōu)策略

能使上式成立的子策略pk*稱為最優(yōu)子策略，記為

pk*

(sk)

={xk*(sk),…,xn*(sn)}

特別當k=1時,稱為最優(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)策略對應(yīng)的最優(yōu)指標f

*1

七、最優(yōu)解11第三節(jié)動態(tài)規(guī)劃的基本方法一、最優(yōu)化原理

作為一個全過程最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，對前面所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。

二、函數(shù)基本方程

f*n+1(sn+1)

=0f*k(sk)

=opt{vk(sk,xk)+fk+1*(sk+1)}

xk∈Xk

f*n+1(sn+1)=1f*k(sk)

=opt{vk(sk,xk)×fk+1*(sk+1)}

xk∈Xk和積k

=

n,n-1,…,2,1k

=

n,n-1,…,2,111第三節(jié)動態(tài)規(guī)劃的基本方法一、最優(yōu)化原理和積k=n,12第三節(jié)動態(tài)規(guī)劃的基本方法三、基本步驟1°建立模型

(1)

劃分階段，設(shè)定k

(2)

設(shè)定狀態(tài)變量sk

(3)

設(shè)定決策變量xk

(4)

建立狀態(tài)轉(zhuǎn)移方程

(5)

確定指標函數(shù)vk，fk*

(6)

建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結(jié)論12第三節(jié)動態(tài)規(guī)劃的基本方法三、基本步驟sabcfedhgt2511214610134121139658105287125220141919k=4=5

k=3=8k=2k=1d1(s)=bd1(s)=bd2(b)=dd3(d)=gd4(g)=t最優(yōu)策略：p1(s1)={s,b,d,g,t｝最優(yōu)值：

f*1(s)=19sabcfedhgt2511214610134121139614……階段N階段n階段114……階段N階段n階段115第四節(jié)配載問題今有一輛載貨量為6t的載貨車，現(xiàn)有3種需要運輸?shù)呢浳?，均可用此載貨車裝運。若已知這3種貨物每一種的質(zhì)量和運輸例如下表所示。在載貨量許可的條件下，每車裝載每一種貨物的件數(shù)不限，應(yīng)如何搭配這3種貨物，才能使每車裝載貨物的利潤最大？貨物種類每件質(zhì)量（t）每件運輸利潤（百元）12823133418該問題中的貨車可以看做是一個背包，需運載的貨物為要裝入背包的物品。

該問題可以看作是一個3階段的動態(tài)規(guī)劃問題。15第四節(jié)配載問題今有一輛載貨量為6t的載貨步驟1，劃分階段。設(shè)每裝一種貨物為一個階段，k=1,2,3。步驟2，確定狀態(tài)變量。設(shè)狀態(tài)變量為

可用于裝載第k種至第n種貨物的裝載量。1） 確定決策變量。設(shè)決策變量表示第k種貨物的裝載件數(shù)

2） 狀態(tài)轉(zhuǎn)移方程為

3） 階段指標函數(shù)。第k階段裝載件貨物時所創(chuàng)的利潤。4） 函數(shù)的基本方程為步驟1，劃分階段。設(shè)每裝一種貨物為一個階段，k=1,2,3。k=3時

階段

01

k=301234560—0—0—0—018018018000018181800001110123012k=3時0k=2時

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450k=2時k=1時階段

0123

k=160+268+1816+024+0260，16,4=26k=1時階段

階段

01

k=301234560—0—0—0—018018018000018181800001110123012

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450

階段

0

1

2

3

k=160+268+1816+024+0260，16,40121第五節(jié)配載問題用動態(tài)規(guī)劃解決持續(xù)三個月生產(chǎn)的問題。問題的數(shù)據(jù)見下表每個月當成一個階段來進行計算求解。還要注意到該問題在實現(xiàn)優(yōu)化的每個階段都必須滿足三個約束條件：（1）最終庫存量必須小于等于倉庫容量；（2）每階段的生產(chǎn)量不能超過生產(chǎn)能力；（3）初始庫存量加上生產(chǎn)量必須大于等于需求量。能力單位成本月需求生產(chǎn)存儲生產(chǎn)持有1月232$175$302月323150303月33220040一月的初始庫存為1單位21第五節(jié)配載問題用動態(tài)規(guī)劃解決持續(xù)三個月生產(chǎn)的問題。問22

--第k階段的需求量；

--第k階段的生產(chǎn)能力；

--第k階段結(jié)束時的存儲能力；

--第k階段生產(chǎn)單位產(chǎn)品的費用；

--第k階段單位產(chǎn)品的庫存持有成本步驟1：劃分階段。把每個月看成一個階段，倒序命名各個時期。即階段1對應(yīng)3月，階段2對應(yīng)2月，階段3對應(yīng)1月。步驟2：確定狀態(tài)變量。設(shè)為狀態(tài)變量，表示第k階段的開始的庫存量。由于1月份初始庫存為1單位，故。另外定義，表示為第3階段末的庫存量。步驟3：確定決策變量。設(shè)為決策變量，表示第k階段的生產(chǎn)量。且必須滿足如下三個約束條件：22--第k階段的需求量；步驟1：劃分階段。把每個月看成23步驟4：狀態(tài)轉(zhuǎn)移方程。步驟5：指標函數(shù)。第k階段的指標函數(shù)是第k階段的生產(chǎn)成本（包括生產(chǎn)費用與貯存費用）。步驟6：函數(shù)基本方程23步驟4：狀態(tài)轉(zhuǎn)移方程。步驟5：指標函數(shù)。第k階段的指標函第一階段：即從3月份開始正向計算。k=1時，問題可以如下表示：

01230———60036001——40064024002—200440680120030240480—00

第一階段：即從3月份開始正向計算。k=1時，問題可以如下表示第二階段：k=2時，該階段的子問題可以表示為：

012

0————M1——300+60029002—150+600330+4002730

第二階段：k=2時，該階段的子問題可以表示為：第三階段：k=3時，該階段的子問題可以表示為：

0123

1—175+M380+9001185+73021280

第三階段：k=3時，該階段的子問題可以表示為：

01230———60036001——40064024002—200440680120030240480—00

012

0————M1——300+60029002—150+600330+4002730

0123

1—175+M380+9001185+73021280

月份初始庫存生產(chǎn)量銷售量月末庫存生產(chǎn)成本持有成本總成本一月1221$350$30$380二月12303000300三月03306000600總計$1250$30$1280最優(yōu)策略

29第六節(jié)資源分配問題資源分配問題:是指將供應(yīng)量有限的一種或若干種資源（如原材料、資金、機器設(shè)備、勞動力等），分配給若干用戶，而使目標函數(shù)最優(yōu)。設(shè)有某一種原料，總量為M，擬用來進行n種生產(chǎn)活動。若分配數(shù)量為的原料用于第i種生產(chǎn)活動，其收益為，應(yīng)該如何分配，才能使n種生產(chǎn)活動的總收益最大？

靜態(tài)規(guī)劃模型為：29第六節(jié)資源分配問題資源分配問題:是指將供應(yīng)量有限的一種或30用動態(tài)規(guī)劃方法求解此類問題時，一般地，將n種活動作為一個互相銜接的整體，由于要確定分配給每種活動的資源數(shù)，因此通常以把資源分配給一個或幾個使用者的過程作為一個階段，每個階段都要確定分配給一種活動的資源量，并要先對n種活動指定分配的階段序號。在資源分配中，由于將階段聯(lián)系在一起的是所有生產(chǎn)活動都在爭取的資源，因此，狀態(tài)變量就要按照資源的分配來確定。故把第k階段的狀態(tài)變量定義為第k階段初所擁有的資源量，即將要在第k種活動到第n種活動間分配的資源量。這樣，我們在確定第k階段的資源分配時就無需考慮以前的資源分配情況。決策變量就定義為對第k種活動的資源投放量，即對第k種活動的資源分配量。30用動態(tài)規(guī)劃方法求解此類問題時，一般地，將n種活動作為一個31某船舶總公司擬將5億元資金投放到下屬A、B、C三個船廠，各船廠在獲得資金后的收益如表所示。試用動態(tài)規(guī)劃方法求使總收益最大的投資分配方案。A、B、C三個船廠分別編號為1，2，3，對A、B、C三個船廠分配資金分別形成1,2,3三個階段，即該問題可作為三階段決策過程。k=1,2,3。

k=1時，將資金分給1,2,3三個船廠；

k=2時，將資金分給2,3兩個船廠；

k=3時，將資金分給3船廠。31某船舶總公司擬將5億元資金投放到下屬A、B、C三個船廠，32K=3時，考慮將資金分給船廠C，

k=3012345013791001234532K=3時，考慮將資金分給船廠C，00033k=2時，考慮將資金分給船廠B、C，

012345k=201234500+10+30+70+90+104+04+14+34+74+96+06+16+36+78+08+18+39+09+19+004681113012311,233k=2時，考慮將資金分給船廠B、C，012345034k=1時，考慮將資金分給船廠A、B、C

012345k=150+133+115+87+68+49+014134k=1時，考慮將資金分給船廠A、B、C01234535k=1時，也可以

012345k=101234500+40+60+80+110+133+03+43+63+83+115+05+45+65+87+07+47+68+08+49+0047911140011,20,1,2,31若總投資額為3億元35k=1時，也可以0123450000若總投資額為336第七節(jié)動態(tài)規(guī)劃應(yīng)用第一節(jié)的集裝箱多式聯(lián)運優(yōu)化問題進行求解表示所有節(jié)點城市的個數(shù)表示i城市可選運輸方式集合，1-公路、2-鐵路、3-水運表示集裝箱多式聯(lián)運中貨物運輸總量表示i城市到j(luò)城市k運輸方式的單位距離的運價表示i城市到j(luò)城市k運輸方式的距離表示i城市到j(luò)城市k運輸方式的速度表示i城市k運輸方式轉(zhuǎn)換為l方式的中轉(zhuǎn)費用表示i城市k運輸方式轉(zhuǎn)換為l方式的中轉(zhuǎn)時間36第七節(jié)動態(tài)規(guī)劃應(yīng)用第一節(jié)的集裝箱多式聯(lián)運優(yōu)化問題進373738約束式（4）是確保運輸?shù)倪B續(xù)性。i-1i+1i分成三種情況來討論均為1，則也為1一個為0，一個1，則必須為0均為0，則也為038約束式（4）是確保運輸?shù)倪B續(xù)性。i-1i+1i分成三種情39模型基于動態(tài)規(guī)劃的基本算法程序設(shè)計如下：步驟1：令每兩個城市之間的運輸過程為動態(tài)規(guī)劃中的一個階段步驟2：選擇貨物到達城市的運輸方式為該階段的狀態(tài)變量如：第2階段的到達方式有公路、鐵路，則設(shè)計一個3×n的狀態(tài)矩陣，矩陣的第k列表示第k個階段的狀態(tài)變量構(gòu)造的列向量（沒有的話，用MATLAB中特有的常量

填充）如：一個3階段的問題，各階段的可達狀態(tài)集合分別為{1},{1，3}，{1，2，3}，則該問題需輸入的狀態(tài)變量矩陣為步驟3：確定決策變量和狀態(tài)轉(zhuǎn)移方程。在此例中，令從每一城市出發(fā)時所選擇的運輸方式作為該階段的決策變量

狀態(tài)轉(zhuǎn)移方程將狀態(tài)矩陣作為動態(tài)規(guī)劃程序的一個輸入變量。

39模型基于動態(tài)規(guī)劃的基本算法程序設(shè)計如下：步驟1：令每兩個40步驟4：刪除不滿足時間強約束的可選擇方案，這也是與在一般情況下運用動態(tài)規(guī)劃求解問題的區(qū)別所在。由于在模型中我們限定了多式聯(lián)運總時間必須在顧客要求的范圍之內(nèi)，因此在進行選擇最優(yōu)方案之前應(yīng)該先排除不滿足時間要求的方案。

步驟5：由邊界條件開始,求出在該階段狀態(tài)為的指標函數(shù)值，選取其中的最優(yōu)值作為該階段狀態(tài)為時所有允許決策下時的最優(yōu)值，求出最優(yōu)決策并進行替換存儲。直到最后求出得到問題的指標函數(shù)最優(yōu)值。步驟6：由k=1開始，按照與前一步驟相反的順序推算，記錄推算結(jié)果，則可得到每階段及全局的最優(yōu)路徑及最優(yōu)解，存儲結(jié)果并輸出。40步驟4：刪除不滿足時間強約束的可選擇方案，這也是與在一般41按照上述算法設(shè)計的思路所設(shè)計的解法程序主要由以下子程序組成：（1）主函數(shù)function[p_opt,fval,tw]=dyn(x,tm,tn，SubObjFun,TransFun,ObjFun)，輸入狀態(tài)變量矩陣和顧客要求的時間約束，輸出的變量為全局最優(yōu)策略組(p_opt)、最優(yōu)指標函數(shù)值(fval)、完成該運輸任務(wù)所需要的時間(tw)。（2）階段指標計算子函數(shù)functiontmp00=SubObjFun(ii,x,u)，輸入階段數(shù)(ii)、狀態(tài)(x)、決策值(u)，輸出的變量為處于該階段時，某一狀態(tài)和決策條件下所需的一階段成本tmp00，供主函數(shù)運行時調(diào)用。（3）狀態(tài)轉(zhuǎn)移計算子函數(shù)functiontmp40=TransFun(ii,x,u),輸入階段數(shù)(ii)、狀態(tài)(x)、決策值(u)，返回處于該階段某一狀態(tài)和決策條件時下一階段將處的狀態(tài)值tmp40。（4）第k階段至最后階段指標函數(shù)子函數(shù)functiontmp80=ObjFun(tmp00,f_opt),輸入階段指標值(tmp00)和后一階段至最后階段指標值(f_opt)，輸出值為該階段至最后階段指標值。41按照上述算法設(shè)計的思路所設(shè)計的解法程序主要由以下子程序組42集裝箱多式聯(lián)運各種運輸方式的成本情況表成都-鄭州鄭州-南京南京-上海公路運輸8.178.789.98鐵路運輸3.323.795.05水路運輸//1.94成本(美元/km.TEU)42集裝箱多式聯(lián)運各種運輸方式的成本情況表公路運輸8.17843將上述參數(shù)輸入到優(yōu)化算法程序中，得到最優(yōu)的運輸方式組合策略為：成都—（公路）—鄭州—（公路）—南京—（鐵路）—上海。

此時的最小運輸成本為39631美元,完成運輸任務(wù)所需要的時間為29.11小時。如果對運輸時間的要求放寬至起運后40-50小時之內(nèi)到達即可，此時再次對該問題求解，得到的最優(yōu)策略組合變?yōu)椋撼啥肌ㄨF路）—鄭州—（鐵路）—南京—（水路）—上海。此時的最小運輸成本為15826美元,完成運輸任務(wù)所需要的時間為46.96小時。43將上述參數(shù)輸入到優(yōu)化算法程序中，得到最優(yōu)的運輸方第六章動態(tài)規(guī)劃第六章動態(tài)規(guī)劃第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題第二節(jié)：動態(tài)規(guī)劃基本概念第三節(jié)：動態(tài)規(guī)劃的基本方法第四節(jié)：配載問題第五節(jié)：生產(chǎn)和庫存控制問題第六節(jié)：資源分配問題第七節(jié)：動態(tài)規(guī)劃應(yīng)用第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題

多式聯(lián)運是一種以實現(xiàn)貨物整體運輸最優(yōu)化為目標的聯(lián)合運輸組織形式，它以集裝箱為媒介，把水路、公路、以及鐵路等多種運輸方式有機地結(jié)合起來，構(gòu)筑連續(xù)的、綜合性的一體化貨物運輸網(wǎng)絡(luò)。在集裝箱多式聯(lián)運系統(tǒng)中，各種運輸方式的組織優(yōu)化直接關(guān)系到貨物運輸?shù)馁M用、時間和運輸質(zhì)量。第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題一、兩地之間集裝箱貨物運輸有三種可選的運輸方式（公路、鐵路、水路運輸）二、集裝箱的中轉(zhuǎn)過程有很好的銜接三、集裝箱運量不可以分割，在某兩個特定的地點之間，只能選擇一種運輸方式四、集裝箱運量對運輸價格及運輸時間沒有明顯的影響五、集裝箱運輸能力幾乎不受限制六、運輸時間須控制在合理范圍之內(nèi)（如集裝箱干線船的班期）。通常情況下，多式聯(lián)運組織優(yōu)化問題具有如下幾個方面的特點：多式聯(lián)運是一種以實現(xiàn)貨物整體運輸最優(yōu)化為ZH物流公司是一家大型的集裝箱多式聯(lián)運經(jīng)營企業(yè)，在成都設(shè)有內(nèi)陸集裝箱貨運站（CFS），經(jīng)營成都——上海間集裝箱貨物運輸服務(wù)，其多式聯(lián)運通道的主要節(jié)點城市為南京與鄭州?，F(xiàn)有一個貨主需要將2個20英尺的集裝箱從成都運往上海，運輸路線為成都-鄭州-南京-上海，要求在貨物起運后25-30小時之內(nèi)到達目的地。第一節(jié)：現(xiàn)實中的動態(tài)規(guī)劃問題成都-鄭州鄭州-南京南京-上海公路運輸1474704349鐵路運輸1353695303水路運輸//392運輸方式鐵路運輸公路運輸水路運輸運載工具速度(km/h)7010036運輸方式鐵路運輸公路運輸水路運輸中轉(zhuǎn)時間(h)7318如何制定運輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運輸總成本？ZH物流公司是一家大型的集裝箱多式48

…S’k+1……S2多階段決策問題

階段、決策、策略動態(tài)規(guī)劃的基本特性（多階段決策問題的基本特性）第二節(jié)動態(tài)規(guī)劃基本概念SkSk+1SnTS’nQ

=

S1反證法容易得證。若{S1,

…

,Sk,Sk+1,

…

,Sn,

T}

全程最優(yōu)則

{Sk+1,

…

,Sn,

T}

子程最優(yōu)5…S’k+1……S2多階段決策問題第二節(jié)動態(tài)規(guī)劃基本概動態(tài)規(guī)劃方法的基本思路最短路問題1234340476117811階段A124374632441514633334A3B1QA2B2B3TC1

C2——標號法動態(tài)規(guī)劃方法的基本思路最短路問題12343404761178三、決策

是指人們對某一階段活動中各種不同的行為或方案或途徑等的一種選擇。用xk表示第k段的決策，稱為第k段決策變量。由于決策隨狀態(tài)而變,所以決策變量xk是狀態(tài)變量sk的函數(shù),記為xk=

xk(sk)動態(tài)規(guī)劃的基本概念一、階段

把所研究的問題恰當?shù)膭澐殖扇舾蓚€相互聯(lián)系的階段。用k=1，2，…，n表示階段序號，稱為階段變量。二、狀態(tài)

狀態(tài)表示某段的初始條件。用sk表示第k段的狀態(tài)，稱為第k段狀態(tài)變量。sk∈Skk階段的允許決策集合三、決策動態(tài)規(guī)劃的基本概念sk∈Skk階段的允許決策集合51

四、狀態(tài)轉(zhuǎn)移方程

sk+1與sk,xk之間必須能夠建立一種明確的數(shù)量對應(yīng)關(guān)系，記為Tk(sk,xk),即有

sk+1=Tk(sk,xk)

這種明確的數(shù)量關(guān)系稱為狀態(tài)轉(zhuǎn)移方程。

五、策略

由各階段決策xk構(gòu)成的決策序列,稱為全過程策略,簡稱策略,記為p1(s1),有

p1(s1)

={x1(s1),x2(s2),…,xn(sn)}

pk(sk)

={xk(sk),xk+1(sk+1),…,xn(sn)}∈Pk稱為第k子過程策略，簡稱子策略?！蔖1而8四、狀態(tài)轉(zhuǎn)移方程五、策略∈P1而52

六、指標函數(shù)

(1)階段指標函數(shù)

用vk(sk,xk)表示第k段處于sk狀態(tài)且所作決策為xk時的指標，則它就是第k段指標函數(shù)，簡記為vk?！蔖1

(2)過程指標函數(shù)

用fk(sk,xk)表示第k子過程的指標函數(shù)。它是各vk的累積效應(yīng)。

常用函數(shù)：fk(sk,xk)=

vi(si,xi)ni=kfk(sk,xk)=

vi(si,xi)ni=k積函數(shù)和函數(shù)9六、指標函數(shù)∈P1(2)過程指標函數(shù)fk(s

七、最優(yōu)解

(1)

最優(yōu)指標函數(shù)

fk*(sk)

=opt{fk(sk,pk(sk))},

k=1,2,…,npk∈Pk

(2)

最優(yōu)策略

能使上式成立的子策略pk*稱為最優(yōu)子策略，記為

pk*

(sk)

={xk*(sk),…,xn*(sn)}

特別當k=1時,稱為最優(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)策略對應(yīng)的最優(yōu)指標f

*1

七、最優(yōu)解54第三節(jié)動態(tài)規(guī)劃的基本方法一、最優(yōu)化原理

作為一個全過程最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，對前面所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。

二、函數(shù)基本方程

f*n+1(sn+1)

=0f*k(sk)

=opt{vk(sk,xk)+fk+1*(sk+1)}

xk∈Xk

f*n+1(sn+1)=1f*k(sk)

=opt{vk(sk,xk)×fk+1*(sk+1)}

xk∈Xk和積k

=

n,n-1,…,2,1k

=

n,n-1,…,2,111第三節(jié)動態(tài)規(guī)劃的基本方法一、最優(yōu)化原理和積k=n,55第三節(jié)動態(tài)規(guī)劃的基本方法三、基本步驟1°建立模型

(1)

劃分階段，設(shè)定k

(2)

設(shè)定狀態(tài)變量sk

(3)

設(shè)定決策變量xk

(4)

建立狀態(tài)轉(zhuǎn)移方程

(5)

確定指標函數(shù)vk，fk*

(6)

建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結(jié)論12第三節(jié)動態(tài)規(guī)劃的基本方法三、基本步驟sabcfedhgt2511214610134121139658105287125220141919k=4=5

k=3=8k=2k=1d1(s)=bd1(s)=bd2(b)=dd3(d)=gd4(g)=t最優(yōu)策略：p1(s1)={s,b,d,g,t｝最優(yōu)值：

f*1(s)=19sabcfedhgt2511214610134121139657……階段N階段n階段114……階段N階段n階段158第四節(jié)配載問題今有一輛載貨量為6t的載貨車，現(xiàn)有3種需要運輸?shù)呢浳?，均可用此載貨車裝運。若已知這3種貨物每一種的質(zhì)量和運輸例如下表所示。在載貨量許可的條件下，每車裝載每一種貨物的件數(shù)不限，應(yīng)如何搭配這3種貨物，才能使每車裝載貨物的利潤最大？貨物種類每件質(zhì)量（t）每件運輸利潤（百元）12823133418該問題中的貨車可以看做是一個背包，需運載的貨物為要裝入背包的物品。

該問題可以看作是一個3階段的動態(tài)規(guī)劃問題。15第四節(jié)配載問題今有一輛載貨量為6t的載貨步驟1，劃分階段。設(shè)每裝一種貨物為一個階段，k=1,2,3。步驟2，確定狀態(tài)變量。設(shè)狀態(tài)變量為

可用于裝載第k種至第n種貨物的裝載量。1） 確定決策變量。設(shè)決策變量表示第k種貨物的裝載件數(shù)

2） 狀態(tài)轉(zhuǎn)移方程為

3） 階段指標函數(shù)。第k階段裝載件貨物時所創(chuàng)的利潤。4） 函數(shù)的基本方程為步驟1，劃分階段。設(shè)每裝一種貨物為一個階段，k=1,2,3。k=3時

階段

01

k=301234560—0—0—0—018018018000018181800001110123012k=3時0k=2時

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450k=2時k=1時階段

0123

k=160+268+1816+024+0260，16,4=26k=1時階段

階段

01

k=301234560—0—0—0—018018018000018181800001110123012

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450

階段

0

1

2

3

k=160+268+1816+024+0260，16,40164第五節(jié)配載問題用動態(tài)規(guī)劃解決持續(xù)三個月生產(chǎn)的問題。問題的數(shù)據(jù)見下表每個月當成一個階段來進行計算求解。還要注意到該問題在實現(xiàn)優(yōu)化的每個階段都必須滿足三個約束條件：（1）最終庫存量必須小于等于倉庫容量；（2）每階段的生產(chǎn)量不能超過生產(chǎn)能力；（3）初始庫存量加上生產(chǎn)量必須大于等于需求量。能力單位成本月需求生產(chǎn)存儲生產(chǎn)持有1月232$175$302月323150303月33220040一月的初始庫存為1單位21第五節(jié)配載問題用動態(tài)規(guī)劃解決持續(xù)三個月生產(chǎn)的問題。問65

--第k階段的需求量；

--第k階段的生產(chǎn)能力；

--第k階段結(jié)束時的存儲能力；

--第k階段生產(chǎn)單位產(chǎn)品的費用；

--第k階段單位產(chǎn)品的庫存持有成本步驟1：劃分階段。把每個月看成一個階段，倒序命名各個時期。即階段1對應(yīng)3月，階段2對應(yīng)2月，階段3對應(yīng)1月。步驟2：確定狀態(tài)變量。設(shè)為狀態(tài)變量，表示第k階段的開始的庫存量。由于1月份初始庫存為1單位，故。另外定義，表示為第3階段末的庫存量。步驟3：確定決策變量。設(shè)為決策變量，表示第k階段的生產(chǎn)量。且必須滿足如下三個約束條件：22--第k階段的需求量；步驟1：劃分階段。把每個月看成66步驟4：狀態(tài)轉(zhuǎn)移方程。步驟5：指標函數(shù)。第k階段的指標函數(shù)是第k階段的生產(chǎn)成本（包括生產(chǎn)費用與貯存費用）。步驟6：函數(shù)基本方程23步驟4：狀態(tài)轉(zhuǎn)移方程。步驟5：指標函數(shù)。第k階段的指標函第一階段：即從3月份開始正向計算。k=1時，問題可以如下表示：

01230———60036001——40064024002—200440680120030240480—00

第一階段：即從3月份開始正向計算。k=1時，問題可以如下表示第二階段：k=2時，該階段的子問題可以表示為：

012

0————M1——300+60029002—150+600330+4002730

第二階段：k=2時，該階段的子問題可以表示為：第三階段：k=3時，該階段的子問題可以表示為：

0123

1—175+M380+9001185+73021280

第三階段：k=3時，該階段的子問題可以表示為：

01230———60036001——40064024002—200440680120030240480—00

012

0————M1——300+60029002—150+600330+4002730

0123

1—175+M380+9001185+73021280

月份初始庫存生產(chǎn)量銷售量月末庫存生產(chǎn)成本持有成本總成本一月1221$350$30$380二月12303000300三月03306000600總計$1250$30$1280最優(yōu)策略

72第六節(jié)資源分配問題資源分配問題:是指將供應(yīng)量有限的一種或若干種資源（如原材料、資金、機器設(shè)備、勞動力等），分配給若干用戶，而使目標函數(shù)最優(yōu)。設(shè)有某一種原料，總量為M，擬用來進行n種生產(chǎn)活動。若分配數(shù)量為的原料用于第i種生產(chǎn)活動，其收益為，應(yīng)該如何分配，才能使n種生產(chǎn)活動的總收益最大？

靜態(tài)規(guī)劃模型為：29第六節(jié)資源分配問題資源分配問題:是指將供應(yīng)量有限的一種或73用動態(tài)規(guī)劃方法求解此類問題時，一般地，將n種活動作為一個互相銜接的整體，由于要確定分配給每種活動的資源數(shù)，因此通常以把資源分配給一個或幾個使用者的過程作為一個階段，每個階段都要確定分配給一種活動的資源量，并要先對n種活動指定分配的階段序號。在資源分配中，由于將階段聯(lián)系在一起的是所有生產(chǎn)活動都在爭取的資源，因此，狀態(tài)變量就要按照資源的分配來確定。故把第k階段的狀態(tài)變量定義為第k階段初所擁有的資源量，即將要在第k種活動到第n種活動間分配的資源量。這樣，我們在確定第k階段的資源分配時就無需考慮以前的資源分配情況。決策變量就定義為對第k種活動的資源投放量，即對第k種活動的資源分配量。30用動態(tài)規(guī)劃方法求解此類問題時，一般地，將n種活動作為一個74某船舶總公司擬將5億元資金投放到下屬A、B、C三個船廠，各船廠在獲得資金后的收益如表所示。試用動態(tài)規(guī)劃方法求使總收益最大的投資分配方案。A、B、C三個船廠分別編號為1，2，3，對A、B、C三個船廠分配資金分別形成1,2,3三個階段，即該問題可作為三階段決策過程。k=1,2,3。

k=1時，將資金分給1,2,3三個船廠；

k=2時，將資金分給2,3兩個船廠；

k=3時，將資金分給3船廠。31某船舶總公司擬將5億元資金投放到下屬A、B、C三個船廠，75K=3時，考慮將資金分給船廠C，

k=3012345013791001234532K=3時，考慮將資金分給船廠C，00076k=2時，考慮將資金分給船廠B、C，

012345k=201234500+10+30+70+90+104+04+14+34+74+96+06+16+36+78+08+18+39+09+19+004681113012311,