最優(yōu)控制.動(dòng)態(tài)規(guī)劃(1)

1、動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃是解決多級(jí)決策過程最優(yōu)化的一種數(shù)學(xué)方法。所謂多級(jí)決策過程，是指把一個(gè)過程分為若干個(gè)階段，而每一個(gè)階段都需作出決策，以便使整個(gè)過程取得最優(yōu)的效果。 最短路線問題問題: 要求從A地到F地，選擇一條最短的線路。A1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957為了便于分析，引入幾個(gè)符號(hào)： N：從某點(diǎn)到終點(diǎn)之間的級(jí)數(shù)；x：表示在任一級(jí)所處的位置，稱為狀態(tài)變量；SN (x)：決策變量，表示當(dāng)處于狀態(tài)x，還有N級(jí)時(shí)，所選取的下一個(gè)點(diǎn)； WN(x)：表示從狀態(tài)x到終點(diǎn)F的N級(jí)過程的最短距離； d(x, SN)：表示從狀態(tài)x到點(diǎn)SN的距離。

2、從最后一級(jí)開始計(jì)算： 2322231133212222211222212221111122111)(, 72519min)(),()(),(min)()(, 72916min)(),()(),(min)()(, 42214min)(),()(),(min)(2)(1)(EDSEWEDdEWEDdDWEDSEWEDdEWEDdDWEDSEWEDdEWEDdDWEWEWA1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957從哪下手？ SN (x)：決策變量，表示當(dāng)處于狀態(tài)x，還有N級(jí)時(shí)，所選取的下一個(gè)點(diǎn)； WN(x)：表示從狀態(tài)x到終點(diǎn)F的N級(jí)過程的最

3、短距離； 同理 255234341242411414133332232311313)(,14)()(,12)()(, 9)()(,14)()(, 8)()(,11)()(, 5)(BASAWCBSBWCBSBWCBSBWDCSCWDCSCWDCSCW所以，最短路線為 FEDCBA2112最短距離為14 一個(gè)N級(jí)最優(yōu)過程，不管第一級(jí)決策如何，其余N-1級(jí)，決策過程至少必須依據(jù)第一級(jí)決策所形成的狀態(tài)組成一個(gè)N-1級(jí)最優(yōu)過程，在此基礎(chǔ)上，在選擇第一級(jí)決策，使總的N級(jí)過程為最優(yōu)。 A1B2B3B1C2C3C1D2D3D1E2EF12345678965411354524244957這種遞推關(guān)系可以用下列

4、遞推方程式來表達(dá)： ),()()()(,min)(11)(FxdxWxSWxSxdxWNNNxSNN是不是窮舉法？ 再看一個(gè)例子最短時(shí)間問題最短時(shí)間問題問題：設(shè)有人要從 A 點(diǎn)開車到 E 站，中間要經(jīng)過任意三個(gè)中間站，站名在圖中圓圈內(nèi)表示。站與站之間稱為段，每段路程所需時(shí)間（小時(shí)）標(biāo)在段上?，F(xiàn)要問，這人應(yīng)如何選擇路線才能最快到達(dá)目的地？1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5()1()4(2最短時(shí)間的到由EB1什么是窮舉法? 從 走到 一共有六條路線，每條路線由四段組成。這六條路線和對(duì)應(yīng)的行車時(shí)間如下AE 路 線 行車時(shí)間（小時(shí)） 13 11

5、14 13 12 9EDCAB232EDCAB222EDCAB122111AB C D EEDCAB121EDCAB221顯然最優(yōu)路線是 ，它所花時(shí)間為9小時(shí)。 EDCAB2211C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5()1()4(2最短時(shí)間的到由EB1 這里每條路線由四段組成，也可以說是四級(jí)決策。 為了計(jì)算每條路線所花時(shí)間，要做三次加法運(yùn)算，為了計(jì)算六條路線所花的時(shí)間要作36=18次運(yùn)算。這種方法稱為“窮舉法”。 顯然當(dāng)段數(shù)很多時(shí)，計(jì)算量是很大的。這種方法的特點(diǎn)是從起點(diǎn)站往前進(jìn)行，而且把這四級(jí)決策一起考慮。應(yīng)注意從到 下一站 所花的時(shí)間為1，

6、而到 所花時(shí)間為3，但最優(yōu)路線卻不經(jīng)過 。 這說明只看下一步的“眼前利益眼前利益”來作決策是沒有意義的。A2B1B2B為將問題表達(dá)得清楚，引進(jìn)下面的術(shù)語（寫法并不完全一樣）。令 表示由某點(diǎn) 到終點(diǎn)的段數(shù)（如 到 為2段， 。nE2CE令 表示當(dāng)前所處點(diǎn)的位置（如 ），稱為狀態(tài)變量。x12,A B C對(duì)比一下最開始的例子2n 令 為決策（控制）決策（控制）變量，它表示當(dāng)處在 位置而還有 段要走時(shí)，所要選取的下一點(diǎn)。例如，從 出發(fā)，下一點(diǎn)為 時(shí)，則表示為 。)(xunxn2C2D222)(DCu令 表示在位置 ，向終點(diǎn)還有 段要走時(shí)，由 到終點(diǎn) 的最短時(shí)間。例如，從C2到E的最短時(shí)間為4，可表示為

7、T2(C2)=4。)(xTnxnxE令 表示從點(diǎn) 到點(diǎn) 的時(shí)間。例如，從 到 的時(shí)間為),(nnuxtx)(xun2C2D3),(22DCnt有了這些術(shù)語后，就可用動(dòng)態(tài)規(guī)劃來解這個(gè)例子。從最后一段出發(fā)進(jìn)行計(jì)算，并將計(jì)算出的最短時(shí)間 用括號(hào)表示在相應(yīng)的點(diǎn) 處（見圖6-1）。)(xTnx n=1 （倒數(shù)第一段） 考慮從 和 到 的路線，由定義可知，最短時(shí)間分別為1D2DE1112()5; () 1T DT D1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短時(shí)間的到由EB1n=2（倒數(shù)第二段）考慮從 到 的路線。 12211122,2

8、212(,)( )2 5minmin4(,)()3 1D Dt C DT DT Ct C DT D由 到 有兩種路線： ， 。兩種路線中的最短時(shí)間由下式確定：123,C C C2CEEDC12EDC22E最優(yōu)決策為 。222DCu1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短時(shí)間的到由EB1由 到 只有一種路線 ，其時(shí)間為1CEEDC1165112CT由 到E也只有一種路線 ，其時(shí)間為 3C51432CTEDC231C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短

9、時(shí)間的到由EB11C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短時(shí)間的到由EB1n=3（倒數(shù)第三段） 從B2到E有兩種路線： 和 ECB32ECB2264264min)(),()(),(min22211211,1321CTCBtCTCBtBTCC最優(yōu)決策213)(CBu最短時(shí)間為：n=4（倒數(shù)第四段） 從A到E的路線有兩種： 和 。EAB1EAB21C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短時(shí)間的到由EB1 910163min)(),()(),(min2321

10、31,421BTBAtBTBAtATBB最優(yōu)決策為 14)(BAu 至此求出了A到E的最短時(shí)間為9，最優(yōu)路線為 。在圖中用粗線表示。這里，為決定最優(yōu)路線進(jìn)行了10次加法，比窮舉法的18次少了8次。當(dāng)段數(shù)n更多時(shí)，節(jié)省計(jì)算將會(huì)更多。EDCAB2211C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5() 1 ()4(2最短時(shí)間的到由EB1 以上面的最短時(shí)間問題為例，如把 當(dāng)作初始狀態(tài)，則余下的決策 對(duì) 來講是最優(yōu)策略；如把 當(dāng)初始狀態(tài)，則余下的決策 對(duì) 來講也構(gòu)成最優(yōu)策略。一般來說，如果一個(gè)最優(yōu)過程用狀態(tài) 來表示，最優(yōu)決策為 ，則對(duì)狀態(tài) 來講， 必定是最優(yōu)的

11、，這可用圖6-2來表示。2C22C D E2C1BEDCB2211BNxxx,10110,Nuuukx11,Nkkuuu1kN0 x1x01kxkxNx0u1ku最優(yōu)解圖6-2 最優(yōu)性原理示意圖動(dòng)態(tài)規(guī)劃的特點(diǎn)： 一是它從最后一級(jí)反向計(jì)算；二是其將一個(gè)N級(jí)決策問題化為N個(gè)單級(jí)決策問題。好處：將一個(gè)復(fù)雜問題化為多個(gè)簡(jiǎn)單問題加以求解。最優(yōu)性原理最優(yōu)性原理貝爾曼的最優(yōu)性原理可敘述如下：“一個(gè)多級(jí)決策問題的最優(yōu)決策具有這樣的性質(zhì)：當(dāng)把其中任何一級(jí)及其狀態(tài)作為初始級(jí)和初始狀態(tài)時(shí)，則不管初始狀態(tài)是什么，達(dá)到這個(gè)初始狀態(tài)的決策是什么，余下的決策對(duì)此初始狀態(tài)必定構(gòu)成最優(yōu)策略?！痹诙鄶?shù)實(shí)際問題中， 級(jí)決策的性能指

12、標(biāo) 取如下形式NJ10,NkkkNuxFJ 是由某級(jí)狀態(tài)和決策決定的性能函數(shù)，要求尋找決策 使J取極小值 。( , )F 110,Nuuu*NJ最優(yōu)性原理可表示為 *1001111,00111100,*),(min),(),(min),(min),(),(),(min011010NuNNuuuNNuuNJuxFuxFuxFuxFuxFuxFuxFJNN根據(jù)上式就可證明最優(yōu)性原理的正確性。若以 為初態(tài)時(shí)，余下的決策 不是最優(yōu)的，那么就存在另一決策序列 所決定的指標(biāo)值 ，于是1x11,Nuu11,Nuu *11NNJJ100*100*),(min),(min00NuNNuNJuxFJJuxFJ這與

13、 是極小值發(fā)生矛盾，所以余下的決策必須是最優(yōu)的。*NJ6-2 離散最優(yōu)控制問題設(shè)控制系統(tǒng)的狀態(tài)方程為) 1, 1 , 0()(),() 1(Nkkukxfkx式中x(k)是k時(shí)刻的幾維狀態(tài)向量，u(k)是k時(shí)刻的p維容許控制向量，設(shè)系統(tǒng)在每一步轉(zhuǎn)移中的性能指標(biāo)為Fx(k),u(k) 如在u(0)的作用下)0(),0()0()0(),0() 1 (1uxFxJuxfx在u(1)的作用下)1 (),1 ()0(),0()0()1 (),1 ()2(2uxFuxFxJuxfx對(duì)N級(jí)決策過程)1(),1()()1 (),1 ()2()0(),0() 1 (NuNxfNxuxfxuxfx性能指標(biāo)10)(

14、),()1(),1()1 (),1 ()0(),0()0(NkNkukxFNuNxFuxFuxFxJ要求選擇控制序列 ) 1(,),1 (),0(Nuuu使性能指標(biāo)達(dá)到極小 根據(jù)最優(yōu)性原理 ) 1, 2 , 1() 1(),1()()() 1(),1(min) 1() 1 ()0(),0(min)0(*)1(*1*1)0(*NjjujxfjxjxJjujxFjxJxJuxFxJjNjujNNuN解上述遞推方程，即可獲得最優(yōu)控制序列。例6-1 設(shè)一階離散系統(tǒng)的狀態(tài)方程為 ) 1, 1 , 0()()() 1(Nkkukxkx初始條件為x(0)，控制變量u不受約束，性能指標(biāo)為1022)(21)(2

15、1NkkuNcxJ求最優(yōu)控制u*(t)，使J達(dá)最小，為簡(jiǎn)便起見，設(shè)N2 解 設(shè)在u(0)、u(1)作用下，系統(tǒng)狀態(tài)為x(0)、x(1)、x(2) 先考慮從x(1)到x(2)的情況，控制為u(1)cxxcxcJccxuuuxcuJuuxcucxxJ1) 1 ()2(1) 1 (211) 1 () 1 (0) 1 () 1 () 1 (0) 1 (21) 1 () 1 (21) 1 (21)2(21) 1 (2*11122221，再考慮從x(0)到x(1)的情況，控制為u(0)0(211) 1 ()21 (2)0(21)0()0(0)0()0()0(121)0(21)0() 1 (121)0(21

16、min)0(21min)0(2*2222222)0(*12)0(*2xccxccxJccxuuJuxccuxJxccuJuxJuu最優(yōu)控制序列為 ccxuccxu21)0() 1 (,21)0()0(*最優(yōu)性能指標(biāo)為 )21 (2)0(2*ccxJ 連續(xù)系統(tǒng)的動(dòng)態(tài)規(guī)劃連續(xù)系統(tǒng)的動(dòng)態(tài)規(guī)劃設(shè)系統(tǒng)的狀態(tài)方程和性能指標(biāo)為 ),(UXtfX 00)(XtXfttffdttUXFttXJ0),(),( （6-19） （6-20） 受約束，可寫成 為某一閉集。要尋找滿足此約束且使 最小的最優(yōu)控制 。U,UJU 設(shè)時(shí)間 在區(qū)間 內(nèi)，則根據(jù)最優(yōu)性原理，從 到 這一段過程應(yīng)當(dāng)是最優(yōu)過程。把這段最優(yōu)指標(biāo)寫成 ,則t

17、,0ftttft),(tXVdUXFttXtXJtXVfttffu),(),(min),(),(（6-21）顯然 滿足終端條件),(tXVffffttXttXV),(),(通常假定 對(duì) 及 的二階偏導(dǎo)數(shù)存在且有界。),(tXVXt現(xiàn)在，考慮系統(tǒng)從 出發(fā)，到 分兩步走：先從 到 ，再 從到 ， 是小量，則ttftttttfttttttttffufdUXFdUXFttXtXV),(),(),(min),(（6-23）根據(jù)最優(yōu)性原理，從 也應(yīng)是最優(yōu)過程。 fttt到因 故,)(tXXttXftttffudUXFttXtttXXV),(, )(min),(這樣，式（6-23）可寫成)( 0),(),(

18、min),(),(min),(2tttVXXVtXVttUXFtttXXVttUXFtXVTuu（6-24）注意到 ，上式右邊括號(hào)中 表示最優(yōu)指標(biāo)，其中 為最優(yōu)控制，不需再選擇， 也與 選擇無關(guān)。故ttUXftXX),(),(tXVUttVU2(, )min(, )(, )(, )0()TuVVV X tF X U ttf X U ttV X tttXt 從上式兩端消去 ，除以 ，再令 ，可得),(tXVt0tmin(, )(, )TuVVF X U tfX U ttX （6-25）引用以前使用過的哈密頓函數(shù) ),(),(),(tUXftUXFtUXHT （6-26） XV （6-27）則（6

19、-25）可寫成 ),(),(mintXVUXHtXVUXHtVu （6-28）（6-25）或（6-28）稱為哈密頓雅可比貝爾曼方程，邊界條件是：哈密頓雅可比貝爾曼方程在理論上很有價(jià)值，但它是 的一階偏微分方程并帶有取極小的運(yùn)算，因此求解是非常困難的，一般情況得不到解析解，只能用計(jì)算機(jī)求數(shù)值解。對(duì)于線性二次問題，可以得到解析解，而且求解結(jié)果與用極小值原理或變分法所得結(jié)果相同。這時(shí)，哈密頓雅可比貝爾曼方程可歸結(jié)為黎卡提方程。在實(shí)際計(jì)算線性二次問題時(shí)，一般用直接求解黎卡提方程來求最優(yōu)控制。),(tXVffffttXttXV),(),(例6-3 設(shè)系統(tǒng)狀態(tài)方程為 uxxx221,初始狀態(tài) )(, 0)

20、0(, 1)0(21tuxx不受約束，性能指標(biāo)為 dtuxJ0221)212(求最優(yōu)控制u*(t)，使性能指標(biāo)J為最小。解 222112*21( , , )220 xVVVH x utxuuxxxHVuux 由于2212121minmin 22uuVVVVHxuxuttxx，因?yàn)橄到y(tǒng)是時(shí)不變的，并且性能指標(biāo)的被積函數(shù)不是時(shí)間的顯函數(shù)，故0Vt解 222112*21( , , )220 xVVVH x utxuuxxxHVuux 由于2212121minmin 22uuVVVVHxuxuttxx，因?yàn)橄到y(tǒng)是時(shí)不變的，并且性能指標(biāo)的被積函數(shù)不是時(shí)間的顯函數(shù)，故0Vt解得221122*122( )2

21、2( )22V xxx xxVu txxx 2212121202VVxxxx引用以前使用過的哈密頓函數(shù) ),(),(),(tUXftUXFtUXHT （6-26） XV （6-27）則（6-25）可寫成 ),(),(mintXVUXHtXVUXHtVu （6-28）思考題 HJB方程與極小值原理的區(qū)別和聯(lián)系？動(dòng)態(tài)規(guī)劃與極小值原理動(dòng)態(tài)規(guī)劃與極小值原理動(dòng)態(tài)規(guī)劃和極小值原理是最優(yōu)控制理論的兩大基石，它們都可以解決有約束的最優(yōu)控制問題，雖然在形式上和解題方法上不同，但卻存在著內(nèi)在的聯(lián)系。下面我們從動(dòng)態(tài)規(guī)劃來推演極小值原理，不過要說明這種推演是基于最優(yōu)指標(biāo)對(duì)和兩次連續(xù)可微這個(gè)條件的。 最優(yōu)性能指標(biāo)與狀態(tài)

22、方程為),(tUXfX 00)(XtX（6-29）要求確定U(t)使性能指標(biāo)fttffdttUXFttXJ0),(),( （6-30）極小。其中， 固定， 自由， 可以有約束，也可以沒有。ftt ,0)(ftXU1、 （狀態(tài)方程） （6-31）HX2、 （協(xié)態(tài)方程） （6-32）XH3、 （邊界方程） （6-33）00)(XtX4、 （橫截條件） （6-34）)()(fftXt5、 （極值條件） （6-35）),(),(mintUXHtUXHu用動(dòng)態(tài)規(guī)劃求解的結(jié)果已在上節(jié)中得到，現(xiàn)在歸納一下：在動(dòng)態(tài)規(guī)劃中協(xié)態(tài)變量 滿足XV哈密頓雅可比貝爾曼方程（6-28）本身說明了哈密頓函數(shù)在最優(yōu)控制上取極值的條件，故等同于上面極小值原理所得的條件5，不過（6-28）還多給出了一點(diǎn)信息，即 。tVH下面由動(dòng)態(tài)規(guī)劃法來推出協(xié)態(tài)方程。 由dtdxXXtXVXtXVtXtXVdtddtdT),(),(),(2XV（6-27）因假設(shè)對(duì)兩次連續(xù)可微，因此上式成立，且可交換求導(dǎo)次序，得XHfXVFXXfXVXFtUXfXXtXVtUXfXVtUXFXtUXfXXtXVttXVXTTTTT)()(),(),(),()(),(),(),(),(22即協(xié)態(tài)方程（因都是最優(yōu)解條件。故省去*號(hào)。由（6-22）和（6-27）再來推橫截條件)(),()(