運(yùn)籌學(xué)第六章

第6章動(dòng)態(tài)規(guī)劃第1節(jié)多階段決策過(guò)程及實(shí)例第2節(jié)動(dòng)態(tài)規(guī)劃的基本概念和方程第3節(jié)動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理第4節(jié)動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系第5節(jié)動(dòng)態(tài)規(guī)劃應(yīng)用舉例

第1節(jié)多階段決策過(guò)程及實(shí)例

動(dòng)態(tài)規(guī)劃研究的對(duì)象是多階段決策問(wèn)題。所謂多階段決策問(wèn)題是指一類(lèi)活動(dòng)過(guò)程，它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決策。這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱(chēng)為策略。多階段決策問(wèn)題就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)。多階段決策問(wèn)題的典型例子：

1.生產(chǎn)決策問(wèn)題：企業(yè)在生產(chǎn)過(guò)程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。

2.機(jī)器負(fù)荷分配問(wèn)題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策

這時(shí)，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終完好的機(jī)器就為au,0<a<1。

在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為

h=h(u2)

假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1。要求制定一個(gè)五年計(jì)劃，在每年開(kāi)始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。

相應(yīng)的機(jī)器年完好率b,0<b<1。

3.航天飛機(jī)飛行控制問(wèn)題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問(wèn)題）。

不包含時(shí)間因素的靜態(tài)決策問(wèn)題（本質(zhì)上是一次決策問(wèn)題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解決。

4

.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問(wèn)題也可以通過(guò)適當(dāng)?shù)匾腚A段的概念，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決，后面將詳細(xì)介紹。

5.最短路問(wèn)題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總費(fèi)用最?。?。6AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876835338422123335526643123456生產(chǎn)存貯決策問(wèn)題最短路問(wèn)題機(jī)器負(fù)荷分配問(wèn)題典型問(wèn)題:第2節(jié)動(dòng)態(tài)規(guī)劃的基本概念和基本方程

2.1動(dòng)態(tài)規(guī)劃的基本概念但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱(chēng)為狀態(tài)允許集合。1.

階段、階段變量把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段;描述階段的變量稱(chēng)為階段變量，常用k表示；階段的劃分，一般是按時(shí)間和空間的自然特征來(lái)劃分；2.狀態(tài)、狀態(tài)變量狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀態(tài)或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)。描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量，常用sk表示第k階段的狀態(tài)。一個(gè)數(shù)、一組數(shù)、一個(gè)向量在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱(chēng)為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有一個(gè)數(shù)一組數(shù)一個(gè)向量在最優(yōu)控制中也稱(chēng)為控制。描述決策的變量，稱(chēng)為決策變量決策變量是狀態(tài)變量的函數(shù)常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。3.決策、決策變量過(guò)程的某一階段、某個(gè)狀態(tài),可以做出不同的決定(選擇),決定下一階段的狀態(tài)，這種決定稱(chēng)為決策。uk(sk)

Dk(sk)系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān)。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。4.多階段決策過(guò)程可以在各個(gè)階段進(jìn)行決策，去控制過(guò)程發(fā)展的多段過(guò)程，其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的。12ks1u1s2u2s3skukSk+1能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類(lèi)特殊的多階段決策過(guò)程，即具有無(wú)后效性的多階段決策過(guò)程。*無(wú)后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展；構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無(wú)后效性的要求；如果狀態(tài)變量不能滿足無(wú)后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下?tīng)顟B(tài)變量要滿足無(wú)后效性的要求；5.策略：按順序排列的決策組成的集合；

由第k

n(終止?fàn)顟B(tài))為止的過(guò)程，稱(chēng)為問(wèn)題的后部子過(guò)程（k子過(guò)程）。

當(dāng)k=1時(shí)，此決策函數(shù)序列成為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略，記為p1,n

(s1)。即

可供選擇的策略有一定范圍，此范圍稱(chēng)為允許策略集合，用p表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱(chēng)為最優(yōu)策略。

