吉林大學(xué)本科運籌學(xué)PPT演示文稿

1、第七章 動態(tài)規(guī)劃,動態(tài)規(guī)劃的基本方法 動態(tài)規(guī)劃應(yīng)用舉例,動態(tài)規(guī)劃,什么是動態(tài)規(guī)劃 解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。 動態(tài)規(guī)劃的形成 產(chǎn)生于20世紀50年代。1951年美國數(shù)學(xué)家貝爾曼(R.Bellman)等人，根據(jù)一類多階段決策問題的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。與此同時，他提出了解決這類問題的“最優(yōu)性原理”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法動態(tài)規(guī)劃。 動態(tài)規(guī)劃的應(yīng)用 在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都有廣泛的應(yīng)用，并且獲得了顯著的效果。,動態(tài)規(guī)劃,動態(tài)規(guī)劃在企業(yè)管理中的主要應(yīng)用領(lǐng)域 最優(yōu)路徑問題 資源

2、分配問題 生產(chǎn)調(diào)度問題 庫存問題 裝載問題 排序問題 設(shè)備更新問題 生產(chǎn)過程最優(yōu)控制問題 等等 動態(tài)規(guī)劃是求解某類問題的一種方法，是考查問題的一種途徑，而不是一種特殊算法(如線性規(guī)劃是一種算法)。因而，它不像線性規(guī)劃那樣有一個標準的數(shù)學(xué)表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理。,動態(tài)規(guī)劃,動態(tài)規(guī)劃模型的分類 根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)變量，分為離散決策過程和連續(xù)決策過程。 根據(jù)決策過程的演變是確定性的還是隨機性的，又可分為確定性決策過程和隨機性決策過程。 組合起來可分為 離散確定性 離散隨機性 連續(xù)確定性 連續(xù)隨機性 本書主要研究離散確定性決策過程。,第8

3、章 動態(tài)規(guī)劃的基本方法,第1節(jié) 多階段決策過程及實例 第2節(jié) 動態(tài)規(guī)劃的基本概念和基本方程 第3節(jié) 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理 第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,第1節(jié) 多階段決策過程及實例,例1 最短路線問題 給定一個線路網(wǎng)絡(luò)，兩點之間連線上的數(shù)字表示兩點間的距離(或費用)，試求一條由A到G的鋪管線路，使總距離為最短(或總費用最小)。,第1節(jié) 多階段決策過程及實例,多階段決策過程 在生產(chǎn)和科學(xué)實驗中，有一類活動的過程，由于它的特殊性，可將過程分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，從而使整個過程達到最好的活動效果。因此，各個階段決策的選取不是任意確定的，它依賴于當前面

4、臨的狀態(tài)，又影響以后的發(fā)展。當各個階段決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線。這種把一個問題可看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，也稱序貫決策過程。,第1節(jié) 多階段決策過程及實例,例2 機器負荷分配問題 某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關(guān)系為 g=g(u1) 這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終時完好的機器就為au，0a1，在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關(guān)系為 h=h(u2) 相應(yīng)的機器年完好率為b,0b1。

5、 假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。,第2節(jié) 動態(tài)規(guī)劃的基本概念和基本方程,例1中求A到G的最短路線問題是動態(tài)規(guī)劃中一個典型例子?，F(xiàn)通過討論它的解法，說明動態(tài)規(guī)劃方法的基本思想，并闡述有關(guān)基本概念。 由圖8-2可知，從A點到G點可以分為6個階段。在第一階段，A為起點，終點有B1、B2兩個，因而這時走的路線有兩個選擇，一是走到B1；一是走到B2，若選擇走到B2的決策，則B2就是第一階段決策的結(jié)果。它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發(fā)

6、，有一個可供選擇的終點集合C2，C3，C4；若選擇由B2走至C2，則C2就是第二階段的終點，同時又是第三階段的始點。遞推下去可看到：各個階段的決策不同，路線就不同。顯然，當某階段的始點給定后，會影響后面各階段的行進路線和整個路線的長短，而后面各階段路線的發(fā)展不受這點以前各階段決策的影響。故此問題的要求是：在各個階段上選則一個恰當?shù)臎Q策，使得由這些決策組成的一個決策序列所決定的一條路線是總路程最短的一條。,2.1 動態(tài)規(guī)劃的基本概念,1階段 把所給問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是根據(jù)時間和空間的自然特

