動態(tài)規(guī)劃模型及實驗

1、第七章 動態(tài)規(guī)劃模型與實驗一個系統(tǒng)依據(jù)某種方式分為許多個不同的階段，這些階段不僅有著次序推移性，而且相互間有著依賴和影響。這種能分成階段推移的系統(tǒng)叫做動態(tài)系統(tǒng)。動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種數(shù)學方法。動態(tài)規(guī)劃的一個顯著特點在于具有明確的階段性，整個系統(tǒng)按某種方式可分為若干個不同的階段，在每個階段由若干種不同的方案可供選擇。這樣，在多階段決策過程中，每個階段決策的選擇，不僅要依據(jù)次序來考查某階段的效果外，而且更要顧及此決策對以后各階段決策的影響，特別是對以后各個階段決策的影響。系統(tǒng)最優(yōu)決策問題要求在系統(tǒng)每個階段可供的多種方案 (決策) 中，選擇一個合適的決策，使整個系統(tǒng)達到最優(yōu)的效果。

2、整個過程分為多階段的決策過程。各個階段所做的決策形成確定整個系統(tǒng)的決策序列，稱這樣的決策序列為系統(tǒng)的一個策略。對應某一確定的策略，整個系統(tǒng)依據(jù)某種數(shù)量指標衡量其優(yōu)劣的決策。多階段決策過程就是在所有允許策略集合中。確定一個達到最優(yōu)指標的最優(yōu)策略。這種衡量系統(tǒng)的指標一般取最大值或最小值的策略。因此，多階段決策過程也是一個可以構成多個變量的最優(yōu)化問題。一個系統(tǒng)能分為多階段的決策過程，有時需要數(shù)學技巧和藝術來劃分，動態(tài)規(guī)劃就是解決此類多階段決策過程的最優(yōu)化方法。7.1動態(tài)規(guī)劃的基本原理實際生活的問題，通過構造數(shù)學模型，具有特殊的動態(tài)系統(tǒng)過程，將基于某種方式把整個過程分成若干個互相聯(lián)系的階段，在其每個階

3、段都需要作出合適決策，從而使整個過程達到最佳效果。同時，各個階段決策的選擇依賴于該階段的狀態(tài)以及前或后階段的變化。各個階段決策確定后，組成一個決策序列，從而形成了整個過程具有前后關聯(lián)的鏈狀結構的多階段決策過程，稱為序貫決策過程。由此，動態(tài)規(guī)劃求解首先關鍵在于如何將實際問題構造成能形成多階段的系統(tǒng)，并且在各個階段能作出序貫性的最佳決策，以使在序貫決策的狀態(tài)推移進程中達到整個系統(tǒng)的最優(yōu)決策。例7.1能分成階段的最短路問題。圖7.1是一個路線網(wǎng)絡圖，連線上的數(shù)字表示兩點之間的距離（或費用），要求尋找一條由A到E的路線，使距離最短（或費用最?。?。657999745105556811 B1 C1 D1

4、A B2 C2 E D28 B3 C3圖7.1 對于這樣一個比較簡單的問題，可直接使用枚舉法列舉所有從A到E的路線，共14條，然后，根據(jù)每條路線的長度（或費用），確定出所應走的路線（費用）最短（少）。直觀的思想，如果已找到由A到E的最短路線是AB1C2D2E（記作L），那么當尋求L中的任何一點（如C2）到E的最短路時，它必然是L中子路線C2D2E（記作L1）。否則若D2到E的最短路是另一條路線L2 ，則把AB1C2與L2連接起來，就會得到一條不同于L的從A到E的最短路。根據(jù)此特性，可以從最后一段開始，用逐步向前遞推的方法，依次求出路段上各點到E的最短路，最后得到A到E的最短路。上述這種由系統(tǒng)的

