第5章

動態規劃5.1多階段決策過程及實例5.2動態規劃的基本概念和基本方程5.3動態規劃的最優性原理和最優性定理5.4動態規劃和靜態規劃的關系14:17【知識點聚焦】

本章主要介紹動態規劃的狀態轉移方程、指標函數、最優值函數、最優策略、最優軌線等基本知識。重點要求學生掌握動態規劃的順序解法、逆序解法；最后，介紹最短路線、資源分配、生產計劃、貨物存儲、可靠性問題、背包問題、推銷商問題及其解法等。并且簡介多維動態規劃降維方法、減少離散狀態點數方法及隨機性問題的動態規劃求解方法。5.1多階段決策過程及實例

多目標問題最早是Franklin在1772年提出來的，1938年Cournot提出了多目標問題的經濟學模型，1896年Pareto首次從數學的角度提出多目標最優化問題。當今，多目標規劃也受到了人們的普遍重視。

在工農業生產中，常常需要考慮某些限制條件下，多個目標的最優化問題。下面舉例說明：14:175.1多階段決策過程及實例多階段決策：將決策的全過程依據時間或空間劃分為若干個互相聯系的階段；并做出方案的選擇，稱之為多階段決策。策略：各個階段所確定的決策就構成一個決策序列，常稱之為策略。策略集合：許多可供選擇的策略集合，稱之為允許策略集合（簡稱策略集合）。最優策略：在允許策略集合中，選擇一個策略，使預定的目標達到最好的效果。稱為最優策略。這類問題就稱為多階段決策問題。在多階段決策問題中，各個階段采取的決策一般來說是與時間有關的，故有“動態”的含義，因此把處理這類問題的方法稱為動態規劃方法。但有一些與時間因素沒有關系的所謂“靜態問題”。只要人為地引進“時間”因素，也可以把它視為多階段決策問題，而用動態規劃方法去處理。14:17舉例【例5-1】最短路徑問題。圖5-1中是一個城市分布地圖，圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數值代表道路的長度。現在，想從城市A到達城市E，怎樣走路程最短，最短路程的長度是多少?圖5-1最短路徑問題14:17【分析】把從A到E的全過程分成四個階段，用k表示階段變量，第1階段有一個初始狀態A，兩條可供選擇的支路ABl、AB2；第2階段有兩個初始狀態B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用表示在第k階段由初始狀態到下階段的初始狀態

的路徑距離，表示從第k階段的到終點E的最短距離，利用倒推方法求解A到E的最短距離。具體計算過程如下：14:17因此由A點到E點的全過程的最短路徑為A→B2→C4→D3→E。最短路程長度為13。(4-1)14:17因此由A點到E點的全過程的最短路徑為A→B2→C4→D3→E。最短路程長度為13。(4-1)14:175.2動態規劃的基本概念和基本方程5.2.1動態規劃的基本概念

（1）階段和階段變量用動態規劃求解一個問題時，需要將問題的全過程恰當地劃分成若干個相互聯系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示。階段的劃分一般是根據時間和空間的自然特征來定的，一般要便于把問題轉化成多階段決策的過程。14:1714:17

（2）狀態和狀態變量某一階段的出發位置稱為狀態，通常一個階段包含若干狀態。狀態通過一個變量來描述，這個變量稱為狀態變量。狀態表示的是事物的性質。（3）決策、決策變量對問題的處理中做出某種選擇性的行動就是決策。一個實際問題可能要有多次決策和多個決策點，在每一個階段中都需要有一次決策。決策也可以用一個變量來描述，稱為決策變量。在實際問題中，決策變量的取值往往限制在某一個范圍之內，此范圍稱為允許決策集合。14:17

（4）策略和最優策略所有階段依次排列構成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實際問題中，從決策允許集合中找出最優效果的策略稱為最優策略。（5）狀態轉移方程前一階段的終點就是后一階段的起點，前一階段的決策變量就是后一階段的狀態變量，這種關系描述了由K階段到K+1階段狀態的演變規律，是關于兩個相鄰階段狀態的方程，稱為狀態轉移方程，是動態規劃的核心。（6）指標函數和最優化概念用來衡量多階段決策過程優劣的一種數量指標，稱為指標函數。它應該在全過程和所有子過程中有定義、并且可度量。指標函數的最優值，稱為最優值函數。14:17

