《動(dòng)態(tài)規(guī)劃》PPT課件

《《動(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ò)