5、作后階段逐段向初是始階段求最優(yōu)的過程稱為動態(tài)規(guī)劃的逆推解法。該過程揭示了動態(tài)規(guī)劃的基礎思想，為使動態(tài)規(guī)劃的思想和方法數(shù)學上描述。下面先引入動態(tài)規(guī)劃中基本概念與最優(yōu)目標函數(shù)的建立。（1）分階段 把所給的系統(tǒng)，適當?shù)匾罁?jù)具體情況分成若干個相互聯(lián)系的階段，描述階段的變量稱為階段變量，常用k表示，并將各個階段按順序或逆序加以編號，如例7.1可分為5個階段來求解，k=1，2，3，4，5。（2）狀態(tài) 狀態(tài)表示系統(tǒng)在某一階段所處的位置，自然狀況或客觀條件。一個階段系統(tǒng)會存在若干個可能的狀態(tài)。在例7.1中，狀態(tài)就是某階段的出發(fā)位置，它既是該階段某之路的起點，又是前一階段某之路的終點，一個階段有若干個狀態(tài)，第一

6、階段有一個狀態(tài)就是初始位置A，第二階段有三個狀態(tài)，即使集合B1，B2，B3，一般第k階段的狀態(tài)就是第k階段所有始點的集合。描述過程狀態(tài)的變量稱為狀態(tài)變量，常用Sk表示第k階段的所有可能狀態(tài)變量的集合，其元素為sk可以是數(shù)，數(shù)組或向量。如例7.1中第三階段有三個狀態(tài)，則sk可能取三個值，即C1,C2,C3，并且S3=C1，C2，C3 稱為第三階段的可達狀態(tài)集合。（3）決策 決策表示當系統(tǒng)處于某一階段的某個狀態(tài)時，可以作出不同的選擇，確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱為決策變量，常用dk(sk)表示第k階段當狀態(tài)處于sk時的決策變量，它是狀態(tài)變量的函數(shù)。而用Dk (S k) 表

7、示相應的決策變量的函數(shù)集，即有dk (sk)Dk (Sk)。如在例7.1第二階段中，從狀態(tài)B2出發(fā)，其允許決策集合為D2(B2)=C1，C2，C3，某一階段的狀態(tài)變量及決策變量的值取定之后，那么下一階段的狀態(tài)隨之確定。例如選取的點為C2，則C2是狀態(tài)B1在決策d2(B1)作用下的一個新的狀態(tài)，記作d2(B1)= C2，下一階段的狀態(tài)類似地對上階段的狀態(tài)和決策變量的依賴關系可用狀態(tài)轉移方程表示：s k+1=T k (s k，d k (s k) ) (7.1)(4) 策略 由系統(tǒng)各階段確定的決策所形成的決策序列稱為策略。從初始狀態(tài)s1出發(fā)由系統(tǒng)的所有n個階段的決策所形成的策略成為全過程策略，記為：

8、P1，n(s 1)=d 1(s 1)，d 2(s 2)，d n (s n ) (7.2)由系統(tǒng)的第k個階段出發(fā)的后面n k +1個階段的決策過程稱為全過程的后部子過程，相應的策略稱為后部子過程策略，記為P k，n(s k)=d k(s k)，d k+1(s k+1)，d n (s n ) (7.3)所有可供選擇的策略集合稱為策略集合，用P表示，從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉移方程 狀態(tài)轉移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。若給定第k階段狀態(tài)的演變過程，并且若該階段的決策變量dk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1也就完全確定，這種對應關系為：

