動(dòng)態(tài)dp模型基本概念

1、動(dòng)態(tài)規(guī)劃模型的基本要素(續(xù))決策(Deci )當(dāng)一個(gè)階段的狀態(tài)確定后,可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài),這種選擇 稱為決策(deci ),在最優(yōu)控制問(wèn)題中也稱為控制(control)。描述決策的變量稱決策變量. 變量允許取值的范圍稱允許決策集合.用 uk(xk)表示第k階段處于狀態(tài)xk時(shí)的決策變量, 它是xk的函數(shù), 用Uk(xk)表示了xk的允許決策集合. 在例1中u2(B)可取C, D, E. 決策變量簡(jiǎn)稱決策.策略(policy)決策組成的序列稱為策略. 由初始狀態(tài)x1開(kāi)始的全過(guò)程的策略記作p1,n(x1), 即p1,n(x1)=u1(x1),u2(x2),.,un(xn).

2、由第k階段的狀態(tài)xk開(kāi)始到終止?fàn)顟B(tài)的后部子過(guò)程的策略記作pk,n(xk), 即pk,n(xk)=uk(xk),uk+1(xk+1),., un(xn).類似地, 由第k到第j階段的子過(guò)程的策略記作pk,j(xk)=uk(xk),uk+1(xk+1),., uj(xj).對(duì)于每一個(gè)階段k的某一給定的狀態(tài)xk. 可供選擇的策略pk,j(xk)有一定的范圍,稱為允許策略集合,用P1,n(x1),Pk,n(xk),Pk,j(xk 表示。從允許策略集合中找出使問(wèn)題達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略.動(dòng)態(tài)規(guī)劃模型的基本要素階段(Step)為了表示決策和過(guò)程的發(fā)展順序,通常根據(jù)決策進(jìn)行的先后次序、時(shí)間順序或空間

3、特征,將全過(guò)程來(lái)劃分為若干階段。階段變量一般用k=1,2,.,n表示。在例1中由“”出發(fā)為第一階段(k=1),由A、B 出發(fā)的為第二階段(k=2),依此下去n=4個(gè)階段。在例2中按照第一、二、三、四季度分為k=1,2,3,4,共4個(gè)階段。狀態(tài)(S e)表示每個(gè)階段開(kāi)始時(shí)過(guò)程所處的自然狀況。它應(yīng)該能夠描述過(guò)程的特征并且具有無(wú)后向性,即當(dāng)某階段的狀態(tài)給定時(shí),這個(gè)階段以后過(guò)程的演變與該階段以前各階段的狀態(tài)無(wú)關(guān),即每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。通常還要求狀態(tài)是直接或間接可以觀測(cè)的。描述狀態(tài)的變量稱狀態(tài)變量。變量允許取值的范圍稱允許狀態(tài)集合。用xk表示第k階段的狀態(tài)變量,它可以是一個(gè)數(shù)或一個(gè)向量。

4、用Xk表示第k階段的允許狀態(tài)集合。在例1中x2可取A,B,X2=A,B。n個(gè)階段的決策過(guò)程有 n+1個(gè)狀態(tài)變量,xn+1表示xn演變的結(jié)果,在例1中x5取目的地“伊犁”。根據(jù)過(guò)程演變的具體情況,狀態(tài)變量可以是離散的或連續(xù)的。為了計(jì)算的方便有時(shí)將連續(xù)變量離散化；為了分析的方便有時(shí)又將離散變量視為連續(xù)的。狀態(tài)變量簡(jiǎn)稱為狀態(tài)。動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支,是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初 數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí),提出了著名的最優(yōu)化原理,把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題,逐個(gè)求解,創(chuàng)

5、立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。多階段決策過(guò)程,是指這樣的一類特殊的活動(dòng)過(guò)程,問(wèn)題可以按時(shí)間順序或空間位置分解成若干相互聯(lián)系的階段,在每一個(gè)階段都要做出決策,全部過(guò)程的決策是一個(gè)決策序列。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu) ,稱為多階段決策問(wèn)題。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái),在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題,用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題,但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃),只要人為地引進(jìn)時(shí)間,把它視為多階段決策過(guò)程,也可