1）動態規劃的基本思想動態規劃是一類解決多階段決策問題的數學方法。在工程技術、科學管理、工農業生產及軍事等領域都有廣泛的應用。在理論上，動態規劃是求解這類問題全局最優解的一種有效方法，特別是對于實際中的某些非線性規劃問題可能是最優解的唯一方法。然而，動態規劃僅僅是解決多階段決策問題的一種方法或者說是考察問題的一種途徑，而不是一種具體的算法。就目前而言，動態規劃沒有統一的標準模型，其解法也沒有標準算法，在實際應用中，需要具體問題具體分析。動態規劃模型的求解是影響動態規劃理論和方法應用的關鍵問題所在，而子問題的求解和大量結果的存儲、調用更是一個難點所在。然而，隨著計算技術的快速發展，特別是內存容量和計算速度的增加，使求解較小規模的動態規劃問題成為可能，從而使得動態規劃的理論和方法在實際中的應用更加廣泛。

5.2.2動態規劃的基本思想和基本方程14:17

2）動態規劃步驟動態規劃算法的關鍵在于正確地寫出基本的遞推關系式和恰當的邊界條件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯系的階段，恰當的選取狀態變量和決策變量及定義最優值函數，從而把一個大問題轉化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐步遞推尋優，在每一個子問題的求解中，均利用了它前面的子問題的最優化結果，依次進行，最后一個子問題所得的最優解就是整個問題的最優解。14:17

3）動態規劃的基本方程最短路問題例：給定一個線路網絡，如圖5-2所示，兩點之間連線上的數字表示兩點間的距離（或費用），試求一條由A到G的鋪管路線，使總距離為最短（或總費用為最小）。圖5-2鋪管線路圖14:17

最短路線有一個重要特征：如果由起點A經過P點和H點而到達終點G是一條最短路線，則由點P出發經過H點到達終點G的這條子路線，對于從點P出發到達終點的所有可能選擇的不同路線來說，必定也是最短路線。例如，在最短路線問題中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最短路線，則D1→E2→F2→G應該是由D出發到G點的所有可能選擇的不同路線中的最短路線。14:17

證明：（反證法）如果不是這樣，則從點P到G點有另一條距離更短的路線存在，把它和原來最短路線由A點到達P點的那部分連接起來，就會得到一條由A點到G點的新路線，它比原來那條最短路線的距離還要短些。這與假設矛盾，是不可能的。根據最短路線這一特性，尋找最短路線的方法就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到G點的最短路線，最后求得由A點到G點的最短路線。所以，動態規劃的方法是從終點逐段向始點方向尋找最短路線。將從最后一段開始計算，由后向前逐步推移至A點，如圖5-3所示。14:17

當k=6時，由F1到終點G只有一條路線，故f6(F1)＝4。同理，f6(F2)＝3；當k=5時，出發點有E1、E2、E3三個。若從E1出發，則有兩個選擇①至F1，②至F2，則

且，當k=4時，有14:17

當k=3時，有

當k=2時，有

當k=1時，出發點有一個A點，則14:17

且，于是得到從起點A到終點G的最短距離為18。為了找出最短路線，再按計算的順序反推之，可求出最優決策函數序列｛Uk｝，即由逆序的方法得到了問題的答案。從上面的計算過程中可以看出，在求解的各個階段，利用了k階段與k+1階段之間的遞推關系：

一般情況，k階段與k+1階段的遞推關系式可寫成14:17

邊界條件為。遞推關系式（5-1）稱為動態規劃的基本方程。下面考慮動態規劃基本方程：設指標函數是取各階段指標的和的形式，即

一般情況，k階段與k+1階段的遞推關系式可寫成（5-1）14:17

其中，表示第j段的指標。它顯然是滿足指標函數三個性質的。所以上式可寫成

當初始狀態給定時，過程的策略就被確定，則指標函數也就確定了，因此，指標函數是初始狀態和策略的函數，可記為14:17

1）動態規劃的基本思想14:17

20世紀50年代，Bellman等人在研究具有無后效性的多階段決策問題的基礎上，提出了最優性原理：“作為整個過程的最優策略具有這樣的性質：不管該最優策略上某狀態以前的狀態和決策如何，對該狀態而言，余下的諸決策必構成最優子策略。”即最優策略的任一后部子策略都是最優的。5.3動態規劃的最優性原理和最優性定理

5.3.1最優性原理14:17

對很多多階段決策問題，在最優策略存在的前提下，根據最優性原理及具體問題可導出基本方程，再由這個方程求解最優策略.從而得到了該多階段決策問題的圓滿結果。但是后來在動態規劃的某些應用過程中發現，最優性原理不是對任何決策過程普遍成立，它與基本方程不是無條件等價，而最優性原理只是最優性定理的必要條件.

5.3.2最優性定理14:17

證明略去（5-4）5.4動態規劃和靜態規劃的關系14:17

