動态規劃數學描述

首先，例舉一個典型的且很直覺的多階段決策問題:

[例] 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A->E。試用動态規劃的最優化原理求出A->E的最省費用。

如圖從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點A和終點E外，其它各點既是上一階段的終點又是下一階段的起點。例如從A到B的第一階段中，A為起點，終點有B1，B2，B3三個，因而這時走的路線有三個選擇，一是走到B1，一是走到B2，一是走到B3。若選擇B2的決策，B2就是第一階段在我們決策之下的結果，它既是第一階段路線的終點，又是第二階段路線的始點。在第二階段，再從B2點出發，對于B2點就有一個可供選擇的終點集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點，同時又是第三階段的始點。同理遞推下去，可看到各個階段的決策不同，線路就不同。很明顯，當某階段的起點給定時，它直接影響着後面各階段的行進路線和整個路線的長短，而後面各階段的路線的發展不受這點以前各階段的影響。故此問題的要求是：在各個階段選取一個恰

當的決策，使由這些決策組成的一個決策序列所決定的一條路線，其總路程最短。

動态規劃為此類多階段決策問題尋求了一種簡便的方法。為了便于讨論，我們先引入動态規劃問題的一些概念、術語和符号。

名詞解釋：

（1）決策和階段

在對問題的進行中作出某種選擇性的行動就是決策。例如在且點需選擇下一步到B1還是到B2，這就是一次決策。一個實際問題可能要有多次決策或多個決策點，為此對整個問題，可按其特點劃分成需要作出選擇的若幹輪次，這些輪次即稱為階段。如圖中，從A到E共分為4個階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。

（2）狀态和狀态變量

某一階段的出發位置稱為狀态。通常一個階段包含若幹狀态。例如階段3含有3種狀态C1，C2，C3。狀态通常可有一個變量來描述，用來描述狀态的變量稱為狀态變量，記第K階段的狀态變量為Uk。例如U3={C1，C2，C3}。

（3）決策變量和允許決策集合

在每一個階段中都需有一次決策，決策也可以用一個變量來描述，稱這種變量為決策變量，一般用Xk表示第K階段的決策變量。在實際問題中，決策變量的取值往往限制在某一個範圍之内，此範圍稱為允許決策集合，用Sk表示第K階段的允許決策集合。例如，S3={D1，D2}，它表示第三階段可有兩種不同的決策。那麼Xk與Sk

之間的關系是UK+1=Xk（Uk）。當第K階段的狀态确定之後，可能作出的決策範圍還要受到這一狀态的影響，這就是說，決策變量Xk是狀态變量Uk的函數，記為Xk（Uk），簡記為Xk。把Xk的取值範圍記為Sk(Uk)，顯然有Xk(Uk)∈Sk(Uk)。

例如在圖的第三階段中，若從狀态C1出發，就可作出二種不同的決策，其允許決策集合S3(C1)={D1，D2}。若選取的點是D2，則D2是狀态C1在決策X3(C1)作用下的下個新的狀态，記作X3(C1)=D2。

（4）政策和最優政策

所有階段依次排列構成問題的全過程。全過程中各階段決策變量Xk(Uk)所組成的有序總體稱為政策。在實際問題中，可供選擇的政策有一定的範圍，該範圍稱為允許政策集合P。從P中找出最優效果的政策稱為最優政策。

（5）狀态轉移方程

前一階段的終點就是後一階段的起點，前一階段的決策變量就是後一階段的狀态變量，這種關系描述了由K階段到K十1階段狀态的演變規律，稱為狀态轉移方程。如上圖的狀态轉移方程為UK+1=Xk（Uk）。

（6）動态規劃的函數基本方程

為了幫助大家了解動态規劃的基本思想，先說最短路線的一個重要特性：如果從A->B->C->D是A至D的最短路線，那麼從B到D的最短路線必是B->C->D。更一般地說:如果最短路線在第K階段通過Pk，則由點Pk出發到達終點的這條路線對于從Pk出發到達終點的所有可能選擇的不同路線來說，必定也是最短路線。

這就引出了從終點逐段向始點方向尋找最短路線的一種方法：

若以Uk表示第K階段的一個決策點，從終點開始，依逆向求出倒數第一階段、倒數第二階段、倒數第三階段、……、倒數第N-1階段中各點到達終點的最短路線。最終求出從起點到終點的最短路線。這就是動态規劃的基本思想。

下面，我們按照動态規劃的方法将上例從最後一段開始計算，由終點E向前逐漸倒推至起點A。

設Uk表示第K階段的一個決策點，Fk（Uk）表示從第K階段中的點Uk到達終點的最短路線的長度，Sk（Xk，Uk）表示第K階段中Xk到Uk的距離。

（當K=5時，F5（E）=0）

當K=4時，F4（D1）=5，F4（D2）=2。

當K=3時，

F3（C1）=min[S3（C1，D1）+F4（D1），S3（C1，D2）+F4（D2）]=min[8，11]=8。

F3（C2）=min[S3（C2，D1）+F4（D1），S3（C2，D2）+F4（D2）]=min[7，11]=7。

F3（C3）=min[S3（C3，D2）+F4（D2）]=min[12]=12。

當K=2時，

F2（B1）=min[S2（B1，C1）+F3（C1），S2（B1，C2）+F3（C2）]=min[20，21]=20。

F2（B2）=min[S2（B2，C1）+F3（C1），S2（B2，C2）+F3（C2），S2（B2，C3）+F3（C3）]

            =min[14，17，16]=14。

F2（B3）=min[S2（B3，C1）+F3（C1），S2（B3，C2）+F3（C2），S2（B3，C3）+F3（C3）]

            =min[21，19，23]=19。

當K=1時，

F1（A）=min[S1（A，B1）+F2（B1），S1（A，B2）+F2（B2），S1（A，B3）+F2（B3）]

            =min[22，19，20]=19。

其中X1（A）=B2，X2（B2）=C1，X3（C1）=D1，X4（D1）=E 組成一個最優政策。路線  A->B2->C1->D1->E  為從A到E的最短路線。最短路線長19。

從上面的計算過程中，我們可以看出，在求解的各個階段，我們利用了K階段與K+1階段之間的如下關系：

     Fk（ Uk）=min[Sk（Uk，Xk）+Fk+1（Xk）]       k=4，3，2，1

     F5（ U5）=0

這種遞推關系，叫做動态規劃的函數基本方程。

動态規劃的最優化原理是“作為整個過程的最優政策具有這樣的性質:無論過去的狀态和決策如何，對前面的決策所形成的狀态而言，餘下的諸決策必須構成最優政策。”

與窮舉法相比，動态規劃的方法有兩個明顯的優點:

(1)大大減少了計算量

(2)豐富了計算結果

從上例的求解結果中，我們不僅得到由A點出發到終點E的最短路線及最短距離，而且還得到了從所有各中間點到終點的最短路線及最短距離，這對許多實際問題來講是很有用的。

動态規劃的最優化概念是在一定條件下，我到一種途徑，在對各階段的效益經過按問題具體性質所确定的運算以後，使得全過程的總效益達到最優。