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

第9頁，課件共52頁，創(chuàng)作于2023年2月

這里每條路線由四段組成，也可以說是四級決策。為了計(jì)算每條路線所花時(shí)間，要做三次加法運(yùn)算，為了計(jì)算六條路線所花的時(shí)間要作3×6=18次運(yùn)算。這種方法稱為“窮舉法”。顯然當(dāng)段數(shù)很多時(shí)，計(jì)算量是很大的。這種方法的特點(diǎn)是從起點(diǎn)站往前進(jìn)行，而且把這四級決策一起考慮。應(yīng)注意從到下一站所花的時(shí)間為1，而到所花時(shí)間為3，但最優(yōu)路線卻不經(jīng)過。這說明只看下一步的“眼前利益”來作決策是沒有意義的。第10頁，課件共52頁，創(chuàng)作于2023年2月為將問題表達(dá)得清楚，引進(jìn)下面的術(shù)語（寫法并不完全一樣）。令表示由某點(diǎn)到終點(diǎn)的段數(shù)（如到為2段，。令表示當(dāng)前所處點(diǎn)的位置（如），稱為狀態(tài)變量。對比一下最開始的例子第11頁，課件共52頁，創(chuàng)作于2023年2月令為決策（控制）變量，它表示當(dāng)處在位置而還有段要走時(shí)，所要選取的下一點(diǎn)。例如，從出發(fā)，下一點(diǎn)為時(shí)，則表示為。令表示在位置，向終點(diǎn)還有段要走時(shí)，由到終點(diǎn)的最短時(shí)間。例如，從C2到E的最短時(shí)間為4，可表示為T2(C2)=4。第12頁，課件共52頁，創(chuàng)作于2023年2月令表示從點(diǎn)到點(diǎn)的時(shí)間。例如，從到的時(shí)間為有了這些術(shù)語后，就可用動態(tài)規(guī)劃來解這個例子。從最后一段出發(fā)進(jìn)行計(jì)算，并將計(jì)算出的最短時(shí)間用括號表示在相應(yīng)的點(diǎn)處（見圖6-1）。第13頁，課件共52頁，創(chuàng)作于2023年2月n=1

（倒數(shù)第一段）

考慮從和到的路線，由定義可知，最短時(shí)間分別為第14頁，課件共52頁，創(chuàng)作于2023年2月n=2（倒數(shù)第二段）考慮從到的路線。由到有兩種路線：，。兩種路線中的最短時(shí)間由下式確定：最優(yōu)決策為。第15頁，課件共52頁，創(chuàng)作于2023年2月由到只有一種路線，其時(shí)間為由到E也只有一種路線，其時(shí)間為

EDC23第16頁，課件共52頁，創(chuàng)作于2023年2月n=3（倒數(shù)第三段）

從B2到E有兩種路線：和第17頁，課件共52頁，創(chuàng)作于2023年2月最優(yōu)決策最短時(shí)間為：第18頁，課件共52頁，創(chuàng)作于2023年2月n=4（倒數(shù)第四段）從A到E的路線有兩種：和。最優(yōu)決策為第19頁，課件共52頁，創(chuàng)作于2023年2月

至此求出了A到E的最短時(shí)間為9，最優(yōu)路線為。在圖中用粗線表示。這里，為決定最優(yōu)路線進(jìn)行了10次加法，比窮舉法的18次少了8次。當(dāng)段數(shù)n更多時(shí)，節(jié)省計(jì)算將會更多。第20頁，課件共52頁，創(chuàng)作于2023年2月

