運籌學(xué)-第9章-動態(tài)規(guī)劃

1、,五 動態(tài)規(guī)劃,第9章 動態(tài)規(guī)劃的基本方法第10章 動態(tài)規(guī)劃應(yīng)用舉例,1,2,動態(tài)規(guī)劃,什么是動態(tài)規(guī)劃解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。動態(tài)規(guī)劃的形成產(chǎn)生于20世紀(jì)50年代。1951年美國數(shù)學(xué)家貝爾曼(R.Bellman)等人，根據(jù)一類多階段決策問題的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。與此同時，他提出了解決這類問題的“最優(yōu)性原理”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的

2、一種新的方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都有廣泛的應(yīng)用，并且獲得了顯著的效果。,3,動態(tài)規(guī)劃,動態(tài)規(guī)劃在企業(yè)管理中的主要應(yīng)用領(lǐng)域最優(yōu)路徑問題資源分配問題生產(chǎn)調(diào)度問題庫存問題裝載問題排序問題設(shè)備更新問題生產(chǎn)過程最優(yōu)控制問題等等 動態(tài)規(guī)劃是求解某類問題的一種方法，是考查問題的一種途徑，而不是一種特殊算法(如線性規(guī)劃是一種算法)。因而，它不像線性規(guī)劃那樣有一個標(biāo)

3、準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理。,4,動態(tài)規(guī)劃,動態(tài)規(guī)劃模型的分類根據(jù)多階段決策過程的時間參量是離散的還是連續(xù)變量，分為離散決策過程和連續(xù)決策過程。根據(jù)決策過程的演變是確定性的還是隨機性的，又可分為確定性決策過程和隨機性決策過程。組合起來可分為離散確定性離散隨機性連續(xù)確定性連續(xù)隨機性本書主要研究離散決策過程。,5,第9章 動態(tài)規(guī)劃的基本方法,第1節(jié) 多階段決策過程及實例第2節(jié)

4、 動態(tài)規(guī)劃的基本概念和基本方程第3節(jié) 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理第4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,6,第1節(jié) 多階段決策過程及實例,多階段決策過程在生產(chǎn)和科學(xué)實驗中，有一類活動的過程，由于它的特殊性，可將過程分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。因此，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個階段決策確定后，就組成了一個決策序

5、列，因而也就決定了整個過程的一條活動路線。這種把一個問題可看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，也稱序貫決策過程。,7,第1節(jié) 多階段決策過程及實例,例1 最短路線問題 給定一個線路網(wǎng)絡(luò)，兩點之間連線上的數(shù)字表示兩點間的距離(或費用)，試求一條由A到G的鋪管線路，使總距離為最短(或總費用最小)。,8,第1節(jié) 多階段決策過程及實例,例2 機器負(fù)荷分配問題某種機器可以在高低兩種不同的負(fù)荷下進行生

6、產(chǎn)。在高負(fù)荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關(guān)系為 g=g(u1)這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終時完好的機器就為au，0＜a＜1，在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關(guān)系為 h=h(u2)相應(yīng)的機器年完好率為b

7、,0＜b＜1。假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,9,第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兩個，因而

8、這時走的路線有兩個選擇，一是走到B1；一是走到B2，若選擇走到B2的決策，則B2就是第一階段決策的結(jié)果。它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發(fā)，有一個可供選擇的終點集合｛C2，C3，C4｝；若選擇由B2走至C2，則C2就是第二階段的終點，同時又是第三階段的始點。遞推下去可看到：各個階段的決策不同，路線就不同。顯然，當(dāng)某階段的始點給定后，會影響后面各階段的行進路線和整個路線的長短，而后面各階段路線的發(fā)

9、展不受這點以前各階段決策的影響。故此問題的要求是：在各個階段上選則一個恰當(dāng)?shù)臎Q策，使得由這些決策組成的一個決策序列所決定的一條路線是總路程最短的一條。,10,2.1 動態(tài)規(guī)劃的基本概念,1．階段把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是根據(jù)時間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。如例1可分為6個階段來求解，k

10、分別等于1、2、3、4、5、6。,,,,,,,,11,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階段所有始點的集合。,,,12,2.1 動