由每段的決策按順序排列組成的決策函數(shù)序列稱(chēng)為k子過(guò)程策略，簡(jiǎn)稱(chēng)子策略，記為pk,n(sk)，即動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，稱(chēng)為指標(biāo)函數(shù)；它是定義在全過(guò)程或所有后部子過(guò)程上確定的數(shù)量函數(shù)(費(fèi)用、成本、利潤(rùn)、路長(zhǎng)等)。用Vk,n

表示。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。(1)過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)和。即其中vj(sj

,uj)

表示第

j階段的階段指標(biāo)。這時(shí)上式可寫(xiě)成(2)過(guò)程和它的任意子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即則可改寫(xiě)成常見(jiàn)的指標(biāo)函數(shù)的形式：表示從第k階段的狀態(tài)Sk開(kāi)始到第n階段的終止?fàn)顟B(tài)的過(guò)程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即最優(yōu)值函數(shù)其中“opt”可根據(jù)題意取min或max

多階段決策過(guò)程的數(shù)學(xué)模型：（具有無(wú)后效性）小結(jié):方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量k﹑狀態(tài)變量sk﹑決策變量uk;指標(biāo):

動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過(guò)程;

效益指標(biāo)函數(shù)形式:

和積無(wú)后效性可遞推解多階段決策過(guò)程問(wèn)題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時(shí)的狀態(tài)序列

最優(yōu)目標(biāo)函數(shù)值從k到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值最短路的特性：如果已有從起點(diǎn)到終點(diǎn)的一條最短路，那么從最短路線上中間任何一點(diǎn)出發(fā)到終點(diǎn)的路線仍然是最短路。（證明用反證法）2.2動(dòng)態(tài)規(guī)劃的基本思想和基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368768353384221233355266431234566

k=5，出發(fā)點(diǎn)E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=3k=1,k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D2f3(C4)=12

u3(C4)=D3k=3,k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3d1(A,B1)+f2(B1)d1(A,B2)+f2(B2)=minf1(A)=min5+133+16=18u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最優(yōu)策略從上面的計(jì)算過(guò)程可以看出，在求解的各個(gè)階段,我們利用了k階段與k+1階段之間的遞推關(guān)系:fk(sk)=min｛dk(sk,uk(sk))+fk+1(uk(sk))｝ukDk(sk)f7(s7)=0k=6,5,4,3,2,1一般情況,k階段與k+1階段的遞推關(guān)系式（動(dòng)態(tài)規(guī)劃的基本方程）邊界條件為動(dòng)態(tài)規(guī)劃方法的基本思想：求解時(shí)從邊界條件開(kāi)始，逆（或順）過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每個(gè)問(wèn)題求解時(shí)，都要使用它前面已求出的子問(wèn)題的最優(yōu)結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。

將多階段決策過(guò)程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)，正確寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡(jiǎn)言之為基本方程）。從而把問(wèn)題化成一族同類(lèi)型的子問(wèn)題；在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過(guò)的各段狀態(tài)便可確定了最優(yōu)路線。動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。每段決策的選取都是從全局考慮的,與該段的最優(yōu)選擇答案一般是不同的。375976713109111316

184AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355

26631234564逆序解法的基本方程(和的情況)邊界條件為式中sk+1=Tk(sk,uk)，其求解過(guò)程，根據(jù)邊界條件，從k=n開(kāi)始，由后向前逆推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求得f1(s1)

就是整個(gè)問(wèn)題的最優(yōu)解。其中fk(sk)表示第k階段的初始狀態(tài)為sk，從k階段到n階段所得到的最優(yōu)效益值。逆序解法的基本方程(積的情況)邊界條件為12s1u1s2u2s3nsnunSn+1kskukSk+1順序解法的基本方程(和的形式)邊界條件為式中sk=Tkr(sk+1,uk)，其求解過(guò)程，根據(jù)邊界條件，從k=1開(kāi)始，由前向后順推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求得fn(sn+1)時(shí)，就得到整個(gè)問(wèn)題的最優(yōu)解。其中fk(sk+1)表示第k階段的結(jié)束狀態(tài)為sk＋1時(shí)，從1階段到k階段所得到的最優(yōu)效益值。順序解法的基本方程(積的形式)邊界條件為12s1u1s2u2s3nsnunSn+1kskukSk+1小結(jié):ⅱ要具有可分離性，并滿足遞推關(guān)系。即ⅲ函數(shù)k（sk，uk，Vk+1,n）對(duì)于變量Vk+1，n要嚴(yán)格單調(diào)。將問(wèn)題的過(guò)程劃分成恰當(dāng)?shù)碾A段；選擇狀態(tài)變量sk,既能描述過(guò)程的變化又滿足無(wú)后效性；確定決策變量uk及每一階段的允許決策集合Dk(sk)；正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程；正確寫(xiě)出指標(biāo)函數(shù)Vk,n，它應(yīng)滿足下面三個(gè)性質(zhì)：ⅰ是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù);第3節(jié)動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理