7、征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。如例1可分為6個階段來求解，k分別等于1、2、3、4、5、6。,2.1 動態(tài)規(guī)劃的基本概念,2狀態(tài) 狀態(tài)表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，又稱不可控因素。在例1中，狀態(tài)就是某階段的出發(fā)位置。它既是該階段某支路的起點，又是前一階段某支路的終點。通常一個階段有若干個狀態(tài)，第一階段有一個狀態(tài)就是點A，第二階段有兩個狀態(tài)，即點集合B1，B2，一般第k階段的狀態(tài)就是第k階段所有始點的集合。,2.1 動態(tài)規(guī)劃的基本概念,描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個數(shù)、一組數(shù)或一向量(多維情形)來描述。常用Sk表示第k

8、階段的狀態(tài)變量。如在例1中第三階段有四個狀態(tài)，則狀態(tài)變量Sk可取四個值，即C1、C2、C3、C4。點集合C1，C2，C3，C4就稱為第三階段的可達狀態(tài)集合。記為S3C1，C2，C3，C4。有時為了方便起見，將該階段的狀態(tài)編上號碼1，2這時也可記S31，2，3，4。第k階段的可達狀態(tài)集合就記為Sk。,馬爾科夫性 這里所說的狀態(tài)應(yīng)具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展，當前的狀態(tài)是以往歷史的一個總結(jié)。這個性質(zhì)稱為無后效性(即馬爾科夫性)。,2.1 動態(tài)規(guī)劃的基本概念,3決策 決策表示當

9、過程處于某一階段的某個狀態(tài)時，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。它可用一個數(shù)、一組數(shù)或一向量來描述。常用uk（sk）表示第k階段當狀態(tài)處于sk時的決策變量。它是狀態(tài)變量的函數(shù)。在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk（sk）Dk(sk)。,2.1 動態(tài)規(guī)劃的基本概念,3決策 如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D2(B1)C1，C2，C3，若選取的點為C2，則C

10、2是狀態(tài)B1在決策u2(B1)作用下的一個新的狀態(tài)，記作u2(B1)=C2。,2.1 動態(tài)規(guī)劃的基本概念,4策略 策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止狀態(tài)為止的過程，稱為問題的后部子過程。由每段的決策按順序排列組成的決策函數(shù)序列 稱為k子過程策略，簡稱子策略，記為 ，即,當k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即,在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。,2.1 動態(tài)規(guī)劃的基本概念,5狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。

11、若給定第k階段狀態(tài)變量的值，如果該段的決策變量uk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對應(yīng)關(guān)系，記為,上式描述了由k階段到k+1階段的階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。如例1中，狀態(tài)轉(zhuǎn)移方程為,2.1 動態(tài)規(guī)劃的基本概念,6指標函數(shù)和最優(yōu)值函數(shù) 用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。常用Vk,n表示，即,對于要構(gòu)成動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為,在實際

12、問題中很多指標函數(shù)都滿足這個性質(zhì)。,2.1 動態(tài)規(guī)劃的基本概念,(1) 過程和它的任一子過程的指標是它所包含的各階段的指標的和。即,其中,表示第j階段的階段指標，這時上式可寫成,(2) 過程和它的任一子過程的指標是它所包含的各階段的指標的乘積。即,這時就可寫成,常見的指標函數(shù)形式,2.1 動態(tài)規(guī)劃的基本概念,指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記為,。它表示從第,k階段的狀態(tài)sk開始到第n階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數(shù)值。即,“opt”是最優(yōu)化(optimization)的縮寫，可根據(jù)題意而取min或max。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,結(jié)合最短路線問題介紹動態(tài)規(guī)劃

