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

第七章動態(tài)規(guī)劃法 動態(tài)規(guī)劃是貝爾曼在50年代作為多段決策過程研究出來的 現(xiàn)已在許多技術(shù)領(lǐng)域中獲得廣泛應(yīng)用 動態(tài)規(guī)劃是一種分段最優(yōu)化方法 它既可用來求解約束條件下的函數(shù)極值問題 也可用于求解約束條件下的泛函極值問題 它與極小值原理一樣 是處理控制矢量被限制在一定閉集內(nèi) 求解最優(yōu)控制問題的有效數(shù)學(xué)方法之一 動態(tài)最優(yōu)的核心是最優(yōu)性原理 它首先將一個多段決策問題轉(zhuǎn)化為一系列單段決策問題 然后從最后一段狀態(tài)開始逆向遞推到初始段狀態(tài)為止的一套求解最優(yōu)策略的完整方法 下面先介紹動態(tài)規(guī)劃的基本概念 然后討論連續(xù)型動態(tài)規(guī)劃 一 多段決策問題動態(tài)規(guī)劃是解決多段決策過程優(yōu)化問題的一種強有力的工具 所謂多段決策過程 是指把一個過程按時間或空間順序分為若干段 然后給每一步作出 決策 或控制 以使整個過程取得最優(yōu)的效果 如圖1所示 對于中間的任意一段 例如第k 1段作出相應(yīng)的 決策 或控制 uk后 才能確定該段輸入狀態(tài)與輸出狀態(tài)間的關(guān)系 即從xk變化到xk 1的狀態(tài)轉(zhuǎn)移規(guī)律 在選擇好每一段的 決策 或控制 uk以后 那么整個過程的狀態(tài)轉(zhuǎn)移規(guī)律從x0經(jīng)xk一直到xN也就被完全確定 全部 決策 的總體 稱為 策略 當(dāng)然 如果對每一段的決策都是按照使某種性能指標為最優(yōu)的原則作出的 那么這就是一個多段最優(yōu)決策過程 圖1多段決策過程示意圖 容易理解 在多段決策過程中 每一段 如第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ī)劃求解多段決策問題 設(shè)汽車從A城出發(fā)到B城 途中需穿越三條河流 它們各有兩座橋P Q可供選擇通過 如圖2所示 各段間的行車時間 或里程 費用等 已標注在相應(yīng)段旁 問題是要確定一條最優(yōu)行駛路線 使從A城出發(fā)到B城的行車時間最短 現(xiàn)將A到B分成四段 每一段都要作一最優(yōu)決策 使總過程時間為最短 所以這是一個多段最優(yōu)決策問題 由圖2可知 所有可能的行車路線共有8條 如果將各條路線所需的時間都一一計算出來 并作一比較 便可求得最優(yōu)路線是AQ1P2Q3B 歷時12 這種一一計算的方法稱為窮舉算法 這種方法計算量大 如本例就要做3 23 24次加法和7次比較 如果決策一個n段過程 則共需 n 1 2n 1次加法和 2n 1 1 次比較 可見隨著段數(shù)的增多 計算量將急劇增加 應(yīng)用動態(tài)規(guī)劃法可使計算量減少許多 動態(tài)規(guī)劃法遵循一個最優(yōu)化原則 即所選擇的最優(yōu)路線必須保證其后部子路線是最優(yōu)的 例如在圖2中 如果AQ1P2Q3B是最優(yōu)路線 那么從這條路線上任一中間點到終點之間的一段路線必定也是最優(yōu)的 否則AQ1P2Q3B就不能是最優(yōu)路線了 根據(jù)這一原則 求解最優(yōu)路線問題 最好的辦法就是從終點開始 按時間最短為目標 逐段向前逆推 依次計算出各站至終點之間的時間最優(yōu)值 并據(jù)此決策出每一站的最優(yōu)路線 如在圖2中 從終點B開始逆推 最后一段 第四段 終點B的前站是P3或Q3 不論汽車先從哪一站始發(fā) 行駛路線如何 在這最后一段 總不外乎是從P3到B 歷時為4 或從Q3到B 歷時為2 將其標明在圖3中相應(yīng)的圓圈內(nèi) 比較P3與Q3這一最后一段最優(yōu)決策為Q3B 最后一段 第四段 終點B的前站是P3或Q3 不論汽車先從哪一站始發(fā) 行駛路線如何 在這最后一段 總不外乎是從P3到B 歷時為4 或從Q3到B 歷時為2 將其標明在圖3中相應(yīng)的圓圈內(nèi) 比較P3與Q3這一最后一段最優(yōu)決策為Q3B 第三段 P3 Q3的前站是P2 Q2 在這一段也不論其先后的情況如何 只需對從P2或Q2到B進行最優(yōu)決策 從P2到B有兩條路線 P2P3B 歷時為6 P2Q3B 歷時為4 取最短歷時4 標注在P2旁 從Q2到B也有兩條路線 Q2P3B 歷時為7 Q2Q3B 歷時為5 取最短歷時5 標注在Q2旁 比較P2與Q2的最優(yōu)值 可知這一段的最優(yōu)路線是P2Q3B 第二段 P2 Q2的前站是P1 Q1 同樣不管汽車是如何到達的P1 Q1 重要的是保證從P1或Q1到B要構(gòu)成最優(yōu)路線 從P1到B的兩條路線中 P1P2Q3B 歷時為11 P1Q2Q3B 歷時為11 取最短歷時11 標注在P1旁 從Q1到B的也有兩條路線中 Q1P2Q3B 歷時為8 Q1Q2Q3B 歷時為13 取最短歷時8 標注在Q1旁 比較P1與Q1的最優(yōu)值 可知這一段的最優(yōu)路線是Q1P2Q3B 第一段 P1 Q1的前站是始發(fā)站A 顯見從A到B的最優(yōu)值為12 故得最優(yōu)路線為AQ1P2Q3B 綜上可見 動態(tài)規(guī)劃法的特點是 1 與窮舉算法相比 可使計算量大大減少 如上述最優(yōu)路線問題 用動態(tài)規(guī)劃法只須做10次加法和6次比較 如果過程為n段 則需做加法 以上例為例 用窮舉法需作4608次加法 而后者只需做34次加法 2 最優(yōu)路線的整體決策是從終點開始 采用逆推方法 通過計算 比較各段性能指標 逐段決策逐步延伸完成的 全部最優(yōu)路線的形成過程已充分表達在圖3中 從最后一段開始 通過比較P3 Q3 得到Q3B 倒數(shù)第二段 通過比較P2 Q2 得到P2Q3B 倒數(shù)第三段 通過比較P1 Q1 得到最優(yōu)決策為Q1P2Q3B 直至最后形成最優(yōu)路線AQ1P2Q3B 象這樣將一個多段決策問題轉(zhuǎn)化為多個單段決策的簡單問題來處理 正是動態(tài)規(guī)劃法的重要特點之一 3 動態(tài)規(guī)劃法體現(xiàn)了多段最優(yōu)決策的一個重要規(guī)律 即所謂最優(yōu)性原理 它是動態(tài)規(guī)劃的理論基礎(chǔ) 對圖4所示的N段決策過程 如果在第k 1段處把全過程看成前k段子過程和后N k段子過程兩部分 對于后部子過程來說 xk可看作是由x0及前k段初始決策 或控制 u0 u1 uk 1所形成的初始狀態(tài) 那么 多段決策的最優(yōu)決策略具有這樣的性質(zhì) 不論初始狀態(tài)和初始決策如何 其余 后段 決策 或控制 對于由初始決策所形成的狀態(tài)來說 必定也是一個最優(yōu)策略 這個性質(zhì)稱為最優(yōu)性原理 圖4N段決策過程 設(shè)圖5中x t 是連續(xù)系統(tǒng)的一條最優(yōu)軌線 x t1 是最優(yōu)軌線上的一點 那么最優(yōu)性原理說明 不管t t1 t0 t1 tf時 系統(tǒng)是怎樣轉(zhuǎn)移到狀態(tài)x t1 的 但從x t1 到x tf 這段軌線必定是最優(yōu)的 因為最優(yōu)軌線的后一段從x t1 到x tf 如果還有另一條軌線是最優(yōu)的話 那么原來從x t0 到x tf 的軌線就不是最優(yōu)的 這與假設(shè)矛盾 因此 最優(yōu)性原理成立 應(yīng)用最優(yōu)性原理可以將一個N段最優(yōu)決策問題轉(zhuǎn)化為N個一段最優(yōu)決策問題 從而大大減少求解最優(yōu)決策問題的計算量 圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程 圖5連續(xù)系統(tǒng)的狀態(tài)轉(zhuǎn)移過程 二 連續(xù)系統(tǒng)的動態(tài)規(guī)劃利用動態(tài)規(guī)劃最優(yōu)性原理 可以推導(dǎo)出性能泛函為極小應(yīng)滿足的條件 哈密爾頓 雅可比方程 它是動態(tài)規(guī)劃的連續(xù)形式 解此方程可求得最優(yōu)控制u t 現(xiàn)在來推導(dǎo)這一方程 設(shè)連續(xù)方程為 1 終端約束 使性能泛函 求最優(yōu)控制u t 或u任意 初始狀態(tài) 2 3 4 根據(jù)最優(yōu)性原理 如果x t 是以x t0 為初始狀態(tài)的最優(yōu)軌線 如圖6所示 圖6連續(xù)系統(tǒng)最優(yōu)軌線 5 設(shè)t t t0 t tf 時 狀態(tài)為x t 它將軌線分成前后兩半斷 那么以x t 為初始狀態(tài)的后半段也必是最優(yōu)軌線 而與系統(tǒng)先前如何到達x t 無關(guān) 若取t0 t t t t 式 4 可寫成 根據(jù)最優(yōu)性原理 如果t到tf的過程是最優(yōu)的 則從t t到tf的后部子過程也是最優(yōu)的 其中t t t tf 因此可寫成 6 7 當(dāng) t很小時 有 式 5 可近似表示為 8 5 將x t t 進行泰勒展開 取一次近似 有 9 10 11 將上式在 x t 領(lǐng)域展成泰勒級數(shù) 考慮到J x x t t 既是x的函數(shù) 也與t有關(guān) 所以 12 8 代入式 8 得 13 12 8 考察上式因為J x t 與u無關(guān) 故J x t 與 可提到min號外面 經(jīng)整理可得 式 14 稱為連續(xù)系統(tǒng)動態(tài)規(guī)劃基本方程或貝爾曼方程 14 貝爾曼方程 它是一個關(guān)于J x t 的偏微分方程 解此方程可求得最優(yōu)控制使J為極小 它的邊界條件為 15 14 如果令哈密爾頓函數(shù)為 式中 則式 14 可寫成 17 16 當(dāng)控制矢量u t 不受限制時 則有 上兩式稱為哈密爾頓 雅可比方程 上式說明 在最優(yōu)軌線上 最優(yōu)控制必須使H達全局最小 實際上這就是極小值原理的另一種形式 18 由貝爾曼方程可推導(dǎo)出協(xié)態(tài)方程和橫截條件 式 14 可寫成 對x求偏導(dǎo)數(shù) 得 20 19 14 由于對t的全導(dǎo)數(shù) 為 22 21 代入式 20 可寫成 20 令 則上式可寫成 23 這就是所求的協(xié)態(tài)方程 與以前結(jié)果完全一致 22 在t tf時 在終端處性能泛函為 式中 與N同維的乘子矢量 24 對x tf 求偏導(dǎo)數(shù) 得 25 26 即 24 將式 24 對tf求偏導(dǎo)數(shù) 得 27 24 考慮式 17 式 20 得 上述結(jié)果與極小值原理中推導(dǎo)的完全一致 上述推導(dǎo)過程實際上等于用動態(tài)規(guī)劃方法間接證明了極小值原理 28 17 20 27 應(yīng)當(dāng)指出 與極小值原理相比 動態(tài)規(guī)劃法需要解偏微分方程式 14 它要求J x t 具有連續(xù)的偏導(dǎo)數(shù) 但在實際工程中 這一點常常不能滿足 因而限制了動態(tài)規(guī)劃法的使用范圍 例1 設(shè) 求最優(yōu)控制u t 使 解 構(gòu)造哈密爾頓函數(shù) 根據(jù)哈密爾頓 雅可比方程 有 考慮控制u不受限制 得 故 邊界條件 因 x tf tf 0 故J x tf 0如果令 則得 這正是應(yīng)用極小值原理所得的結(jié)果 二者完全一致 例2 設(shè)受控系統(tǒng)狀態(tài)方程為 初始狀態(tài)為 性能泛函為 試求在u無限制情況下 使J取極小時的最優(yōu)控制 解 構(gòu)造哈密爾頓函數(shù) 由哈密爾頓 雅可比方程 因u無限制 可從 求得 代入上式 并注意到J 與t無關(guān) 因而 有 為求解此偏微分方程 設(shè)其解為 滿足方程 得 各項系數(shù)為 可得 解為 最優(yōu)控制 最優(yōu)控制可由狀態(tài)反饋實現(xiàn) 如圖7所示 進一步考察系統(tǒng)的狀態(tài)軌線 系統(tǒng)的狀態(tài)方程 為齊次方程 它的解為 于是最優(yōu)控制為 性能泛函最優(yōu)值為 例3 設(shè)受控系統(tǒng)的微分方程為 使性能指標 即要求快速響應(yīng) 求最優(yōu)控制u 且滿足 解 若選 可得系統(tǒng)的狀態(tài)方程 根據(jù)哈密爾頓 貝爾曼方程 為使 取全局最小 可得 在所論情況下 因J 與t無關(guān) 故哈密爾頓 貝爾曼方程為 這是一個非線性偏微分方程 需借助電子計算機求解J 再求J 對x2的偏導(dǎo)數(shù)便可求得最優(yōu)控制 綜上所述