9、sk+1=Tk (sk ，dk(s k )所描述了由第k個階段到第k+1個階段的狀態(tài)轉移規(guī)律，稱為狀態(tài)轉移方程。Tk 稱為第k階段的狀態(tài)轉移系數(shù)。如例7.1中，狀態(tài)轉移方程為s k+1=d k (s k )(6) 階段收益 系統(tǒng)某一階段的狀態(tài)一經(jīng)確定，執(zhí)行某一決策所得的效益稱為階段效益，它是整個系統(tǒng)總收益的一部份。階段效益是階段狀態(tài)和決策變量的函數(shù)，反映該階段的價值與目標。對第k階段的某一狀態(tài)sk執(zhí)行某一決策d k(s k )的階段效益可用r k(s k ，d k(s k )來表示。在例7.1中的階段效益為走完一段路程所花費的距離。(7) 指標函數(shù)和最優(yōu)值函數(shù) 系統(tǒng)執(zhí)行某一策略所產(chǎn)生效果的優(yōu)劣

10、可用數(shù)量指標來衡量，這樣的數(shù)量指標是整個系統(tǒng)總效益的反映，它是各個階段狀態(tài)和決策的函數(shù)，稱為指標函數(shù)。它是定義在全進程和所有子進程上確定的數(shù)量函數(shù)，記 F k，n(sk, p k，n )，i=n，n-1，1 (7.4)表示從階段k的某一狀態(tài)sk 出發(fā)的后部子進程上的指標函數(shù)，其中pk，n表示從狀態(tài)sk出發(fā)的一個子策略，最優(yōu)策略下指標函數(shù)的指標為最優(yōu)策略指標，記為 (7.5)其中Pk, n表示由狀態(tài)Sk出發(fā)的所有允許子策略集合，“opt”為英文Optimization（最優(yōu)）的縮寫，可以依題意取min或max。由上述指標函數(shù)的定義，可得指標函數(shù)（例7.1的指標函數(shù)注記r k(s k ，d k(s

11、 k )表示第k 階段中點s k 到d k(s k )的距離）。 其中 (7.6)而最優(yōu)策略指標為 (7.7)在例7.1中顯然有 fn+1(sn+1) = 0 (7.8)稱為邊值條件，動態(tài)規(guī)劃的求解對k=n, n-1,1由（7.7）式求最優(yōu)策略指標的過程。一般地對多數(shù)指標函數(shù)的形式?。?.6）式，而最優(yōu)策略指標取形如（7.7）式，以求和形式出現(xiàn)，另一種常用形式是的各階段的指標函數(shù)為乘積，即 (7.9)其相應的最優(yōu)策略指標為 (7.10)對更一般的系統(tǒng)來說，指標函數(shù)未必是求和或乘積形式，但應具有可分離性，并滿足遞推關系，一般具有形式 (7.11) (7.12)在第k階段，指標函數(shù)最優(yōu)策略指標，即

12、最優(yōu)值，稱為最優(yōu)值函數(shù)，即fk(sk)。根據(jù)上述確定的階段編號、狀態(tài)變量、決策變量、狀態(tài)轉移方程以及指標函數(shù)，確定例7.1的最短路線，計算步驟如下：根據(jù)最短路線特性，尋找最短路線的方法，將從最后一段開始，用由后向前逐步遞推的方法，求出各點到E點的最短路線，最后求得由A點到E點的最短路線。所以，動態(tài)規(guī)劃的方向是從各點逐段向始點方向尋找最短路線的一種方法，見圖7.2顯示行進方向1 2 3 4 5始點 終點動態(tài)規(guī)劃尋優(yōu)途徑圖7.2當k= 4時，由D1到終點E只有一條路線，故f4(D1) = 6，同理，f4(D2) = 5。當k= 3時，出發(fā)點有C1、C2、C3三個，若從C1出發(fā)，則有兩個選擇，一是至

13、D1，一是至D2，則其相應的決策為d3(C1)=D1，表示由D1至終點E的最短距離為11，其最短路線是C1D1E。同理，從C2和C3出發(fā)，則有其相應的決策為d3(C2) = D2。且d3(C3) = D3。類似地，可計算當k=2時，有f 2（B1）= 18 d2（B1）= C2f 2（B2）= 19 d2（B2）= C2f 2（B3）= 15 d2（B3）= C2當k=1時，出發(fā)點只有一個A點，則且d1（A）= B1 ，于是獲得從始點A至終點E的最短距離為15。為使找出最短路線，再接計算的順序推之，可求出最優(yōu)決策函數(shù)序列dk，即由d1（A）= B1 ，d2（B1）= C2 ，d3（C2）= D

14、2 ，d4（D2）= E，組成一個最優(yōu)策略。那么最短路線為AB1C2D2E。從上述例7.1的計算過程，可知動態(tài)規(guī)劃的方法比枚舉有以下優(yōu)點：（1）減少計算量，使用枚舉法，要對18條路線比較，即比較運算進行18次，逐階段累計加法為64次。使用動態(tài)規(guī)劃來計算，比較運算為7次，加法運算16次，可見，動態(tài)規(guī)劃方法比窮舉法減少了許多計算量，而且隨著規(guī)模擴大，計算量將大大地減少。（2）豐富了計算結果，雖然枚舉法執(zhí)行了較多的運算，其結果只有從起點A到終點E的一個結果，用動態(tài)規(guī)劃方法以較少的運算不僅得到從A至E的最優(yōu)路線，而且還確定了各中間點到終點E的最優(yōu)路線。7.2 LINGO軟件計算動態(tài)規(guī)劃 使用LINGO

15、軟件計算上述動態(tài)規(guī)劃問題。設：A頂點（城市）1，B12，B23，B34，C15，C26，C37，D18，D29，E點（城市）10。本例使用LINGO程序的編制動態(tài)規(guī)劃模型如下：MODEL:SETS: ! Dynamic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here is our primitive set of ten cities, where F( i) rep

16、resents the shortest path distance from city i to the last city; CITIES /1.10/: F; ! The derived set ROADS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.); ROADS( CITIES, CITIES)/ 1,2 1,3 1,4 2,5 2,6 3,5 3,6

17、 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D( i, j) is the distance from city i to j;ENDSETSDATA: ! Here are the distances that correspond to the above links; D = 5 7 9 9 8 11 7 4 5 10 5 7 6 5 8 11 6 5;ENDDATA! If you are already in City 10, then the cost to travel to City 10 is 0; F( SIZ

18、E( CITIES) = 0;! The following is the classic dynamic programming recursion. In words, the shortest distance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance from j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITI

19、ES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) );END程序第十行，集合CITES表示點，賦值F(i)表示從城市i到最后一個城市的最短距離。第十五行中集合ROADS(,)表示連接城市間的弧，而數(shù)據(jù)D()表示從城市到城市的距離。動態(tài)規(guī)劃的目標函數(shù)，即為從城市到最后城市10的最短距離為所有從城市到城市可達到路加上從到城市10的最短距離的和的最小值。使用SOLVE求解得結果如下，其中F（i）表示第i個（城市）點至最后（城市）終點E的距離。從上述計算過程，可歸納k階段與k+1 階段之間的遞推關系 (7.13)稱為動態(tài)規(guī)劃的基本方程，以及邊值條件為：f

20、 n+1 (sn+1 )=0動態(tài)規(guī)劃方法的基本思想歸納如下：歸納出基本的遞推關系式和恰當?shù)倪呏禇l件，即基本方程。在多階段決策過程中，雖是獨立的階段，但又將當前階段效益和未來效益階段結合起來的一種最優(yōu)化方法。在求解整個系統(tǒng)的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每階段的決策都有該階段的函數(shù)，所以最優(yōu)策略經(jīng)過的各段狀態(tài)，便可逐次變遞推換得到，從而確定了最優(yōu)的路線。 例如，在例7.1中，初始狀態(tài)A已知，上述逐次變換如圖7.3。 d1(A) d2(B1) d4(D2) （已知） A B1 C2 E圖7.3從而可得最優(yōu)策略為d1(A)，d2(B1)，d4(D2)，相應的最短路線為AB1C2D2E，計算過程

