北京交通大學(xué)最優(yōu)控制理論與算法研究生課程第六章-動態(tài)規(guī)劃與離散系統(tǒng)最優(yōu)控制

1、動態(tài)規(guī)劃與離散系統(tǒng)最優(yōu)控制(1/3),第6章 動態(tài)規(guī)劃與離散系統(tǒng)最優(yōu)控制前面討論了連續(xù)系統(tǒng)最優(yōu)控制問題的基于經(jīng)典變分法和龐特里亞金的極大值原理的兩種求解方法。所謂連續(xù)系統(tǒng),即系統(tǒng)方程是用線性或非線性微分方程描述的動態(tài)系統(tǒng)。該類系統(tǒng)的控制問題是與傳統(tǒng)的控制系統(tǒng)和控制元件的模擬形式實現(xiàn)相對應(yīng), 如模擬運算放大器件、模擬自動化運算儀表、模擬液壓放大元件等。隨著計算機(jī)技術(shù)及其計算機(jī)控制技術(shù)的發(fā)展, 離散系統(tǒng)的最優(yōu)控制問題也必然成為最優(yōu)

2、控制中需深入探討的控制問題, 而且成為現(xiàn)代控制技術(shù)更為關(guān)注的問題。,,,動態(tài)規(guī)劃與離散系統(tǒng)最優(yōu)控制(2/3),離散系統(tǒng)的控制問題為人們所重視的原因有二,1) 連續(xù)系統(tǒng)在實現(xiàn)控制時，在應(yīng)用計算機(jī)控制技術(shù)、數(shù)字控制技術(shù)時, 須經(jīng)采樣后成為離散化系統(tǒng), 再加以控制如許多現(xiàn)代工業(yè)控制領(lǐng)域的實際計算機(jī)控制問題。2) 有些實際控制問題本身即為離散系統(tǒng),如某些經(jīng)濟(jì)計劃系統(tǒng)、人口系統(tǒng)的時間坐標(biāo)只能以小時、天或月等標(biāo)記;再如機(jī)床加工中心的時間坐

3、標(biāo)是以一個事件(如零件加工活動)的發(fā)生或結(jié)束為標(biāo)志的。,,,動態(tài)規(guī)劃與離散系統(tǒng)最優(yōu)控制(3/3),本節(jié)將介紹解決離散系統(tǒng)最優(yōu)控制的有效工具—貝爾曼動態(tài)規(guī)劃, 以及線性離散系統(tǒng)的二次最優(yōu)控制問題。內(nèi)容為最優(yōu)性原理與離散系統(tǒng)的動態(tài)規(guī)劃法線性離散系統(tǒng)的二次型最優(yōu)控制,,,最優(yōu)性原理與離散系統(tǒng)的動態(tài)規(guī)劃法(1/3),6.1 最優(yōu)性原理與離散系統(tǒng)的動態(tài)規(guī)劃法基于對多階段決策過程的研究結(jié)果, 貝爾曼在20世紀(jì)50年代首先提出了求解離散多階

4、段決策優(yōu)化問題的動態(tài)規(guī)劃法。多階段決策優(yōu)化問題方法在許多領(lǐng)域得到應(yīng)用和發(fā)展, 如在生產(chǎn)計劃、資源配置、信息處理、模式識別等方面都有成功的應(yīng)用。本節(jié)介紹將動態(tài)規(guī)劃優(yōu)化方法應(yīng)用于動態(tài)系統(tǒng)的最優(yōu)控制問題, 構(gòu)成最優(yōu)控制的兩種主要求解方法之一的最優(yōu)控制動態(tài)規(guī)劃法。,,,最優(yōu)性原理與離散系統(tǒng)的動態(tài)規(guī)劃法(2/3),動態(tài)規(guī)劃的核心是貝爾曼最優(yōu)性原理這個原理歸結(jié)為一個基本的遞推公式。求解多階段決策問題時, 要從末端開始, 逆向遞推, 直至始端。

5、動態(tài)規(guī)劃的離散基本形式受到問題的維數(shù)的限制, 應(yīng)用有一定的局限性。但對于求解決線性離散系統(tǒng)的二次型性能指標(biāo)的最優(yōu)控制問題特別有效。至于連續(xù)系統(tǒng)的最優(yōu)控制問題的動態(tài)規(guī)劃法, 不僅是一種可供選擇的有充分性的最優(yōu)控制求解法,它還揭示了動態(tài)規(guī)劃與變分法、極大值原理之間的關(guān)系, 具有重要的理論價值。,,,最優(yōu)性原理與離散系統(tǒng)的動態(tài)規(guī)劃法(3/3),下面分別介紹多階段決策問題最優(yōu)性原理一般問題的問題描述離散系統(tǒng)的動態(tài)規(guī)劃法,,,多階段決策

