第二節(jié) 最優(yōu)化原理與動態(tài)規(guī)劃

第二節(jié)最優(yōu)化原理與動態(tài)規(guī)劃第一頁，共三十二頁，編輯于2023年，星期四一、動態(tài)規(guī)劃方法導(dǎo)引

1.全枚舉法或窮舉法。共有18條可能路線，進(jìn)行比較，求得最優(yōu)路線Q→A3→B1→C1→T。QTA1A2A3B1B2B3C1C224374642442514633334第二頁，共三十二頁，編輯于2023年，星期四2.“局部最優(yōu)路徑”法：選擇當(dāng)前最短途徑，“逢近便走”。所取決策必是Q→A1→B2→C2→T，全程長度是13。QTA1A2A3B1B2B3C1C224374642442514633334第三頁，共三十二頁，編輯于2023年，星期四◆全枚舉法計(jì)算工作量將會十分龐大。◆局部最優(yōu)求出的解不一定是最優(yōu)解。第四頁，共三十二頁，編輯于2023年，星期四3.動態(tài)規(guī)劃方法就是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的方法。解題步驟如下：●把問題劃分為幾個階段?！癜措A段順序首先考慮最后階段如第四階段的最優(yōu)決策，也就是走哪條路線最短?！癜措A段順序依次考慮第三、第二，第一階段的最優(yōu)決策，為此只需確定每一階段上各初始點(diǎn)的最優(yōu)決策即可。第五頁，共三十二頁，編輯于2023年，星期四◆用動態(tài)規(guī)劃方法逐段求解時，每個階段上的求優(yōu)方法基本相同，而且比較簡單，每一階段的計(jì)算都要利用上一階段的計(jì)算結(jié)果，因而減少了很多計(jì)算量。階段數(shù)愈多，這種效果愈明顯。

第六頁，共三十二頁，編輯于2023年，星期四二、動態(tài)規(guī)劃解題

標(biāo)號法：最短路徑：Q→A3→B1→C1→TQTA1A2A3B1B2B3C1C224374642442514633334階段1階段2階段3階段40，T3,T4,T4,C17,C26,C111,B1,B28,B18,B111,A3第七頁，共三十二頁，編輯于2023年，星期四三、動態(tài)規(guī)劃的基本概念。1.階段(stage)和階段變量。把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。QTA1A2A3B1B2B3C1C224374642442514633334第八頁，共三十二頁，編輯于2023年，星期四用以描述階段的變量叫作階段變量，一般以k表示階段量．階段數(shù)k的編號法有兩種：(1)順序編號；(2)逆序編號法。QTA1A2A3B1B2B3C1C224374642442514633334第九頁，共三十二頁，編輯于2023年，星期四2.狀態(tài)(state)、狀態(tài)變量和可能狀態(tài)集(1)狀態(tài)與狀態(tài)變量。QTA1A2A3B1B2B3C1C224374642442514633334第十頁，共三十二頁，編輯于2023年，星期四(2)動態(tài)規(guī)劃維數(shù)。(3)可能狀態(tài)集：用S(sk)表示。QTA1A2A3B1B2B3C1C224374642442514633334第十一頁，共三十二頁，編輯于2023年，星期四3.決策(decision)、決策變量和允許決策集合(1)決策。QTA1A2A3B1B2B3C1C224374642442514633334第十二頁，共三十二頁，編輯于2023年，星期四(2)決策變量:xk=xk(sk)決策變量xk(sk)的允許決策集用Dk(sk)表示,xk(sk)∈Dk(sk)允許決策集合實(shí)際是決策的約束條件。QTA1A2A3B1B2B3C1C224374642442514633334第十三頁，共三十二頁，編輯于2023年，星期四4.策略和允許策略集合策略(Policy)全過程策略指具有n個階段全部過程，簡稱策略。表示為

{x1(s1),x2(s1),…,xn(sn)}。k后部子過程策略,表示為pk(xk)QTA1A2A3B1B2B3C1C224374642442514633334第十四頁，共三十二頁，編輯于2023年，星期四(2)允許策略集合記作P。最優(yōu)策略:從允許策略集中，找出的具有最優(yōu)效果的策略。QTA1A2A3B1B2B3C1C224374642442514633334第十五頁，共三十二頁，編輯于2023年，星期四5.狀態(tài)轉(zhuǎn)移方程(狀態(tài)轉(zhuǎn)移律)：多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的?；蚝唽憺榈谑?，共三十二頁，編輯于2023年，星期四6.指標(biāo)函數(shù)(1)階段指標(biāo)函數(shù)(也稱階段收益)vk(sk,xk)簡記為vk

