第七章動態(tài)規(guī)劃

1、第七章第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法，它將多階段決策問題轉化成一系列比較簡單的最優(yōu)化問題動態(tài)規(guī)劃首先將復雜的問題分解才相互關聯(lián)的若干階段，每一個階段都是一個最優(yōu)化子問題，然后逐階段的決策，當所有階段決策都確定了，整個問題的決策也就確定了動態(tài)規(guī)劃中階段可以用時間表示，這就是“動態(tài)”的含義當然，對于與時間無關的一些靜態(tài)問題也可以人為地引入“時間”轉化成動態(tài)問題7.1 動態(tài)規(guī)劃基本原理動態(tài)規(guī)劃基本原理 一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念 動態(tài)規(guī)劃中所涉及到的概念有階段、狀態(tài)、決策與策略、狀態(tài)轉移、指標函數(shù) (1)階段 將所給問題的過程，按時間或空

2、間特征分解成若干互相聯(lián)系的階段，以便按順序去求每階段的解，常用字母k表示階段變量 (2)狀態(tài) 各階段開始時的客觀條件叫做狀態(tài)描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合稱為狀態(tài)集合，用Sk表示 動態(tài)規(guī)劃中的狀態(tài)必須具有無后效性，即當某階段狀態(tài)給定以后，在這階段以后過程的發(fā)展不受這段以前各段狀態(tài)的影響也就是說，當前的狀態(tài)是過去歷史的一個完整總結，過程的過去歷史只能通過當前狀態(tài)去影響它未來的發(fā)展 (3)決策和策略 當各段的狀態(tài)取定以后，就可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策表示決策的變量，稱為決策變量，常用uk(sk)表

3、示第k階段當狀態(tài)為sk時的決策變量在實際問題中，決策變量的取值往往限制在一定范圍內，稱此范圍為允許決策集合，常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，即uk(sk)Dk(sk) 一個按順序排列的決策組成的集合稱為策略一個n階段決策過程，從第k階段到第n階段的過程稱為問題的一個后部子過程，或k子過程由k子過程的每一階段的決策按順序排列組成的策略序列稱為k子策略，記為pk，n(sk)，即 pk，n(sk)= uk(sk)， uk+1(sk+1)， uk+2 (sk+2)，un(sn) 當k=1時，p1，n(s1)就是全過程的一個策略 對每個實際問題，其k子過程可供選擇的策略有一定范

4、圍，稱為允許策略集合，記作Pk，n，使整個問題達到最優(yōu)效果的策略就是最優(yōu)策略 (4)狀態(tài)轉移方程 動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結果如果給定了第k階段的狀態(tài)sk，本階段決策為uk，則第k+l階段的狀態(tài)sk+1也就完全確定，它們的關系可用公式 sk+lTk(sk，uk) 表示該公式表示了由第k階段到第k+l階段的狀態(tài)轉移規(guī)律，所以稱為狀態(tài)轉移方程 (5)指標函數(shù) 用于衡量所選定策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)，它是定義在全過程或則子過程上的數(shù)量函數(shù)，是各階段的狀態(tài)和決策變量的函數(shù)它分為階段指標函數(shù)和過程指標函數(shù)兩種階段指標函數(shù)是指第k階段狀態(tài)sk采取決策uk時的效益，用d

5、k (sk，uk)表示過程指標函數(shù)指在第k階段狀態(tài)為sk采用策略pk，n時，后部子過程的收益，用Vk，n(sk，pk，n)表示Vk，n(sk，pk，n)與dk(sk，uk)之間的關系常見的有求和型和乘積型兩種： 或nkjjjjnkknkusdpsV)()(,，nkjjjjnkknkusdpsV)()(,， 最優(yōu)指標函數(shù)表示從第k階段狀態(tài)sk采用最優(yōu)策略到過程終止時的最佳效益值，記為fk(sk)fk(sk)與Vk，n(sk，pk，n)間的關系為 式中opt表示最優(yōu)化，根據(jù)具體問題表示為max或min 當k=1時，f1(s1)就是從初始狀態(tài)s1到全過程結束的整體最優(yōu)函數(shù))()()(,*,nkknk

6、PpnkknkkkpsVoptpsVsfnknk， 二、動態(tài)規(guī)劃的基本方程二、動態(tài)規(guī)劃的基本方程 動態(tài)規(guī)劃方法基于貝爾曼(R.Bellman)提出的最優(yōu)化原理：一個過程的最優(yōu)策略具有這種性質，即不管先前的狀態(tài)和決策如何，余下的所有決策必構成的最優(yōu)子策略 最優(yōu)性原理是動態(tài)規(guī)劃理論的核心這個原理說明，最優(yōu)策略的任一后部子策略也是最優(yōu)的根據(jù)這個原理，在求解多階段決策問題時，前面的各狀態(tài)和決策，對其后面的子問題來說，只不過相當于其初始條件而已，并不影響后面過程的最優(yōu)決策因此，可以把多階段決策問題求解過程表示成一個連續(xù)的遞推過程，由后向前逐步計算這要利用第k階段與第k+1階段之間的關系，通常如下：)()

