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

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

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

3、條路線(xiàn)和對(duì)應(yīng)的行車(chē)時(shí)間如下,路 線(xiàn) 行車(chē)時(shí)間（小時(shí)） 13 11 14 13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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