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

一、動(dòng)態(tài)規(guī)劃方法導(dǎo)引

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

◆用動(dòng)態(tài)規(guī)劃方法逐段求解時(shí)，每個(gè)階段上的求優(yōu)方法基本相同，而5二、動(dòng)態(tài)規(guī)劃解題

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

{x1(s1),x2(s1),…,xn(sn)}。k后部子過(guò)程策略,表示為pk(xk)QTA1A2A3B1B2B3C1C2243746424425146333344.策略和允許策略集合策略(Policy)QTA1A2A3B13(2)允許策略集合記作P。最優(yōu)策略:從允許策略集中，找出的具有最優(yōu)效果的策略。QTA1A2A3B1B2B3C1C224374642442514633334(2)允許策略集合記作P。145.狀態(tài)轉(zhuǎn)移方程(狀態(tài)轉(zhuǎn)移律)：多階段決策過(guò)程的發(fā)展就是用階段狀態(tài)的相繼演變來(lái)描述的?；蚝?jiǎn)寫為5.狀態(tài)轉(zhuǎn)移方程(狀態(tài)轉(zhuǎn)移律)：多階段決策過(guò)程的發(fā)展就是用156.指標(biāo)函數(shù)(1)階段指標(biāo)函數(shù)(也稱階段收益)vk(sk,xk)簡(jiǎn)記為vk

。(2)過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))。Vk,n(sk,xk,sk+1,xk+1,…,sn,xn)。簡(jiǎn)記為Vk,n。6.指標(biāo)函數(shù)(1)階段指標(biāo)函數(shù)(也稱階段收益)(2)過(guò)程指標(biāo)16◆動(dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))，必須具有關(guān)于階段指標(biāo)的可分離形式(和、積或其他形式)：

表示某種運(yùn)算，可為加、減、乘、除、開方等?！魟?dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))，必須具有關(guān)于17◆常見(jiàn)有:和◆常見(jiàn)有:和18相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策賂的各段決策稱為該過(guò)程上的最優(yōu)決策，記為7.最優(yōu)指標(biāo)函數(shù)：fk(sk)