7、(11)()()(1111邊界條件，已知，csfnnksfusdoptsfnnkkkkkukkK或邊界條件，已知，)()(11)()()(1111csfnnksfusdoptsfnnkkkkkukkk該方程稱為動態(tài)規(guī)劃的基本方程 三、動態(tài)規(guī)劃的求解方法三、動態(tài)規(guī)劃的求解方法 動態(tài)規(guī)劃的求解有兩種基本方法：逆序解法(后向動態(tài)規(guī)劃方法)、順序解法(前向動態(tài)規(guī)劃方法)當尋優(yōu)的方向與多階段決策過程的實際行進方向相反，從最后一段開始計算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法與之相反，順序解法的尋優(yōu)方向與過程的行進方向相同，計算時從第一段開始逐段向后遞推，計算后一階段要用到前一階段的求優(yōu)結果，最后一

8、段計算的結果就是全過程的最優(yōu)結果一般而言，如果已知過程的初始狀態(tài) ，則用逆序解法；如果已知過程的終止狀態(tài) ，則用順序解法這兩種方法除了尋優(yōu)方向不同外，狀態(tài)轉移方程、指標函數(shù)的定義和基本方程形式一般也有差異，但并無本質上的區(qū)別下面主要介紹逆序解法 1s1ns設已知初始狀態(tài)為 1s 第 階段：指標函數(shù)的最優(yōu)值 此為一維極值問題，不妨設有最優(yōu)解 ，于是可有最優(yōu)值 n),()()(nnnsDxnnusvoptsfnnn)(nnnsuu )(nnsf 第 階段：類似地有其中*表示“+”或“”， ，可解得最優(yōu)解 ，于是最優(yōu)值為 1n)(*),()(111)(11111nnnnnsDxnnsfusVopts

9、fnnn)(111nnnnusTs，)(111nnnsuu)(11nnsf 不妨設第k+1階段的最優(yōu)解為 和最優(yōu)值，則對于第 階段有)(111kkksuu)(11kksfk)(*)()(11)(kkkkksDxkksfusVoptsfkkk，其中 ，可解得最優(yōu)解 和最優(yōu)值為 )(1kkkkusTs，)(kkksuu )(kksf 依此類推，直到第1階段，有，其中 ，可解得最優(yōu)解 和最優(yōu)值為 )(*)()(22111)(11111sfusVoptsfsDx，)(1112usTs，)(111suu )(11sf 由于已知 ，則可知u1與 從而可知，按上面的過程反推回去，即可得到每一階段和全過程的最

10、優(yōu)決策1s)(11sf)(2222sfus，例7.1 求解下面的優(yōu)化問題，321010. .294)(max3212321ixxxxtsxxxXfi 解 這是一個靜態(tài)問題，為了應用動態(tài)規(guī)劃，先人為的賦予它“階段”的概念首先考慮x1的取值，然后考慮x2的取值，x3的取值，這樣就將原問題劃分為3個階段，下面的關鍵是如何選擇狀態(tài)變量，使各后部子過程之間具有遞推關系 通?？梢园褯Q策變量uk定義為原靜態(tài)問題中的變量xk，即uk=xk (k=1，2，3)狀態(tài)變量一般為累計量或隨遞推過程變化的量這里可以把個階段的決策變量的最大可能取值定為狀態(tài)變量sk，初始狀態(tài)s1=10這樣就有k=1時，s1=10，u1=x

11、1；k=2時，s2= s1u1，u2=x2；k=1時，s3= s2u2，u3=x3 狀態(tài)轉移方程為sk+1= skuk，指標函數(shù)為 其中，基本方程為33 ,),(kiiiikusdV11114),(uusd22229),(uusd233332),(uusd，0)(123)(),(max)(44110sfksfusdsfkkkkksukkkk當k=3時， ，顯 然 2max)(2303333usfsu 3*3su 當k=2時， )(29max)(9max)(222203320222222ususfusfsusu由高等數(shù)學知識可得 2/92s時， 2*2*20suu 或則時， ； 時， 2/92s

12、0*2u2/92s2*2su當k=1時 ， )(4max)(22101111sfusfsu當 時， ，2*2su 2229)(ssf) 0(90959max)( 94max)10(*1111100111100111usususufuu但是 與 矛盾，所以舍去；10*121uss2/92s當 時， 0*2u22222)(ssf)10(24max)10(21110011uufu由高等數(shù)學知識可得 0*1u200)10(1f由狀態(tài)轉移方程順推，得 ，顯然應取 10*121uss0*2u，所以 10*223uss，而 103*3 su所以最優(yōu)解為 TTTuuuxxx，1000321321200maxz

13、7.2動態(tài)規(guī)劃迭代算法動態(tài)規(guī)劃迭代算法 上節(jié)的多階段決策問題可以確定出階段的數(shù)目，稱為固定階段的多階段決策問題本節(jié)要討論的是階段數(shù)不固定的有限階段決策過程及其求解方法 考慮如下的最短路問題假設有n個點：1，2，n，任意兩點i與j之間的距離(或行程時間，運費等)為cij，0cij+cij=0表示i與j為同點，cij表示兩點間無通路由點直接到另一點算作一步要求在不限定步數(shù)的條件下，找出點l到點n的最短路線 我們把類似上述不限定數(shù)的有限階段決策問題柿為階段數(shù)不固定的有限階段決策過程在解此問題時可以不考慮回路，因為含有回路的路線一定不是最短路 設f (i) 表示由點i到點n的最短距離，則由貝爾曼最優(yōu)性

14、原理，得，0)(121)(min)(1nfnijfcifijnj 這就是上述問題的動態(tài)規(guī)劃函數(shù)的基本方程它是關于最優(yōu)值函數(shù)的函數(shù)方程，而不是遞推關系式這給求解帶來一定的困難下面介紹求解的兩種逐次逼近方法一、函數(shù)迭代法一、函數(shù)迭代法 函數(shù)迭代法的基本思想是構造一個函數(shù)序列來逼近最優(yōu)值函數(shù) 首先令k=1，)(ifk)(if，0)(121)(11nfnicifin然后構造 ，0)(121)(min)(111nfnijfcifkkijnjk當 時，就取 niififkk，21)()(1niififk，21)()(否則令k=k+1再按上式迭代計算 的意義十分直觀，表示由i點出發(fā)，至多走k步（即經過k1個

15、點）到達點n的最短路線的長度因為不考慮回路，所以算法的迭代次數(shù)一定不超過k1 )(ifk 例例7.2 設點1，2，3，4之間的距離如圖圖7.1所示試用函數(shù)迭代法求各點到點4的最短路線及相應的最短距離解：顯然58674 圖7.104840768705650)(44ijcC對點1，2，3到點4的最短距離計算過程如下： k=1時，f1(i)=ci4，i=1，2，3，即f1(1)=，f1(2)=8，f1(3)=4 ( fk(4)0， ，不必計算)kk=2時， ，故)(min)(112jfcifijnj) 1 (10046850min) 1 (12ff，) 2(80847805min) 2(12ff，)