6、問題(1/12),1. 多階段決策問題在討論動態(tài)規(guī)劃法之前,先考察一個簡單的最短時間行車問題,簡稱行車問題。例 如圖10所示, 某交通工具從S站出發(fā), 終點為 F 站, 全程可分為4段。中間可能經(jīng)過的各站及站間的行車時間均已標(biāo)記在圖上。,,,,圖10 某行車路線圖,試求最短行車時間的行車路線。,多階段決策問題(2/12),由S站出發(fā)至終點F站可有多種不同的行車路線, 沿各種行車路線所耗費的時間不同。為使總的行車時間最短,司機(jī)在

7、路程的前3段要作出3次決策。,,,,首先，一開始司機(jī)要在經(jīng)過x1(1)站還是x2(1)站兩種情況中作出決策。 到x1(1)站或x2(1)后, 又面臨下一站是經(jīng)過x1(2)站還是x2(2)站的第2次決策。同樣,在后續(xù)的每個階段都要作出類似的決策。,多階段決策問題(3/12),,,,,因此,計算8種不同的行車路線所耗費的總行車時間,取最小者即可求出最短時間行車路線。若行車問題需作決策的階段數(shù)n較大,每次決策中可供選擇的方案較

8、多時,用上述的窮（枚）舉法來解決最短行車時間問題計算量非常大。一般說來,用窮舉法計算時間與作決策的階段數(shù)n和每次決策中可供選擇的方案數(shù)成指數(shù)關(guān)系, 即通常所稱的指數(shù)爆炸、維數(shù)災(zāi)難。,多階段決策問題(4/12),通過分析發(fā)現(xiàn), 另一種求最短時間行車路線方法的是:從最后一階段開始,先分別算出x1(3)站和x2(3)站到終點F的最短時間（成本）,并分別記為J[x1(3)]和J[x2(3)]。,,,,實際上, 最后一階段沒有選擇的余地。因

9、此,由圖10可求得J[x1(3)]=4, J[x2(3)]=3,多階段決策問題(5/12),為便于今后求解過程的應(yīng)用,可將從x1(3)站和x2(3)站到終點的最短時間J[x1(3)]和J[x2(3)]的數(shù)值標(biāo)記于代表該站的小圓圈內(nèi), 如圖11所示。,,,,其他站的情況依此類推。,圖11 最優(yōu)行車路線圖,多階段決策問題(6/12),由此向后倒推,繼續(xù)考察倒數(shù)第2段, 計算x1(2)站和x2(2)站到終點F的最短時間, 并分別記為J[

10、x1(2)]和J[x2(2)]。,,,,由圖10可知,從x1(2)站到達(dá)終點F的路線中下一站只能是x1(3)站和x2(3)站中之一。由于從x1(3)站和x2(3)站分別前往終點的最短時間已經(jīng)計算出, 因此, 從x1(2)站和x2(2)到終點的最短時間分別為，J[x1(2)]=min{1+J[x1(3)],1+J[x2(3)]}=4 J[x2(2)]=min{2+J[x1(3)],2+J[x2(3)]}=5其相應(yīng)的最短時間行車路線

11、{x1(2),x2(3),F}和{x2(2),x2(3), F}。,多階段決策問題(7/12),類似于前面過程,其他各站到終點的最短時間和相應(yīng)的行車路線如圖11所示.,,,,從圖11得到各站到終點站F的最短時間行車路線和所耗費的行車時間, 從起點站S到終點站F的最短時間行車路線和所耗費的行車時間。,多階段決策問題(8/12),上述最短行車時間路線問題及其求解方法可以推廣為多階段決策優(yōu)化問題, 如建筑安裝工期計劃、經(jīng)濟(jì)發(fā)展計劃、資源合理配

12、置等, 其相應(yīng)的最優(yōu)性指標(biāo)可以為所耗費的時間最短,也可以為所耗費的能源最小、所得到的效益最好等。因此,前面介紹逆向遞推求解最優(yōu)化問題的方法是一種具有普遍性意義的多階段決策優(yōu)化方法,稱為動態(tài)規(guī)劃法。從上述解題的敘述過程可以看出, 動態(tài)規(guī)劃法具有如下特點。,,,,多階段決策問題(9/12),1) 與窮舉法相比, 動態(tài)規(guī)劃法可使計算量大為減少。事實上, 用動態(tài)規(guī)劃法解多階段決策問題,只需作一些簡單的、非常有限的加法運算和求極大運算。如

