1、運籌學(xué)（二） 動態(tài)規(guī)劃,動態(tài)規(guī)劃,動態(tài)規(guī)劃是運籌學(xué)的一個分支，它是解決多階段決策問題的一種數(shù)學(xué)方法。大約產(chǎn)生于上個世紀(jì)50年代， 已廣泛的應(yīng)用于工程技術(shù)、工農(nóng)業(yè)生產(chǎn)以及軍事等部門，并獲得了顯著的效果，尤其是在企業(yè)管理決策方面。,動態(tài)規(guī)劃,在企業(yè)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制等問題，是現(xiàn)代企業(yè)管理中一種重要的決策方法。,主要內(nèi)容,動態(tài)規(guī)劃（1） 動態(tài)規(guī)劃基本原理與方法 動態(tài)規(guī)劃（2） 動態(tài)規(guī)劃應(yīng)用舉例,運籌學(xué)（二） 動態(tài)規(guī)劃（1）,動態(tài)規(guī)劃基本原理與方法,主要內(nèi)容,1. 多階段決策過程及實例 2

2、. 動態(tài)規(guī)劃基本概念 3. 動態(tài)規(guī)劃基本原理 4. 動態(tài)規(guī)劃與其它方法的比較 5. 動態(tài)規(guī)劃的理論基礎(chǔ) 6. 動態(tài)規(guī)劃的具體解法,1. 多階段決策過程與實例,在生產(chǎn)實踐和科學(xué)實驗中，存在這樣一類活動過程：其過程分為若干個互相聯(lián)系的階段，在每一個階段都需要作出決策，目的是使整個過程達(dá)到最好的活動效果。,示例1,例1 最短路線問題給定一個線路網(wǎng)絡(luò)，兩點之間連線上的數(shù)字表示兩點間的距離(或費用)，試求一條由A到G的鋪管線路，使總距離為最短(或總費用最小)。,最短路線問題示意圖,最短路線問題示意圖,在最短線路問題中，各個階段決策的選取不是任意確定的，它既依賴于當(dāng)前所處的位置（或狀態(tài)），又影響以后的決策

3、（或發(fā)展）。當(dāng)各個階段決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線。,示例2,例2 機器負(fù)荷分配問題某種機器可以在高低兩種不同的負(fù)荷下進行生產(chǎn)。在高負(fù)荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關(guān)系為 g=g(u1) 這時，機器的年完好率為a，即如果年初投入高負(fù)荷狀態(tài)生產(chǎn)的完好機器數(shù)量為u，到年終時完好的機器就為au，其中0a1；,在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關(guān)系為 h=h(u2) 相應(yīng)的機器年完好率為b，其中0b1。,假定開始生產(chǎn)時，完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不

4、同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,多階段決策過程示意圖,從決策的角度來看，上述前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，也稱序貫決策過程。這種問題就稱為多階段決策問題。,在多階段決策問題中，各個階段采取的決策，一般來說與時間有關(guān)，決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義。,但是，一些與時間沒有關(guān)系的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃等）問題，只要人為地引進“時間”因素，也可以把它視為多階段決策問題，用動態(tài)規(guī)劃的方法去處理。,2. 動態(tài)規(guī)劃基本概念,下面結(jié)合最短路線問題，對動態(tài)規(guī)劃所涉及到的基本概念進

5、行說明。,在最短路線問題中，從A點到G點可以分為6個階段，是一個6階段的多階段決策問題。其目的是：在各個階段上選擇一個恰當(dāng)?shù)臎Q策，使得由這些決策組成的一個決策序列所決定的一條路線是總路程最短的一條。,最短路線問題示意圖,動態(tài)規(guī)劃問題涉及到的基本概念主要有：階段、狀態(tài)、決策、策略、狀態(tài)轉(zhuǎn)移方程和指標(biāo)函數(shù)（以及最優(yōu)值函數(shù)）。,階段,1）階段 將所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。 描述階段的變量稱為階段變量，常用k表示。,階段,階段的劃分，一般是根據(jù)時間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。如例1可分為6個階段來求解，k分別等于

