1、第4章 動(dòng)態(tài)規(guī)劃(Dynamic Programming),動(dòng)態(tài)規(guī)劃的基本概念和思想 最短路徑問(wèn)題 背包問(wèn)題 投資分配問(wèn)題,例 5.1.1 管道設(shè)計(jì),最短路問(wèn)題就是從某地出發(fā)，途經(jīng)若干中間點(diǎn)最后到達(dá)目的地，要求找出路程或費(fèi)用最小的路線。一般的最短路問(wèn)題將在下一章討論，這里只討論分層的最短路問(wèn)題。下面的管道設(shè)計(jì)問(wèn)題(例5.1.1)就是其中之一。,從A點(diǎn)到E點(diǎn)要鋪設(shè)一條煤氣管道， 中間必須經(jīng)過(guò)三個(gè)中間站， 第一站可在B1、B2、B3中選擇， 第二站可在C1、C2、C3中選擇， 第三站可在D1、D2、D3中選擇， 要求選擇一條由A 到E的鋪管路線，使總長(zhǎng)度最短。 其中兩點(diǎn)連線上的數(shù)字表示兩點(diǎn)間管線的

2、長(zhǎng)度。,從A點(diǎn)到E點(diǎn)鋪設(shè)管道，可以按其地理特點(diǎn)自然地分成四個(gè)階段：（如下圖所示） 從A到B是第一階段，從B到C是第二階段， 從C到D是第三階段，從D到E是第四階段，,在階段2，從B3點(diǎn)出發(fā)，只有C1、C3兩種可選擇的點(diǎn)， 如選C1,則C1就是階段2在B3點(diǎn)的決策結(jié)果； C1點(diǎn)既是階段2鋪設(shè)管道的終點(diǎn)，又是階段3鋪設(shè)管道的起點(diǎn)；,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,同樣的理由，可以遞推得其余階段的鋪設(shè)路線，如階段3在C1點(diǎn)的決策是D1，階段4在D1點(diǎn)的決策只有E點(diǎn)；由于到E點(diǎn)是整個(gè)鋪設(shè)管道的終點(diǎn)，至此，決策過(guò)程完成，鋪設(shè)一條A點(diǎn)到E點(diǎn)的管道是由四個(gè)階段的管道組

3、成的，如A-B3-C1-D1-E，它也稱(chēng)為一個(gè)策略。,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,可以看出，各個(gè)階段的決策不同，鋪設(shè)的管道也不同，并且當(dāng)某個(gè)階段的始點(diǎn)給定后，它直接影響著后面各階段的行進(jìn)路線和管道的長(zhǎng)短，而后面各階段的路線 的選取不受這點(diǎn)以前各階段路線的影響。,5,4,2,6,3,4,6,5,6,1,2,2,2,3,3,2,3,4,因此，最短路線問(wèn)題可簡(jiǎn)化為四個(gè)階段的決策問(wèn)題，使由這四個(gè)階段決策組成決策序列，也稱(chēng)為策略所決定的一條路線的總長(zhǎng)度最短。,遞推關(guān)系式為:,例 5.1.2 多階段資源分配問(wèn)題,設(shè)有數(shù)量為x的某種資源，將它投入兩種生產(chǎn)方式A和B

4、中：以數(shù)量y投入生產(chǎn)方式A，剩下的量投入生產(chǎn)方式B，則可得到收入g(y)+h(x-y)，其中g(shù)(y)和h(y)是已知函數(shù)，并且g(0)=h(0)=0；同時(shí)假設(shè)以y與x-y分別投入兩種生產(chǎn)方式A，B后可以回收再生產(chǎn)，回收率分別為a與b。試求進(jìn)行n個(gè)階段后的最大總收入。,若以y與x-y分別投入生產(chǎn)方式A與B，在第一 階段生產(chǎn)后回收的總資源為x1=ay+b(x-y)，再將x1 投入生產(chǎn)方式A和B，則可得到收入g(y1)+h(x1-y1)， 繼續(xù)回收資源x2=ay1+b(x1-y1)， 若上面的過(guò)程進(jìn)行n個(gè)階段，我們希望選擇n 個(gè)變量y,y1,y2,yn-1，使這n個(gè)階段的總收入最大。,因此，問(wèn)題就變

5、成：求y,y1,y2,yn-1，以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 達(dá)到最大，且滿足條件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi與xi均非負(fù),i=1,2, ,n-1,開(kāi)始有資源x,再進(jìn)行k階段生產(chǎn)并 采取最優(yōu)分配策略后得到的最大總收入,當(dāng)k=1時(shí)，有 當(dāng)k=2時(shí)，有,x,A,B,y,x-y,第一階段,回收,x1=ay+b(x-y),A,B,第二階段,y1,x1-y1,遞推關(guān)系式為:,例 5.1.3 生產(chǎn)和存儲(chǔ)控制問(wèn)題,某工廠生產(chǎn)某種季節(jié)性商品，需要作下一

6、 年度的生產(chǎn)計(jì)劃，假定這種商品的生產(chǎn)周期需 要兩個(gè)月，全年共有6個(gè)生產(chǎn)周期，需要作出 各個(gè)周期中的生產(chǎn)計(jì)劃。,設(shè)已知各周期對(duì)該商品的需要量如下表所示：,假設(shè)這個(gè)工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日班生產(chǎn)，當(dāng)開(kāi)足日班時(shí)，每一個(gè)生產(chǎn)周期能生產(chǎn)商品15個(gè)單位，每生產(chǎn)一個(gè)單位商品的成本為100元。當(dāng)開(kāi)足夜班時(shí)，每一生產(chǎn)周期能生產(chǎn)的商品也是15個(gè)，但是由于增加了輔助性生產(chǎn)設(shè)備和生產(chǎn)輔助費(fèi)用，每生產(chǎn)一單位商品的成本為120元。由于生產(chǎn)能力的限制，可以在需求淡季多生產(chǎn)一些商品儲(chǔ)存起來(lái)以備需求旺季使用，但存儲(chǔ)商品是需要存儲(chǔ)費(fèi)用的，假設(shè)每單位商品存儲(chǔ)一周期需要16元，問(wèn)應(yīng)該如何作生產(chǎn)和存儲(chǔ)計(jì)劃，才能使總的生產(chǎn)和

