最優(yōu)控制第七章動態(tài)規(guī)劃法

最優(yōu)控制第七章動態(tài)規(guī)劃法第一頁，共六十八頁，2022年，8月28日動態(tài)規(guī)劃是貝爾曼在50年代作為多段決策過程研究出來的，現(xiàn)已在許多技術(shù)領(lǐng)域中獲得廣泛應(yīng)用。動態(tài)規(guī)劃是一種分段最優(yōu)化方法，它既可用來求解約束條件下的函數(shù)極值問題，也可用于求解約束條件下的泛函極值問題。它與極小值原理一樣，是處理控制矢量被限制在一定閉集內(nèi)，求解最優(yōu)控制問題的有效數(shù)學(xué)方法之一。第二頁，共六十八頁，2022年，8月28日動態(tài)最優(yōu)的核心是最優(yōu)性原理，它首先將一個(gè)多段決策問題轉(zhuǎn)化為一系列單段決策問題，然后從最后一段狀態(tài)開始逆向遞推到初始段狀態(tài)為止的一套求解最優(yōu)策略的完整方法。下面先介紹動態(tài)規(guī)劃的基本概念，然后討論連續(xù)型動態(tài)規(guī)劃。第三頁，共六十八頁，2022年，8月28日一、多段決策問題動態(tài)規(guī)劃是解決多段決策過程優(yōu)化問題的一種強(qiáng)有力的工具。所謂多段決策過程，是指把一個(gè)過程按時(shí)間或空間順序分為若干段，然后給每一步作出“決策”(或控制)，以使整個(gè)過程取得最優(yōu)的效果。第四頁，共六十八頁，2022年，8月28日如圖1所示，對于中間的任意一段，例如第k+1段作出相應(yīng)的“決策”(或控制)uk后，才能確定該段輸入狀態(tài)與輸出狀態(tài)間的關(guān)系，即從xk變化到xk+1的狀態(tài)轉(zhuǎn)移規(guī)律。在選擇好每一段的“決策”(或控制)uk以后，那么整個(gè)過程的狀態(tài)轉(zhuǎn)移規(guī)律從x0經(jīng)xk一直到xN也就被完全確定。全部“決策”的總體，稱為“策略”。