6、1、2、3、4、5、6。,階段,最短路線問題中“階段”的示意圖,狀態(tài),2）狀態(tài) 狀態(tài)表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，又稱不可控因素。,狀態(tài),在例1中，狀態(tài)就是某階段的出發(fā)位置。它既是該階段某支路的起點，又是前一階段某支路的終點。,狀態(tài),最短路線問題中“狀態(tài)”的示意圖,狀態(tài),通常一個階段有若干個狀態(tài)，第一階段有一個狀態(tài)就是點A，第二階段有兩個狀態(tài)，即點集B1，B2，第k階段的狀態(tài)就是第k階段所有始點的集合。,狀態(tài),描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個數(shù)、一組數(shù)或一向量(多維情形)來描述。,狀態(tài),常用sk表示第k階段的狀態(tài)變量。如在例1中第三階段有四個狀

7、態(tài)，則狀態(tài)變量sk可取四個值，即C1、C2、C3、C4。點集合C1，C2，C3，C4就稱為第三階段的可達(dá)狀態(tài)集合。記為 S3C1，C2，C3，C4,最短路線問題中“狀態(tài)集合”的示意圖,狀態(tài),有時為了方便起見，將該階段的狀態(tài)編上號碼1，2，這時也可記 S31，2，3，4 第k階段的可達(dá)狀態(tài)集合就記為Sk。,在例1中，當(dāng)某階段的始點給定后，雖然會影響后面各階段的行進路線和整個路線的長短，而后面各階段路線的發(fā)展不受這點以前各階段決策的影響。,狀態(tài)無后效性示意圖,馬爾科夫性,這里，狀態(tài)應(yīng)具有如下性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。換句話說，過程的過去歷史

8、只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的一個總結(jié)。這個性質(zhì)稱為無后效性(即馬爾科夫性)。,決策,3）決策 決策表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。,決策,描述決策的變量，稱為決策變量。它可用一個數(shù)、一組數(shù)或一向量來描述。常用uk(sk)表示第k階段當(dāng)狀態(tài)處于sk時的決策變量。它是狀態(tài)變量的函數(shù)。,決策,在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然, uk(sk) Dk(sk) 。,決策,

9、如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D2(B1)C1，C2，C3，若選取的點為C2，則C2是狀態(tài)B1在決策u2(B1)作用下的一個新的狀態(tài)，記作 u2(B1)=C2。,決策,最短路線問題中“決策”的示意圖,策略,4）策略 策略是一個按順序排列的決策組成的集合。 由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程。,最短路線問題“子過程”的示意圖,策略,由每段的決策按順序排列組成的決策函數(shù)序列 稱為k子過程策略，簡稱子策略，記為 ，即,策略,當(dāng)k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即,策略,在實際問題中，可供選擇的策略

10、有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。,狀態(tài)轉(zhuǎn)移方程,5）狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程是確定活動過程如何由一個狀態(tài)演變到另一個狀態(tài)。若給定第k階段狀態(tài)變量的值，如果該段的決策變量uk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1的值也就完全確定，即sk+1的值隨sk和uk的值變化而變化。,狀態(tài)轉(zhuǎn)移方程,這種確定的對應(yīng)關(guān)系，記為,上式描述了由k階段到k+1階段的階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。,狀態(tài)轉(zhuǎn)移方程,如例1中，狀態(tài)轉(zhuǎn)移方程為,指標(biāo)函數(shù)和最優(yōu)值函數(shù),6）指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指

11、標(biāo)，稱為指標(biāo)函數(shù)。 指標(biāo)函數(shù)是定義在全過程和所有后部子過程上的確定的數(shù)量函數(shù)。,最短路線問題“指標(biāo)函數(shù)”的示意圖,指標(biāo)函數(shù),常用Vk,n表示，即,指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為 它表示從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值，即,最優(yōu)值函數(shù),“opt”是最優(yōu)化(optimization)的縮寫，可 根據(jù)題意而取min或max。,最短路線問題“最優(yōu)值函數(shù)”的示意圖,當(dāng)應(yīng)用動態(tài)規(guī)劃進行求解的多階段決策問題時，其指標(biāo)函數(shù)應(yīng)具有可分離性，并滿足遞推關(guān)系，即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為,指標(biāo)函數(shù)的性質(zhì),在實際問題中很多指標(biāo)函數(shù)都