多階段決策過(guò)程的特點(diǎn)：每個(gè)階段都要進(jìn)行決策，策略是由n個(gè)相繼進(jìn)行的決策構(gòu)成的決策序列。前一階段的終止?fàn)顟B(tài)又是下一階段的初始狀態(tài)，因此，確定階段最優(yōu)決策不能只從本階段的效應(yīng)來(lái)考慮，必須是整個(gè)過(guò)程通盤(pán)考慮，整體規(guī)劃。即階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)。理論基礎(chǔ)

適應(yīng)于用動(dòng)態(tài)規(guī)劃方法求解的是具有無(wú)后效性的多階段決策過(guò)程。

動(dòng)態(tài)規(guī)劃方法的理論基礎(chǔ)是基于R.Bellman提出的最優(yōu)性原理：“一個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論其初始狀態(tài)及初始決策如何，對(duì)于先前決策所形成的狀態(tài)而言，余下的諸決策仍構(gòu)成最優(yōu)策略?！?/p>

最優(yōu)性原理的含義是：最優(yōu)策略的任何一部分子策略，也是它相應(yīng)初始狀態(tài)的最優(yōu)策略。每個(gè)最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。反映動(dòng)態(tài)規(guī)劃基本方程的是最優(yōu)化定理，它是策略最優(yōu)的充分必要條件，而最優(yōu)化原理僅僅是策略最優(yōu)的必要條件，它是最優(yōu)化定理的推論。最優(yōu)性定理及證明略。第4節(jié)動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系例1用逆推解法求解下面問(wèn)題:分三個(gè)階段，即k=1，2，3;解：設(shè)狀態(tài)變量（因此可得狀態(tài)轉(zhuǎn)移方程）：考慮效益函數(shù)的形式分階段狀態(tài)變量與決策變量有密切關(guān)系，狀態(tài)變量一般為累計(jì)量或隨遞推過(guò)程變化的量。確定決策變量：x1,x2,x3通?？扇§o態(tài)規(guī)劃中的變量為決策變量

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

最優(yōu)指標(biāo)函數(shù)：fk(sk)

基本方程當(dāng)階段k=3時(shí)，有當(dāng)階段k=2時(shí)，有得最優(yōu)決策最優(yōu)目標(biāo)函數(shù)有兩個(gè)解，其中x2=0舍去。因2階導(dǎo)數(shù)在x*2處小于0，故有極大值。當(dāng)階段k=1時(shí)，有最優(yōu)決策最優(yōu)目標(biāo)函數(shù)因此最后可得：s3=s2-x*2=s1-x*1-x*2問(wèn)如何分配投資數(shù)額才能使總效益最大?解：可列出靜態(tài)規(guī)劃問(wèn)題的模型如下分三個(gè)階段，即k=1，2，3。狀態(tài)變量sk為第k階段初可分配給第k到第3個(gè)項(xiàng)目的資金數(shù)決策變量xk為決定投給第k個(gè)項(xiàng)目的資金

確定狀態(tài)變量(因此可得狀態(tài)轉(zhuǎn)移方程)：例2某公司有資金10萬(wàn)元，若投資于項(xiàng)目(i=1,2,3)的投資額為xi時(shí)，其效益分別為狀態(tài)轉(zhuǎn)移方程

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

最優(yōu)指標(biāo)函數(shù)：fk(sk)

基本方程最優(yōu)目標(biāo)函數(shù)f3(s3)=2s32

當(dāng)階段k=3時(shí)，有f3(s3)=max｛2x32｝0≤

