ppt第六章動態(tài)規(guī)劃

1、6.1 多級決策的例子——最短時間問題6.2 最優(yōu)性原理6.3 用動態(tài)規(guī)劃解資源分配問題6.4 用動態(tài)規(guī)劃求離散最優(yōu)控制6.5 連續(xù)系統(tǒng)的動態(tài)規(guī)劃6.6 動態(tài)規(guī)劃與極小值原理6.7 小結(jié),第六章 動態(tài)規(guī)劃,動態(tài)規(guī)劃是貝爾曼(Bellman)在五十年代為解決多級決策過程而提出來的。它可以解決很多領(lǐng)域中的問題，如生產(chǎn)過程的決策，收益和投資問題，有多級反應(yīng)器的化工裝置的設(shè)計，多級軋鋼機的最速軋制問題，資源分配、機

2、器負荷分配、生產(chǎn)計劃編制，特別是控制工程問題。,,,它和極小值原理一樣，可解決控制變量受約束的最優(yōu)控制問題，而且在這兩種方法之間存在某種內(nèi)在的聯(lián)系。動態(tài)規(guī)劃的中心思想是利用所謂“最優(yōu)性原理”，把一個 級決策過程化為 個單級決策過程，從而使問題簡單。,6.1 多級決策的例子——最短時間問題,,,,圖6-1 按最短時間的路徑選擇,（一）窮舉法,,,,從 走到 一共有六條路線，每條路線由四段組成。這六

3、條路線和對應(yīng)的行車時間如下,路 線 行車時間（小時） 13 11 14 13

4、12 9,,,,,,,,顯然最優(yōu)路線是 ，它所花時間為9小時。,這里每條路線由四段組成，也可以說是四級決策。 為了計算每條路線所花時間，要做三次加法運算，為了計算六條路線所花的時間要作3×6=18次運算。這種方法稱為“窮舉法”。 顯然當段數(shù)很多時，計算量是很大的。這種方法的特點是從起點站往前進行，而且把這四級決策一起考

5、慮。應(yīng)注意從到 下一站 所花的時間為1，而到 所花時間為3，但最優(yōu)路線卻不經(jīng)過 。 這說明只看下一步的“眼前利益”來作決策是沒有意義的。,,,,,（二）動態(tài)規(guī)劃法,為將問題表達得清楚，引進下面的術(shù)語。,,,,,,令 表示由某點 到終點的段數(shù)（如 到 為2段）。,,,令 表示當前所處點的位置（如 ），稱為狀態(tài)變量。,令 為決策（控制）變量，它表示當

6、處在 位置而還有 段要走時，所要選取的下一點。例如，從 出發(fā)，下一點為 時，則表示為 。,,,,,,,,令 表示從點 到點 的時間。例如，從 到 的時間為,,,有了這些術(shù)語后，就可用動態(tài)規(guī)劃來解這個例子。從最后一段出發(fā)進行計算，并將計算出的最短時間 用括號表示在相應(yīng)的點 處（見圖

7、6-1）。,1 （倒數(shù)第一段）,,,,考慮從 和 到 的路線，由定義可知，最短時間分別為,,,n=1,2（倒數(shù)第二段）,,,,,,,,,,考慮從 、 或 到 的路線。由 到 有兩種路線： ， 。兩種路線中的最短時間由下式確定：,,最優(yōu)決策為 。,,,,,由 到

8、 只有一種路線 ，其時間為,,,,3（倒數(shù)第三段）,,,,考慮從B1或B2到E的路線。B1到E有兩種路線： 和 。最短時間為,,,最優(yōu)決策,,,從B2到E有兩種路線： 和 。最短時間為,,,最優(yōu)決策為 。,4（倒數(shù)第四段）,,,,,從 到 的路線有兩種： 和 。最短時間為：,,,最優(yōu)決策為

9、 。,,至此求出了A到E的最短時間為9，最優(yōu)路線為 。在圖6-1中用粗線表示。這里，為決定最優(yōu)路線進行了10次加法，比窮舉法的18次少了8次。當段數(shù)n更多時，節(jié)省計算將會更多。,,,,,,從上面解題過程可見，動態(tài)規(guī)劃解題的兩個特點：它是從最后一級往后倒著計算的；它把一個 級決策問題（這里是決定一整條路線）化為 個單級決策問題，即把一個復雜問題化為多個簡單問題來求解。我

10、們可看出 階段與 階段有下面的關(guān)系（ ）,,（6-1）,,,（表示最后一級）,,,,,(6-1)式稱為函數(shù)方程，從(6-1)式可見,在選擇了決策 后有兩個影響，其一是直接影響下一段的時間（眼前利益），其二是影響以后 段的最短時間 （未來利益）。因此動態(tài)規(guī)劃方法可以說是把眼前利益和未來利益區(qū)分開來又結(jié)合