12、滿足這個性質(zhì)。,其中 表示第j階段的階段指標(biāo)，這時上式可寫成,常見的指標(biāo)函數(shù)形式,(1) 過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)的和。即,常見的指標(biāo)函數(shù)形式,(2) 過程和它的任一子過程的指標(biāo)是它所包含的各階段指標(biāo)的乘積，即,這時就可寫成,3. 動態(tài)規(guī)劃基本原理,下面結(jié)合最短路線問題，介紹動態(tài)規(guī)劃方法的基本思想。,最短路線問題求解思路,最短路線問題求解示意圖,最短路線有一個重要特性：如果由起點A經(jīng)過P點和H點而到達(dá)終點G是一條最短路線，則由點P出發(fā)經(jīng)過H點到達(dá)終點G的這條子路線，對于從點P出發(fā)到達(dá)終點的所有可能選擇的不同路線來說，必定也是最短路線。,例如，在最短路線問題中，若找到了

13、AB1C2D1E2F2G是由A到G的最短路線，則D1E2F2G應(yīng)該是由D1出發(fā)到G點的所有可能選擇的不同路線中的最短路線。,根據(jù)最短路線這一特性，尋找最短路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到G點的最短路線，最后求得由A點到G點的最短路線。,所以，動態(tài)規(guī)劃的方法是：從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法逆推解法。,動態(tài)規(guī)劃方法示意圖,最短路線問題動態(tài)規(guī)劃求解示意圖,為了找出最短路線，再按計算的順序反推之，可求出最優(yōu)決策函數(shù)序列，即,找出相應(yīng)的最短路線為,從上面的計算過程中可以看出：在求解的各個階段，利用了k階段與k+1階段之間的遞推關(guān)系：,一般情況，k階段與k

14、+1階段的遞推關(guān)系式可寫成：,邊界條件為,遞推關(guān)系式(1-1)稱為動態(tài)規(guī)劃的基本方程。,動態(tài)規(guī)劃方法基本思想,在將問題的過程分成幾個相互聯(lián)系的階段，并恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)的基礎(chǔ)上，把一個大問題化成一族同類型的子問題，然后逐個求解。,動態(tài)規(guī)劃方法基本思想,即根據(jù)基本方程，從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。,建立動態(tài)規(guī)劃模型的五個要點,(1) 將問題的過程劃分成恰當(dāng)?shù)碾A段； (2) 正確選擇狀態(tài)變量sk，使它既能描述過程的演變，又要滿足無后效性； (3) 確定

15、決策變量uk及每階段的允許決策集合Dk(sk)； (4) 正確寫出狀態(tài)轉(zhuǎn)移方程；,建立動態(tài)規(guī)劃模型的五個要點,(5) 正確寫出指標(biāo)函數(shù)Vk,n的關(guān)系，它應(yīng)滿足下面三個性質(zhì)： 是定義在全過程和所有后部子過程上的數(shù)量函數(shù)；, 要具有可分離性，并滿足遞推關(guān)系,即 函數(shù) 對于變量Vk+1,n要嚴(yán)格單調(diào)。,建立動態(tài)規(guī)劃模型的五個要點,其中 表示第j段的指標(biāo)。它顯然是 滿足指標(biāo)函數(shù)三個性質(zhì)的。,考察動態(tài)規(guī)劃基本方程,設(shè)指標(biāo)函數(shù)是取各階段指標(biāo)的和的形式，即,。,上式可寫成,當(dāng)初始狀態(tài)和過程的策略給定時，指標(biāo)函數(shù)也就確定了。因此，指標(biāo)函數(shù)是初始狀態(tài)和策略的函數(shù)?？捎洖?。,其子策略 可看成是由決策 和子策略

16、組合而成，即,上面遞推關(guān)系又可寫成,用p*k,n(sk)表示初始狀態(tài)為sk的后部子過程所有子策略中的最優(yōu)子策略，則最優(yōu)值函數(shù)為,由于,同時,4. 動態(tài)規(guī)劃與其它方法的比較,1）與窮舉法的比較 2）與靜態(tài)規(guī)劃的比較,與窮舉法相比有以下優(yōu)點,(1) 減少了計算量。計算例1若用窮舉法，就要對48條路線進行比較，運算在計算機上進行時，比較運算要進行47次；求各條路線的距離，即使用逐段累加方法，也要進行6+12+24+48+48138次加法運算。,與窮舉法相比有以下優(yōu)點,用動態(tài)規(guī)劃方法來計算，比較運算(從k=5段開始向前算)共進行3+3+4+4+115次。每次比較運算相應(yīng)有兩次加法運算，再去掉中間重復(fù)兩