11、態(tài)規(guī)劃的基本概念,描述過程狀態(tài)的變量稱為狀態(tài)變量。它可用一個數(shù)、一組數(shù)或一向量(多維情形)來描述。常用Sk表示第k階段的狀態(tài)變量。如在例1中第三階段有四個狀態(tài)，則狀態(tài)變量Sk可取四個值，即C1、C2、C3、C4。點集合｛C1，C2，C3，C4｝就稱為第三階段的可達(dá)狀態(tài)集合。記為S3＝｛C1，C2，C3，C4｝。有時為了方便起見，將該階段的狀態(tài)編上號碼1，2…這時也可記S3＝｛1，2，3，4｝。第k階段的可達(dá)狀態(tài)集合就記為Sk。,馬爾科夫

12、性這里所說的狀態(tài)應(yīng)具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的一個總結(jié)。這個性質(zhì)稱為無后效性(即馬爾科夫性)。,13,2.1 動態(tài)規(guī)劃的基本概念,3．決策決策表示當(dāng)過程處于某一階段的某個狀態(tài)時，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變

13、量，稱為決策變量。它可用一個數(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)。,,14,2.1 動態(tài)規(guī)劃的基本概念,3．決策 如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D

14、2(B1)＝｛C1，C2，C3｝，若選取的點為C2，則C2是狀態(tài)B1在決策u2(B1)作用下的一個新的狀態(tài)，記作u2(B1)=C2。,,,15,2.1 動態(tài)規(guī)劃的基本概念,4．策略策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程。由每段的決策按順序排列組成的決策函數(shù)序列 稱為k子過程策略，簡稱子策略，記為

15、 ，即,當(dāng)k=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即,在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。,16,2.1 動態(tài)規(guī)劃的基本概念,,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

16、的值也就完全確定。即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)移方程為,17,2.1 動態(tài)規(guī)劃的基本概念,,6．指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。常用Vk,n表示，即,對于要構(gòu)成動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性

17、，并滿足遞推關(guān)系。即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為,在實際問題中很多指標(biāo)函數(shù)都滿足這個性質(zhì)。,,18,2.1 動態(tài)規(guī)劃的基本概念,,(1) 過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)的和。即,其中,表示第j階段的階段指標(biāo)，這時上式可寫成,(2) 過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即,這時就可寫成,常見的指標(biāo)函數(shù)形式,,,,19,2.1 動態(tài)規(guī)劃的基本概念,,指標(biāo)函數(shù)的最優(yōu)值，稱

18、為最優(yōu)值函數(shù)，記為,。它表示從第,k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即,“opt”是最優(yōu)化(optimization)的縮寫，可根據(jù)題意而取min或max。,20,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,結(jié)合最短路線問題介紹動態(tài)規(guī)劃方法的基本思想。生活中的常識告訴我們，最短路線有一個重要特性：如果由起點A經(jīng)過P點和H點而到達(dá)終點G是一條最短路線，則由點P出發(fā)經(jīng)過H點到達(dá)終點G的這條子路線

19、，對于從點P出發(fā)到達(dá)終點的所有可能選擇的不同路線來說，必定也是最短路線。例如，在最短路線問題中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最短路線，則D1→E2→F2→G應(yīng)該是由D1出發(fā)到G點的所有可能選擇的不同路線中的最短路線。證明：（用反證法）如果不是這樣，則從點P到G點有另一條距離更短的路線存在，把它和原來最短路線由A點到達(dá)P點的那部分連接起來，就會得到一條由A點到G點的新路線，它比原來那條最短路線的距離還要短些。

20、這與假設(shè)矛盾，是不可能的。,21,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,根據(jù)最短路線這一特性，尋找最短路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到G點的最短路線，最后求得由A點到G點的最短路線。所以，動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方下面按照動態(tài)規(guī)劃的方法，將例1從最后一段開始計算，由后向前逐步推移至A點。,22,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,當(dāng)k=6時，由F1到終點G只有一

21、條路線，故,。同理，,當(dāng)k=5時，出發(fā)點有 三個。若從E1出發(fā)，則有兩個選擇①至F1，②至F2，則,其相應(yīng)的決策為,這說明，由E1至終點G的最短距離為7，其最短路線是,23,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,同理，從E2和E3出發(fā)，則有,其相應(yīng)的決策為,且,24,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,當(dāng)k=4時，有,當(dāng)k=3時，有,當(dāng)k=2時，有,當(dāng)k=1時，出發(fā)點有一個A點，則,且,。于是

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

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