11、起來考慮的一種優(yōu)化方法。這些特點都是由動態(tài)規(guī)劃法的基本原理——最優(yōu)性原理所決定的。,6.2 最優(yōu)性原理,貝爾曼的最優(yōu)性原理可敘述如下：“一個多級決策問題的最優(yōu)決策具有這樣的性質(zhì)：當把其中任何一級及其狀態(tài)作為初始級和初始狀態(tài)時，則不管初始狀態(tài)是什么，達到這個初始狀態(tài)的決策是什么，余下的決策對此初始狀態(tài)必定構(gòu)成最優(yōu)策略?！?,,,,,,,,,,以上面的最短時間問題為例，如把 當作初始狀態(tài)，則余下的決策 2E對 來講是最優(yōu)

12、策略；如把 當初始狀態(tài)，則余下的決策 對 來講也構(gòu)成最優(yōu)策略。一般來說，如果一個最優(yōu)過程用狀態(tài) 來表示，最優(yōu)決策為 ，則對狀態(tài) 來講， 必定是最優(yōu)的，這可用圖6-2來表示。,,圖6-2 最優(yōu)性原理示意圖,,,在多數(shù)實際問題中， 級決策的性能指標 取如下形式,,,,,,,是由某級狀態(tài)和決策決定的性能函數(shù)，要求尋找決策

13、 使J取極小值 。,最優(yōu)性原理可表示為,,（6-2）,,,,,,根據(jù)上式就可證明最優(yōu)性原理的正確性。若以 為初態(tài)時，余下的決策 不是最優(yōu)的，那么就存在另一決策序列 所決定的指標值 ，于是,,,這與 是極小值發(fā)生矛

14、盾，所以余下的決策必須是最優(yōu)的。,,,,（6-1）式的函數(shù)方程與（6-2）式所表示的最優(yōu)性原理是一致的，只是表示方法不同。（6-1）式中 的下標n表示離終點的級數(shù)，（6-2）式中 的下標 表示離起點的級數(shù)。兩式的對照留給讀者去做。,,（6-3）,,由上式可見，最優(yōu)化的過程是從最里面的方括號開始向外擴展的，即尋找最優(yōu)控制的次序是

15、 。因此根據(jù)最優(yōu)性原理，動態(tài)規(guī)劃是從最后一級倒退計算的。,將（6-2）式進一步分解為,6.3 用動態(tài)規(guī)劃解資源分配問題,,,,,,,,我們提到過，動態(tài)規(guī)劃的應(yīng)用范圍是非常廣的。這里介紹用動態(tài)規(guī)劃解決資源分配問題。假定有 種資源用來生產(chǎn) 種產(chǎn)品（資源可以指工人、機床、資金等，每種資源的總數(shù)為 ）。如果生產(chǎn)第 種產(chǎn)品時投入的各種資源量為

16、 則可以得到的收益為 ，它是所分配的資源量的函數(shù)，可寫成 ?，F(xiàn)在問應(yīng)如何分配這些資源到各個產(chǎn)品上，使得所有產(chǎn)品的總收益為最大？,,,（6-4）,取最大，其中滿足約束,,,（6-5）,,,（6-6）,寫成數(shù)學形式，即要使,,,,,上面的問題可以用動態(tài)規(guī)劃求解。為了說明問題簡單起見，這里只考慮單資源分配問題，即如何將一種資源分配給 種產(chǎn)品，使總收益最大。

17、設(shè)這種資源的總數(shù)為 ，分配給第 種產(chǎn)品的數(shù)量為 ，則性能指標為,,,（6-7）,取最大，約束條件是,,,（6-8）,,,,,,為了用動態(tài)規(guī)劃求解，引進一個函數(shù) ，它表示將資源量 分配給第1至第 種產(chǎn)品時所能得到的最大收益。顯然 表示將總資源 分配到所有 種產(chǎn)品上所得到的最大收益，即,,,（6-9）,容易看出，函數(shù) 有下列

18、性質(zhì),,,即沒有資源投入時收益為零。,,,這表明將資源量只用于生產(chǎn)一種產(chǎn)品時的總收益，就是這種產(chǎn)品本身收益。,即不生產(chǎn)產(chǎn)品時收益為零。,這些性質(zhì)構(gòu)成了以后解題的邊界的條件。,,,,,,,,,,,,,,,,如果把 種產(chǎn)品的資源分配看成是 步?jīng)Q策，則 表示 步?jīng)Q策的指標最優(yōu)值， 表示用決策量 時第

19、 步的指標值， 表示余下 步?jīng)Q策的指標最優(yōu)值，根據(jù)最優(yōu)性原理（對照（6-2）式），則有,,（6-10）,,,,,,,這表明若 在第1至 種產(chǎn)品上的最優(yōu)分配為 ，則 一定是資源量 在前 -1種產(chǎn)品上的最優(yōu)分配。,例1-1,,,,,解 由邊界條件知 。現(xiàn)在慮 ， 它表示用1個單元資源

20、分配到2個產(chǎn)品上的最大收益。 表示投入第2個產(chǎn)品的資源，則 可取值1或0，對應(yīng)地將有下表。,,,,,,,,,,,根據(jù)（6-10）式可得,,同理，當可取值3，2，1，0時可求得,,再考慮3個產(chǎn)品的資源分配，可得這三個產(chǎn)品投入資源的單元數(shù)為1，2，3，4時的，最優(yōu)值如下,,,即把一個單元的資源分配給第三種產(chǎn)品，把三個單元的資源分配給第一種產(chǎn)品，第二種產(chǎn)品不分配資源，這時總收益達最大值28。,可見,6.4 用動態(tài)規(guī)劃