第五頁，共六十八頁，2022年，8月28日當(dāng)然，如果對每一段的決策都是按照使某種性能指標(biāo)為最優(yōu)的原則作出的，那么這就是一個(gè)多段最優(yōu)決策過程。圖1多段決策過程示意圖第六頁，共六十八頁，2022年，8月28日容易理解，在多段決策過程中，每一段(如第k+1段)的輸出狀態(tài)(xk+1)都僅僅與該段的決策(uk)及該段的初始狀態(tài)(xk)有關(guān)。而與其前面各段的決策及狀態(tài)的轉(zhuǎn)移規(guī)律無關(guān)。這種性質(zhì)稱為無后效性。下面以最優(yōu)路線問題為例，來討論動態(tài)規(guī)劃求解多段決策問題。第七頁，共六十八頁，2022年，8月28日設(shè)汽車從A城出發(fā)到B城，途中需穿越三條河流，它們各有兩座橋P、Q可供選擇通過，如圖2所示。各段間的行車時(shí)間(或里程、費(fèi)用等)已標(biāo)注在相應(yīng)段旁。問題是要確定一條最優(yōu)行駛路線，使從A城出發(fā)到B城的行車時(shí)間最短。第八頁，共六十八頁，2022年，8月28日第九頁，共六十八頁，2022年，8月28日現(xiàn)將A到B分成四段，每一段都要作一最優(yōu)決策，使總過程時(shí)間為最短。所以這是一個(gè)多段最優(yōu)決策問題。由圖2可知，所有可能的行車路線共有8條。如果將各條路線所需的時(shí)間都一一計(jì)算出來，并作一比較，便可求得最優(yōu)路線是AQ1P2Q3B，歷時(shí)12。這種一一計(jì)算的方法稱為窮舉算法。這種方法計(jì)算量大，如本例就要做3×23=24次加法和7次比較。如果決策一個(gè)n段過程，則共需(n-1)2n-1次加法和(2n-1-1)次比較。可見隨著段數(shù)的增多，計(jì)算量將急劇增加。第十頁，共六十八頁，2022年，8月28日應(yīng)用動態(tài)規(guī)劃法可使計(jì)算量減少許多。動態(tài)規(guī)劃法遵循一個(gè)最優(yōu)化原則：即所選擇的最優(yōu)路線必須保證其后部子路線是最優(yōu)的。例如在圖2中，如果AQ1P2Q3B是最優(yōu)路線，那么從這條路線上任一中間點(diǎn)到終點(diǎn)之間的一段路線必定也是最優(yōu)的。否則AQ1P2Q3B就不能是最優(yōu)路線了。第十一頁，共六十八頁，2022年，8月28日根據(jù)這一原則，求解最優(yōu)路線問題，最好的辦法就是從終點(diǎn)開始，按時(shí)間最短為目標(biāo)，逐段向前逆推。依次計(jì)算出各站至終點(diǎn)之間的時(shí)間最優(yōu)值，并據(jù)此決策出每一站的最優(yōu)路線。如在圖2中，從終點(diǎn)B開始逆推。第十二頁，共六十八頁，2022年，8月28日最后一段(第四段)：終點(diǎn)B的前站是P3或Q3，不論汽車先從哪一站始發(fā)，行駛路線如何，在這最后一段，總不外乎是從P3到B，歷時(shí)為4，或從Q3到B，歷時(shí)為2，將其標(biāo)明在圖3中相應(yīng)的圓圈內(nèi)。比較P3與Q3這一最后一段最優(yōu)決策為Q3B。第十三頁，共六十八頁，2022年，8月28日最后一段(第四段)：終點(diǎn)B的前站是P3或Q3，不論汽車先從哪一站始發(fā)，行駛路線如何，在這最后一段，總不外乎是從P3到B，歷時(shí)為4，或從Q3到B，歷時(shí)為2，將其標(biāo)明在圖3中相應(yīng)的圓圈內(nèi)。比較P3與Q3這一最后一段最優(yōu)決策為Q3B。第十四頁，共六十八頁，2022年，8月28日第三段：P3、Q3的前站是P2、Q2。在這一段也不論其先后的情況如何，只需對從P2或Q2到B進(jìn)行最優(yōu)決策。從P2到B有兩條路線：P2P3B，歷時(shí)為6；P2Q3B，歷時(shí)為4，取最短歷時(shí)4，標(biāo)注在P2旁。從Q2到B也有兩條路線：Q2P3B，歷時(shí)為7；Q2Q3B，歷時(shí)為5，取最短歷時(shí)5，標(biāo)注在Q2旁。比較P2與Q2的最優(yōu)值，可知這一段的最優(yōu)路線是P2Q3B。第十五頁，共六十八頁，2022年，8月28日第二段：P2、Q2的前站是P1、Q1。同樣不管汽車是如何到達(dá)的P1、Q1，重要的是保證從P1或Q1到B要構(gòu)成最優(yōu)路線。從P1到B的兩條路線中，P1P2Q3B，歷時(shí)為11；P1Q2Q3B，歷時(shí)為11，取最短歷時(shí)11，標(biāo)注在P1旁。從Q1到B的也有兩條路線中，Q1P2Q3B，歷時(shí)為8；Q1Q2Q3B，歷時(shí)為13，取最短歷時(shí)8，標(biāo)注在Q1旁。比較P1與Q1的最優(yōu)值，可知這一段的最優(yōu)路線是Q1P2Q3B。第十六頁，共六十八頁，2022年，8月28日第一段：P1、Q1的前站是始發(fā)站A。顯見從A到B的最優(yōu)值為12，故得最優(yōu)路線為AQ1P2Q3B。第十七頁，共六十八頁，2022年，8月28日綜上可見，動態(tài)規(guī)劃法的特點(diǎn)是：1)與窮舉算法相比，可使計(jì)算量大大減少。如上述最優(yōu)路線問題，用動態(tài)規(guī)劃法只須做10次加法和6次比較。如果過程為n段，則需做加法。以上例為例，用窮舉法需作4608次加法，而后者只需做34次加法。第十八頁，共六十八頁，2022年，8月28日2)最優(yōu)路線的整體決策是從終點(diǎn)開始，采用逆推方法，通過計(jì)算、比較各段性能指標(biāo)，逐段決策逐步延伸完成的。全部最優(yōu)路線的形成過程已充分表達(dá)在圖3中。從最后一段開始，通過比較P3、Q3，得到Q3B；倒數(shù)第二段，通過比較P2、Q2，得到P2Q3B；倒數(shù)第三段，通過比較P1、Q1，得到最優(yōu)決策為Q1P2Q3B；直至最后形成最優(yōu)路線AQ1P2Q3B。象這樣將一個(gè)多段決策問題轉(zhuǎn)化為多個(gè)單段決策的簡單問題來處理，正是動態(tài)規(guī)劃法的重要特點(diǎn)之一。第十九頁，共六十八頁，2022年，8月28日3)動態(tài)規(guī)劃法體現(xiàn)了多段最優(yōu)決策的一個(gè)重要規(guī)律，即所謂最優(yōu)性原理。它是動態(tài)規(guī)劃的理論基礎(chǔ)。第二十頁，共六十八頁，2022年，8月28日對圖4所示的N段決策過程，如果在第k+1段處把全過程看成前k段子過程和后N-k段子過程兩部分。對于后部子過程來說，xk可看作是由x0及前k段初始決策(或控制)u0,u1,…,uk-1所形成的初始狀態(tài)。那么，多段決策的最優(yōu)決策略具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何，其余(后段)決策(或控制)對于由初始決策所形成的狀態(tài)來說，必定也是一個(gè)最優(yōu)策略。這個(gè)性質(zhì)稱為最優(yōu)性原理。第二十一頁，共六十八頁，2022年，8月28日圖4N段決策過程第二十二頁，共六十八頁，2022年，8月28日設(shè)圖5中x*(t)是連續(xù)系統(tǒng)的一條最優(yōu)軌線。x(t1)是最優(yōu)軌線上的一點(diǎn)，那么最優(yōu)性原理說明，不管t=t1,t0<t1<tf時(shí)，系統(tǒng)是怎樣轉(zhuǎn)移到狀態(tài)x(t1)的，但從x(t1)到x(tf)這段軌線必定是最優(yōu)的。因?yàn)樽顑?yōu)軌線的后一段從x(t1)到x(tf)如果還有另一條軌線是最優(yōu)的話，那么原來從x(t0)到x(tf)的軌線就不是最優(yōu)的，這與假設(shè)矛盾。因此，最優(yōu)性原理成立。第二十三頁，共六十八頁，2022年，8月28日應(yīng)用最優(yōu)性原理可以將一個(gè)N段最優(yōu)決策問題轉(zhuǎn)化為N個(gè)一段最優(yōu)決策問題，從而大大減少求解最優(yōu)決策問題的計(jì)算量。圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程第二十四頁，共六十八頁，2022年，8月28日圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程第二十五頁，共六十八頁，2022年，8月28日二、連續(xù)系統(tǒng)的動態(tài)規(guī)劃利用動態(tài)規(guī)劃最優(yōu)性原理，可以推導(dǎo)出性能泛函為極小應(yīng)滿足的條件——哈密爾頓－雅可比方程。它是動態(tài)規(guī)劃的連續(xù)形式，解此方程可求得最優(yōu)控制u*(t)?，F(xiàn)在來推導(dǎo)這一方程。第二十六頁，共六十八頁，2022年，8月28日設(shè)連續(xù)方程為(1)終端約束使性能泛函求最優(yōu)控制u*(t)，或u任意。初始狀態(tài)(2)(3)(4)第二十七頁，共六十八頁，2022年，8月28日根據(jù)最優(yōu)性原理，如果x*(t)是以x(t0)為初始狀態(tài)的最優(yōu)軌線。如圖6所示。圖6連續(xù)系統(tǒng)最優(yōu)軌線第二十八頁，共六十八頁，2022年，8月28日(5)設(shè)t=t′