以上面的最短時(shí)間問題為例，如把當(dāng)作初始狀態(tài)，則余下的決策對來講是最優(yōu)策略；如把當(dāng)初始狀態(tài)，則余下的決策對來講也構(gòu)成最優(yōu)策略。一般來說，如果一個最優(yōu)過程用狀態(tài)來表示，最優(yōu)決策為，則對狀態(tài)來講，必定是最優(yōu)的，這可用圖6-2來表示。第21頁，課件共52頁，創(chuàng)作于2023年2月圖6-2最優(yōu)性原理示意圖第22頁，課件共52頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃的特點(diǎn)：一是它從最后一級反向計(jì)算；二是其將一個N級決策問題化為N個單級決策問題。好處：將一個復(fù)雜問題化為多個簡單問題加以求解。第23頁，課件共52頁，創(chuàng)作于2023年2月最優(yōu)性原理

貝爾曼的最優(yōu)性原理可敘述如下：“一個多級決策問題的最優(yōu)決策具有這樣的性質(zhì)：當(dāng)把其中任何一級及其狀態(tài)作為初始級和初始狀態(tài)時(shí)，則不管初始狀態(tài)是什么，達(dá)到這個初始狀態(tài)的決策是什么，余下的決策對此初始狀態(tài)必定構(gòu)成最優(yōu)策略。”第24頁，課件共52頁，創(chuàng)作于2023年2月在多數(shù)實(shí)際問題中，級決策的性能指標(biāo)取如下形式

是由某級狀態(tài)和決策決定的性能函數(shù)，要求尋找決策使J取極小值。第25頁，課件共52頁，創(chuàng)作于2023年2月最優(yōu)性原理可表示為

第26頁，課件共52頁，創(chuàng)作于2023年2月根據(jù)上式就可證明最優(yōu)性原理的正確性。若以為初態(tài)時(shí)，余下的決策不是最優(yōu)的，那么就存在另一決策序列所決定的指標(biāo)值，于是這與是極小值發(fā)生矛盾，所以余下的決策必須是最優(yōu)的。第27頁，課件共52頁，創(chuàng)作于2023年2月6-2離散最優(yōu)控制問題設(shè)控制系統(tǒng)的狀態(tài)方程為式中x(k)是k時(shí)刻的幾維狀態(tài)向量，u(k)是k時(shí)刻的p維容許控制向量，設(shè)系統(tǒng)在每一步轉(zhuǎn)移中的性能指標(biāo)為F[x(k),u(k)]如在u(0)的作用下在u(1)的作用下對N級決策過程第28頁，課件共52頁，創(chuàng)作于2023年2月性能指標(biāo)要求選擇控制序列使性能指標(biāo)達(dá)到極小根據(jù)最優(yōu)性原理解上述遞推方程，即可獲得最優(yōu)控制序列。第29頁，課件共52頁，創(chuàng)作于2023年2月例6-1設(shè)一階離散系統(tǒng)的狀態(tài)方程為初始條件為x(0)，控制變量u不受約束，性能指標(biāo)為求最優(yōu)控制u*(t)，使J達(dá)最小，為簡便起見，設(shè)N＝2解設(shè)在u(0)、u(1)作用下，系統(tǒng)狀態(tài)為x(0)、x(1)、x(2)先考慮從x(1)到x(2)的情況，控制為u(1)第30頁，課件共52頁，創(chuàng)作于2023年2月再考慮從x(0)到x(1)的情況，控制為u(0)最優(yōu)控制序列為最優(yōu)性能指標(biāo)為第31頁，課件共52頁，創(chuàng)作于2023年2月

連續(xù)系統(tǒng)的動態(tài)規(guī)劃

設(shè)系統(tǒng)的狀態(tài)方程和性能指標(biāo)為

（6-19）

（6-20）

受約束，可寫成為某一閉集。要尋找滿足此約束且使最小的最優(yōu)控制。第32頁，課件共52頁，創(chuàng)作于2023年2月

設(shè)時(shí)間在區(qū)間內(nèi)，則根據(jù)最優(yōu)性原理，從到這一段過程應(yīng)當(dāng)是最優(yōu)過程。把這段最優(yōu)指標(biāo)寫成,則（6-21）顯然滿足終端條件通常假定對及的二階偏導(dǎo)數(shù)存在且有界。第33頁，課件共52頁，創(chuàng)作于2023年2月現(xiàn)在，考慮系統(tǒng)從出發(fā)，到分兩步走：先從到，再從到，是小量，則（6-23）根據(jù)最優(yōu)性原理，從也應(yīng)是最優(yōu)過程。