13、方法的基本思想。 生活中的常識告訴我們，最短路線有一個重要特性：如果由起點A經(jīng)過P點和H點而到達終點G是一條最短路線，則由點P出發(fā)經(jīng)過H點到達終點G的這條子路線，對于從點P出發(fā)到達終點的所有可能選擇的不同路線來說，必定也是最短路線。例如，在最短路線問題中，若找到了AB1C2D1E2F2G是由A到G的最短路線，則D1E2F2G應(yīng)該是由D1出發(fā)到G點的所有可能選擇的不同路線中的最短路線。 證明：（用反證法）如果不是這樣，則從點P到G點有另一條距離更短的路線存在，把它和原來最短路線由A點到達P點的那部分連接起來，就會得到一條由A點到G點的新路線，它比原來那條最短路線的距離還要短些。這與假設(shè)矛盾，是不

14、可能的。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,根據(jù)最短路線這一特性，尋找最短路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到G點的最短路線，最后求得由A點到G點的最短路線。所以，動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法。下面按照動態(tài)規(guī)劃的方法，將例1從最后一段開始計算，由后向前逐步推移至A點。,2.1 動態(tài)規(guī)劃的基本概念,2.2 動態(tài)規(guī)劃的基本思想和基本方程,當k=6時，由F1到終點G只有一條路線，故,。同理，,當k=5時，出發(fā)點有 三個。若從E1出發(fā)，則有兩個選擇至F1， 至F2，則,其相應(yīng)的決策為,這說明，由E1至終點G的最短距離為7，其最短路線是,

15、2.2 動態(tài)規(guī)劃的基本思想和基本方程,同理，從E2和E3出發(fā)，則有,其相應(yīng)的決策為,且,2.2 動態(tài)規(guī)劃的基本思想和基本方程,當k=4時，有,當k=3時，有,當k=2時，有,當k=1時，出發(fā)點有一個A點，則,且,。于是得到從起點A到終點G的最短距離為18。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,為了找出最短路線，再按計算的順序反推之，可求出最優(yōu)決策函數(shù)序列,，即由,組成一個最優(yōu)策略。因而，找出相應(yīng)的最短路線為,2.2 動態(tài)規(guī)劃的基本思想和基本方程,從上面的計算過程中可以看出，在求解的各個階段，我們利用了,k階段與k+1階段之間的遞推關(guān)系：,一般情況，k階段與k+1階段的遞推關(guān)系式可寫成,邊界條

16、件為,遞推關(guān)系式(8-1)稱為動態(tài)規(guī)劃的基本方程。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,動態(tài)規(guī)劃方法基本思想歸納： 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件(簡言之為基本方程)。要做到這一點，必須先將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題化成一族同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結(jié)

17、合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。 如例1最短路線問題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有,從而可得最優(yōu)策略為u1(A),u2(B1),u0(F2)，相應(yīng)的最短路線為,2.2 動態(tài)規(guī)劃的基本思想和基本方程,求解最短路問題的標號法逆序解法,2.2 動態(tài)規(guī)劃的基本思想和基本方程,求解最短路問題的標號法順序解法,2.2 動態(tài)規(guī)劃的基本思想和

18、基本方程,動態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點： (1) 減少了計算量。計算例1若用窮舉法，就要對48條路線進行比較，運算在計算機上進行時，比較運算要進行47次；求各條路線的距離，即使用逐段累加方法，也要進行6+12+24+48+48138次加法運算。用動態(tài)規(guī)劃方法來計算，比較運算(從k=5段開始向前算)共進行3+3+4+4+115次。每次比較運算相應(yīng)有兩次加法運算，再去掉中間重復(fù)兩次(即B1C1，B2C4各多算了一次)，實際只有28次加法運算?？梢姡瑒討B(tài)規(guī)劃方法比窮舉法減少了計算量。而且隨著段數(shù)的增加，計算量將大大地減少。 (2) 豐富了計算結(jié)果。在逆序(或順序)解法中，我們得到的不僅僅是由A點

19、(或G點)出發(fā)到G點(或A點)的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點出發(fā)到G點(或A點)的最短路線及相應(yīng)的距離。這就是說，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,建立動態(tài)規(guī)劃模型的五個要點： (1) 將問題的過程劃分成恰當?shù)碾A段； (2) 正確選擇狀態(tài)變量sk，使它既能描述過程的演變，又要滿足無后效性； (3) 確定決策變量uk及每階段的允許決策集合Dk(sk)； (4) 正確寫出狀態(tài)轉(zhuǎn)移方程； (5) 正確寫出指標函數(shù)的關(guān)系，它應(yīng)滿足下面性質(zhì)： 是定義在全過程和所有后部子過程上的數(shù)量函數(shù)； 要具有可分離性，并滿足遞推關(guān)系。即,2.2