13、對一個有n個階段,除最后一段外每一個狀態(tài)下一步有m種可能決策方案的多階段決策問題, 共需作(n-2)m2+m=(mn-2m+1)m次加法運算,以及(mn-2m+1)(m-1)次從二取一的極大運算而對窮舉法,則需作m×mn-2×(n-1)=mn-1(n-1)次加法運算和mn-1-1次的從二取一的極大運算。如對前面的n=4, m=2的最短時間行車問題,用動態(tài)規(guī)劃法求解共需作10次加法運算和5次從二取一的極大運算。而用

14、窮舉法求解,則分別為24次和8次。,,,,多階段決策問題(10/12),因此,動態(tài)規(guī)劃法在減少計算量上的效果是顯著的。階段數(shù)n越大, 決策方案m越多, 則動態(tài)規(guī)劃法的優(yōu)點更為突出。如對n=10,m=4的多階段決策問題,用動態(tài)規(guī)劃法求解共需作132次加法運算和33次從二取一的極大運算,而用窮舉法求解分別為2359296次和262143次。因此, 動態(tài)規(guī)劃法的效果是非常顯著的。,,,,多階段決策問題(11/12),2) 用動態(tài)規(guī)劃法求

15、解多階段決策問題的思路是:為了最后確定由起點S至終點F的最優(yōu)路線，首先逆向遞推求出各狀態(tài)至終點F的最優(yōu)路線在求取當(dāng)前狀態(tài)到終點的極值時,只需知道當(dāng)前狀態(tài)值和上一次的最優(yōu)(集合)值, 就可以得到當(dāng)前的最優(yōu)值, 并以此作為下一次優(yōu)化的初始數(shù)據(jù)貝爾曼的最優(yōu)性原理就是運用這個原理給出遞推方法的,,,,多階段決策問題(12/12),3) 由圖11可知,與從起點S至終點F的最優(yōu)路線{S, x2(1), x1(2), x2(3), F} 相對應(yīng)

16、的, 該最優(yōu)路線的從x2(1)站至終點F部分的路線{ x2(1), x1(2), x2(3), F }是從x2(1)站至終點F的最優(yōu)路線 類似地,從x1(2)站至終點F的最優(yōu)路線{x1(2),x2(3),F}是從起點S至終點F的最優(yōu)路線{S,x2(1),x1(2),x2(3),F}的一部分,也是從x2(1)至終點F的最優(yōu)路線{x2(1), x1(2), x2(3), F}的一部分 對于多階段決策問題,最優(yōu)路線和最優(yōu)決策具有這種性質(zhì)不

17、是偶然的, 而反映了該問題的一種規(guī)律性,即所謂的貝爾曼的最優(yōu)性原理 它是動態(tài)規(guī)劃法的核心,,,,最優(yōu)性原理一般問題的問題描述(1/22),2. 最優(yōu)性原理一般問題的問題描述動態(tài)規(guī)劃的基本原理介紹一些專有名詞介紹多階段決策問題介紹最優(yōu)性原理應(yīng)用最優(yōu)性原理求解多階段決策過程,并推廣至離散系統(tǒng)最優(yōu)控制下面將在函數(shù)空間中描述N個階段的決策過程, 為此先引進(jìn)下述概念與定義。狀態(tài)向量x(k), 表示過程在 k 時刻的狀態(tài)。對控制

18、問題, 相當(dāng)于狀態(tài)變量向量。,,,,最優(yōu)性原理一般問題的問題描述(2/22),2) 決策向量u(k), 表示過程在k時刻的從某一狀態(tài)轉(zhuǎn)變?yōu)榱硪粻顟B(tài)的動因（激勵）。對控制問題, 則相當(dāng)于控制輸入向量。3) 策略{u(0),u(1),…,u(N-1)}是各個階段的決策所組成的決策集合。對控制問題, 則相當(dāng)于控制輸入向量的序列。4) 成本(cost)J, 由于狀態(tài)發(fā)生轉(zhuǎn)移所耗費的成本。對最優(yōu)控制問題, 相當(dāng)于其性能指標(biāo)。,,,,最

19、優(yōu)性原理一般問題的問題描述(3/22),設(shè)在決策u(k)的作用下, 發(fā)生了狀態(tài)從x(k)到x(k+1)的轉(zhuǎn)移。顯然新的狀態(tài)x(k+1)完全取決于原來的狀態(tài)x(k)和所采取的決策u(k)。也可以把這種轉(zhuǎn)移看成是在決策u(k)作用下的狀態(tài)從x(k)到x(k+1)的一種變換, 且這種變換關(guān)系是唯一的,即 x(k+1)=f(x(k),u(k),k)在每一階段, 通常有若干個決策可供選

