動態(tài)規(guī)劃基本概念

1、運運 籌籌 學(xué)學(xué)動態(tài)規(guī)劃第五章 動態(tài)規(guī)劃 動態(tài)規(guī)劃是運籌學(xué)的一個重要分支，它是從1951年開始，由美國人貝爾曼（R.Belman）為首的一個學(xué)派發(fā)展起來的。動態(tài)規(guī)劃在經(jīng)濟、管理、軍事、工程技術(shù)等方面都有廣泛的應(yīng)用。 動態(tài)規(guī)劃是解決多階段決策過程的最優(yōu)化問題的一種方法。所謂多階段決策過程是指這樣一類決策過程：它可以把一個復(fù)雜問題按時間（或空間）分成若干個階段，每個階段都需要作出決策，以便得到過程的最優(yōu)結(jié)局。由于在每個階段采取的決策是與時間有關(guān)的而且前一階段采取的決策如何，不但與該階段的經(jīng)濟效果有關(guān)，還影響以后各階段的經(jīng)濟效果，可見這類多階段決策問題是一個動態(tài)的問題，因此，處理的方法稱為動態(tài)規(guī)劃方

2、法。然而，動態(tài)規(guī)劃也可以處理一些本來與時間沒有關(guān)系的靜態(tài)模型，這只要在靜態(tài)模型中人為地引入“時間”因素，分成時段，就可以把它看作是多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。 動態(tài)規(guī)劃對于解決多階段決策問題的效果是明顯的，但也有一定的局限性。首先，它沒有統(tǒng)一的處理方法，必須根據(jù)問題的各種性質(zhì)并結(jié)合一定的技巧來處理；另外當(dāng)變量的維數(shù)增大時，總的計算量及存貯量急劇增大。由于計算機的存貯量及計算速度的限制，目前的計算機仍不能用動態(tài)規(guī)劃方法來解決較大規(guī)模的問題，這就是所謂“維數(shù)障礙”。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種

3、算法。必須對具體問察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立題進(jìn)行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。 1 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念n 1.1 多階段決策問題多階段決策問題 在研究社會經(jīng)濟、經(jīng)營管理和工程技術(shù)領(lǐng)域內(nèi)的有關(guān)問題中，有一類特殊形式的動態(tài)決策問題多階段決策問題。在多階段決策過程中，系統(tǒng)的動態(tài)過程可以按照時間進(jìn)程分為相互聯(lián)系而又相互區(qū)別的各個階段，在每個階段都要進(jìn)行決策。系統(tǒng)在每個階段存在許多不同的狀態(tài)，在某個時點的狀態(tài)往往要依某種形式受到過

4、去某些決策的影響，而系統(tǒng)的當(dāng)前狀態(tài)和決策又會影響系統(tǒng)過程今后的發(fā)展。因而在尋求多階段決策問題的最優(yōu)解時，重要的是不能僅僅從眼前的局部利益出發(fā)進(jìn)行決策，而需要從系統(tǒng)所經(jīng)過的整個期間的總效應(yīng)出發(fā)，有預(yù)見性地進(jìn)行動態(tài)決策，找到不同時點的最優(yōu)決策及整個過程的最優(yōu)策略。 下面舉例說明什么是多階段決策問題。 例1（最短路線問題）在線路網(wǎng)絡(luò)圖1中，從A至E有一批貨物需要調(diào)運。圖上所標(biāo)數(shù)字為各節(jié)點之間的運輸距離，為使總運費最少，必須找出一條由A至E總里程最短的路線。AB1B2EB3C2C3C1D2D3D14534443165887710296為了找到由A至E的最短線路，可以將該問題分成ABCDE 4個階段，在

5、每個階段都需要作出決策，即在A點需決策下一步到B1還是到B2或B3；同樣，若到達(dá)第二階段某個狀態(tài)，比如B1 ，需決定走向C1還是C2 ；依次類推，可以看出：各個階段的決策不同，由A至E的路線就不同，當(dāng)從某個階段的某個狀態(tài)出發(fā)作出一個決策，則這個決策不僅影響到下一個階段的距離，而且直接影響后面各階段的行進(jìn)線路。所以這類問題要求在各個階段選擇一個恰當(dāng)?shù)臎Q策，使這些決策序列所決定的一條路線對應(yīng)的總路程最短。圖圖1 例2（帶回收的資源分配問題）某廠新購某種機床125臺。據(jù)估計，這種設(shè)備5年后將被其它設(shè)備所代替。此機車如在高負(fù)荷狀態(tài)下工作，年損壞率為1/2，年利潤為10萬元；如在低負(fù)荷狀態(tài)下工作，年損壞