20、動態(tài)規(guī)劃的基本思想和基本方程,所以，得到動態(tài)規(guī)劃逆序解法的基本方程：,邊界條件為,式中,求解過程，根據(jù)邊界條件，從k=n開始，由后向前逆推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出,時，就得到整個問題的最優(yōu)解。,2.2 動態(tài)規(guī)劃的基本思想和基本方程,動態(tài)規(guī)劃順序解法的基本方程,邊界條件為,式中,求解過程：根據(jù)邊界條件，從k=1開始，由前向后順推，逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出 ，,就得到整個問題的最優(yōu)解。,第3節(jié) 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,動態(tài)規(guī)劃的最優(yōu)性原理： “作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言

21、，余下的諸決策必須構(gòu)成最優(yōu)策略?！?簡言之，一個最優(yōu)策略的子策略總是最優(yōu)的。 動態(tài)規(guī)劃的基本方程或者說最優(yōu)性定理才是動態(tài)規(guī)劃的理論基礎(chǔ),第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,相同點 動態(tài)規(guī)劃、線性規(guī)劃和非線性規(guī)劃都屬于數(shù)學(xué)規(guī)劃范圍，研究對象本質(zhì)上都是求極值問題，都是利用迭代法去逐步求解。 不同點 線性規(guī)劃和非線性規(guī)劃研究的問題通常與時間無關(guān)，故又稱為靜態(tài)規(guī)劃。線性規(guī)劃迭代中的每一步是就問題的整體加以改善的。 動態(tài)規(guī)劃研究的問題與時間有關(guān)，研究具有多階段決策過程的一類問題，將問題的整體按時間或空間的特征分成若干個前后銜接的時空階段，把多階段決策問題表示為前后有關(guān)聯(lián)的一系列單階段決策問題，然后逐個加以

22、解決，從而求出整個問題的最優(yōu)決策序列。 對于某些靜態(tài)問題，也可以人為地引入時間因素，把它看作是按階段進行的一個動態(tài)規(guī)劃問題，這就使得動態(tài)規(guī)劃成為求解某些線性、非線性規(guī)劃的有效方法。,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,動態(tài)規(guī)劃方法 逆序解法 順序解法 關(guān)鍵：正確寫出動態(tài)規(guī)劃的遞推關(guān)系式 逆推形式，當初始狀態(tài)給定時，用逆推比較方便 順推形式，當終止狀態(tài)給定時，用順推比較方便,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,考查如圖所示的n階段決策過程。其中取狀態(tài)變量為,決策變量為,。在第k階段，決策xk使狀態(tài)sk(輸入）轉(zhuǎn)移,為sk+1 (輸出)，設(shè)狀態(tài)轉(zhuǎn)移函數(shù)為,假定過程的總效益(指標函數(shù))與各階段效益(階段

23、指標函數(shù))的關(guān)系為,其中記號*都表示為+,或都表示為。問題是：使,達到最優(yōu)化，即求,，為簡單起見，不妨此處就求,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,4.1 逆推解法 設(shè)已知初始狀態(tài)為s1，并假定最優(yōu)值函數(shù)fk(sk)表示第k階段的初始狀態(tài)為sk，從k階段到n階段所得到的最大效益。,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,例3 用逆推解法求解下面問題,解 : 按問題的變量個數(shù)劃分階段，把它看作為一個三階段決策問題。 設(shè)狀態(tài)變量為s1, s2,s3,s4，并記s1=c；取問題中的變量x1,x2,x3為決策變量；各階段指標函數(shù)按乘積方式結(jié)合。令最優(yōu)值函數(shù)fk(sk)表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得到的最大值。,設(shè),第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,用逆推解法，從后向前依次有,及最優(yōu)解,由,得,和,(舍去),，而,，故,為極大值點。,最優(yōu)解,由,所以,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,像前面一樣利用微分法易知,故,由于已知,而按計算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,即,由,所以,所以,因此得到最優(yōu)解為,最大值為,由,第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,4.2 順推解法 設(shè)已知終止狀