20、擇,我們用Ω(k)代表第k個階段可供選擇的決策集合。一般說來, 階段不同, 其決策集合Ω(k)也不同。用Ω代表全部可供選擇的決策的集合,即Ω=Ω(0)∪Ω(1)∪…∪Ω(N-1),,,,最優(yōu)性原理一般問題的問題描述(4/22),多階段的決策問題描述如下:設(shè)系統(tǒng)由決策u(k), 經(jīng)變換式(182)把狀態(tài)從x(k)轉(zhuǎn)移到x(k+1), 其相應(yīng)耗費的成本為F(x(k),u(k),k), k=0, 1,…, N-1?，F(xiàn)需通過一變換序列

21、f(x(0),u(0),0), f(x(1),u(1),1), …, f(x(N-1),u(N-1),N-1)將初始狀態(tài)x(0)經(jīng)x(1), …, x(N-1)轉(zhuǎn)移到終態(tài) x(N), 這N次轉(zhuǎn)移相對應(yīng)的所耗費的總成本為試求出一個決策序列{u(0),u(1),…,u(N-1)}?Ω, 使N階段決策問題的總成本最小。,,,,,x(k+1)=f(x(k),u(k),k) (182),最優(yōu)性原理一般問題的問題描述(6/22),問題

22、(183)的描述形式和最短路徑問題有所不同。如果把(182)看作約束條件, 最短路徑問題是一個無約束的動態(tài)規(guī)劃問題, 而問題(183)是一個具有約束的動態(tài)規(guī)劃問題, 因為在每一級優(yōu)化(決策)的時候,都要考慮狀態(tài)與控制之間的變換關(guān)系。動態(tài)規(guī)劃法是求解多階段決策問題的一種最優(yōu)化方法。這一問題的核心是最優(yōu)性原理。最優(yōu)性原理可以表述如下:一個最優(yōu)性決策具有這樣的性質(zhì), 即不論初始狀態(tài)和初始決策如何, 對于前面決策所形成的狀態(tài)來說,其余

23、諸決策序列必須構(gòu)成一個最優(yōu)決策。為了證實最優(yōu)性原理, 有下面的定理.,,,,,最優(yōu)性原理一般問題的問題描述(7/22)—定理7-17,定理17 若用u(0, N-1)表示N階段決策過程中的一個策略,u(0, k-1)和u(k, N-1)分別為前k個階段和后N-k個階段的子策略;并用J[x(0),u(0,N-1)]表示N階段決策過程的總成本, J[x(0),u(0,k-1)]和J[x(k),u(k,N-1)]分別為前k個階段和后N-k

24、個階段的總成本, 即存在如下兩個等式u (0, N-1) ={u(0,k-1), u(k, N-1)}J[ x(0), u(0, N-1)]=J[x(0), u(0,k-1)]+J[x(k), u(k, N-1)]則策略u*(0,N-1)={u*(0),u*(1),…,u*(N-1)}為最優(yōu)性決策的充分必要條件為:對任意k,0<k<N-1,下列關(guān)系成立式中 x(k) = f(x(k-1), u(k-1), k-1)

25、 是后N-k個階段的初始狀態(tài)。,,,,最優(yōu)性原理一般問題的問題描述(8/22),證明 (1) 必要性證明。由最優(yōu)策略的定義, 并應(yīng)用式(184)和式(185),有由于上式右邊括弧中第一項與子策略u(k, N-1)無關(guān),因此有,,,,u(0,N-1)={u(0,k-1),u(k,N-1)} (184)J[x(0),u(0,N-1)]=J[x(0),u(0,

26、k-1)]+J[x(k),u(k,N-1)] (185),,最優(yōu)性原理一般問題的問題描述(9/22),(2) 充分性證明。設(shè) 為任意一個策略, 且是后N-k個階段的初始狀態(tài), 則于是,,,,,,,最優(yōu)性原理一般問題的問題描述(10/22),因此, 若式(186)成立, 則對任一策略 ,都有

27、即u*(0, N-1)為最優(yōu)策略。 ???由上述定理17描述的最優(yōu)性原理,可得如下推論。推論2 若u*(0, N-1)是最優(yōu)策略,則對任一k,0<k<N-1,其子策略u*(k, N-1)對以x*(k)=f(x*(k-1),u*(k-1),k-1)為初始狀態(tài)的后N-k個階段來說,也必是最優(yōu)策略。