24、個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。,28,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。如例1最短路

25、線問題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有,從而可得最優(yōu)策略為｛u1(A),u2(B1),…,u0’(F2)｝，相應(yīng)的最短路線為,,,,,29,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,求解最短路問題的標(biāo)號法——逆序解法,30,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,求解最短路問題的標(biāo)號法——順序解法,31,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,動態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點：(1) 減少了計算量。計算例1若用窮

26、舉法，就要對48條路線進行比較，運算在計算機上進行時，比較運算要進行47次；求各條路線的距離，即使用逐段累加方法，也要進行6+12+24+48+48＝138次加法運算。用動態(tài)規(guī)劃方法來計算，比較運算(從k=5段開始向前算)共進行3+3+4+4+1＝15次。每次比較運算相應(yīng)有兩次加法運算，再去掉中間重復(fù)兩次(即B1→C1，B2→C4各多算了一次)，實際只有28次加法運算?？梢?，動態(tài)規(guī)劃方法比窮舉法減少了計算量。而且隨著段數(shù)的增加，計算量將

27、大大地減少。(2) 豐富了計算結(jié)果。在逆序(或順序)解法中，我們得到的不僅僅是由A點(或G點)出發(fā)到G點(或A點)的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點出發(fā)到G點(或A點)的最短路線及相應(yīng)的距離。這就是說，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。,32,2.2 動態(tài)規(guī)劃的基本思想和基本方程,,建立動態(tài)規(guī)劃模型的五個要點：(1) 將問題的過程劃分成恰當(dāng)?shù)碾A段；(2) 正確選擇狀態(tài)變量sk，使它既能描述過程的演變，

28、又要滿足無后效性；(3) 確定決策變量uk及每階段的允許決策集合Dk(sk)；(4) 正確寫出狀態(tài)轉(zhuǎn)移方程；(5) 正確寫出指標(biāo)函數(shù)Vk,n的關(guān)系，它應(yīng)滿足下面三個性質(zhì)： ① 是定義在全過程和所有后部子過程上的數(shù)量函數(shù)； ② 要具有可分離性，并滿足遞推關(guān)系。即 ③ 函數(shù) 對于變量Vk+1,n要嚴(yán)格單調(diào)。,33,第3節(jié) 動態(tài)規(guī)劃的

29、最優(yōu)性原理和最優(yōu)性定理,,動態(tài)規(guī)劃的最優(yōu)性原理：“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?！?簡言之，一個最優(yōu)策略的子策略總是最優(yōu)的。動態(tài)規(guī)劃的基本方程或者說最優(yōu)性定理才是動態(tài)規(guī)劃的理論基礎(chǔ),具體說，此問題先從F開始，因為F是終點。再無后繼過程，故可以接著考慮第5階段上所有可能狀態(tài)E1，E2的最優(yōu)后續(xù)過程。因為從E1 ,E2到F的路線是

30、唯一的，所以E1，E2的最優(yōu)決策和最優(yōu)后繼過程就是到F，它們的最短距離分別是4和3。 接著考慮階段4上可能的狀態(tài)D1，D2，D3 到F的最優(yōu)決策和最優(yōu)后繼過程．在狀態(tài)D1上，到E1是3，到E2是5，綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決策是到E1,最優(yōu)后繼過程是D1→E1→F ，最短距離是7。同理，狀態(tài)D2的最優(yōu)決策是至E2 ；D3的最優(yōu)決策是到E1。,同樣，當(dāng)階段4上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后，便可以開始考慮階段3上

31、所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如C1的最優(yōu)決策是到D1,最優(yōu)路線是C1→D1→E1→F ，最短距離是12…依此類推，最后可以得到從初始狀態(tài)A的最優(yōu)決策是到F最優(yōu)路線是A→B1→C2→D2→E2 →F ，全程的最短距離是17。圖7—1中粗實線表示各點到的最優(yōu)路線，每點上方括號內(nèi)的數(shù)字表示該點到終點的最短路距離。,,,,,綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法屬較科學(xué)有