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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、點(diǎn)）到達(dá)點(diǎn)n的最短路線的長(zhǎng)度因?yàn)椴豢紤]回路，所以算法的迭代次數(shù)一定不超過(guò)k1 )(ifk 例例7.2 設(shè)點(diǎn)1，2，3，4之間的距離如圖圖7.1所示試用函數(shù)迭代法求各點(diǎn)到點(diǎn)4的最短路線及相應(yīng)的最短距離解：顯然58674 圖7.104840768705650)(44ijcC對(duì)點(diǎn)1，2，3到點(diǎn)4的最短距離計(jì)算過(guò)程如下： k=1時(shí)，f1(i)=ci4，i=1，2，3，即f1(1)=，f1(2)=8，f1(3)=4 ( fk(4)0， ，不必計(jì)算)kk=2時(shí)， ，故)(min)(112jfcifijnj) 1 (10046850min) 1 (12ff，) 2(80847805min) 2(12ff，)

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

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

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