28、 ???,,,,,,,,最優(yōu)性原理一般問題的問題描述(11/22),證明 用反證法。假設(shè)u*(k,N-1)是最優(yōu)策略，而對于以x*(k)=f(x*(k-1),u*(k-1),k-1)為初始狀態(tài)的后N-k個階段來說不是最優(yōu)策略, 即有則,,,,,,,,最優(yōu)性原理一般問題的問題描述(12/22),即{u*(0,k-1), u(k,N-1)}為比u*(0,N-1)更優(yōu)的策略,與u*(0,N-1

29、)為最優(yōu)策略的假設(shè)矛盾。因此,最優(yōu)策略u*(0,N-1)的子策略u*(k,N-1)對以x*(k)=f(x*(k-1),u*(k-1),k-1)為初始狀態(tài)的后N-k個階段來說,也必是最優(yōu)策略推論得證。 證畢由上述定理和推論,可得最優(yōu)性原理的另一個表達(dá)形式式中, J*[x(k),u*(k,N-1)]表示以k時刻的狀態(tài)x(k)為初始狀態(tài), 后N-k個階段在最優(yōu)策略u*(

30、k, N-1)下的最優(yōu)總成本, 最優(yōu)策略u*(k, N-1)為最優(yōu)策略u*(0, N-1)的后N-k個決策。,,,,,,,,最優(yōu)性原理一般問題的問題描述(13/22),基于最優(yōu)性原理的表達(dá)形式(187)和總成本的表達(dá)式(183), 可推得即,,,,,,,,,最優(yōu)性原理一般問題的問題描述(14/22),因此, 有如下一步逆向遞推形式 ……式中, J*[x(N), N]為

31、總成本的邊界條件, 相當(dāng)于控制性能指標(biāo)泛函中的末值型指標(biāo)。對總成本表達(dá)式, 則有如下總成本J的邊界條件J*[x(N), N]=0,,,最優(yōu)性原理一般問題的問題描述(15/22),由上述遞推解過程,可歸納得如下動態(tài)規(guī)劃法的遞推方程,即貝爾曼遞推方程???為了更好地理解動態(tài)規(guī)劃的本質(zhì),再作如下說明。1) 結(jié)合定理17的推論和式(187), 最優(yōu)性原理可以表述為:“一個最優(yōu)性策略具有這樣的性質(zhì), 即不論過去的狀態(tài)及過去的決策

32、如何, 如把當(dāng)前狀態(tài)視為后續(xù)過程的初始狀態(tài), 則其后諸決策仍必須構(gòu)成一最優(yōu)策略。,,,,最優(yōu)性原理一般問題的問題描述(16/22),2) 最優(yōu)性原理得以成立的一個前提條件(必要條件),即所謂的過程無后效性,是當(dāng)前狀態(tài)x(k)僅由前一階段狀態(tài)x(k-1)和決策u(k-1)唯一決定。前一階段狀態(tài)x(k-1)和決策u(k-1)對后續(xù)過程的影響通過當(dāng)前狀態(tài)x(k)起作用, 并無其它直接影響。這種性質(zhì)在數(shù)學(xué)上稱為馬爾柯夫(Markov)特性。

33、,,,最優(yōu)性原理一般問題的問題描述(17/22),3) 在N階段決策過程中,前k個階段的子策略對總成本的影響表現(xiàn)在兩個方面,其一是直接決定前k個階段的局部總成本,其二通過對狀態(tài)x(k)的影響, 間接地影響后N-k個階段的局部總成本。因此,為了構(gòu)成一個最優(yōu)策略,其前k個階段的子策略必須通盤考慮這兩個方面的影響。定理17中式(186) 體現(xiàn)了這一思想, 即在求前k個階段的子策略時, 應(yīng)使前k個階段的局部總成本與后N-k個階段的局部

34、總成本之和最小, 而不是僅使前k個階段的局部總成本最小。,,,最優(yōu)性原理一般問題的問題描述(18/22),4) 從動態(tài)規(guī)劃的逆向遞推求解公式(194)可知, 欲求出最優(yōu)決策u*(0), 就得先求出最優(yōu)決策u*(1);依此類推,要求出最優(yōu)決策u*(1),就得先求出最優(yōu)決策u*(2); …,最后,歸結(jié)為首先求出最優(yōu)決策u*(N-1),再逐步遞推回代,相繼得到最優(yōu)決策序列{u*(N-2),…,u*(1),u*(0)}。由此可知,動態(tài)規(guī)

35、劃法的解題順序和事物的發(fā)展進(jìn)程相反。下面通過一實例進(jìn)一步說明多階段決策的動態(tài)規(guī)劃法的應(yīng)用。,,,最優(yōu)性原理一般問題的問題描述(19/22)—例7-14,例14 圖12所示的是某零件的加工工序圖,各節(jié)點代表機(jī)床,箭頭代表加工工序,節(jié)點間的數(shù)字表示零件加工的經(jīng)濟(jì)效益。試求一產(chǎn)生最大經(jīng)濟(jì)效益的工序路線。,,,最優(yōu)性原理一般問題的問題描述(20/22),解 根據(jù)多階段決策的動態(tài)規(guī)劃法,反復(fù)使用逆向遞推公式,則有J*[F]=0