6、率為1/5，年利潤為6萬元。問應(yīng)如何安排這些機床的生產(chǎn)負(fù)荷，才能使5年內(nèi)獲得的利潤最大？ 本問題具有時間上的次序性，在五年計劃的每一年都要作出關(guān)于這些機床生產(chǎn)負(fù)荷的決策，并且一旦作出決策，不僅影響到本年利潤的多少，而且影響到下一年初完好機床數(shù)，從而影響以后各年的利潤。所以在每年初作決策時，必須將當(dāng)年的利潤和以后各年利潤結(jié)合起來，統(tǒng)籌考慮。 與上面例1、例2類似的多階段決策問題還有資源分配、生產(chǎn)存貯、可靠性、背包、設(shè)備更新問題等等。 1.2 動態(tài)規(guī)劃的基本概念 1.階段階段 動態(tài)規(guī)劃問題通常都具有時間或空間上的次序性，因此求解這類問題時，首先要將問題按一定的次序劃分成若干相互聯(lián)系的階段，以便能按

7、一定次序去求解。如例1，可以按空間次序劃分為ABCDE 4個階段，而例2，按照時間次序可分成5個階段。 2.狀態(tài)狀態(tài) 在多階段決策過程中，每階段都需要作出決策，而決策是根據(jù)系統(tǒng)所處情況決定的。狀態(tài)是描述系統(tǒng)情況所必需的信息。如例1中每階段的出發(fā)點位置就是狀態(tài)，例2中每年初擁有的完好機床數(shù)是作出機床負(fù)荷安排的根據(jù)，所以年初完好機床數(shù)是狀態(tài)。一般地，狀態(tài)可以用一個變量來描述，稱為狀態(tài)變量。記第k 階段的狀態(tài)變量為xk，k=1,2, ,n. 3.決策決策:多階段決策過程的發(fā)展是用各階段的狀態(tài)演變來描述的，階段決策就是決策者從本階段某狀態(tài)出發(fā)對下一階段狀態(tài)所作出的選擇。描述決策的變量稱為決策變量，當(dāng)?shù)?/p>

8、k 階段的狀態(tài)確定之后，可能作出的決策要受到這一狀態(tài)的影響。這就是說決策變量uk還是狀態(tài)變量xk 的函數(shù)，因此，又可將第k階段xk狀態(tài)下的決策變量記為uk(xk)。 在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策變量集合，記作Dk(uk)。如例2中取高負(fù)荷運行的機床數(shù)uk為決策變量，則0ukxk（xk是k階段初完好機床數(shù)）為允許決策變量集合。4.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程:在多階段決策過程中，如果給定了k 階段的狀態(tài)變量xk和決策變量uk，則第k+1階段的狀態(tài)變量xk+1也會隨之而確定。也就是說xk+1是xk和uk函數(shù)，這種關(guān)系可記為 xk+1=T(xk, uk) 稱之為

9、狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程。 5.策略策略:在一個多階段決策過程中，如果各個階段的決策變量uk(xk) （k=1，2，n）都已確定，則整個過程也就完全確定。稱決策序列u1(x1), u2(x2), , un(xn)為該過程的一個策略策略，從階段k到階段n的決策序列稱為子策略子策略，表示成uk(xk), uk+1(xk+1), , un(xn) 。如例1中，選取一路線AB1C2D2E 就是一個策略： u1(A)= B1, u2(B1)= C2, u3(C2)= D2, u4(D2)=E 由于每一階段都有若干個可能的狀態(tài)和多種不同的決策，因而一個多階段決策的實際問題存在許多策略可供選擇，稱其中能夠滿

10、足預(yù)期目標(biāo)的策略為最優(yōu)策略最優(yōu)策略。例1中存在12條不同路線，其中AB2C1D2E是最短線路。6.指標(biāo)函數(shù)指標(biāo)函數(shù):用來衡量過程優(yōu)劣的數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)指標(biāo)函數(shù)。在階段k的xk狀態(tài)下執(zhí)行決策uk，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也必然對目標(biāo)函數(shù)給予影響，階段效應(yīng)就是執(zhí)行階段決策時給目標(biāo)函數(shù)的影響。 多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是各階段的階段效應(yīng)累積形成的。常見的全過程目標(biāo)函數(shù)有以下兩種形式：n （1）全過程的目標(biāo)函數(shù)等于各階段目標(biāo)函數(shù)的和，即： R=r1 (x1, u1) +r2 (x2, u2) +rn(xn, un)n （2）全過程的目標(biāo)函數(shù)等于各階段目標(biāo)函數(shù)的積，即： R=r1 (

11、x1, u1) r2 (x2, u2) rn(xn, un) 指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)函數(shù)值最優(yōu)函數(shù)值。一般，f1（x1）表示從第1階段x1狀態(tài)出發(fā)至第n階段（最后階段）的最優(yōu)指標(biāo)函數(shù)， fk（xk）表示從第k階段xk狀態(tài)出發(fā)至第n階段的最優(yōu)指標(biāo)函數(shù)(k=1，2，n）。 2 動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理 多階段決策過程的特點是每個階段都要進(jìn)行決策，具有n個階段的決策過程的策略是由n個相繼進(jìn)行的階段決策構(gòu)成的決策序列。由于前階段的終止?fàn)顟B(tài)又是后一階段的初始狀態(tài)，因此確定階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤考慮，整體規(guī)劃。就是說，階段k的最優(yōu)決策不應(yīng)只是本階段的最優(yōu)，而必須