x3≤s3最優(yōu)決策為x3*=s3當(dāng)階段k=2時(shí)，有2階導(dǎo)數(shù)大于0，存在極小點(diǎn)。最大值點(diǎn)只能在[0，s2]端點(diǎn)上取得，即當(dāng)當(dāng)當(dāng)時(shí)，時(shí)，時(shí)，此時(shí)此時(shí)當(dāng)階段k=1時(shí)，有2階導(dǎo)數(shù)>0，故比較[0,10]的端點(diǎn)因?yàn)椤嘧顑?yōu)投資方案是全部資金投于第3個(gè)項(xiàng)目，可得最大收益200萬(wàn)元。S2>9/2當(dāng)當(dāng)時(shí)時(shí)矛盾，舍去。（最優(yōu)決策）S2<9/2

當(dāng)階段k=n時(shí)逆推解法小結(jié)：

設(shè)已知初始狀態(tài)s1，最優(yōu)值函數(shù)fk(sk)表示從k階段到n階段所得到的最大效益。以求最大化為例來(lái)說(shuō)明。即其中s表示狀態(tài)，x表示決策（控制）?？傻米顑?yōu)決策xn=xn(sn)和最優(yōu)值fn(sn)。若D(sn)只有一個(gè)決策,則可寫(xiě)成xn=xn(sn)。具體方法如下：

當(dāng)階段k=n-1時(shí)其中狀態(tài)轉(zhuǎn)移方程得到最優(yōu)決策xn-1=xn-1(sn-1)和最優(yōu)值fn-1(sn-1)。

當(dāng)階段k=k時(shí)其中狀態(tài)轉(zhuǎn)移方程得最優(yōu)決策xk=xk(sk)和最優(yōu)值fk(sk)。如此類(lèi)推，直到第一階段。當(dāng)階段k=1時(shí)其中狀態(tài)轉(zhuǎn)移方程得最優(yōu)決策x1=x1(s1)和最優(yōu)值f1(s1)。由于初始狀態(tài)s1已知,故x1=x1(s1)和f1(s1)是確定的,根據(jù)狀態(tài)轉(zhuǎn)移方程按照上述遞推過(guò)程相反順序推算下去，就可逐步確定出每階段的決策及效益。例3用順推解法求解下面問(wèn)題:設(shè)s4=c,fk(sk+1)表示第k階段的結(jié)束狀態(tài)為

sk+1，從1階段到k階段的最大值。分三個(gè)階段，即k=1，2，3;解：設(shè)狀態(tài)變量（因此可得狀態(tài)轉(zhuǎn)移方程）：確定決策變量：x1,x2,x3

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

最優(yōu)指標(biāo)函數(shù)：fk(sk+1)

基本方程當(dāng)階段k=1時(shí)，有當(dāng)階段k=2時(shí)，有得最優(yōu)決策最優(yōu)目標(biāo)函數(shù)當(dāng)階段k=3時(shí)，有最優(yōu)決策最優(yōu)目標(biāo)函數(shù)因此最后可得：例4用動(dòng)態(tài)規(guī)劃方法解下面問(wèn)題解：設(shè)狀態(tài)變量為s0、s1、s2、s3按問(wèn)題中變量的個(gè)數(shù)分為三個(gè)階段，即k=1，2，3

確定決策變量：x1,x2,x3

fk(sk)表示第k階段的結(jié)束狀態(tài)為sk，從1階段到k階段的最大值。確定狀態(tài)變量(因此可得狀態(tài)轉(zhuǎn)移方程)：狀態(tài)轉(zhuǎn)移方程最優(yōu)目標(biāo)函數(shù)f1(s1)=(4/9)s12

當(dāng)階段k=1時(shí)，有f1(s1)=max｛4x12｝X1＝s1/3最優(yōu)決策為x1*=s1/3當(dāng)階段k=2時(shí)，有因該點(diǎn)不在允許決策集合內(nèi)，最大值點(diǎn)只能在[0，s2/2]端點(diǎn)上取得，即所以h2(s2,x2)的最大值點(diǎn)在x2=0處，故得到f2(s2)=(4/9)s22及相應(yīng)的最優(yōu)解x2*=0。當(dāng)階段k=3時(shí)，有由于s3不知道，故須再對(duì)s3求一次極值，即