36、J*[x1(4)]=4,,,J*[x2(4)]=3J*[x1(3)]=max{4+J*[x1(4)]}=8J*[x2(3)]=max{1+J*[x1(4)],3+J*[x2(4)]}=5……J*[S]=max{4+J*[x1(1)],5+J*[x2(1)]}=16,最優(yōu)性原理一般問題的問題描述(21/22),解 根據(jù)將所求得的各點的最佳效益標(biāo)記在代表各機(jī)床的圓圈內(nèi),并同時將前面所求得的各相鄰機(jī)床之間的決策作于工序圖上,即可得圖

37、13。,,,圖13 某機(jī)械加工最優(yōu)工序圖,最優(yōu)性原理一般問題的問題描述(22/22),由圖13可以很方便地得到從加工起始機(jī)床S到完成最后加工的機(jī)床F的最佳經(jīng)濟(jì)效益工序路線{S,x2(1),x2(2),x2(3),x1(4),F}。由該圖也可以很方便地求出各機(jī)床到機(jī)床F的最佳路線。,,,離散系統(tǒng)的動態(tài)規(guī)劃法(1/9),3. 離散系統(tǒng)的動態(tài)規(guī)劃法離散系統(tǒng)的最優(yōu)控制問題可以歸結(jié)為一個多階段決策優(yōu)化問題,其中決策變量即為其控制輸入變量,

38、總成本為其性能指標(biāo)泛函。因此,利用前面的多階段決策問題的動態(tài)規(guī)劃法,可得離散系統(tǒng)最優(yōu)控制問題的動態(tài)規(guī)劃解法。,,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(2/9)—定理7-18,定理18 (離散系統(tǒng)的動態(tài)規(guī)劃法) 設(shè)離散系統(tǒng)的狀態(tài)方程、狀態(tài)初始條件和性能指標(biāo)泛函分別為式中, f(x,u,k)和L(x,u,k)都是關(guān)于狀態(tài)x(k)和時間k的連續(xù)可微函數(shù);S(x(kf),kf)是關(guān)于x(kf)和kf的連續(xù)可微函數(shù)；u(k)和x(k)分別為r

39、維和n維向量;,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(3/9),容許控制u(k)滿足u(k)?U, k?[k0,kf]式中,U為受不等式約束條件限制的控制量u(k)的Rr空間中的閉集。設(shè)使性能指標(biāo)泛函(196)極小的最優(yōu)控制函數(shù)為u*(k)、最優(yōu)狀態(tài)軌線為x*(k)。則u*(k)和x*(k)滿足如下逆向遞推方程,即貝爾曼遞推方程,,,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(4/9),在離散系統(tǒng)最優(yōu)控制問題的動態(tài)規(guī)劃求解方法中,若控制量u(k)不受約

40、束,可以在Rr空間中自由取值,則由貝爾曼遞推方程(198)求解最優(yōu)控制量u*(k),可等效地求解如下關(guān)系式即,,,,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(5/9)—例7-15,下面通過一個例子來說明由定理18求解離散系統(tǒng)的最優(yōu)控制問題。例15 已知被控系統(tǒng)為求在性能指標(biāo)泛函下的最優(yōu)控制序列u*(k)和最優(yōu)軌線x*(k)。,,,,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(6/9),解 由離散系統(tǒng)最優(yōu)控制問題的貝爾曼逆向遞推方程(198),可

41、得因此,由可解得,,,,,,,,離散系統(tǒng)的動態(tài)規(guī)劃法(7/9),再由可解得,,,最后,由可解得,離散系統(tǒng)的動態(tài)規(guī)劃法(8/9),因此,由初始狀態(tài)x(0)=2,可解得最優(yōu)控制序列和最優(yōu)軌線分別為,,,離散系統(tǒng)的動態(tài)規(guī)劃法(9/9),前面討論了一般求解離散系統(tǒng)最優(yōu)控制問題的動態(tài)規(guī)劃法,給出了求解方法和基本步驟。對于一般的非線性離散系統(tǒng),采用上述動態(tài)規(guī)劃法很難得到其最優(yōu)控制函數(shù)u*(t)和最優(yōu)狀態(tài)x*(t)的解析表達(dá)式

42、,使得離散系統(tǒng)最優(yōu)控制問題的求解較復(fù)雜,難以實際應(yīng)用。但對于線性離散系統(tǒng), 當(dāng)其最優(yōu)控制問題的性能指標(biāo)泛函為二次型性能指標(biāo)時, 其最優(yōu)控制函數(shù)u*(t)和最優(yōu)狀態(tài)x*(t)具有較簡潔的解析表達(dá)式, 并能很方便地構(gòu)成最優(yōu)狀態(tài)反饋律和閉環(huán)最優(yōu)控制系統(tǒng)。下面,作為離散最優(yōu)控制問題的動態(tài)規(guī)劃法的具應(yīng)用,我們將討論線性離散系統(tǒng)的二次型性能指標(biāo)泛函下的最優(yōu)控制問題, 即離散最優(yōu)二次型問題。,,,線性離散系統(tǒng)的二次型最優(yōu)控制(1/3),6.2 線