12、是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個后部子過程的最優(yōu)決策。 對此，貝爾曼在深入研究的基礎(chǔ)上，針對具有無后效性的多階段決策過程的特點，提出了著名的多階段決策的最優(yōu)性原最優(yōu)性原理理： “整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過程過去整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過程過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。諸決策必須構(gòu)成最優(yōu)策略。” 簡而言之，最優(yōu)性原理的含意就是：最優(yōu)策略的任何一部最優(yōu)策略的任何一部分子策略也必須是最優(yōu)的。分子策略也必須是最優(yōu)的。 如例1，AB2C1D2E是由A到E

13、的最短路線，我們在該路線上任取一點C1 ，按照最優(yōu)性原理C1D2E應(yīng)該是C1到E的最短路。很容易用反證法證明這一結(jié)論的正確性，從而說明最優(yōu)性原理的正確性。 按最優(yōu)性原理，可以將例1分成ABCDE 4個階段，由后向前逐步求出各點到E的最短線路，直至求出A至E的最短線路。K=4時，出發(fā)點有D1，D2，D3，記f4（Di）（i=1,2,3）為Di到E的最短距離；u4(Di)表示從狀態(tài)Di出發(fā)采取的決策。顯然： f4（D1）=7，u4(D1)=E f4（D2）=8，u4(D2)=E f4（D3）=6，u4(D3)=EK=3時，出發(fā)點有C1，C2，C3f3（C1）=mind（C1D1）+f4（D1）,d

14、（C1D2）+f4（D2） =min4+7,2+8=10, u3(C1)= D2f3（C2）=mind（C2D2）+f4（D2）,d（C2D3）+f4（D3） =min5+8,7+6=13, u3(C2)= D2或D3f3（C3）=mind（C3D2）+f4（D2）,d（C3D3）+f4（D3） =min10+8,9+6=15, u3(C3)= D3K=2時，出發(fā)點有B1，B2，B3f2（B1）=mind（B1C1）+f3（C1）,d（B1C2）+f3（C2） =min6+10,4+13=16, u2(B1)= C1f2（B2）=mind（B2C1）+f3（C1）,d（B2C3）+f3（C3）

15、 =min3+10,1+15=13, u2(B2)= C1f2（B3）=mind（B3C2）+f3（C2）,d（B3C3）+f3（C3） =min8+13,4+15=19, u2(B3)= C3 K=1時，出發(fā)點只有A d（AB1）+f2（B1） 4+16 f1（A）=min d（AB2）+f2（B2）= 5+13 =18, d（AB3）+f2（B3） 3+19 u1(A)= B2 由f1（A）=18，可知從起點A到終點E的最短距離為18。 為了找出最短線路，再按計算順序反推回去，可求出最優(yōu)決策序列，即由 u1(A)= B2 ，u2(B2)= C1 ，u3(C1)= D2，u4(D2)=E組成