6、以用動(dòng)態(tài)規(guī)劃方法方便地求解。例2 生產(chǎn)計(jì)劃問(wèn)題 工廠生產(chǎn)某種產(chǎn)品, 每 (千件)的成本為1(千元), 每次開(kāi)工的固定成本為3(千元), 工廠每季度的最大生產(chǎn)能力為6(千件). 經(jīng) , 市場(chǎng)對(duì)該產(chǎn)品的需求量第一、二、三、四季度分別為 2, 3, 2, 4(千件). 如果工廠在第一、二季度將全年的需求都生產(chǎn)出來(lái), 自然可以降低成本(少付固定成本費(fèi)), 但是對(duì)于第三、四季度才能上市的產(chǎn)品需付 費(fèi), 每季每千件的 費(fèi)為0.5(千元). 還規(guī)定年初和年末這種產(chǎn)品均無(wú)庫(kù)存. 試制訂一個(gè)生產(chǎn)計(jì)劃, 即安排每個(gè)季度的產(chǎn)量, 使一年的總費(fèi)用(生產(chǎn)成本和 費(fèi))最少.該規(guī)劃問(wèn)題看似一個(gè)線性規(guī)劃或線性整數(shù)混合規(guī)劃問(wèn)題

7、, 但實(shí)際上由于問(wèn)題的動(dòng)態(tài)特性, 是不容易建立常規(guī)的規(guī)劃問(wèn)題的 (非常復(fù)雜)! 但可以分階段進(jìn)行決策,即多階段決策問(wèn)題. 需要引入新的方法動(dòng)態(tài)規(guī)劃方法.引例1： 最短路問(wèn)題 從到伊犁間有一個(gè)鐵路網(wǎng),某學(xué)生暑假打算到伊犁旅游,出于經(jīng)濟(jì)關(guān)系只能坐火車(chē),而且要求費(fèi)用最少。下圖標(biāo)出了各種可能的行車(chē)路線,請(qǐng)為這位同學(xué)的決策做出指導(dǎo)。C1F865A5D 4G伊犁454375 B5663E 5H求費(fèi)用最小的方案4窮舉法所有路徑的費(fèi)用?多階段決策問(wèn)題！動(dòng)態(tài)規(guī)劃建模引例動(dòng)態(tài)規(guī)劃模型基本概念動(dòng)態(tài)規(guī)劃模型基本要素動(dòng)態(tài)規(guī)劃基本定理動(dòng)態(tài)規(guī)劃的示意圖動(dòng)態(tài)規(guī)劃的應(yīng)用6. 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本方程(逆推方程)f ( x )

8、 opt x , u , fxkkkkk 1k 1u k U kx T x , u ( x ), k 1,2,L , nk 1kkkkfn 1 ( xn 1 ) ( xn 1 ) 初值fn+1(xn+1)是決策過(guò)程的終端條件, 往往為一個(gè)已知數(shù). 當(dāng)x 只取固定的狀態(tài)時(shí)稱固定終端 當(dāng)xn+1可在終端集合Xn+1中變動(dòng)時(shí)稱終端.動(dòng)態(tài)規(guī)劃的基本方程(順推方程)f ( x) opt x, u , fx kk 1k 1kk 1ku Ux T x k , k ( x ), k 2,L , nkkk 1 u kkf1 ( x 2 ) opt ( x 1 , u 1 )u 1 U 1動(dòng)態(tài)規(guī)劃的基本定理最優(yōu)性

9、定理設(shè)階段數(shù)為n的多階段決策過(guò)程,其階段為k=1,2,.,n, 對(duì)于初始狀態(tài)x1X1,策略p1,n*=u1*,.un*是最優(yōu)策略的充要條件是對(duì)于任意的k,1kn,有V x , p * optVx , p, optV x , p 1 ,n 1 1 ,n 1,k 1 1 1,k 1k ,n k k ,n p 1 k 1 P1 k 1 ( x1 ) p k n Pk n 1 ( xk )最優(yōu)化原理(是上定理的推論) 若p1,n*P1,n(x1)是最優(yōu)策略,則對(duì)于任意的k,1kn, 它的子策略pkn*對(duì)于由x1和p1,k-1*確定的以xk*為起點(diǎn)的第k到n后部子過(guò)程而言,也是最優(yōu)策略。最優(yōu)化原理給出了

