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

第六章動(dòng)態(tài)規(guī)劃第六章動(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é)：配載問(wèn)題第五節(jié)：生產(chǎn)和庫(kù)存控制問(wèn)題第六節(jié)：資源分配問(wèn)題第七節(jié)：動(dòng)態(tài)規(guī)劃應(yīng)用第一節(jié)：現(xiàn)實(shí)中的動(dòng)態(tài)規(guī)劃問(wèn)題

多式聯(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é)：現(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)：多式聯(lián)運(yùn)是一種以實(shí)現(xiàn)貨物整體運(yùn)輸最優(yōu)化為ZH物流公司是一家大型的集裝箱多式聯(lián)運(yùn)經(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)城市為南京與鄭州?，F(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)輸1474704349鐵路運(yùn)輸1353695303水路運(yùn)輸//392運(yùn)輸方式鐵路運(yùn)輸公路運(yùn)輸水路運(yùn)輸運(yùn)載工具速度(km/h)7010036運(yùn)輸方式鐵路運(yùn)輸公路運(yùn)輸水路運(yùn)輸中轉(zhuǎn)時(shí)間(h)7318如何制定運(yùn)輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運(yùn)輸總成本？ZH物流公司是一家大型的集裝箱多式5

…S’k+1……S2多階段決策問(wèn)題

階段、決策、策略動(dòng)態(tài)規(guī)劃的基本特性（多階段決策問(wèn)題的基本特性）第二節(jié)動(dòng)態(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多階段決策問(wèn)題第二節(jié)動(dòng)態(tài)規(guī)劃基本概動(dòng)態(tài)規(guī)劃方法的基本思路最短路問(wèn)題1234340476117811階段A124374632441514633334A3B1QA2B2B3TC1

C2——標(biāo)號(hào)法動(dòng)態(tài)規(guī)劃方法的基本思路最短路問(wèn)題12343404761178三、決策

是指人們對(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=1，2，…，n表示階段序號(hào)，稱為階段變量。二、狀態(tài)

狀態(tài)表示某段的初始條件。用sk表示第k段的狀態(tài)，稱為第k段狀態(tài)變量。sk∈Skk階段的允許決策集合三、決策動(dòng)態(tài)規(guī)劃的基本概念sk∈Skk階段的允許決策集合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)移方程。

五、策略

由各階段決策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)稱子策略?！蔖1而8四、狀態(tài)轉(zhuǎn)移方程五、策略∈P1而9

六、指標(biāo)函數(shù)

(1)階段指標(biāo)函數(shù)

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

(2)過(guò)程指標(biāo)函數(shù)

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

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

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

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

七、最優(yōu)解

(1)

最優(yōu)指標(biāo)函數(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)}

特別當(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ì)應(yīng)的最優(yōu)指標(biāo)f

*1

七、最優(yōu)解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)

=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é)動(dòng)態(tài)規(guī)劃的基本方法一、最優(yōu)化原理和積k=n,12第三節(jié)動(dòng)態(tài)規(guī)劃的基本方法三、基本步驟1°建立模型

(1)

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

(2)

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

(3)

設(shè)定決策變量xk

(4)

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

(5)

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

(6)

建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結(jié)論12第三節(jié)動(dòng)態(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é)配載問(wèn)題今有一輛載貨量為6t的載貨車，現(xiàn)有3種需要運(yùn)輸?shù)呢浳铮捎么溯d貨車裝運(yùn)。若已知這3種貨物每一種的質(zhì)量和運(yùn)輸例如下表所示。在載貨量許可的條件下，每車裝載每一種貨物的件數(shù)不限，應(yīng)如何搭配這3種貨物，才能使每車裝載貨物的利潤(rùn)最大？貨物種類每件質(zhì)量（t）每件運(yùn)輸利潤(rùn)（百元）12823133418該問(wèn)題中的貨車可以看做是一個(gè)背包，需運(yùn)載的貨物為要裝入背包的物品。

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

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

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

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

階段

01

k=301234560—0—0—0—018018018000018181800001110123012k=3時(shí)0k=2時(shí)

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450k=2時(shí)k=1時(shí)階段

0123

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

階段

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é)配載問(wèn)題用動(dòng)態(tài)規(guī)劃解決持續(xù)三個(gè)月生產(chǎn)的問(wèn)題。問(wèn)題的數(shù)據(jù)見(jiàn)下表每個(gè)月當(dāng)成一個(gè)階段來(lái)進(jìn)行計(jì)算求解。還要注意到該問(wèn)題在實(shí)現(xiàn)優(yōu)化的每個(gè)階段都必須滿足三個(gè)約束條件：（1）最終庫(kù)存量必須小于等于倉(cāng)庫(kù)容量；（2）每階段的生產(chǎn)量不能超過(guò)生產(chǎn)能力；（3）初始庫(kù)存量加上生產(chǎn)量必須大于等于需求量。能力單位成本月需求生產(chǎn)存儲(chǔ)生產(chǎn)持有1月232$175$302月323150303月33220040一月的初始庫(kù)存為1單位21第五節(jié)配載問(wèn)題用動(dòng)態(tài)規(guī)劃解決持續(xù)三個(gè)月生產(chǎn)的問(wèn)題。問(wèn)22