21、，使用圖7.4直觀簡明地表示，圖中每節(jié)點處上方的方格內的數(shù)，表示該點到終點E的最短距離，用直線連接點表示該點到終點E的最短路線，未連線的點表示該點到終點E不是最短路線，（舍去），圖中粗線表示由始點A到終點E的最短路線，這種由E點開始從后向前，即從終點至起點求優(yōu)的過程叫做逆推解法，逆推法不僅求出A到E最優(yōu)路線，而且確定了任意點到點E的最優(yōu)路線，如果問題不僅要求確定從點A到點E的最優(yōu)路線，并要求知道A到其它點的最優(yōu)路線，可采用從始端逐步向終端求優(yōu)的順推解法。2318191611101465 B1 C1 D1 A B2 C2 E D2 B3 C3圖7.47.3 順推解法對例7.1來說，順推解法以A為

22、始端，逐階段計算各中間點到A的最優(yōu)路線，直至確定E到A的最優(yōu)路線，用順推法求解時，可以根據(jù)情況對階段重新編號，確定各階段的允許狀態(tài)集合，各狀態(tài)的允許決策集合，狀態(tài)轉移方程，階段效益及指標函數(shù)，如果階段編號，狀態(tài)變量與決策變量取值保持不變，則第k階段的狀態(tài)變量應是sk+1，而不是sk。這由于在順推算法時sk+1成為k階段的“初始狀態(tài)”，而sk成為采取某一決策后的“終止狀態(tài)”。因此，相應的狀態(tài)轉移方程為 (7.14) 它應是逆推算法中狀態(tài)轉移方程的逆變換，其次從初始階段向最后階段過渡的指標函數(shù)與最優(yōu)指標應滿足 (7.15) (7.16)邊值條件為 (7.17) 在例7.1中，若階段編號，狀態(tài)變量與