10、最優(yōu)策略的必要條件, 通常略述為:不論過(guò)去的狀態(tài)和決策如何, 對(duì)于前面的決策形成的當(dāng)前的狀態(tài)而言,余下的各個(gè)決策必定 最優(yōu)策略.動(dòng)態(tài)規(guī)劃模型的基本要素(續(xù))(9) 最優(yōu)策略(optimal policy)和最優(yōu)軌線(optimal trajectory)使指標(biāo)函數(shù)Vk,n達(dá)到最優(yōu)值的策略是從k開(kāi)始的后部子過(guò)程的最優(yōu)策略, 記作 pk,n*=uk*,., un*, p1,n*又是全過(guò)程的最優(yōu)策略,簡(jiǎn)稱最優(yōu)策略。從初始狀態(tài)x1(=x1*) 出發(fā), 過(guò)程按照p1,n*和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列x1*,x2*,., xn+1*稱最優(yōu)軌線。C1F865A45D 4G伊犁54375 B5E 663

11、5H4動(dòng)態(tài)規(guī)劃模型的基本要素(續(xù))(8)最優(yōu)值函數(shù)(optimal value function) 在xk給定時(shí)指標(biāo)函數(shù)Vk,n對(duì) pk,n的最優(yōu)值稱為最優(yōu)值函數(shù),記作fk(xk),即f ( x ) optV x , p ( x )k kk ,n k k ,n kp k n ( x k )Pk n ( x k )其中opt可根據(jù)具體情況取max或min。上式的意義是,對(duì)于某個(gè)階段k的某個(gè)狀態(tài)xk,從該階段k到最終目標(biāo)階段n的最優(yōu)指標(biāo)函數(shù)值等于從xk出發(fā)取遍所有能策略pk,n所得到的指標(biāo)值中最優(yōu)的一個(gè)。利用指標(biāo)函數(shù)的性質(zhì)有V x , p ( x ) x , u , Vx , p( x )k ,n