與靜態規劃相比，動態規劃的優越性在于：（1）能夠得到全局最優解。由于約束條件確定的約束集合往往很復雜，即使指標函數較簡單，用非線性規劃方法也很難求出全局最優解。而動態規劃方法把全過程化為一系列結構相似的子問題，每個子問題的變量個數大大減少，約束集合也簡單得多，易于得到全局最優解。特別是對于約束集合、狀態轉移和指標函數不能用分析形式給出的優化問題，可以對每個子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對于這類問題，動態規劃通常是求全局最優解的唯一方法。5.4動態規劃和靜態規劃的關系14:17

（2）可以得到一族最優解。與非線性規劃只能得到全過程的一個最優解不同，動態規劃得到的是全過程及所有后部子過程的各個狀態的一族最優解。有些實際問題需要這樣的解族，即使不需要，它們在分析最優策略和最優值對于狀態的穩定性時也是很有用的。當最優策略由于某些原因不能實現時，這樣的解族可以用來尋找次優策略。（3）能夠利用經驗提高求解效率。如果實際問題本身就是動態的，由于動態規劃方法反映了過程逐段演變的前后聯系和動態特征，在計算中可以利用實際知識和經驗提高求解效率。如在策略迭代法中，實際經驗能夠幫助選擇較好的初始策略，提高收斂速度。14:17

動態規劃的主要缺點是：（1）沒有統一的標準模型，也沒有構造模型的通用方法，甚至還沒有判斷一個問題能否構造動態規劃模型的準則。這樣就只能對每類問題進行具體分析，構造具體的模型。對于較復雜的問題在選擇狀態、決策、確定狀態轉移規律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應用上的局限性。（2）用數值方法求解時存在維數災。若一維狀態變量有m個取值，那么對于n維問題，狀態x_k就有mn個值，對于每個狀態值都要計算、存儲函數f_k(x_k)，對于n稍大的實際問題的計算往往是不現實的。目前還沒有克服維數災難的有效方法。5.4.1逆推解法14:17

設已知初始狀態為s1，第k階段的初始狀態為sk，并假定最優值函數fk(sk)表示使從k階段到n階段所得到的最大效益。從第n階段開始，則有5.4.1逆推解法其中Dn(sn)是由狀態sn所確定的第n階段的允許決策集合。解此一維極值問題，就得到最優解xn(sn)和最優值fn(sn)。(注意：若Dn(sn)只有一個決策，則xn∈Dn(sn)就應寫成xn=xn(sn)。在第n-1階段，有14:17其中sk+1=Tk(sk,xk),解得最優解xk=xk(sk)和最優值fk(sk).如此類推，直到第一階段，有

其中sn=Tn-1(sn-1,xn-1),解此一維極值問題，得到最優解xn-1=xn-1(sn-1)和最優值fn-1(sn-1)在第k階段，有14:17

其中s2=T1(s1,x1)，解得最優解x1=x1(s1)和最優值f1(s1).由于初始狀態s1可知，故x1=x1(s1)和f1(s1)是確定的，從而s2=T1(s1,x1)也就可確定，于是x2=x2(s2)和f2(s2)也就可以確定。這樣，按照上述遞推過程相反的順序推算下去，就可逐步確定確定出每階段的決策及效益。【例5-2】用逆推解法求解下列問題14:17

解：按問題的變量個數劃分階段，把它看作為一個三階段決策問題。設狀態變量為s1，s2，s3，s4，并記s1=c,取問題中的變量x1、x2、x3為決策變量；各階段指標函數按乘積方式結合。令最優值函數fk(sk)表示為第k階段的初始狀態為sk，從k階段到3階段所得到的最大值。設14:17

解：按問題的變量個數劃分階段，把它看作為一個三階段決策問題。設狀態變量為s1，s2，s3，s4，并記s1=c,取問題中的變量x1、x2、x3為決策變量；各階段指標函數按乘積方式結合。令最優值函數fk(sk)表示為第k階段的初始狀態為sk，從k階段到3階段所得到的最大值。設14:17

解：按問題的變量個數劃分階段，把它看作為一個三階段決策問題。設狀態變量為s1，s2，s3，s4，并記s1=c,取問題中的變量x1、x2、x3為決策變量；各階段指標函數按乘積方式結合。令最優值函數fk(sk)表示為第k階段的初始狀態為sk，從k階段到3階段所得到的最大值。設14:17

設已知終止狀態Sn+1，并假定最優值函數fk(s)，是以s為k階段的結束狀態，從1階段到k階段所獲得的最大效益。已知終止狀態用順推方法與已知初始狀態用逆推方法本質上是沒有區別的。假定狀態變換5.4.1逆推解法的逆推變換為首先，第一階段開始，求出14:17

解：按問題的變量個數劃分階段，把它看作為一個三階段決策問題。設狀態變量為s1，s2，s3，s4，并記s1=c,取問題中的變量x1、x2、x3為決策變量；各階段指標函數按乘積方式結合。令最優值函數f