當(dāng)階段k=1時(shí)順推解法小結(jié)：

設(shè)已知初始狀態(tài)sn+1，最優(yōu)值函數(shù)fk(s)表示第k階段末的結(jié)束狀態(tài)為s，從1階段到k階段所得到的最大效益。以求最大化為例來(lái)說(shuō)明。即其中s表示狀態(tài)，x表示決策（控制）?？傻米顑?yōu)決策x1=x1(s2)和最優(yōu)值f1(s2)。若D1(s1)只有一個(gè)決策,則可寫(xiě)成x1=x1(s2)。具體方法如下：

當(dāng)階段k=2時(shí)其中狀態(tài)轉(zhuǎn)移方程得到最優(yōu)決策x2=x2(s3)和最優(yōu)值f2(s3)。

當(dāng)階段k=k時(shí)其中狀態(tài)轉(zhuǎn)移方程得最優(yōu)決策xk=xk(sk+1)和最優(yōu)值fk(sk+1)。如此類(lèi)推，直到第n階段。

當(dāng)階段k=n時(shí)其中狀態(tài)轉(zhuǎn)移方程得最優(yōu)決策xn=xn(sn+1)和最優(yōu)值fn(sn+1)。由于終止?fàn)顟B(tài)sn+1已知,故xn=xn(sn+1)和fn(sn+1)是確定的,根據(jù)狀態(tài)轉(zhuǎn)移方程按照上述遞推過(guò)程相反順序推算下去，就可逐步確定出每階段的決策及效益。動(dòng)態(tài)規(guī)劃的優(yōu)缺點(diǎn)：優(yōu)點(diǎn):.

最優(yōu)解是全局最優(yōu)解。

.能得到一系列（包括子過(guò)程）的最優(yōu)解。

.不需要對(duì)系統(tǒng)狀態(tài)轉(zhuǎn)移方程、階段效應(yīng)函數(shù)等的解析性質(zhì)作任何假設(shè)。缺點(diǎn)：

.沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)模型和標(biāo)準(zhǔn)的算法可供使用。

.應(yīng)用具有局限性，要求滿足“無(wú)后效性”。

.存在“維數(shù)災(zāi)難”問(wèn)題，變量的個(gè)數(shù)增加，計(jì)算的難度成倍增加。第5節(jié)動(dòng)態(tài)規(guī)劃應(yīng)用舉例

5.1節(jié)一維資源分配問(wèn)題設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)問(wèn)應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？將數(shù)量一定的一種或若干種資源，恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，使效益函數(shù)為最優(yōu)。maxz=g1(x1)+g2(x2)+‥‥+gn(xn)x1+x2+…+xn=axi≥0i=1,2,…,ns.t.決策集合：Dk(sk)={uk|0uk=xksk}uk:分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，即uk=xk；sk:分配給用于生產(chǎn)第k種至第n種產(chǎn)品的原料數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk=sk-xk最優(yōu)值函數(shù)fk(sk):數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收益，動(dòng)態(tài)規(guī)劃的遞推關(guān)系為：某工業(yè)部門(mén)根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備5臺(tái)分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備，可以為公司提供的盈利如表。

問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。例1解：將問(wèn)題按工廠分為三個(gè)階段，甲、乙、丙分別編號(hào)為1，2，3。=g3﹙0﹚=0=maxk=3時(shí)，0s35，0x3s3f3(s3)=max﹝g3﹙x3﹚﹞0≤x3≤s3f4(s4)=0g3(0)g3(1)

=4x3*(1)=1S3=0,f3(0)=max｛g3﹙x3﹚+f4(s4)｝

0≤x3≤s3x3*(0)=0x3=0,1S3=1,f3(1)=max｛g3﹙x3﹚+f4(s4)｝0≤x3≤s3當(dāng)階段k=2時(shí)，s3=s2-x2，

0s25，0x2s2，有結(jié)果列于下表：f3(1-0)=f3(1)=4

f3(5-3)=f3(2)=max=21g1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0)