16、最優(yōu)策略，也就是最短線路為： AB2C1D2E 從上面的例子不難看出，對于最短線路問題，有如下的遞推關(guān)系（函數(shù)方程）： fk（xk）=mind（xk,uk(xk)）+fk+1（T(xk, uk)） fn+1（xn+1）=0 k=n,n-1,1 一般情況下，多階段決策問題存在下面的遞推關(guān)系： fk（xk）= opt rk(xk, uk(xk)fk+1（T(xk, uk)） uk Dk(uk) fn+1（xn+1）=C k=n,n-1,1 這里rk(xk, uk(xk)是第階段采用uk(xk)決策產(chǎn)生的階段效應(yīng)；fn+1（xn+1）=C是邊界條件；“”號大多數(shù)情況下是 “+”號，也可能是“”號。稱

17、上述遞推關(guān)系為動態(tài)規(guī)劃的基動態(tài)規(guī)劃的基本方程本方程，這個方程是最優(yōu)化原理的具體表達(dá)形式。在基本方程中， rk(xk, uk)， xk+1=T(xk, uk)都是已知函數(shù)，最優(yōu)子策略fk（xk）與fk+1（xk+1）之間是遞推關(guān)系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），這就決定了應(yīng)用動態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的。 另一方面，由于k+1階段的狀態(tài)xk+1=T(xk, uk)是由前面的狀態(tài)和決策所形成的，在計算fk+1（xk+1）時還不能具體確定xk+1的，這就要求必須就k+1階段的各個可能狀態(tài)計算fk+1（xk+1），因此動態(tài)規(guī)劃不但能求出整個問題

18、的最優(yōu)策略和最優(yōu)目標(biāo)值，而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標(biāo)值。 3 建立動態(tài)規(guī)劃數(shù)學(xué)模型的步驟 “最優(yōu)化原理”是動態(tài)規(guī)劃的核心,所有動態(tài)規(guī)劃問題的遞推關(guān)系都是根據(jù)這個原理建立起來的,并且根據(jù)遞推關(guān)系依次計算,最終可求得動態(tài)規(guī)劃問題的解。 一般來說，利用動態(tài)規(guī)劃求解實際問題需先建立問題的動態(tài)模型，具體步驟如下： 將問題按時間或空間次序劃分成若干階段。有些問題不具有時空次序，也可以人為地引進(jìn)時空次序，劃分階段。 正確選擇狀態(tài)變量xk。這一步是形成動態(tài)模型的關(guān)鍵，狀態(tài)變量是動態(tài)規(guī)劃模型中最重要的參數(shù)。一般來說，狀態(tài)變量應(yīng)具有以下三個特性： 要能夠用來描述決策過程的演變特征。 要滿

19、足無后效性。即如果某階段狀態(tài)已給定后，則以后過程的進(jìn)展不受以前各狀態(tài)的影響，也就是說，過去的歷史只通過當(dāng)前的狀態(tài)去影響未來的發(fā)展。 遞推性。即由k階段的狀態(tài)變量xk及決策變量uk可以計算出k+1階段的狀態(tài)變量xk+1。 確定決策變量uk及允許決策變量集合Dk(uk)。 根據(jù)狀態(tài)變量之間的遞推關(guān)系，寫出狀態(tài)轉(zhuǎn)移方程： xk+1=T(xk, uk(xk) 建立指標(biāo)函數(shù)。一般用rk(xk, uk)描寫階段效應(yīng)，fk（xk）表示kn階段的最優(yōu)子策略函數(shù)。 建立動態(tài)規(guī)劃基本方程： fk（xk）= opt rk(xk, uk(xk)fk+1（xk+1） uk Dk(uk) fn+1（xn+1）=C k=n

20、,n-1,1 以上是建立動態(tài)規(guī)劃模型的過程，這個過程是正確求解動態(tài)規(guī)劃的基礎(chǔ)。 在動態(tài)規(guī)劃基本方程中， rk(xk, uk)， xk+1=T(xk, uk)都是已知函數(shù)，最優(yōu)子策略fk（xk）與fk+1（xk+1）之間是遞推關(guān)系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），這就決定了應(yīng)用動態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的。由后向前逐步計算，最終可以算出全過程的最優(yōu)策略函數(shù)值及最優(yōu)策略。 另一方面，由于k+1階段的狀態(tài)xk+1=T(xk, uk)是由前面的狀態(tài)xk和決策uk所形成的，在計算fk+1（xk+1）時還不能具體確定xk+1的值，所以，這就要求必須就

21、k+1階段的各個可能狀態(tài)計算fk+1（xk+1），因此動態(tài)規(guī)劃方法不但能求出整個問題的最優(yōu)策略和最優(yōu)目標(biāo)值，而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標(biāo)值。 下面就按上述步驟求解例2。 例2（帶回收的資源分配問題）某廠新購某種機床125臺。據(jù)估計，這種設(shè)備5年后將被其它設(shè)備所代替。此機床如在高負(fù)荷狀態(tài)下工作，年損壞率為1/2，年利潤為10萬元；如在低負(fù)荷狀態(tài)下工作，年損壞率為1/5，年利潤為6萬元。問應(yīng)如何安排這些機床的生產(chǎn)負(fù)荷，才能使5年內(nèi)獲得的利潤最大？ 解：以年為階段，k=1，2，3，4，5 取k年初完好的機床數(shù)為狀態(tài)變量xk 以k年初投入高負(fù)荷運行的機床數(shù)為決策變量uk，則低負(fù)荷運行機床數(shù)是xk-uk，于是狀態(tài)轉(zhuǎn)移方程為： xk+1=1/2uk+4/5（xk-uk）=0.8xk-0.3uk 以利潤為目標(biāo)函數(shù)，則k年利潤為： 10uk+6（xk-uk）=4uk+6xk 記fk（xk）為k年至5年末最大總利潤，則動態(tài)規(guī)劃基本方程為： fk（xk）= max 4uk+6xk+fk+1（0.8xk-0.3uk） 0ukxk f6（x6）=0 k=5,4,3,2,1以上是