第34頁，課件共52頁，創(chuàng)作于2023年2月因故這樣，式（6-23）可寫成（6-24）第35頁，課件共52頁，創(chuàng)作于2023年2月注意到，上式右邊括號中表示最優(yōu)指標(biāo)，其中為最優(yōu)控制，不需再選擇，也與選擇無關(guān)。故從上式兩端消去，除以，再令，可得

（6-25）第36頁，課件共52頁，創(chuàng)作于2023年2月引用以前使用過的哈密頓函數(shù)

（6-26）

（6-27）則（6-25）可寫成

（6-28）第37頁，課件共52頁，創(chuàng)作于2023年2月（6-25）或（6-28）稱為哈密頓—雅可比—貝爾曼方程，邊界條件是：哈密頓—雅可比—貝爾曼方程在理論上很有價(jià)值，但它是的一階偏微分方程并帶有取極小的運(yùn)算，因此求解是非常困難的，一般情況得不到解析解，只能用計(jì)算機(jī)求數(shù)值解。對于線性二次問題，可以得到解析解，而且求解結(jié)果與用極小值原理或變分法所得結(jié)果相同。這時(shí)，哈密頓——雅可比——貝爾曼方程可歸結(jié)為黎卡提方程。在實(shí)際計(jì)算線性二次問題時(shí)，一般用直接求解黎卡提方程來求最優(yōu)控制。第38頁，課件共52頁，創(chuàng)作于2023年2月例6-3設(shè)系統(tǒng)狀態(tài)方程為初始狀態(tài)不受約束，性能指標(biāo)為求最優(yōu)控制u*(t)，使性能指標(biāo)J為最小。解由于因?yàn)橄到y(tǒng)是時(shí)不變的，并且性能指標(biāo)的被積函數(shù)不是時(shí)間的顯函數(shù)，故第39頁，課件共52頁，創(chuàng)作于2023年2月解由于因?yàn)橄到y(tǒng)是時(shí)不變的，并且性能指標(biāo)的被積函數(shù)不是時(shí)間的顯函數(shù)，故解得第40頁，課件共52頁，創(chuàng)作于2023年2月引用以前使用過的哈密頓函數(shù)

（6-26）

（6-27）則（6-25）可寫成

（6-28）第41頁，課件共52頁，創(chuàng)作于2023年2月思考題HJB方程與極小值原理的區(qū)別和聯(lián)系？第42頁，課件共52頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃與極小值原理

動態(tài)規(guī)劃和極小值原理是最優(yōu)控制理論的兩大基石，它們都可以解決有約束的最優(yōu)控制問題，雖然在形式上和解題方法上不同，但卻存在著內(nèi)在的聯(lián)系。下面我們從動態(tài)規(guī)劃來推演極小值原理，不過要說明這種推演是基于最優(yōu)指標(biāo)對和兩次連續(xù)可微這個條件的。第43頁，課件共52頁，創(chuàng)作于2023年2月最優(yōu)性能指標(biāo)與狀態(tài)方程為（6-29）要求確定U(t)使性能指標(biāo)

（6-30）極小。其中，固定，自由，可以有約束，也可以沒有。第44頁，課件共52頁，創(chuàng)作于2023年2月1、（狀態(tài)方程）（6-31）2、（協(xié)態(tài)方程）（6-32）3、（邊界方程）（6-33）4、（橫截條件）（6-34）5、（極值條件）（6-35）第45頁，課件共52頁，創(chuàng)作于2023年2月用動態(tài)規(guī)劃求解的結(jié)果已在上節(jié)中得到，現(xiàn)在歸納一下：在動態(tài)規(guī)劃中協(xié)態(tài)變量滿足哈密頓—雅可比—貝爾曼方程（6-28）本身說明了哈密頓函