17、次(即B1C1，B2C4各多算了一次)，實際只有28次加法運算。可見，動態(tài)規(guī)劃方法比窮舉法減少了計算量。而且隨著段數(shù)的增加，計算量將大大地減少。,與窮舉法相比有以下優(yōu)點,(2) 豐富了計算結(jié)果。在上述解法中，我們得到的不僅僅是由A點出發(fā)到G點的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點出發(fā)到G點的最短路線及相應(yīng)的距離。這就是說，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。,與靜態(tài)規(guī)劃的比較,相同點 動態(tài)規(guī)劃、線性規(guī)劃和非線性規(guī)劃都屬于數(shù)學(xué)規(guī)劃范圍，研究對象本質(zhì)上都是求極值問題，都是利用迭代法去逐步求解。,不同點 1）線性規(guī)劃和非線性規(guī)劃研究的問題通常與時間無關(guān)，故又稱為靜態(tài)規(guī)劃。線性規(guī)

18、劃迭代中的每一步是就問題的整體加以改善的。,不同點 2）動態(tài)規(guī)劃研究的問題與時間有關(guān)，研究具有多階段決策過程的一類問題，將問題的整體按時間或空間的特征分成若干個前后銜接的時空階段，把多階段決策問題表示為前后有關(guān)聯(lián)的一系列單階段決策問題，然后逐個加以解決，從而求出整個問題的最優(yōu)決策序列。,不同點 3）動態(tài)規(guī)劃對于某些靜態(tài)問題，也可以人為地引入時間因素，把它看作是按階段進行的一個動態(tài)規(guī)劃問題，這就使得動態(tài)規(guī)劃成為求解某些線性、非線性規(guī)劃的有效方法。,5. 動態(tài)規(guī)劃的理論基礎(chǔ),動態(tài)規(guī)劃的理論基礎(chǔ)是什么？,動態(tài)規(guī)劃的最優(yōu)性原理,動態(tài)規(guī)劃的最優(yōu)性原理：“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的

19、狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?！焙喲灾粋€最優(yōu)策略的子策略總是最優(yōu)的。,動態(tài)規(guī)劃的最優(yōu)性定理：對于階段數(shù)為n的多階段決策過程， 為最優(yōu)策略的充要條件是對任意一個k(0kn-1)， ，有,動態(tài)規(guī)劃的最優(yōu)性定理,動態(tài)規(guī)劃的最優(yōu)性定理,上式中， ，它是由給定的初始狀態(tài)s0和子策略P0,k-1所確定的k階段狀態(tài)。當(dāng)V是效益函數(shù)時，opt取max；當(dāng)V是損失函數(shù)時，opt取min。,動態(tài)規(guī)劃的最優(yōu)性定理,6. 動態(tài)規(guī)劃的具體解法,在應(yīng)用動態(tài)規(guī)劃求解多階段決策問題時，有兩種具體的求解方法： 1）逆推解法； 2）順推解法； 3）算例,動態(tài)規(guī)劃逆推解法的基本方程

20、,動態(tài)規(guī)劃逆推解法的基本方程為：,邊界條件為,式中,其求解過程為：根據(jù)邊界條件，從k=n開始，由后向前逆推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出 時，就得到整個問題的最優(yōu)解。,求解過程,算例,例3 用逆推解法求解下面問題,算例,解 : 按問題的變量個數(shù)劃分階段，把它看作為一個三階段決策問題。 設(shè)狀態(tài)變量為s1，s2，s3和s4，并記s1=c；取問題中的變量x1，x2和x3為決策變量；各階段指標(biāo)函數(shù)按乘積方式結(jié)合。令最優(yōu)值函數(shù)fk(sk)表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得到的最大值。,算例,設(shè),則有,及最優(yōu)解,算例,用逆推解法，從后向前依次有,由 可得,算例,(舍去),所以， 為極大值點。此時,算例,由于,算例,仿前分析，可得,算例,由于已知,根據(jù)計算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。,算例,即,由,可得,算例,可得,由,算例,因此得到最優(yōu)解為,