--第k階段的需求量；

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

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

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

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

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

第一階段：即從3月份開(kāi)始正向計(jì)算。k=1時(shí)，問(wèn)題可以如下表示第二階段：k=2時(shí)，該階段的子問(wèn)題可以表示為：

012

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

第二階段：k=2時(shí)，該階段的子問(wèn)題可以表示為：第三階段：k=3時(shí)，該階段的子問(wèn)題可以表示為：

0123

1—175+M380+9001185+73021280

第三階段：k=3時(shí)，該階段的子問(wèn)題可以表示為：

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

012

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

0123

1—175+M380+9001185+73021280

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

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

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

k=1時(shí)，將資金分給1,2,3三個(gè)船廠；

k=2時(shí)，將資金分給2,3兩個(gè)船廠；

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

k=3012345013791001234532K=3時(shí)，考慮將資金分給船廠C，00033k=2時(shí)，考慮將資金分給船廠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時(shí)，考慮將資金分給船廠B、C，012345034k=1時(shí)，考慮將資金分給船廠A、B、C

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

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時(shí)，也可以0123450000若總投資額為336第七節(jié)動(dòng)態(tài)規(guī)劃應(yīng)用第一節(jié)的集裝箱多式聯(lián)運(yùn)優(yōu)化問(wèn)題進(jìn)行求解表示所有節(jié)點(diǎn)城市的個(gè)數(shù)表示i城市可選運(yùn)輸方式集合，1-公路、2-鐵路、3-水運(yùn)表示集裝箱多式聯(lián)運(yùn)中貨物運(yùn)輸總量表示i城市到j(luò)城市k運(yùn)輸方式的單位距離的運(yùn)價(jià)表示i城市到j(luò)城市k運(yùn)輸方式的距離表示i城市到j(luò)城市k運(yùn)輸方式的速度表示i城市k運(yùn)輸方式轉(zhuǎn)換為l方式的中轉(zhuǎn)費(fèi)用表示i城市k運(yùn)輸方式轉(zhuǎn)換為l方式的中轉(zhuǎn)時(shí)間36第七節(jié)動(dòng)態(tài)規(guī)劃應(yīng)用第一節(jié)的集裝箱多式聯(lián)運(yùn)優(yōu)化問(wèn)題進(jìn)373738約束式（4）是確保運(yùn)輸?shù)倪B續(xù)性。i-1i+1i分成三種情況來(lái)討論均為1，則也為1一個(gè)為0，一個(gè)1，則必須為0均為0，則也為038約束式（4）是確保運(yùn)輸?shù)倪B續(xù)性。i-1i+1i分成三種情39模型基于動(dòng)態(tài)規(guī)劃的基本算法程序設(shè)計(jì)如下：步驟1：令每?jī)蓚€(gè)城市之間的運(yùn)輸過(guò)程為動(dòng)態(tài)規(guī)劃中的一個(gè)階段步驟2：選擇貨物到達(dá)城市的運(yùn)輸方式為該階段的狀態(tài)變量如：第2階段的到達(dá)方式有公路、鐵路，則設(shè)計(jì)一個(gè)3×n的狀態(tài)矩陣，矩陣的第k列表示第k個(gè)階段的狀態(tài)變量構(gòu)造的列向量（沒(méi)有的話，用MATLAB中特有的常量

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

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

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

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

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

多式聯(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é)：現(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)：多式聯(lián)運(yùn)是一種以實(shí)現(xiàn)貨物整體運(yùn)輸最優(yōu)化為ZH物流公司是一家大型的集裝箱多式聯(lián)運(yùn)經(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)城市為南京與鄭州?，F(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)輸1474704349鐵路運(yùn)輸1353695303水路運(yùn)輸//392運(yùn)輸方式鐵路運(yùn)輸公路運(yùn)輸水路運(yùn)輸運(yùn)載工具速度(km/h)7010036運(yùn)輸方式鐵路運(yùn)輸公路運(yùn)輸水路運(yùn)輸中轉(zhuǎn)時(shí)間(h)7318如何制定運(yùn)輸方式組合優(yōu)化方案使在滿足客戶需求的條件下降低集裝箱運(yùn)輸總成本？ZH物流公司是一家大型的集裝箱多式48