12、 k k ,n kk k k k 1,n k 1 k 1,n k 1 f ( x ) opt x , u , Vx, p( x)k kk k kk 1 ,n k 1 k 1 ,n k 1p k n Pk n f ( x ) opt x , u , fxkkk kk k 1 k 1p k n Pk n動(dòng)態(tài)規(guī)劃模型的基本要素(續(xù))(7) 階段指標(biāo)(階段收益)系統(tǒng)某一階段的狀態(tài)一經(jīng)確定, 執(zhí)行某一決策所得到的效益或描述該階段決策的數(shù)量指標(biāo), 稱為階段指標(biāo)(階段收益).它是整個(gè)系統(tǒng)總收益的一部分,是階段狀態(tài)和決策變量的函數(shù), 記為vk(xk, uk(xk)在例1中階段指標(biāo)為走完一段路程的花費(fèi)一般地,

13、指標(biāo)函數(shù)Vk,n(xk,pk,n(xk)是由階段指標(biāo)vk(j=k,k+1,.n)組成的,就常見(jiàn)的形式有階段指標(biāo)vk(j=k,k+1,.n)之和V x , p ( x ) n v ( x , u )k ,n k k ,n k j k j j j階段指標(biāo)vk(j=k,k+1,.n)之積Vk ,n nxk , pk ,n ( xk )v j ( x j , u j )j k階段指標(biāo)vk(j=k,k+1,.n) 的極大(或極小):V x , p ( x ) opt v ( x , u )k ,n k k ,n kj j jk j n動(dòng)態(tài)規(guī)劃模型的基本要素(續(xù))狀態(tài)轉(zhuǎn)移方程(equation of s

14、e transition)確定過(guò)程由一個(gè)狀態(tài)到下一個(gè)狀態(tài)演變規(guī)律的方程. 在確定性過(guò)程中, 一旦某階段的狀態(tài)和決策為已知, 下階段的狀態(tài)便完全確定. 用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律,寫(xiě)作：x T x , u ( x ), k 1,2,L , nk 1kkkk在例1中狀態(tài)轉(zhuǎn)移方程為：xk+1=uk(xk)指標(biāo)函數(shù)(objective function) 是衡量過(guò)程優(yōu)劣的數(shù)量指標(biāo), 它是關(guān)于策略的數(shù)量函數(shù), 從階段k到階段n的指標(biāo)函數(shù)用Vk,n(xk,pk,n(xk)表示, k=1,2,.,n. 能夠用動(dòng)態(tài)規(guī)劃解決 的指標(biāo)函數(shù)應(yīng)具有可分離性, 即Vk,n可表為xk, uk, Vk+1, n 的函數(shù)

15、,記為：V x , p ( x ) x , u , V x , p ( x )k ,n k k ,n kk k kk 1 ,n k 1 k 1 ,n k 1即V x , u , Vk ,nk k kk 1 ,n其中k 是關(guān)于變量 Vk ,n的單調(diào)遞增函數(shù) .同時(shí)必須注意到 指標(biāo)函數(shù)Vk,n是狀態(tài)xk和策略pk,n(xk)的函數(shù)例4 背包問(wèn)題max 7 y 1 16 y 2 19 y 3 15 y 4求解如下0-1背包問(wèn)題3y 1 6y 2 7 y 3 5y 4 9y 0,1i計(jì)算價(jià)值/體積比 7 , 16 , 19 , 1522 非最優(yōu)解3675近似求解方法10 01解建立4級(jí)的動(dòng)態(tài)規(guī)劃模型u

16、 1u 2u 3u 4x 11x 2 2x 3 3x 44x 5v 1v 2v 3v 4x 0,1,2,3,4,5,6,7 ,8,9u 0,1kk例3 資源分配研究一個(gè)人力資源分配方案。某建筑公司有三個(gè)工區(qū)都需要增加人力資源，對(duì)各工區(qū)增加人力后，其收益也相應(yīng)增加，如表所示. 請(qǐng)尋求人力資源的最佳分配方案，使全公司增加的總 。解建立三級(jí)的動(dòng)態(tài)規(guī)劃模型u 1u 2u 3x 11 x1 u 1 x 2 2 x 2 u 2 x 33x 4v 1 (u 1 ( x1 )v 2 (u 2 ( x 2 )v 3 (u 3 ( x 3 )x 0,1,2,3,4,5,6,7,8 u 0,1,2,3,4,5,6,

17、7 ,8kk人力工區(qū)01234567880909598100205607073747530426404550515253xk1 xk uk dk , u k 0,1,2,3,4,5,6v x , u 0.5x 3 uk , uk 0k kkk 0,u 0k基本逆推方程為f ( x ) min v ( x , u ) f xk ku Uk k kk 1 k 1f x 0 k kx 0 x 0,1,2,3,4x 3 0,1,2,3,4,5,65 554x 0, d 2 x 0,1,2,3,4 x1 0u 1 * 5112u * 02u 3 * 6u 4 * 0 x201234u2*f2(x2)x1

18、0u1*f1(x1)x401234u4*f4(x4)x30123456u3*f3(x3)例2 生產(chǎn)計(jì)劃問(wèn)題(求解)工廠生產(chǎn)某種產(chǎn)品, 每 (千件)的成本為1(千元), 每次開(kāi)工的固定成本為 3(千元), 工廠每季度的最大生產(chǎn)能力為6(千件). 經(jīng) , 市場(chǎng)對(duì)該產(chǎn)品的需求量四個(gè)季度分別為 2, 3, 2, 4(千件). 每季每千件的 費(fèi)為0.5(千元). 還規(guī)定年初和年末這種產(chǎn)品均無(wú)庫(kù)存. 試制訂一個(gè)生產(chǎn)計(jì)劃, 使一年的總費(fèi)用最少.求解看成多階段問(wèn)題按照計(jì)劃時(shí)間自然劃分n(=4)個(gè)階段, 狀態(tài)定義為每階段開(kāi)始時(shí)的量xk, 決策為每個(gè)階段的產(chǎn)量uk, 記每個(gè)階段的需求量(已知)為dk，則狀態(tài)轉(zhuǎn)移方程為：xk1 xk uk dk , (xk 0), k 1,2,L, n( 4)設(shè)每個(gè)階段開(kāi)工固定成本費(fèi)用為a(=3),生產(chǎn) 數(shù)量產(chǎn)品的成本為b(=1), 每階段 數(shù)量產(chǎn)品的 費(fèi)用為c(=0.5), 階段指標(biāo)為階段的生產(chǎn)成本費(fèi)用和費(fèi)用之和, 即a bu , u 0 v x , u cx k kk k kk0,uk 0指標(biāo)函數(shù)Vk,n為vk之和, 最優(yōu)值函數(shù)fk(xk)為從第k階段的狀態(tài)xk出發(fā)到過(guò)程終結(jié)的最小費(fèi)用, 則基本逆推方程為f (x ) min v (x , u ) f x (fn