7、存儲(chǔ)費(fèi)用最小？,設(shè)第i個(gè)周期的生產(chǎn)量為xi，周期末的存儲(chǔ)量為uj，那 么這個(gè)問(wèn)題用式子寫(xiě)出來(lái)就是：求x1, x2,x6， u1, u2, u3, u4, u5,（ u0, u6 已知）,滿足條件：,Sk是這個(gè)周期的商品的需要量。,x1+u0=5+u1 x2+u1=5+u2 x3+u2=10+u3 x4+u3=30+u4 x5+u4=50+u5 x6+u5=8+u6,即,1500,3300,15,30,其中,其生產(chǎn)和庫(kù)存費(fèi)用為,用 表示開(kāi)始的庫(kù)存量為u0, 第k個(gè)周期 末庫(kù)存量為uk的前k個(gè)周期的最優(yōu)生產(chǎn)和庫(kù)存費(fèi) 用, 遞推關(guān)系式為:,多階段決策問(wèn)題,一.簡(jiǎn)介 1.研究對(duì)象:用來(lái)解決多階段決策過(guò)

8、程最優(yōu)化的一種數(shù)量方法。 2.方法:把一個(gè)n 維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題，從而一個(gè)一個(gè)地去解決。 3.劃分:系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間或空間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段；每個(gè)階段都要進(jìn)行決策, 4.目的:在多階段決策過(guò)程中目的是使整個(gè)過(guò)程的決策達(dá)到最優(yōu)效果。,例如生產(chǎn)庫(kù)存問(wèn)題,產(chǎn)品倉(cāng)庫(kù)容量H=9。期初庫(kù)存量為2，要求期末（七月底）庫(kù)存量為0。每個(gè)月生產(chǎn)的產(chǎn)品在月末入庫(kù)。求最優(yōu)生產(chǎn)計(jì)劃xk,分析處理方法,靜態(tài)處理 線性(整數(shù))規(guī)劃 動(dòng)態(tài)處理 動(dòng)態(tài)規(guī)劃,生產(chǎn)庫(kù)存問(wèn)題的動(dòng)態(tài)結(jié)構(gòu),按月分7個(gè)階段,8個(gè)狀態(tài),一般多階段決策問(wèn)題的結(jié)構(gòu),二、基本概念 1、階段： 把一個(gè)問(wèn)題的過(guò)程，恰當(dāng)

9、地分為若干個(gè)相互聯(lián)系的階段，以便于按一定的次序去求解。 描述階段的變量稱(chēng)為階段變量，常用自然數(shù)k表示。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于問(wèn)題轉(zhuǎn)化為多階段決策。,2、狀態(tài)：表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量。,狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱(chēng)為狀態(tài)允許集合，用表示表示第k階段的狀態(tài)。,1,2,3,4,例如,狀態(tài)變量,狀態(tài),分為四個(gè)階段，五個(gè)狀態(tài),S1=A, S2=B1,B2,B3,S3=C1,C2,C3 S4=E1, E2, E3,S5=F.,S1,S2,S3,

10、S4,S5,3、決策：(從一個(gè)階段的狀態(tài)到下一個(gè)階段狀態(tài) 的選擇),描述決策的變量，稱(chēng)為決策變量。決策變量是狀態(tài)變量的函數(shù)用xk(sk)表示。 在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱(chēng)為允許決策集合, 用 表示 。,S3,可以在各個(gè)階段進(jìn)行決策，去控制過(guò)程發(fā)展的多階段過(guò)程；其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的。,4、多階段決策過(guò)程,5. 狀態(tài)轉(zhuǎn)移方程：是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。,圖示如下：,其狀態(tài)轉(zhuǎn)移方程如下（一般形式）,能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類(lèi)特殊的多階段決策過(guò)程，即具有無(wú)后效性的多階段決策過(guò)程。,動(dòng)態(tài)規(guī)劃中能 處理的狀態(tài)

11、轉(zhuǎn)移 方程的形式。,狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下,無(wú)后效性(馬爾可夫性),如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)和決策（歷史）的影響；,狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。如果已知第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。,6.策略：從初始階段到最終階段，每一階段的決策所形成的序列,子策略：從k階段到最終階段n，每一階段的決策所形成的序列,最優(yōu)子策略：最優(yōu)效果的子策略，記為,7. 指標(biāo)函數(shù):分為階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段，從狀態(tài)sk出發(fā)，采用決策xk時(shí)的效益值，用rk(sk,xk)表示。過(guò)程指標(biāo)函數(shù)是指過(guò)程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值.記為 Rk,nRk,n(sk,xk,sk+1,xk+1,sn,xn),最優(yōu)指標(biāo)函數(shù)：對(duì)應(yīng)于從狀態(tài) sk 出發(fā)的最優(yōu)子策略,的效益。記為,k,n,即從k到最終階段n過(guò)程指標(biāo)函數(shù)的最優(yōu)值。,Bellman(1951提出)最優(yōu)性原理,“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和決策如何，余下的決策必然形成最優(yōu)子策略”,即若某一全過(guò)程最優(yōu)策略為,則對(duì)上述策略中所隱含的任意狀態(tài)