16、 3 (40440876min) 3 (12ff，k=3時， ，故)(min)(213jfcifijnj) 1 (1004685100min) 1 (23ff，)2(8084780105min)2(23ff，) 3(4044087106min) 3(23ff， 因此，f2(i)就是點i到點4的最短距離點1到點4的最短距離為 ，最段路線為134類似可得點2，3到4的最短距離分別為8，4，最短路線分別為24，34)3()(min)1(113112fcjfcfijnj二、策略迭代法二、策略迭代法 策略迭代法的思想是先選取一個初始策略，然后調整得到新的策略，當策略不在發(fā)生改變的時候就得到最優(yōu)策略具體計

17、算過程如下： 首先，任意選擇一個初始策略 ，令k=1；121)(1niiu，然后，計算函數(shù)值，0)(121)()()(,nfniiufcifkkkiuikk并確定新策略 ，新策略滿足:)(1iuk)(min)(11jfciufkijjkk 最后，如果對 ，則 為最優(yōu)策略，否則令k=k+1，再按上式迭代計算)()(1iuiuikk，)(iuk 策略迭代法每次迭代包括求值和改善策略兩步，要比函數(shù)迭代法復雜，計算量也大但是策略迭代法所需的迭代次數(shù)往往少于函數(shù)迭代法，特別是當初始策略選取較好時例例7.3 用策略迭代法求解例7.2解：設初始策略為 4 , 2 , 4 , 3)(11iuu 計算在策略u1

18、下的由點i到點4的路程f1(i)，i=1，2，3 ( fk(4)0， 不必計算)k808)4()2(1141fcf1587)2()3(1121fcf21156) 3() 1 (1131fcf計算指標函數(shù)值f2(i)并確定新的策略u2， in)(min) 1 (112jfcfjj，)1(2)1(12uu，80815780215min)(min)2(122jfcfjj，)2(4)2(12uu，40415087216min)(min)3(132jfcfjj)3(4)3(12uu計算指標函數(shù)值f3(i)并確定新的策略u3，1004685130min)(min) 1 (213jfcfjj) 1 (3) 1 (23uu，8084780135min)(min)2(223jfcfjj)2(4)2(23uu，4044087136min)(min)3(233jfcfjj)3(4)3(23uu計算指標函數(shù)值f4(i)并確定新的策略u4，1004685100min)(min) 1 (314jfcfjj) 1 (3) 1 (34uu，8084780105min)(min)2(324jfcfjj)2(4)2(34uu，4044087106min)(min)3(334jf