有簡(jiǎn)記為相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)198.概念的關(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+28.概念的關(guān)系。狀態(tài)sk階段k決策xk(sk)vk(sk,20四、最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型1.最優(yōu)化原理(貝爾曼最優(yōu)化原理)

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

則四、最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型1.最優(yōu)化原理(212.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型(逆序法時(shí))(8.3a)(8.3b)2.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型(逆序法時(shí))(8.3a)(8.3b)22(8.3c)(8.3d)或(8.3b)和(8.3d)稱為邊界條件。(8.3c)(8.3d)或(8.3b)和(8.3d)稱為邊界23五、動(dòng)態(tài)規(guī)劃方法的基本步驟1.階段的劃分2.正確地定義狀態(tài)變量sk五、動(dòng)態(tài)規(guī)劃方法的基本步驟1.階段的劃分2.正確地定義狀態(tài)24(1)要能夠正確地描述受控過(guò)程的變化特征。

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

(3)要滿足可知性。(1)要能夠正確地描述受控過(guò)程的變化特征。253.正確地定義決策變量及各階段的允許決策集合Dk(sk)

4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。3.正確地定義決策變量及各階段的允許決策集合Dk(sk)265.根據(jù)題意,正確地構(gòu)造出指標(biāo)函數(shù)，應(yīng)滿足下列性質(zhì)：(1)可分性，。(2)為了進(jìn)行動(dòng)態(tài)規(guī)劃計(jì)算滿足遞推性，或6.確立邊界條件寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程。5.根據(jù)題意,正確地構(gòu)造出指標(biāo)函數(shù)，應(yīng)滿足下列性質(zhì)：或6.確27階段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)解的方向階段1階段2階段k階段k+1階段n……狀態(tài)S1決狀態(tài)S2v128六、動(dòng)態(tài)規(guī)劃的分類離散決策過(guò)程連續(xù)決策過(guò)程根據(jù)多階段決策過(guò)程的時(shí)間參量根據(jù)決策過(guò)程的演變確定性決策過(guò)程隨機(jī)性決策過(guò)程離散確定性決策過(guò)程連續(xù)確定性決策過(guò)程離散隨機(jī)性決策過(guò)程連續(xù)隨機(jī)性決策過(guò)程六、動(dòng)態(tài)規(guī)劃的分類離散連續(xù)根據(jù)多階段決策過(guò)程的根據(jù)決策過(guò)程的29七、學(xué)習(xí)方法建議第一步先看問(wèn)題，充分理解問(wèn)題的條件、情況及求解目標(biāo)。第二步分析針對(duì)該動(dòng)態(tài)規(guī)劃問(wèn)題的“四大要素、一個(gè)方程”。第三步動(dòng)手把求解思路整理出來(lái)，或者說(shuō)，把該問(wèn)題作為習(xí)題獨(dú)立的來(lái)做。七、學(xué)習(xí)方法建議30精品課件！精品課件！31精品課件！精品課件！32第四步把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述。第五步對(duì)照自己的求解，分析成敗。◆動(dòng)態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合sk

Sk②決策變量及其允許集合xkDk

③狀態(tài)轉(zhuǎn)移方程

sk+1=Tk

(sk,xk

)

④階段收益vk

(sk,xk

)

第四步把自己的求解放到一邊，看書中的求解方法，要充分理33一、動(dòng)態(tài)規(guī)劃方法導(dǎo)引

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

◆用動(dòng)態(tài)規(guī)劃方法逐段求解時(shí)，每個(gè)階段上的求優(yōu)方法基本相同，而38二、動(dòng)態(tài)規(guī)劃解題

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

{x1(s1),x2(s1),…,xn(sn)}。k后部子過(guò)程策略,表示為pk(xk)QTA1A2A3B1B2B3C1C2243746424425146333344.策略和允許策略集合策略(Policy)QTA1A2A3B46(2)允許策略集合記作P。最優(yōu)策略:從允許策略集中，找出的具有最優(yōu)效果的策略。QTA1A2A3B1B2B3C1C224374642442514633334(2)允許策略集合記作P。475.狀態(tài)轉(zhuǎn)移方程(狀態(tài)轉(zhuǎn)移律)：多階段決策過(guò)程的發(fā)展就是用階段狀態(tài)的相繼演變來(lái)描述的。或簡(jiǎn)寫為5.狀態(tài)轉(zhuǎn)移方程(狀態(tài)轉(zhuǎn)移律)：多階段決策過(guò)程的發(fā)展就是用486.指標(biāo)函數(shù)(1)階段指標(biāo)函數(shù)(也稱階段收益)vk(sk,xk)簡(jiǎn)記為vk

。(2)過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))。Vk,n(sk,xk,sk+1,xk+1,…,sn,xn)。簡(jiǎn)記為Vk,n。6.指標(biāo)函數(shù)(1)階段指標(biāo)函數(shù)(也稱階段收益)(2)過(guò)程指標(biāo)49◆動(dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))，必須具有關(guān)于階段指標(biāo)的可分離形式(和、積或其他形式)：

表示某種運(yùn)算，可為加、減、乘、除、開方等?！魟?dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)(指標(biāo)函數(shù))，必須具有關(guān)于50◆常見(jiàn)有:和◆常見(jiàn)有:和51相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策賂的各段決策稱為該過(guò)程上的最優(yōu)決策，記為7.最優(yōu)指標(biāo)函數(shù)：fk(sk)

有簡(jiǎn)記為相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)528.概念的關(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+28.概念的關(guān)系。狀態(tài)sk階段k決策xk(sk)vk(sk,53四、最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型1.最優(yōu)化原理(貝爾曼最優(yōu)化原理)

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

則四、最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型1.最優(yōu)化原理(542.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型(逆序法時(shí))(8.3a)(8.3b)2.動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型(逆序法時(shí))(8.3a)(8.3b)55(8.3c)(8.3d)或(8.3b)和(8.3d)稱為邊界條件。(8.3c)(8.3d)或(8.3b)和(8.3d)稱為邊界56五、動(dòng)態(tài)規(guī)劃方法的基本步驟1.階段的劃分2.正確地定義狀態(tài)變量sk五、動(dòng)態(tài)規(guī)劃方法的基本步驟1.階段的劃分2.正確地定義狀態(tài)57(1)要能夠正確地描述受控過(guò)程的變化特征。

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

(3)要滿足可知性。(1)要能夠正確地描述受控過(guò)程的變化特征。583.正確地定義決策變量及各階段的允許決策集合Dk(sk)

4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。3.正確地定義決策變量及各階段的允許決策集合Dk(sk)5