資源描述:
《《動(dòng)態(tài)規(guī)劃》PPT課件》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第五章動(dòng)態(tài)規(guī)劃§1多階段決策過(guò)程及實(shí)例§2動(dòng)態(tài)規(guī)劃的基本概念和基本方程§3動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理§4動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系§1多階段決策過(guò)程及實(shí)例在實(shí)際中,有一類(lèi)問(wèn)題可以看作是一活動(dòng)的過(guò)程,由于它的特殊性,可將過(guò)程分為若干個(gè)相互聯(lián)系階段,在每個(gè)階段都要依據(jù)該階段所處的狀態(tài)作出相應(yīng)的決策,該決策又引起該階段狀態(tài)的轉(zhuǎn)移,決定了下一階段的狀態(tài),當(dāng)每個(gè)階段的決策確定后,由這些決策組成一個(gè)決策序列,即整個(gè)過(guò)程的一條活動(dòng)路線。這類(lèi)活動(dòng)過(guò)程稱(chēng)為多階段決策過(guò)程。這類(lèi)問(wèn)題稱(chēng)為多階段決策問(wèn)題。12n狀態(tài)狀態(tài)狀態(tài)……狀態(tài)狀態(tài)決策決策決策例1最短路線問(wèn)題如下圖,是一線路網(wǎng)絡(luò),兩點(diǎn)之間連線上的數(shù)字
2、表示兩點(diǎn)之間的距離(或費(fèi)用)試求一條由A到G的鋪管線路,使總距離為最短(或總費(fèi)用最?。?狀態(tài)狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策決策23456狀態(tài)狀態(tài)決策決策決策B2C3D2E3F2GB2C3D2E3F2GAV6,6=3AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432V1,6=24V5,6=9V4,6=11V3,6=14V2,6=21V1,6=24例2機(jī)器負(fù)荷分配問(wèn)題某種機(jī)器可以在高低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)u的關(guān)系為在低負(fù)荷下進(jìn)行生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器
3、數(shù)u的關(guān)系為1狀態(tài)狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策決策2345狀態(tài)決策決策u1u2u3u4u5s2s3s4s5s6s1設(shè):§2動(dòng)態(tài)規(guī)劃的基本概念和基本方程2.1動(dòng)態(tài)規(guī)劃的基本概念1.階段把過(guò)程依據(jù)一定的時(shí)間和空間特征恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的階段,以便利用動(dòng)態(tài)規(guī)劃的方法求解。描述階段的變量稱(chēng)為階段變量,用k表示。k=1,2,…,n2.狀態(tài)每個(gè)階段開(kāi)始所處的自然狀況或客觀條件,稱(chēng)為狀態(tài)。狀態(tài)是不可控的,是客觀存在的。描述狀態(tài)的變量稱(chēng)為狀態(tài)變量,用sk表示。狀態(tài)變量可以是一個(gè)數(shù)或一個(gè)向量。狀態(tài)變量sk的取值范圍稱(chēng)為可達(dá)狀態(tài)集合,用Sk表示。例1中,S3={C1,C2,C3,C4}。狀態(tài)變量的性
4、質(zhì)(無(wú)后效性)如果某階段的狀態(tài)給定后,則該階段以后的過(guò)程的發(fā)展不受該階段以前各階段狀態(tài)的影響。即過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響未來(lái)的發(fā)展,當(dāng)前的狀態(tài)是以往歷史的總結(jié),以后發(fā)展的依據(jù)。這個(gè)性質(zhì)稱(chēng)為無(wú)后效性(即馬爾科夫性)。無(wú)后效性的特征:在每個(gè)階段所作的決策只依據(jù)當(dāng)前的狀態(tài),和以往的狀態(tài)無(wú)關(guān)。在選取狀態(tài)變量時(shí),一定要保證狀態(tài)變量具有無(wú)后效性,否則不能利用動(dòng)態(tài)規(guī)劃的方法求解。3.決策在每個(gè)階段所作的決定或選擇稱(chēng)為決策或控制。決策依據(jù)與當(dāng)前狀態(tài),又決定下一階段的狀態(tài)。描述決策的變量稱(chēng)為決策變量,用uk(sk)表示。他是狀態(tài)變量sk的函數(shù)。決策變量的取值范圍稱(chēng)為容許決策集合,用Dk(
5、sk)表示。在例1中D1(A)={B1,B2}D2(B1)={C1,C2,C3},D2(B2)={C2,C3,C4}D4(D1)={E2,E3}在例2中D1(s1)={u1(s1)
6、0≤{u1(s1)≤s1}D2(s2)={u2(s2)
7、0≤{u2(s2)≤s2}Dk(sk)={uk(sk)
8、0≤{uk(sk)≤sk}4.策略按一定順序排列的決策序列集合稱(chēng)為策略。由過(guò)程的第k階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程,稱(chēng)為問(wèn)題的后部子過(guò)程(或稱(chēng)為k子過(guò)程)。由k子過(guò)程的每個(gè)階段的決策函數(shù)組成的決策函數(shù)序列集合{uk(sk),uk+1(sk+1),…,un(sn)}稱(chēng)為k子過(guò)程策略,簡(jiǎn)稱(chēng)為子策略,記
9、為pk,n(sk),即pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}當(dāng)k=1時(shí),此決策函數(shù)序列稱(chēng)為全過(guò)程的一個(gè)策略,簡(jiǎn)稱(chēng)為策略,記為p1,n(s1)。即p1,n(sk)={u1(s1),u2(s2),…,un(sn)}策略的取值范圍稱(chēng)為容許策略集合,用P表示。在P中,使指標(biāo)函數(shù)達(dá)到最優(yōu)的策略稱(chēng)為最優(yōu)策略。例1中,每一條線路就是一個(gè)策略,容許策略集合中有48個(gè)策略。A到G的最短線路就是最優(yōu)策略。5.狀態(tài)轉(zhuǎn)移方程若給定第k個(gè)階段狀態(tài)變量sk的值,該階段的決策變量uk的值一經(jīng)確定,第k+1個(gè)階段的狀態(tài)變量sk+1的值也就完全確定了,即sk+1是sk和uk的函數(shù),
10、記為sk+1=Tk(sk,uk)該函數(shù)描述由第k個(gè)階段到第k+1個(gè)階段的狀態(tài)轉(zhuǎn)移規(guī)律,稱(chēng)為狀態(tài)轉(zhuǎn)移方程。例1中,狀態(tài)轉(zhuǎn)移方程為例2中,狀態(tài)轉(zhuǎn)移方程為6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來(lái)衡量過(guò)程和子過(guò)程(策略和子策略)優(yōu)劣的一種數(shù)量指標(biāo),稱(chēng)為指標(biāo)函數(shù)。它是定義在全過(guò)程和后部子過(guò)程上的數(shù)量函數(shù),用Vk,n表示。即指標(biāo)函數(shù)的性質(zhì):動(dòng)態(tài)規(guī)劃中的指標(biāo)函數(shù)應(yīng)具有可分離性,并滿(mǎn)足地推關(guān)系,常見(jiàn)指標(biāo)函數(shù)的形式(1)過(guò)程和子過(guò)程的指標(biāo)函數(shù)可分解為它所包含的階段的指標(biāo)的和,即(2)過(guò)