43、性離散系統(tǒng)的二次型最優(yōu)控制類似于線性連續(xù)系統(tǒng)的二次型最優(yōu)控制問題, 線性離散系統(tǒng)的二次型最優(yōu)控制律也是線性控制, 易于實現(xiàn)。下面將介紹線性離散系統(tǒng)的二次型最優(yōu)控制,內(nèi)容為：時變狀態(tài)調(diào)節(jié)器 定常狀態(tài)調(diào)節(jié)器,,,時變狀態(tài)調(diào)節(jié)器(1/14),1. 時變狀態(tài)調(diào)節(jié)器線性連續(xù)系統(tǒng)的二次型最優(yōu)控制問題在前面已經(jīng)作了詳細(xì)的討論下面將會看到, 線性離散系統(tǒng)的二次型最優(yōu)控制問題的解可最后歸結(jié)到一個最優(yōu)狀態(tài)反饋律和求解一個與黎卡提矩陣微分方程

44、相類似的黎卡提矩陣差分方程。線性離散系統(tǒng)的二次型性能指標(biāo)泛函下的最優(yōu)控制問題的描述如下。,,,時變狀態(tài)調(diào)節(jié)器(2/14),線性離散系統(tǒng)的二次型最優(yōu)控制問題 設(shè)線性時變離散系統(tǒng)的狀態(tài)方程和初始條件分別為x(k+1)=G(k)x(k)+H(k)u(k) x(k0)=x0式中,控制量u(k)不受約束。尋找最優(yōu)控制函數(shù)u*(k),使下列二次型性能指標(biāo)泛函為最小式中,F和Q(k)為非負(fù)定矩陣;R(k)為正定矩陣;末態(tài)時刻

45、kf是固定的。,,,時變狀態(tài)調(diào)節(jié)器(3/14),下面討論用動態(tài)規(guī)劃法求解上述離散系統(tǒng)的最優(yōu)控制問題。根據(jù)貝爾曼的動態(tài)規(guī)劃法,求解上述最優(yōu)控制問題需從最后一級開始,由后往前按貝爾曼遞推公式進(jìn)行計算。因此,由貝爾曼遞推方程(198),可得如下線性離散系統(tǒng)的二次型最優(yōu)控制問題的遞推計算公式和邊界條件,,,,時變狀態(tài)調(diào)節(jié)器(4/14),因此,對最后一級應(yīng)有,,,將系統(tǒng)的狀態(tài)方程代入上式,可得,時變狀態(tài)調(diào)節(jié)器(5/14),由于u(k)不受約束

46、,上式對u(k)求極值等價于求解如下方程,,,解得式中,K(kf-1)為如下kf-1時刻的最優(yōu)狀態(tài)反饋矩陣,時變狀態(tài)調(diào)節(jié)器(6/14),將最優(yōu)控制函數(shù)u*(kf-1)代入式(205),則有如下最后一級的最優(yōu)成本函數(shù),,,時變狀態(tài)調(diào)節(jié)器(7/14),定義則式(210)可表示為,,,,時變狀態(tài)調(diào)節(jié)器(8/14),最優(yōu)成本函數(shù)的逆向遞推的邊界條件(204)也可以表示為因此,上述在最后一級應(yīng)用動態(tài)規(guī)劃法的遞推方程所得到的最

47、優(yōu)狀態(tài)反饋矩陣和最優(yōu)成本函數(shù)可總結(jié)為其中,,,,,時變狀態(tài)調(diào)節(jié)器(9/14),依貝爾曼的逆向遞推公式,在倒數(shù)第二級應(yīng)有比較上式和式(205)可以看出,兩式形式上相同。因此,只要注意兩式之間的如下對應(yīng)關(guān)系kf-1?kf , kf-2?kf-1, P(kf-1) ?P(kf)=F就可以類似于最后一級的推導(dǎo),得到在倒數(shù)第二級的如下最優(yōu)控制解的結(jié)論,,,,時變狀態(tài)調(diào)節(jié)器(10/14),其中,,,,時變狀態(tài)調(diào)節(jié)器(11

48、/14),依此類推,我們可以證明如下離散時變系統(tǒng)的二次型性能指標(biāo)最優(yōu)控制問題在倒數(shù)第步的逆向遞推方程,,,,式中,k=kf-1,kf-2,…,0;逆向遞推的邊界條件為,時變狀態(tài)調(diào)節(jié)器(12/14),從上面的推導(dǎo)可知,離散系統(tǒng)的二次型最優(yōu)控制問題的最優(yōu)控制u*(k)是狀態(tài)變量x(k)的線性反饋,其中r×n維矩陣K(k)稱為最優(yōu)狀態(tài)反饋增益矩陣。由上述遞推計算式可知,K(k)只與G(k),H(k),F,Q(k)和R(k)有關(guān),與