(t0<t′<tf)時(shí)，狀態(tài)為x(t′)，它將軌線分成前后兩半斷。那么以x(t′)為初始狀態(tài)的后半段也必是最優(yōu)軌線。而與系統(tǒng)先前如何到達(dá)x(t′)無關(guān)。若取t0=t,t′=t+?t，式(4)可寫成第二十九頁，共六十八頁，2022年，8月28日根據(jù)最優(yōu)性原理，如果t到tf的過程是最優(yōu)的，則從t+?t到tf的后部子過程也是最優(yōu)的，其中t<t+?t<tf。因此可寫成(6)(7)當(dāng)?t很小時(shí)，有第三十頁，共六十八頁，2022年，8月28日式(5)可近似表示為(8)(5)第三十一頁，共六十八頁，2022年，8月28日將x(t+?t)進(jìn)行泰勒展開，取一次近似，有(9)(10)(11)第三十二頁，共六十八頁，2022年，8月28日將上式在[x,t]領(lǐng)域展成泰勒級數(shù)，考慮到J*[x+?x,t+?t]既是x的函數(shù)，也與t有關(guān)，所以(12)(8)第三十三頁，共六十八頁，2022年，8月28日代入式(8)，得(13)(12)(8)第三十四頁，共六十八頁，2022年，8月28日考察上式因?yàn)镴*[x,t]與u無關(guān)，故J*[x,t]與可提到min號外面。經(jīng)整理可得式(14)稱為連續(xù)系統(tǒng)動態(tài)規(guī)劃基本方程或貝爾曼方程。(14)第三十五頁，共六十八頁，2022年，8月28日貝爾曼方程。它是一個(gè)關(guān)于J*[x,t]的偏微分方程。解此方程可求得最優(yōu)控制使J為極小。它的邊界條件為

