動態(tài)規(guī)劃問題的研究09理學研470920622 王慶權動態(tài)規(guī)劃所研究的對象是多階段決策問題， 所謂多階段決策問題是指一類活動過程， 它可以分為若干個互相聯(lián)系的階段， 在每個階段都需要作出決策。這個決策不僅決定決定這一階段的利益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱之為策略。多階段決策問題就是 求一個策略，使各階段的效益的總和達到最優(yōu)。問題的提出多階段決策問題在日常生活中是經常遇到的，下面舉兩個例子：問題一、最短路徑問題給出一個網絡(如下圖)，從Ao點鋪設一條煤氣管道到A6點，必須經過五個中間站，第一站可以在a,Bi中選擇。類似地，第二、三、四、五站可以在A2,B2,C2,D2、A3,B3,C3、A4，B4，C4、和A5，Bs中選擇。能用管道連接的兩站之間的距離已經給定，兩點之間沒有連線的表示這兩點之間不能鋪設管道。要求選擇一條由 人到Aj鋪設管線，使總距離最短。問題二、多階段資源分配問題設有數(shù)量為x的某種資源，將它投入兩種生產方式 A和B中，以數(shù)量y投入生產方式A，剩下的量投入生產方式B,則可得到收入g(y)?h(x-y)，其中g(y)和h(y)是已知函數(shù)，并且g(0)=h(0)=0。再假設以y與x-y分別投入兩種生產方式A,B后可以回收再生產，回收率分別a與b(0乞a乞1,0乞b乞1)。因此在第一階段生產后回收的總資源為為=ay?b(x-y)。我們再將捲投入生產方式A和b,和第一階段一樣，若以％與為-％分別投入生產方式A和B，則又可得到收入g(y,)h(x^yj，回收資源x2^ay!匕(為-yj。因此，兩個階段的總收入為 g(y)h(^y)-g(yjh(x^yj如果上面的過程進行n個階段，希望選擇y,y1,y2JH,ynJ，使n個階段的總收入最大，則我們的問題就變成：求yy,y2,IH,yn□，使g(y)h(x-y)g(yjh(x“—yj川g(ynj)hg-y.」)達到最大，且滿足條件,=ay+b(x_y)X2=ayi+b(xi_yjJIIIIHIIXn」=ayn/+b(Xn/—%/)[0蘭yWx,oWyi蘭x,i=1,2，川，n—1問題的解決首先，我們來分析一下上面的兩個問題，我們可以將上面的問題描述成如下：有一個系統(tǒng)，可以分成若干個階段，任意階段 k，系統(tǒng)的狀態(tài)可以用兀表示(xk可以是數(shù)量、向量、集合等)。在每一階段k的每一個狀態(tài)Xk都有一個決策集合Qk(xJ，在Qk(xk)中選定一個決策qk?Qk(xk)，狀態(tài)xk就轉移到新的狀態(tài)xk1.=Tk(xk,qk)，并且得到效益R<(xk，qk)。我們的目的就是在每一個階段都在它的決策集合中選擇一個決策， 使所有階段的總效益Rk(xk,qk)達到最大。這樣的多階段決策問題稱為動態(tài)規(guī)劃，它表示是一個k多步最優(yōu)解問題。我們來分析問題一，首先這顯然是一個多決策問題，從 人至人可以分為6個階段。從A出發(fā)到A或B!為第一階段，這時有兩個選擇：走到A或者走到B。若我們選擇走到A的決策，則A就是下一階段的起始點。在下一階段，我們從 A點出發(fā)，有一個可供選擇的決策集合｛A,B2,C2｝，很明顯，前面各階段的決策如何選擇，直接影響著其余各階段的行進路線，我們的目的就是在每個階段選擇一個決策，使它們決定的總路程最短。下面我們來球此問題的最短路線，并以此來說明處理多階段決策問題的基本思想一一最優(yōu)化原理。先引入一下幾個符號：令n表示由某點至終點A6之間的階段數(shù)。例如A0至A是6個階段，令s表示在任一階段所處的狀態(tài)，s稱為狀態(tài)變量，例如在第三階段的開始點是a2，則稱所處的狀態(tài)為 。令Xn（S）為決策變量，它表示當狀態(tài)處于S，還有n個階段時所選擇的一個決策。 令fn（S）表示現(xiàn)在處在狀態(tài)s還有n個階段時，由s至終點A的最短距離。令d（s,Xn）表示s點到點焉的距離。我們從最后一個階段開始計算并逐步推移至 A0點。由定義，訊人）表示由A至A的最短距離。故人（人）=4，同理fi（B5）=3?，F(xiàn)計算最后兩個階段，n=2,若從A出發(fā)，則有兩個選擇，一是至A，一是至B5，所以f2（A0=min{d（A4,A5）仏陽小代泯）￡假）}=min{34,53}=7這說明由A至終點Ae的最短距離是乙其最短路線是A4—A^—Ae.X2（A4）=A5。如果從b4出發(fā)，則f2（B4）=min{d（B4，A5）仏人）8厲也）「d）}=min{54,23}=5X2（B4）=B5，最短路線是B4>B5>A6，最短路程是5。同理我們可得f2G）=min{dGA）fi（A）,d（C4,B5）fid）}=min{64,63}=9X2（C4）=B5，最短路線是C4>B5>Ae，最短路程是9?，F(xiàn)在討論n=3的情況，我們分別以A3,B3,C3為出發(fā)點來計算。f3（A3）=min{d（A3，A』彳乂⑴“他也）f??』}=min{27,25^7X3（Aj）=B4，最短路線是A3rB4—B5—As，最短路程是7。上式表示由A出發(fā)有兩種選擇，到A或b4，如果選A，那么到達A以后，一定要走a4到A6的最短路線；如果這一步選 B4，那么到達B4以后，一定走B4到A最短路線。所以A>A的最短路線就是這兩條中較短的一條。同理f3（B3）=min{d（B3,B4）fzQ）}=min{15,29}=6X3（BJ=B4，最短路線是B3>B4>B5、A，最短路程是6。f3（C3）=min{d（C3,B4）f2（B4）,dG,C4）f2（C4）}=min{35,39^8X3（C3）=B4，最短路線是C3>B4>B5、A，最短路程是&n=4的情況完全類似，我們可以得到門心仏人)73(陽戍宀尼)n{67,86}=13x4(A)二A同理f4(B2)=10,X4(B2)=A.f4(C2)=9,X4(C2)=B3.f4(D2)=12,X4(D2)當n=5時，有人啟兩點，在A處有3個決策A2,B>,C2供選擇，如果選擇A2，那么從A出發(fā)一定是走由A到A6的最短路線；同樣，如果選擇B2，那么從B2點以后一定是走由B2到A的最短路線；選C2點也是如此，所以只要在這三條路線中選一條最短路線， 就是A到A6的最短路線。f5(A)=min{d(AA)f4(A),d(A,B2)f/BjaAO f/C?)}-min{2 13,310,69}=13x5(A)=B2，最短路線是AtB2tAtB4tB5tA，同樣f5(BJ=min{d(B1,B2)f^),d(B,G)彳心^宀口)f^)}=min{810,79,1612}=16X^BJ=C2，最短路線是BrC2rB^B4rB5rA。當n=6時，出發(fā)點只有一個A點，有兩種選擇，因此f6(Ao)=min{d(Ao,A)f5(A),d(Ao,BJf5(BJ}=min{513,1316}=18鳳(人)=A至此，上圖的最短路線已經求得，為 A)>A,>B2-A^-B4—?Bs—?A。從上面的計算過程，我們可以看出，在求解的各個階段，我們利用了n階段的最優(yōu)值與n-1階段的最優(yōu)值之間的如下關系 ：fn(s)=min{d(s,Xn(s))fn4(Xn(s))},n=2,3|||6,￡(s)=d(s,As)最優(yōu)化原理動態(tài)規(guī)劃就是根據(jù)上述遞推關系求得問題的解的， 這種遞推關系是根據(jù)動態(tài)規(guī)劃的最優(yōu)化原理而推到出來的。我們給出動態(tài)規(guī)劃最優(yōu)化原理的描述一個過程的最優(yōu)策略具有這樣的性質，即無論其初始狀態(tài)及其出事決策如何，其以后諸決策對以第一個決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構成最優(yōu)策略。動態(tài)規(guī)劃最優(yōu)化原理的直接解釋：如下圖，如果I ----n是從A到C的最優(yōu)路線，那么路線n—定是從B到C的最優(yōu)路線，這是很容易用反證法來證明的。如果n不是從 B到C的最優(yōu)路線。 n'是比n好的從B到C的路線，那么I--n就是比1----n更好的從a到C的路線，這與I---n是最優(yōu)路線矛盾。下面我們利用動態(tài)規(guī)劃最優(yōu)化原理給出問題二多資源分配問題的遞推公式令fk(x)表示有資源，再進行k個階段生產并采取最優(yōu)分配策略后得到的最大總收入。當k=1時，f,x)二max{g(y)?h(x-y)}，當k=2時，由于前一個階段分別以 y、x-y投0應蘭入A、B,生產以后可以回收％=ay，b(x-y)作為下一階段開始時可以投入生產的資源數(shù)量，若采取最優(yōu)方式投入生產，由最優(yōu)化原理，后一個階段的收入是 f'xj，所以f2(x)=max{g(y)h(x-y)fi(ayb(x-y))}0空空對任意的k，2乞k乞n，同樣的分析可得fk(x)=嬲汝9(丫)h(x-y)fk」(ayb(x-y))}因此，我們得到遞推關系如下：f1(x^r^a)<{g(y)h(x-y)}fk(x) h(x-y)f」ayb(x-y))},k一2從對階段決策問題的數(shù)學模型可以看到， 一個多階段決策過程的極值函數(shù)可以看作是過程的初始狀態(tài)與階段數(shù)目的函數(shù)。 任意給定一個決策序列， 如果是最優(yōu)的，那么從后面最后k階段開始，對由這個策略形成的后面k階段的初始狀態(tài)組成的k階段問題而言，這個策略的后面的k個決策一定是這個 k階段問題的最優(yōu)策略，與這 k階段以前的決策無關。木蘭辭：唧唧復唧唧，木蘭當戶織。不聞機杼聲，惟聞女嘆息。問女何所思，問女何所憶。女亦無所思，女亦無所憶。昨夜見軍帖，可汗大點兵，軍書十二卷，卷卷有爺名。阿爺無大兒,木蘭無長兄。愿為市鞍馬，從此替爺征。愿為市鞍馬，從此替爺征。-東市買駿馬，西市買鞍鞘，南市買轡頭，北市買長鞭。旦辭爺娘去，暮宿黃河邊，不聞爺娘喚女聲，但聞黃河流水鳴濺濺。旦辭黃河去,暮至黑山頭，不聞爺娘喚女聲，但聞