《系統(tǒng)工程》課件第05章 動態(tài)規(guī)劃

第5章

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

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

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

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

的路徑距離，表示從第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動態(tài)規(guī)劃的基本概念和基本方程5.2.1動態(tài)規(guī)劃的基本概念

（1）階段和階段變量用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當?shù)貏澐殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示。階段的劃分一般是根據(jù)時間和空間的自然特征來定的，一般要便于把問題轉(zhuǎn)化成多階段決策的過程。14:1714:17

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

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

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

5.2.2動態(tài)規(guī)劃的基本思想和基本方程14:17

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

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

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

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

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

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

當k=3時，有

當k=2時，有

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

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

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

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

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

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

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

1）動態(tài)規(guī)劃的基本思想14:17

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

5.3.1最優(yōu)性原理14:17

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

5.3.2最優(yōu)性定理14:17

證明略去（5-4）5.4動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系14:17

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

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

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

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

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

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

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

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

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

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

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