21、求離散最優(yōu)控制,離散系統(tǒng)的狀態(tài)方程為,,,（6-11）,性能指標為,,（6-12）,例6-2,系統(tǒng)方程為,,,給定 （6-13）,,（6-14）,,要求用動態(tài)規(guī)劃尋找最優(yōu)控制序列 使J最小。,,,,求 使 最小，得,,這個結(jié)果與例5-4用離散極小值原理求解結(jié)果完全一樣。,于是最優(yōu)性能指標與最優(yōu)狀態(tài)轉(zhuǎn)移為,6.5 連續(xù)系統(tǒng)的動態(tài)規(guī)劃,設(shè)系統(tǒng)的狀態(tài)方程和性能指標為,,,,,,,,受約束，可

22、寫成 為某一閉集。要尋找滿足此約束且使 最小的最優(yōu)控制 。,,（6-21）,,顯然 滿足終端條件,,,,,,通常假定 對 及 的二階偏導數(shù)存在且有界。,,（6-23）,根據(jù)最優(yōu)性原理，從 也應(yīng)是最優(yōu)過程。,,,因 故,,這樣，式（6-23）可寫

23、成,,（6-24）,,,,,從上式兩端消去 ，除以 ，再令 ，可得,,（6-25）,引用以前使用過的哈密頓函數(shù),（6-26）,（6-27）,則（6-25）可寫成,（6-28）,（6-25）或（6-28）稱為哈密頓—雅可比—貝爾曼方程，邊界條件是（6-22）式。哈密頓—雅可比—貝爾曼方程在理論上很有價值，但它是 的一階偏微分方程并帶有取極小的運算，因此求解是非常困難的，一般情況得不到解析解，只能用

24、計算機求數(shù)值解。對于線性二次問題，可以得到解析解，而且求解結(jié)果與用極小值原理或變分法所得結(jié)果相同。這時，哈密頓——雅可比——貝爾曼方程可歸結(jié)為黎卡提方程。在實際計算線性二次問題時，一般用直接求解黎卡提方程來求最優(yōu)控制。,,6.6 動態(tài)規(guī)劃與極小值原理,動態(tài)規(guī)劃和極小值原理是最優(yōu)控制理論的兩大基石，它們都可以解決有約束的最優(yōu)控制問題，雖然在形式上和解題方法上不同，但卻存在著內(nèi)在的聯(lián)系。下面我們從動態(tài)規(guī)劃來推演極小值原理，不過要說明這種推

25、演是基于最優(yōu)指標對和兩次連續(xù)可微這個條件的。,于是最優(yōu)性能指標與最優(yōu)狀態(tài)轉(zhuǎn)移為,,,（6-29）,,要求確定 使性能指標,,（6-30）,,極小。其中， 固定， 自由， 可以有約束，也可以沒有。,,,1、 （狀態(tài)方程） （6-31）,,2、 （協(xié)態(tài)方程） （6-32）,,3、 （邊界方程）

26、 （6-33）,,4、 （橫截條件） （6-34）,,5、 （極值條件） （6-35）,,用動態(tài)規(guī)劃求解的結(jié)果已在上節(jié)中得到，現(xiàn)在歸納一下：在動態(tài)規(guī)劃中協(xié)態(tài)變量 滿足,,,,哈密頓—雅可比—貝爾曼方程（6-28）本身說明了哈密頓函數(shù)在最優(yōu)控制上取極值的條件，故等同于上面極小值原理所得的條件5，不過（6-28）還多給出了一

27、點信息，即 。,下面由動態(tài)規(guī)劃法來推出協(xié)態(tài)方程。,由（6-27）,,,,因假設(shè)對兩次連續(xù)可微，因此上式成立，且可交換求導次序，得,,即協(xié)態(tài)方程（6-32）（因都是最優(yōu)解條件。故省去*號）。由（6-22）和（6-27）再來推橫截條件,,,,6.7 小結(jié),1. 動態(tài)規(guī)劃是把多級決策問題化為多個單級決策問題來求解的，而單級問題比多級問題容易處理得多。這種把一個復雜的特定問題化為（又可稱為嵌入）一系列性質(zhì)

28、相似的易于求解的問題的做法稱為“不變嵌入”法。,2. 動態(tài)規(guī)劃的基礎(chǔ)是最優(yōu)性原理。這個原理告訴我們：在多級最優(yōu)決策中，不管初始狀態(tài)是什么，余下的決策對此狀態(tài)必定構(gòu)成最優(yōu)決策。根據(jù)這個原理，動態(tài)規(guī)劃解決多級決策問題（包括離散系統(tǒng)最優(yōu)控制）是從最后一級開始倒向計算的。,,,3. 連續(xù)系統(tǒng)的動態(tài)規(guī)劃可導出哈密頓——雅可比——貝爾曼方程，這個方程一般只能有數(shù)值解。從它可推演出極小值原理，不過要假定 , 二次連