49、系統(tǒng)的初始狀態(tài)無關(guān)。因此,由最優(yōu)狀態(tài)反饋律實現(xiàn)最優(yōu)二次型閉環(huán)控制時,可事先離線計算出K(k),在線控制時僅作簡單比例控制運算。,,,,時變狀態(tài)調(diào)節(jié)器(13/14),將反饋增益矩陣K(k)的計算式代入黎卡提矩陣型差分方程,經(jīng)整理可得黎卡提矩陣型差分方程的另一種表示形式其中,,,,,,,時變狀態(tài)調(diào)節(jié)器(14/14),與黎卡提矩陣微分方程相對應(yīng)的,上述關(guān)于P(k)遞推計算的差分方程稱為黎卡提矩陣差分方程。由于矩陣F為非負(fù)定矩陣,因

50、此,可以證明黎卡提矩陣差分方程的解P(k)至少為非負(fù)定的。進(jìn)一步,若矩陣F為正定矩陣,則該差分方程的解P(k)為正定的。,,,,定常狀態(tài)調(diào)節(jié)器(1/8),2. 定常狀態(tài)調(diào)節(jié)器 正如線性定常連續(xù)系統(tǒng)的無限時間定常狀態(tài)調(diào)節(jié)器可由線性時變連續(xù)系統(tǒng)的有限時間狀態(tài)調(diào)節(jié)器令末態(tài)時刻tf??而導(dǎo)出一樣,線性定常離散系統(tǒng)的無限時間定常狀態(tài)調(diào)節(jié)器也可由前面討論的有限時間的線性離散時變系統(tǒng)狀態(tài)調(diào)節(jié)器令末態(tài)時刻kf??導(dǎo)出。下面將給出線性定常離散系統(tǒng)

51、的無限時間定常狀態(tài)調(diào)節(jié)器的有關(guān)結(jié)論。線性定常離散系統(tǒng)的無限時間定常狀態(tài)調(diào)節(jié)器問題的描述如下。,,,定常狀態(tài)調(diào)節(jié)器(2/8),設(shè)狀態(tài)能鎮(zhèn)定的線性定常系統(tǒng)的狀態(tài)方程和初始條件分別為x(k+1)=Gx(k)+Hu(k) x(k0)=x0式中,控制量u(k)不受約束。尋找最優(yōu)控制函數(shù)u*(k),使下列二次型性能指標(biāo)泛函為最小式中,Q為非負(fù)定矩陣;R為正定矩陣。,,,,定常狀態(tài)調(diào)節(jié)器(3/8),由前面討論的有限時間的線性離散系

52、統(tǒng)狀態(tài)調(diào)節(jié)器的逆向遞推解式,令末態(tài)時刻kf??,可得無限時間的離散定常系統(tǒng)狀態(tài)調(diào)節(jié)器問題的控制律,,,,,定常狀態(tài)調(diào)節(jié)器(4/8),從上面的推導(dǎo)可知,離散系統(tǒng)的定常調(diào)節(jié)器問題的最優(yōu)控制u*(k)是狀態(tài)變量x(k)的線性反饋,其中r×n維矩陣K稱為最優(yōu)定常狀態(tài)反饋增益矩陣。由式(232)和式(233)可知,K只與G,H,Q和R有關(guān),與系統(tǒng)的狀態(tài)x(k)無關(guān)。因此,由最優(yōu)狀態(tài)反饋律實現(xiàn)閉環(huán)控制時,可事先離線計算出K,然后可實現(xiàn)

53、定常的最優(yōu)狀態(tài)反饋律。與解線性定常連續(xù)系統(tǒng)的定常狀態(tài)調(diào)節(jié)器問題的黎卡提矩陣型代數(shù)方程相對應(yīng)的,矩陣型代數(shù)方程(233)稱為離散形式的黎卡提矩陣型代數(shù)方程。可以證明,若線性定常離散系統(tǒng)是狀態(tài)能鎮(zhèn)定的,矩陣代數(shù)方程(233)的解P至少為非負(fù)定的。,,,,定常狀態(tài)調(diào)節(jié)器(5/8)—例7-16,例16 已知被控系統(tǒng)x(k+1)=gx(k)+hu(k)求系統(tǒng)在性能指標(biāo)泛函為最小的定常調(diào)節(jié)器的最優(yōu)狀態(tài)反饋律。解 由式(233),