。(2)過程指標(biāo)函數(shù)(指標(biāo)函數(shù))。Vk,n(sk,xk,sk+1,xk+1,…,sn,xn)。簡記為Vk,n。第十七頁，共三十二頁，編輯于2023年，星期四◆動態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)(指標(biāo)函數(shù))，必須具有關(guān)于階段指標(biāo)的可分離形式(和、積或其他形式)：

表示某種運(yùn)算，可為加、減、乘、除、開方等。第十八頁，共三十二頁，編輯于2023年，星期四◆常見有:和第十九頁，共三十二頁，編輯于2023年，星期四相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為7.最優(yōu)指標(biāo)函數(shù)：fk(sk)

有簡記為第二十頁，共三十二頁，編輯于2023年，星期四8.概念的關(guān)系。狀態(tài)sk階段kT(sk,xk)決策xk(sk)vk(sk,xk)狀態(tài)sk+1階段k+1T(sk+1,xk+1)決策xk+1(sk+1)vk+1(sk+1,xk+1)狀態(tài)sk+2第二十一頁，共三十二頁，編輯于2023年，星期四四、最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型1.最優(yōu)化原理(貝爾曼最優(yōu)化原理)

若某一全過程最優(yōu)策略為：

則第二十二頁，共三十二頁，編輯于2023年，星期四2.動態(tài)規(guī)劃的數(shù)學(xué)模型(逆序法時)(8.3a)(8.3b)第二十三頁，共三十二頁，編輯于2023年，星期四(8.3c)(8.3d)或(8.3b)和(8.3d)稱為邊界條件。第二十四頁，共三十二頁，編輯于2023年，星期四五、動態(tài)規(guī)劃方法的基本步驟1.階段的劃分2.正確地定義狀態(tài)變量sk第二十五頁，共三十二頁，編輯于2023年，星期四(1)要能夠正確地描述受控過程的變化特征。

(2)包含到達(dá)這個狀態(tài)前的足夠信息，且滿足無后效性。

(3)要滿足可知性。第二十六頁，共三十二頁，編輯于2023年，星期四3.正確地定義決策變量及各階段的允許決策集合Dk(sk)

4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。第二十七頁，共三十二頁，編輯于2023年，星期四5.根據(jù)題意,正確地構(gòu)造出指標(biāo)函數(shù)，應(yīng)滿足下列性質(zhì)：(1)可分性，。(2)為了進(jìn)行動態(tài)規(guī)劃計(jì)算滿足遞推性，或6.確立邊界條件寫出動態(tài)規(guī)劃函數(shù)基本方程。第二十八頁，共三十二頁，編輯于2023年，星期四階段1階段2階段k階段k+1階段n……狀態(tài)S1決策x1狀態(tài)S2v1決策x2狀態(tài)S3v2決策xk狀態(tài)Sk+1vk決策xk+1vk+1決策xnvn尋求最優(yōu)解的方向第二十九頁，共三十二頁，編輯于2023年，星期四六、動態(tài)規(guī)劃的分類離散決策過程連續(xù)決策過程根據(jù)多階段決策過程的時間參量根據(jù)決策過程的演變確定性決策過程隨機(jī)性決策過程離散確定性決策過程連續(xù)確定性決策過程離散隨機(jī)性決策過程連續(xù)隨機(jī)性決策過程第三十頁，共三十二頁，編輯于2023年，星期四七、學(xué)習(xí)方法建議第一步先看問題，充分理解問題的條件、情況及求解目標(biāo)。第二步分析針對該動態(tài)規(guī)劃問題的“四大要素、一個方程”。第三步動手把求解思路整理出來，或者說，把該問題作為習(xí)題獨(dú)立的來做。第三十一頁，共三十二頁，編輯于2023年，星期四第四步把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述。第五步對照自己的求解，分析成敗?！魟討B(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合sk

Sk