…S’k+1……S2多階段決策問(wèn)題

階段、決策、策略動(dòng)態(tài)規(guī)劃的基本特性（多階段決策問(wèn)題的基本特性）第二節(jié)動(dòng)態(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多階段決策問(wèn)題第二節(jié)動(dòng)態(tài)規(guī)劃基本概動(dòng)態(tài)規(guī)劃方法的基本思路最短路問(wèn)題1234340476117811階段A124374632441514633334A3B1QA2B2B3TC1

C2——標(biāo)號(hào)法動(dòng)態(tài)規(guī)劃方法的基本思路最短路問(wèn)題12343404761178三、決策

是指人們對(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=1，2，…，n表示階段序號(hào)，稱為階段變量。二、狀態(tài)

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

四、狀態(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)移方程。

五、策略

由各階段決策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)稱子策略?！蔖1而8四、狀態(tài)轉(zhuǎn)移方程五、策略∈P1而52

六、指標(biāo)函數(shù)

(1)階段指標(biāo)函數(shù)

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

(2)過(guò)程指標(biāo)函數(shù)

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

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

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

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

七、最優(yōu)解

(1)

最優(yōu)指標(biāo)函數(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)}

特別當(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ì)應(yīng)的最優(yōu)指標(biāo)f

*1

七、最優(yōu)解54第三節(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)

=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é)動(dòng)態(tài)規(guī)劃的基本方法一、最優(yōu)化原理和積k=n,55第三節(jié)動(dòng)態(tài)規(guī)劃的基本方法三、基本步驟1°建立模型

(1)

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

(2)

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

(3)

設(shè)定決策變量xk

(4)

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

(5)

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

(6)

建立函數(shù)基本方程2°遞推(逆推)求解3°得出(順推)結(jié)論12第三節(jié)動(dòng)態(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é)配載問(wèn)題今有一輛載貨量為6t的載貨車，現(xiàn)有3種需要運(yùn)輸?shù)呢浳?，均可用此載貨車裝運(yùn)。若已知這3種貨物每一種的質(zhì)量和運(yùn)輸例如下表所示。在載貨量許可的條件下，每車裝載每一種貨物的件數(shù)不限，應(yīng)如何搭配這3種貨物，才能使每車裝載貨物的利潤(rùn)最大？貨物種類每件質(zhì)量（t）每件運(yùn)輸利潤(rùn)（百元）12823133418該問(wèn)題中的貨車可以看做是一個(gè)背包，需運(yùn)載的貨物為要裝入背包的物品。

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

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

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

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

階段

01

k=301234560—0—0—0—018018018000018181800001110123012k=3時(shí)0k=2時(shí)

階段

012

k=201234560+0——0+0——0+0——0+013+0—0+1813+0—0+1813+0—0+1813+026+00001318182600010020120450k=2時(shí)k=1時(shí)階段

0123

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

階段

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é)配載問(wèn)題用動(dòng)態(tài)規(guī)劃解決持續(xù)三個(gè)月生產(chǎn)的問(wèn)題。問(wèn)題的數(shù)據(jù)見(jiàn)下表每個(gè)月當(dāng)成一個(gè)階段來(lái)進(jìn)行計(jì)算求解。還要注意到該問(wèn)題在實(shí)現(xiàn)優(yōu)化的每個(gè)階段都必須滿足三個(gè)約束條件：（1）最終庫(kù)存量必須小于等于倉(cāng)庫(kù)容量；（2）每階段的生產(chǎn)量不能超過(guò)生產(chǎn)能力；（3）初始庫(kù)存量加上生產(chǎn)量必須大于等于需求量。能力單位成本月需求生產(chǎn)存儲(chǔ)生產(chǎn)持有1月232$175$302月323150303月33220040一月的初始庫(kù)存為1單位21第五節(jié)配載問(wèn)題用動(dòng)態(tài)規(guī)劃解決持續(xù)三個(gè)月生產(chǎn)的問(wèn)題。問(wèn)65

--第k階段的需求量；

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

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

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

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

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

第一階段：即從3月份開(kāi)始正向計(jì)算。k=1時(shí)，問(wèn)題可以如下表示第二階段：k=2時(shí)，該階段的子問(wèn)題可以表示為：

012

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

第二階段：k=2時(shí)，該階段的子問(wèn)題可以表示為：第三階段：k=3時(shí)，該階段的子問(wèn)題可以表示為：

0123

1—175+M380+9001185+73021280

第三階段：k=3時(shí)，該階段的子問(wèn)題可以表示為：

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

012

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

0123

1—175+M380+9001185+73021280

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

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

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

k=1時(shí)，將資金分給1,2,3三個(gè)船廠；

k=2時(shí)，將資金分給2,3兩個(gè)船廠；

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

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

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