=max｛g1﹙x1﹚+f2(s1-x1)｝x1=0,1,2,3,4,5當(dāng)階段k=1時(shí)，s2=s1-x1，

s1=5，0x1s1，有S1=5,f1(S1)=max｛g1﹙x1﹚+f2(s2)｝0≤x1≤s1x1*(5)=0,20+213+167+149+1012+513+0=

max結(jié)果可寫(xiě)成表格的形式S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一張表S3*=s2*-x2*=5-2=3x3*=3x2*=2按計(jì)算表格的順序逆推，可知最優(yōu)分配方案有兩個(gè)：甲工廠分配0臺(tái)，乙工廠分配2臺(tái),丙工廠分配3臺(tái)。甲工廠分配2臺(tái)，乙工廠分配2臺(tái)，丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬(wàn)元1.2資源連續(xù)分配問(wèn)題:一般問(wèn)題的提法是

A種生產(chǎn)數(shù)量u1投入收益g(u1)

年終資源回收率a如此進(jìn)行n年，如何確定投入A的資源量u1、…、un，使總收入最大？

B種生產(chǎn)數(shù)量s1-u1收益h(s1-u1)

年終資源回收率b資源數(shù)量s1第一年資源數(shù)量s2=au1+b(s1-u1)第二年

A種生產(chǎn)數(shù)量u2投入;收益g(u2);年終回收率a

B種生產(chǎn)數(shù)量s2-u2;收益h(s2-u2);年終回收率b到n年此問(wèn)題的靜態(tài)規(guī)劃問(wèn)題模型為：動(dòng)態(tài)規(guī)劃的逆推關(guān)系方程為：最后求得得f1(s1)即為所求問(wèn)題的最大收入。

高負(fù)荷:產(chǎn)量函數(shù)g=8u1,u1是投入生產(chǎn)的機(jī)器

數(shù)量，年完好率為a=0.7，低負(fù)荷:產(chǎn)量函數(shù)h=5y，y是投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開(kāi)始生產(chǎn)時(shí)完好機(jī)器的數(shù)量為1000臺(tái)。

機(jī)器

例2機(jī)器負(fù)荷分配問(wèn)題解：設(shè)階段數(shù)k表示年度。試問(wèn)每年如何安排機(jī)器在高低兩種負(fù)荷下的生產(chǎn)，可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。狀態(tài)變量sk為第k年度初擁有的完好機(jī)器臺(tái)數(shù)；

決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)。低負(fù)荷下生產(chǎn)的機(jī)器臺(tái)數(shù)是sk-uk。

狀態(tài)轉(zhuǎn)移方程第k年度產(chǎn)量為

遞推方程為指標(biāo)函數(shù)允許決策集合

0uksk當(dāng)k=5時(shí),f5(s5)=max﹛8u5+5﹙s5-u5﹚

+f6(s6)﹜0≤u5≤s5=max﹛3u5+5s5﹜0≤u5≤s5u5*=s5,f5(s5)=8s5當(dāng)k=4時(shí),

f4(s4)=max﹛8u4+5(s4–u4)