(15)(14)第三十六頁，共六十八頁，2022年，8月28日如果令哈密爾頓函數(shù)為式中則式(14)可寫成(17)(16)第三十七頁，共六十八頁，2022年，8月28日當(dāng)控制矢量u(t)不受限制時(shí)，則有上兩式稱為哈密爾頓－雅可比方程。上式說明，在最優(yōu)軌線上，最優(yōu)控制必須使H達(dá)全局最小。實(shí)際上這就是極小值原理的另一種形式。(18)第三十八頁，共六十八頁，2022年，8月28日由貝爾曼方程可推導(dǎo)出協(xié)態(tài)方程和橫截條件。式(14)可寫成對x求偏導(dǎo)數(shù)，得(20)(19)(14)第三十九頁，共六十八頁，2022年，8月28日由于對t的全導(dǎo)數(shù)，為(22)(21)代入式(20)可寫成(20)第四十頁，共六十八頁，2022年，8月28日令，則上式可寫成(23)這就是所求的協(xié)態(tài)方程，與以前結(jié)果完全一致。(22)第四十一頁，共六十八頁，2022年，8月28日在t=tf時(shí)，在終端處性能泛函為式中μ——與N同維的乘子矢量。(24)第四十二頁，共六十八頁，2022年，8月28日對x(tf)求偏導(dǎo)數(shù)，得(25)(26)即(24)第四十三頁，共六十八頁，2022年，8月28日將式(24)對tf求偏導(dǎo)數(shù)，得(27)(24)第四十四頁，共六十八頁，2022年，8月28日考慮式(17)、式(20)得上述結(jié)果與極小值原理中推導(dǎo)的完全一致。上述推導(dǎo)過程實(shí)際上等于用動態(tài)規(guī)劃方法間接證明了極小值原理。(28)(17)(20)(27)第四十五頁，共六十八頁，2022年，8月28日應(yīng)當(dāng)指出，與極小值原理相比，動態(tài)規(guī)劃法需要解偏微分方程式(14)，它要求J[x,t]具有連續(xù)的偏導(dǎo)數(shù)，但在實(shí)際工程中，這一點(diǎn)常常不能滿足，因而限制了動態(tài)規(guī)劃法的使用范圍。第四十六頁，共六十八頁，2022年，8月28日例1：設(shè)，求最優(yōu)控制u*(t)使第四十七頁，共六十八頁，2022年，8月28日解：構(gòu)造哈密爾頓函數(shù)根據(jù)哈密爾頓－雅可比方程，有第四十八頁，共六十八頁，2022年，8月28日考慮控制u不受限制，得第四十九頁，共六十八頁，2022年，8月28日故第五十頁，共六十八頁，2022年，8月28日邊界條件，因Φ[x(tf),tf]=0，故J[x(tf)]=0

如果令，則得這正是應(yīng)用極小值原理所得的結(jié)果，二者完全一致。第五十一頁，共六十八頁，2022年，8月28日例2：設(shè)受控系統(tǒng)狀態(tài)方程為初始狀態(tài)為性能泛函為試求在u無限制情況下，使J取極小時(shí)的最優(yōu)控制。第五十二頁，共六十八頁，2022年，8月28日解：構(gòu)造哈密爾頓函數(shù)第五十三頁，共六十八頁，2022年，8月28日由哈密爾頓－雅可比方程因u無限制，可從求得第五十四頁，共六十八頁，2022年，8月28日代入上式，并注意到J*與t無關(guān)，因而，有第五十五頁，共六十八頁，2022年，8月28日為求解此偏微分方程，設(shè)其解為滿足方程，得第五十六頁，共六十八頁，2022年，8月28日各項(xiàng)系數(shù)為可得解為最優(yōu)控制第五十七頁，共六十八頁，2022年，8月28日最優(yōu)控制可由狀態(tài)反饋實(shí)現(xiàn)，如圖7所示。第五十八頁，共六十八頁，2022年，8月28日進(jìn)一步考察系統(tǒng)的狀態(tài)軌線。系統(tǒng)的狀態(tài)方程為齊次方程。第五十九頁，共六十八頁，2022年，8月28日它的解為第六十頁，共六十八頁，2022年，8月28日于是最優(yōu)控制為性能泛函最優(yōu)值為第六十一頁，共六十八頁，2022年，8月28日例3：設(shè)受控系統(tǒng)的微分方程為使性能指標(biāo)即要求快速響應(yīng)，求最優(yōu)控制u*，且滿足。第六十二頁，共六十八頁，2022年，8