23、決策變量的定值不變，則順推解法的指標函數(shù)為最優(yōu)指標為在圖7.5中，表示順推過程的圖解，詳細計算不再聱述，每個節(jié)點處上方方格內的數(shù)表示該點到A點的最短距離，用直線連接的點表示該點到始點A的最短路線，粗線表示A到E的最短路線。235791413111918 B1 C1 D1 A B2 C2 E D2 B3 C3圖7.5注意A到D1有兩條最短路，即AB1C1D1，或AB2C3D1。使用LINGO軟件程序編制軟件本例的順推法，只要設E1點（城市），D12，D23，C14，C25，C36，B17，B28，B39，A10點（城市）。計算動態(tài)規(guī)劃（順推法）LINGO程序如下：MODEL:SETS: ! Dy

24、namic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here is our primitive set of ten cities, where F( i) represents the shortest path distance from city i to the last city; CITIES /1.10/: F; ! The derived set ROA

25、DS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.); ROADS( CITIES, CITIES)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10/: D; ! D( i, j) is the distance from city i to j;ENDSETS

26、DATA: ! Here are the distances that correspond to the above links; D = 6 5 5 6 8 7 5 11 9 11 8 7 5 4 10 5 7 9;ENDDATA! If you are already in City 10, then the cost to travel to City 10 is 0; F( SIZE( CITIES) = 0;! The following is the classic dynamic programming recursion. In words, the shortest dis

27、tance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance from j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) );END 詳細解釋參見逆推法，使用SOLVE求解得結果如下，其中F(i）表示第i個點至起點A的距離。 歸納如下，使用動態(tài)規(guī)劃解一個可分階段的多階段決策問題時，必須包含下面步驟。（1）將系統(tǒng)劃分成恰當?shù)碾A段，并編號；（2）確定狀態(tài)變量，狀態(tài)變量集合；（3）確定決策變量，以及允許決策變量集合；（4）建立狀態(tài)轉移方程；（5）確定各階段的階段效益；（6）建立指標函數(shù)；（7）為邊值條件，求最優(yōu)指標并給出相應于最優(yōu)指標的狀態(tài)轉移方程。（8）對k=1,2，n，從最優(yōu)指標的狀態(tài)轉移方程求得最優(yōu)決策。上述求解過程由圖7.6所示，在選擇狀態(tài)變量時應能正確地反映整