+f5(0.7u4+0.9(s4–u4))﹜0≤u4≤s4=max﹛13.6u4+12.2(s4-u4﹜0≤u4≤s4=max﹛1.4u4+12.2s4﹜0≤u4≤s4u4*=

s4,f4(s4)=13.6s4依次類(lèi)推可得，u3*=s3f3(s3)=17.5s3

u2*=0

f2(s2)=20.8s2

u1*=0

f1(s1)=23.7s1最高產(chǎn)量為f1(s1)

=23700(臺(tái))。因此最優(yōu)策略為:

u1*=0,u2*=0,u3*=s3,u4*=s4u5*=s5,u5*=s5,f5(s5)=8s5u4*=

s4,f4(s4)=13.6s45.2生產(chǎn)存貯問(wèn)題一個(gè)生產(chǎn)部門(mén)，如何在已知生產(chǎn)成本、庫(kù)存費(fèi)用和各階段市場(chǎng)需求條件下，決定各階段產(chǎn)量，使計(jì)劃內(nèi)的費(fèi)用總和為最小的問(wèn)題。例8.某工廠要對(duì)一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)于該產(chǎn)品的需求量如下表所示。假定該廠生產(chǎn)每批產(chǎn)品的固定成本3千元，若不生產(chǎn)就為0；每單位產(chǎn)品成本為1千元；每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過(guò)6個(gè)單位；每個(gè)時(shí)期未售出的產(chǎn)品，每單位需付存貯費(fèi)0.5千元。還假定在第一個(gè)時(shí)期的初始庫(kù)存量為0，第四個(gè)時(shí)期末的庫(kù)存量也為0。問(wèn)該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，才能在滿足市場(chǎng)需求條件下，使總成本最小。解：設(shè)dk為第k階段的需求量，xk為第k階段的生產(chǎn)量，vk為第k時(shí)期末庫(kù)存量。有vk=vk-1+xk-dk把生產(chǎn)的四個(gè)時(shí)期作為四個(gè)階段，k=1,2,3,4。由題意知，第k階段的生產(chǎn)成本為第k時(shí)期末庫(kù)存量為vk時(shí)的存儲(chǔ)費(fèi)用為hk(vk)=0.5vk第k時(shí)期內(nèi)的總成本為ck(xk)+hk(vk)動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系式為當(dāng)k=1時(shí)，由f1(v1)=min{c1(x1)+h1(v1)}

對(duì)v1在0與之間的值分別進(jìn)行計(jì)算即v1=0,1,2,3,4，于是由x1=min{v1+2,6}知，x1可取值為2,3,4,5,6。分別計(jì)算如下：

f1(0)=min{3+x1+0.5×0}=5 所以x1=2x1=min(v1+2,6)x1=2

f1(1)=min{3+x1+0.5×1}=6.5所以x1=3

f1(2)=min{3+x1+0.5×2}=8 所以x1=4

f1(3)=min{3+x1+0.5×3}=9.5 所以x1=5

f1(4)=min{3+x1+0.5×4}=11 所以x1=6k=2，f2(v2)=min{c2(x2)+h2(v2)+f1(v2+3-x2)}0≤x2≤min{v2+3,6}x1=3x1=4x1=5x1=6v2可在0與之間取值。即v2可取值0,1,2,3。x2可在0與min{v2+3,6}之間取值。分別計(jì)算如下：由有x2=0。由有x2=0。用同樣的方法計(jì)算f2(2)=min{c2(x2)+h2(2)+f1(5－x2)}=14,有x2=5 0≤x2≤5 f2(3)=min{c2(x2)+h2(3)+f1(6－x2)}=15.5，有x2=6 0≤x2≤6k=3，f3(v3)=min{c3(x3)+h3(v3)+f2(v3+2－x3)}，v3可在0與min{4,6－2}=4之間取值。x3可在0與min{v3+2,6}之間取值。分別計(jì)算如下：有x3=0。用同樣的方法計(jì)算

f3(2)=min{c3(x3)+h3(2)+f2(4－x3)}=17.5，有x3=4 0≤x3≤4

f3(3)=min{c3(x3)+h3(3)+f2(5－x3)}=19，有x3=5 0≤x3≤5

f3(4)=min{c3(x3)+h3(4)+f2(6－x3)}=20.5，有x3=6 0≤x3≤6有x3=0或3。k=4，因要求第4時(shí)期末的庫(kù)存量為0，即v4=0，故有

f4(0)=min{c4(x4)+h4(0)+f3(4－x4)}

0≤x4≤4

x4=0。按計(jì)算順序反推算，可找出每個(gè)時(shí)期的最優(yōu)生產(chǎn)決策為: x1=5，x2=0，x3=6，x4=0其相應(yīng)的最小總成本為20.5千元。例10某車(chē)間需要按月在月底都要供應(yīng)一定數(shù)量的部件總裝車(chē)間，由于生產(chǎn)條件的變化，該車(chē)間在各月中生產(chǎn)每單位這種部件所耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車(chē)間的各個(gè)月份的需求量以及在加工車(chē)間生產(chǎn)該部件每單位數(shù)所需工時(shí)數(shù)如表6-7所示。設(shè)庫(kù)存容量H=9，開(kāi)始時(shí)庫(kù)存量為2，期終庫(kù)存量為