運(yùn)籌學(xué)第五章

1、1,運(yùn)籌學(xué).,運(yùn)籌學(xué),動(dòng)態(tài)規(guī)劃,2,多階段決策過(guò)程的最優(yōu)化動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃方法的基本步驟動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,本章內(nèi)容重點(diǎn),3,一、多階段決策問(wèn)題(Multi-Stage decision process)多階段決策過(guò)程特點(diǎn):,1.多階段決策過(guò)程的最優(yōu)化,4,1.多階段決策過(guò)程的最優(yōu)化,動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。然而它也

2、可以處理與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題，只要在問(wèn)題中人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題。在本章中將介紹這種處理方法。,5,1.多階段決策過(guò)程的最優(yōu)化,二、多階段決策問(wèn)題舉例 屬于多階段決策類(lèi)的問(wèn)題很多，例如： 1)工廠生產(chǎn)過(guò)程：由于市場(chǎng)需求是一隨著時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，逐月或者逐季度地根據(jù)庫(kù)存和需求情況決定生產(chǎn)計(jì)劃安排。,6,1.多階段決

3、策過(guò)程的最優(yōu)化,2)設(shè)備更新問(wèn)題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買(mǎi)來(lái)時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓?zhuān)幚韮r(jià)值也高，隨著使用年限的增加，就會(huì)逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長(zhǎng)、處理價(jià)值也越低，自然，如果賣(mài)去舊的買(mǎi)新的，還需要付出更新費(fèi)．因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。,7,1.多階段決策過(guò)程的最優(yōu)化,3)連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題：一般化工生產(chǎn)過(guò)程中

4、，常包含一系列完成生產(chǎn)過(guò)程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。,8,1.多階段決策過(guò)程的最優(yōu)化,以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，因此在這類(lèi)多階段決策問(wèn)題中，階段的劃分常取時(shí)間區(qū)段來(lái)表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)”的含義，所以把處理這類(lèi)動(dòng)態(tài)問(wèn)題的方法稱(chēng)為動(dòng)態(tài)規(guī)劃方法。不過(guò)，實(shí)際中尚有許多不包含時(shí)

5、間因素的一類(lèi)“靜態(tài)”決策問(wèn)題，就其本質(zhì)而言是一次決策問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。,9,1.多階段決策過(guò)程的最優(yōu)化,4）資源分配問(wèn)題：便屬于這類(lèi)靜態(tài)問(wèn)題。如：某工業(yè)部門(mén)或公司，擬對(duì)其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問(wèn)題原本要求一次確定出對(duì)各企業(yè)的資源分配量，它與時(shí)間因素?zé)o關(guān)，不屬動(dòng)態(tài)決策，但是，我們可以人為地規(guī)定一個(gè)資源分配的階段和

6、順序，從而使其變成一個(gè)多階段決策問(wèn)題(后面我們將詳細(xì)討論這個(gè)問(wèn)題)。,10,1.多階段決策過(guò)程的最優(yōu)化,5）運(yùn)輸網(wǎng)絡(luò)問(wèn)題：如圖5-1所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從fk(sk)至v10的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。,11,1.多階段決策過(guò)程的最優(yōu)化,圖5-11 運(yùn)輸網(wǎng)絡(luò)圖示,12,1.多階段

7、決策過(guò)程的最優(yōu)化,三、動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題的特點(diǎn) 通常多階段決策過(guò)程的發(fā)展是通過(guò)狀態(tài)的一系列變換來(lái)實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過(guò)去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問(wèn)題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類(lèi)特殊的多階段決策問(wèn)題，即具有“無(wú)后效性”的多階段決策過(guò)程。所謂無(wú)后效性，又稱(chēng)馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其

8、往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無(wú)關(guān)。,13,1.多階段決策過(guò)程的最優(yōu)化,四、動(dòng)態(tài)規(guī)劃方法導(dǎo)引 例5.1：為了說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖5-1所示為例討論的求最短路問(wèn)題的方法。 第一種方法稱(chēng)做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對(duì)它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一段的走法有三種，第二三兩段的走法各有兩種，

9、第四段的走法僅一種，因此共有3×2×2×1＝12條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1 →v3 → v7 → v9 →v10 ,最短距離是18．,14,1.多階段決策過(guò)程的最優(yōu)化,顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算． 第二種方法即所謂“局部最優(yōu)路徑”法，是說(shuō)某人從k出發(fā)，他并不顧及全線是否最短，

10、只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1 →v3 →v5 → v8 → v10 ，全程長(zhǎng)度是20；顯然，這種方法的結(jié)果常是錯(cuò)誤的．,15,1.多階段決策過(guò)程的最優(yōu)化,第三種方法是動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃方法尋求該最短路問(wèn)題的基本思想是，首先將問(wèn)題劃分為4個(gè)階段，每次的選擇總是綜合后繼過(guò)程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得的情況下，全程的最優(yōu)路線便也隨之

11、得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過(guò)程，動(dòng)態(tài)規(guī)劃方法總是從過(guò)程的最后階段開(kāi)始考慮，然后逆著實(shí)際過(guò)程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。,,16,1.多階段決策過(guò)程的最優(yōu)化,具體說(shuō)，此問(wèn)題先從v10開(kāi)始，因?yàn)関10是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第4階段上所有可能狀態(tài)v8 ,v9的最優(yōu)后續(xù)過(guò)程．因?yàn)閺膙8 ,v9 到v10的路線是唯一的，所以v8 ,v9 的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到v10 ，它們的最短距離分別是5

12、和3。 接著考慮階段3上可能的狀態(tài)v5 ,v6 , v7 , 到v10的最優(yōu)決策和最優(yōu)后繼過(guò)程．在狀態(tài)V5上，雖然到v8是8，到v9是9，但是綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到v9,最優(yōu)后繼過(guò)程是v5→v9 → v10 ，最短距離是12．同理，狀態(tài)v6的最優(yōu)決策是至v8 ；v7的最優(yōu)決策是到v9 。,17,1.多階段決策過(guò)程的最優(yōu)化,同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段2上所有可能狀

13、態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如v2的最優(yōu)決策是到v5,最優(yōu)路線是v2→v5→v9→v10 ，最短距離是15…依此類(lèi)推，最后可以得到從初始狀態(tài)v1的最優(yōu)決策是到v3最優(yōu)路線是v1→v3→v7→v9→v10 ，全程的最短距離是18。圖5—1中粗實(shí)線表示各點(diǎn)到的最優(yōu)路線，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。,18,1.多階段決策過(guò)程的最優(yōu)化,綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有

14、動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問(wèn)題分解為一系列同類(lèi)型的更易求解的子問(wèn)題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過(guò)程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問(wèn)題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個(gè)問(wèn)題的最優(yōu)策略和最優(yōu)路線。計(jì)算過(guò)程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。,19,2.動(dòng)態(tài)規(guī)劃的基本概念,一、動(dòng)態(tài)規(guī)劃的基本概念 使用動(dòng)態(tài)規(guī)劃方法解

15、決多階段決策問(wèn)題，首先要將實(shí)際問(wèn)題寫(xiě)成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對(duì)動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語(yǔ)進(jìn)一步加以說(shuō)明和定義：,20,2.動(dòng)態(tài)規(guī)劃的基本概念,(一) 階段和階段變量 為了便于求解和表示決策及過(guò)程的發(fā)展順序，而把所給問(wèn)題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問(wèn)題，稱(chēng)之為多段決策問(wèn)題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問(wèn)題，通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量

16、叫作階段變量，一般以k表示階段變量．階段數(shù)等于多段決策過(guò)程從開(kāi)始到結(jié)束所需作出決策的數(shù)目，圖5—1所示的最短路問(wèn)題就是一個(gè)四階段決策過(guò)程。,21,2.動(dòng)態(tài)規(guī)劃的基本概念,（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集 1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱(chēng)為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過(guò)程進(jìn)行的先后，每個(gè)階段的狀態(tài)

17、可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱(chēng)輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見(jiàn)，通常定義階段的狀態(tài)即指其初始狀態(tài)。,22,2.動(dòng)態(tài)規(guī)劃的基本概念,2．可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱(chēng)為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫(xiě)字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間

18、，視具體問(wèn)題而定．在圖5—1所示的最短路問(wèn)題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1={v1}；第二階段則有三個(gè)狀態(tài)：v2 ,v3 ,v4 ,狀態(tài)變量s2的狀態(tài)集合S2={v2 ,v3 ,v4} ；第三階段也有三個(gè)狀態(tài):v5 ,v6 ,v7 ，狀態(tài)變量s3的狀態(tài)集合S3={v5 ,v6 ,v7} ；第四階段則有二個(gè)狀態(tài)： v8 ,v9 , 狀態(tài)變量s4的狀態(tài)集合S4={v8 ,v9} ；,23,（三）決策、決策變量和允許決策集

19、合 所謂決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱(chēng)之決策變量和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k= uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱(chēng)之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)

20、表示, uk(sk)∈ Uk(sk)允許決策集合實(shí)際是決策的約束條件。,2.動(dòng)態(tài)規(guī)劃的基本概念,24,（四）、策略和允許策略集合 策略(Policy)也叫決策序列．策略有全過(guò)程策略和k部子策略之分，全過(guò)程策略是指具有n個(gè)階段的全部過(guò)程，由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列，簡(jiǎn)稱(chēng)策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱(chēng)為k部子策略,表示為pk,n{uk,uk+1,…

21、,un} ，顯然當(dāng)k=1時(shí)的k部子策略就是全過(guò)程策略。 在實(shí)際問(wèn)題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱(chēng)之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱(chēng)為最優(yōu)策略。,2.動(dòng)態(tài)規(guī)劃的基本概念,25,（五）狀態(tài)轉(zhuǎn)移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)

22、移到終止?fàn)顟B(tài)sk+1 ，或者說(shuō)，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1 ，多階段決策過(guò)程的發(fā)展就是用階段狀態(tài)的相繼演變來(lái)描述的。 對(duì)于具有無(wú)后效性的多階段決策過(guò)程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過(guò)去的狀態(tài)s1,s2,… ,sk-1及其決策u1(s1), u2(s2)…uk-1(sk-1)無(wú)關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：,2.動(dòng)態(tài)規(guī)劃的基本

23、概念,,(5-1),26,通常稱(chēng)式(5-1)為多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程。有些問(wèn)題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。 (六) 指標(biāo)函數(shù) 用來(lái)衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱(chēng)為指標(biāo)函數(shù)。它是定義在全過(guò)程或各子過(guò)程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問(wèn)題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。例如：圖5—1的指標(biāo)就是運(yùn)費(fèi)。

24、,2.動(dòng)態(tài)規(guī)劃的基本概念,27,(1)階段指標(biāo)函數(shù)（也稱(chēng)階段效應(yīng)）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為gk 。圖5-1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3,即v2到v5的距離為3。 (2)過(guò)程指標(biāo)函數(shù)（也稱(chēng)目標(biāo)函數(shù)）。用Rk(sk,uk)表示第k子過(guò)程的指標(biāo)函數(shù)。如圖5-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作

25、決策為uk時(shí)，從sk點(diǎn)到終點(diǎn)v10的距離。由此可見(jiàn)，Rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過(guò)程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴(yán)格說(shuō)來(lái)，應(yīng)表示為:,2.動(dòng)態(tài)規(guī)劃的基本概念,,28,不過(guò)實(shí)際應(yīng)用中往往表示為Rk(sk,uk)或Rk(sk)。還跟第k子過(guò)程上各段指標(biāo)函數(shù)有關(guān)，過(guò)程指標(biāo)函數(shù)Rk(sk)通常是描述所實(shí)現(xiàn)的全過(guò)程或k后部子過(guò)程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)gk(sk,uk)累積形

26、成的，適于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題的過(guò)程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式．對(duì)于部子過(guò)程的指標(biāo)函數(shù)可以表示為： 式中，?表示某種運(yùn)算，可以是加、減、乘、除、開(kāi)方等。,2.動(dòng)態(tài)規(guī)劃的基本概念,,(5-2),29,多階段決策問(wèn)題中，常見(jiàn)的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:

27、 (5-3) 有些問(wèn)題，如系統(tǒng)可靠性問(wèn)題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如： (5-4) 總之，具體問(wèn)題的目標(biāo)函數(shù)表達(dá)形式需要視具體問(wèn)題而定。,2.動(dòng)態(tài)規(guī)劃的基本概念,,,30,(七) 最優(yōu)解 用fk(sk)表示第k子過(guò)

28、程指標(biāo)函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱(chēng)fk(sk)為第k子過(guò)程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略稱(chēng)為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk) ；而構(gòu)成該子策賂的各段決策稱(chēng)為該過(guò)程上的最優(yōu)決策，記為 ；有 簡(jiǎn)記為,2.動(dòng)態(tài)規(guī)劃的基本概念,,,,,31,特別當(dāng)k=1且s1取值唯一時(shí)，f1(s1)就是問(wèn)題的最優(yōu)值，而p1*就是最優(yōu)策略。如例只有唯一始點(diǎn)v1即s1取值唯一

29、,故f1(s1)=18就是例的最優(yōu)值，而 就是例的最優(yōu)策略。 但若取值不唯一,則問(wèn)題的最優(yōu)值記為f0有 最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略： 我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱(chēng)為問(wèn)題的最 優(yōu)解。,2.動(dòng)態(tài)規(guī)劃的基本概念,,,,,,,,32,按上述定義，所謂最優(yōu)決策是指它們?cè)谌^(guò)程上整體最優(yōu)(即所構(gòu)成的全過(guò)程策略為最優(yōu))，而不一定在各階段上單獨(dú)最優(yōu)。 (八) 多階段決策問(wèn)題的數(shù)學(xué)模型

30、 綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類(lèi)多階段決策問(wèn)題，亦即具有無(wú)后效性的多階段決策問(wèn)題的數(shù)學(xué)模型呈以下形式:,2.動(dòng)態(tài)規(guī)劃的基本概念,（5-5）,33,式中“OPT”表示最優(yōu)化，視具體問(wèn)題取max或min。 上述數(shù)學(xué)模型說(shuō)明了對(duì)于給定的多階段決策過(guò)程，求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列 ，使之既滿(mǎn)足式(5-5)給出的全部約束條件，又使式(5-5

31、)所示的目標(biāo)函數(shù)取得極值，并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí)，過(guò)程狀態(tài)演變序列即最優(yōu)路線,2.動(dòng)態(tài)規(guī)劃的基本概念,34,二、動(dòng)態(tài)規(guī)劃的最優(yōu)化原理與基本方程 1．標(biāo)號(hào)法 為進(jìn)一步闡明動(dòng)態(tài)規(guī)劃方法的基本思路，我們介紹一種只適用于例這類(lèi)最優(yōu)路線問(wèn)題的特殊解法——標(biāo)號(hào)法。標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過(guò)分段標(biāo)號(hào)來(lái)求出最優(yōu)路線的一種簡(jiǎn)便、直觀的方法。通常標(biāo)號(hào)法采取“逆序求解”的方法來(lái)尋找問(wèn)題的最優(yōu)解，即從最后階段開(kāi)始，逐次向階段數(shù)小的方向

32、推算，最終求得全局最優(yōu)解。,2.動(dòng)態(tài)規(guī)劃的基本原理,35,下面給出標(biāo)號(hào)法的一般步驟： 1.從最后一段標(biāo)起，該段各狀態(tài)(即各始點(diǎn))到終點(diǎn)的距離用數(shù)字分別標(biāo)在各點(diǎn)上方的方格內(nèi)，并用粗箭線連接各點(diǎn)和終點(diǎn)。 2.向前遞推，給前一階段的各個(gè)狀態(tài)標(biāo)號(hào)。每個(gè)狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點(diǎn)的最短距離。即為該狀態(tài)到該階段已標(biāo)號(hào)的各終點(diǎn)的段長(zhǎng)，再分別加上對(duì)應(yīng)終點(diǎn)上方的數(shù)字而取其最小者。將剛標(biāo)號(hào)的點(diǎn)沿著最短距

33、離所對(duì)應(yīng)的已標(biāo)號(hào)的點(diǎn)用粗箭線連接起來(lái)，表示出各剛標(biāo)號(hào)的點(diǎn)到終點(diǎn)的最短路線。,2.動(dòng)態(tài)規(guī)劃的基本原理,36,3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點(diǎn))也標(biāo)號(hào)，起點(diǎn)方格內(nèi)的數(shù)字就是起點(diǎn)到終點(diǎn)的最短距離，從起點(diǎn)開(kāi)始連接終點(diǎn)的粗箭線就是最短路線。 用標(biāo)號(hào)法來(lái)求解下例 例5.2：網(wǎng)絡(luò)圖5—2表示某城市的局部道路分布圖。一貨運(yùn)汽車(chē)從S出發(fā)，最終到達(dá)目的地E。其中Ai(i＝1，2，3),Bj(j＝1，2)和Ck(k＝1，2

34、)是可供汽車(chē)選擇的途經(jīng)站點(diǎn)，各點(diǎn)連線上的數(shù)字表示兩個(gè)站點(diǎn)問(wèn)的距離。問(wèn)此汽車(chē)應(yīng)走哪條路線，使所經(jīng)過(guò)的路程距離最短?,2.動(dòng)態(tài)規(guī)劃的基本原理,37,2.動(dòng)態(tài)規(guī)劃的基本原理,圖5-2 某城市的局部道路分布圖,38,第一步：先考慮第四階段，即k=4，該階段共有兩個(gè)狀態(tài)：C1、C2，設(shè)f4(C1)和f4(C2)分別表示C1、C2到E的最短距離，顯然有f4(C1)=5和f4(C2)=8，邊界條件f5(E)=0 。 第二步：即k

35、=3,該階段共有兩個(gè)狀態(tài):B1 , B2 (1) 從B1出發(fā)有兩種決策:B1→C1，B1→C2 。記d3(B1,C1)表示B1到C1的距離,即,這里的每一種決策的階段指標(biāo)函數(shù)就是距離，所以，B1→C1的階段指標(biāo)函數(shù)為d3(B1,C1)＝6，B1→C2的階段指標(biāo)函數(shù)為d3(B1,C2)＝5。因此有, f3(B1)＝min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝min(6＋5，

36、5＋8)＝11。那么，從出發(fā)到E的最短路線是B1→C1→E，對(duì)應(yīng)的決策u3(B1) = C1 。,2.動(dòng)態(tài)規(guī)劃的基本原理,39,(2)從B2出發(fā)也有兩種決策:B2→C1,B2→C2同理, 有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+87)＝14，那么，從B2出發(fā)到E的最短路線是B2→C1→E，且u3(B2)=C1 。 第三步：即k＝2,該階段共有三個(gè)

37、狀態(tài):Al,A2,A3 (1)從Al出發(fā)有兩種決策：A1→B1,A1→B2。則 f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝min{6＋11，5＋14}＝17，即A1到E的最短路線為A1→B1→C1→E，且u3(A1)＝B1 。 (2)從A2出發(fā)也有兩種決策:A2→B1,A2→B2。此時(shí)， f2(A2)＝min{d2(A2,B1)+f3(B1),d2(A2

38、,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E，且u3(A2)＝B1。,2.動(dòng)態(tài)規(guī)劃的基本原理,40,(3)從A3出發(fā)也有兩種決策:A3→B1,A3→B2 此時(shí) f2(A2)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}＝min{7+11，4+14}＝18，即A3到E的最短路線為A3→B1→C1→E ，對(duì)應(yīng)的u2(A3)＝B2 。

39、第四步：即k＝1，該階段只有一個(gè)狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么, f1(S)=min{d1(S,A1)+f2(A1),d2(S,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E ，且u3(A2)＝B1 。 那么,從S到E共有三條最短路線： 此時(shí),u1(S)＝A1題 和 此時(shí),u1(S)＝A3 ，最短距離為21。,

40、2.動(dòng)態(tài)規(guī)劃的基本原理,,,,,,,41,結(jié)果如圖5-3所示。 每個(gè)狀態(tài)上方的方格內(nèi)的數(shù)字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構(gòu)成每一狀態(tài)到E的最短路線。因此，標(biāo)號(hào)法不但給出起點(diǎn)到終點(diǎn)的最短路線和最短距離，同時(shí)也給出每一狀態(tài)到終點(diǎn)的最短路線及其最短距離。如,A1到E的最短路線是 ,最短矩離是17 圖見(jiàn)下頁(yè),2.動(dòng)態(tài)規(guī)劃的基本原理,42,2.動(dòng)態(tài)規(guī)劃的基本原理,圖5-3某城

41、市局部道路求最短路徑的過(guò)程,43,2．最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個(gè)全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過(guò)程中的任意狀態(tài)而言，無(wú)論其過(guò)去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過(guò)程最優(yōu)策略為：,2.動(dòng)態(tài)規(guī)劃的基本原理,則對(duì)上述策略中所隱含的任一狀態(tài)而言， 第k子過(guò)程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過(guò)程最優(yōu)策略p1*中，即為,44,如第一節(jié)所述，基于上

42、述原理，提出了一 種逆序遞推法；這里可以指出，該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱(chēng)為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。 3.函數(shù)基本方程 在例中，用標(biāo)號(hào)法求解最短路線的計(jì) 算公式可以概括寫(xiě)成：(5-6) 其中， 在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離,是邊界條件，表示全過(guò)程到第四階段終點(diǎn)結(jié)束。,2.動(dòng)態(tài)規(guī)劃的基本原理,,,,45,一般地，對(duì)于

43、n個(gè)階段的決策過(guò)程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下： (1)當(dāng)過(guò)程指標(biāo)函數(shù)為下列“和”的形式時(shí)， 相應(yīng)的函數(shù)基本方程為 （5—7）,2.動(dòng)態(tài)規(guī)劃的基本原理,,,,46,(2) 當(dāng)過(guò)程指標(biāo)函數(shù)為下列“積”的形式時(shí), 相應(yīng)的函數(shù)基本方程為 （5—8） 可以看出，和、積函數(shù)的基本方程中邊界 條件(即

44、 的取值)是不同的。,2.動(dòng)態(tài)規(guī)劃的基本原理,,,,,47,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,標(biāo)號(hào)法僅適用于求解象最短路線問(wèn)題那樣可以用網(wǎng)絡(luò)圖表示的多階段決策問(wèn)題。但不少多階段決策問(wèn)題不能用網(wǎng)絡(luò)圖表示。此時(shí),應(yīng)該用函數(shù)基本方程來(lái)遞推求解.一般來(lái)說(shuō),要用函數(shù)基本方程逆推求解,首先要有效地建立動(dòng)態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個(gè)實(shí)際問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)求解,還必須首先根據(jù)問(wèn)題的要求。把它

45、構(gòu)造成動(dòng)態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個(gè)動(dòng)態(tài)規(guī)劃模型,往往問(wèn)題也就解決了一大半,而一個(gè)正確的動(dòng)態(tài)規(guī)劃模型,應(yīng)該滿(mǎn)足哪些條件呢?,48,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,1．應(yīng)將實(shí)際問(wèn)題恰當(dāng)?shù)胤指畛蒼個(gè)子問(wèn)題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。 2．正確地定義狀態(tài)變量sk，使它既能正確地描述過(guò)程的狀態(tài)，又能滿(mǎn)足無(wú)后

46、效性．動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說(shuō)的狀態(tài)的概念是有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征：,49,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,(1)要能夠正確地描述受控過(guò)程的變化特征。 (2)要滿(mǎn)足無(wú)后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定，那么在該階段以后，過(guò)程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無(wú)后效性，就不能作為狀態(tài)變量來(lái)構(gòu)造動(dòng)態(tài)規(guī)劃的模型。 (3)要滿(mǎn)足可知性。即所規(guī)定的各段狀態(tài)變量的值，

47、可以直接或間接地測(cè)算得到。一般在動(dòng)態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進(jìn)行累計(jì)的量。此外，在與靜態(tài)規(guī)劃模型的對(duì)應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗(yàn)，線性與非線性規(guī)劃中約束條件的個(gè)數(shù)，相當(dāng)于動(dòng)態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)．而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。,50,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗(yàn)，一般將問(wèn)題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模

48、型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。 4. 能夠正確地寫(xiě)出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk ,uk),51,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,5．根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿(mǎn)足下列性質(zhì)：

49、(1)可分性，即對(duì)于所有k后部子過(guò)程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策 uk ,uk+1,┈,un,就是說(shuō)它是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)。 (2)要滿(mǎn)足遞推關(guān)系，即 (3)函數(shù) 對(duì)其變?cè)猂k+1來(lái)說(shuō)要嚴(yán)格單調(diào)。,,,,52,6．寫(xiě)出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見(jiàn)的指標(biāo)函數(shù)是取各段指標(biāo)和的形式 其中 表示第i階段

50、的指標(biāo)，它顯然是滿(mǎn)足上述三個(gè)性質(zhì)的。所以上式可以寫(xiě)成 ：,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,,53,二．動(dòng)態(tài)規(guī)劃方法的基本步驟 為進(jìn)一步說(shuō)明動(dòng)態(tài)規(guī)劃模型建立的基本方法及其求解過(guò)程,下面通過(guò)實(shí)際例子用上述方法具體給出求解動(dòng)態(tài)規(guī)劃方法的基本步驟： 例5.3:有某種機(jī)床,可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn),在高負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機(jī)床數(shù)量u1的關(guān)系為g=g(u1)=8u1,這時(shí),年終機(jī)床完好

51、臺(tái)數(shù)將為au1,(a為機(jī)床完好率，0<a<1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機(jī)床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應(yīng)的機(jī)床完好率為b(0<b<1,設(shè)b=0,9),一般情況下a<b。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,54,假設(shè)某廠開(kāi)始有x=1000臺(tái)完好的機(jī)床，現(xiàn)要制定一個(gè)五年生產(chǎn)計(jì)劃，問(wèn)每年開(kāi)始時(shí)如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)

52、量為最高。 解：首先構(gòu)造這個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃模型。 1．變量設(shè)置 (1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=5。 (2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺(tái)數(shù)，同時(shí)也是第k-1年度末時(shí)的完好機(jī)床數(shù)量。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,55,(3)決策變量uk，表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù)。于是sk- uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù)． 這里sk與uk均

53、取連續(xù)變量，當(dāng)它們有非整數(shù)數(shù)值時(shí)．可以這樣理解：如sk＝0.6，就表示一臺(tái)機(jī)器在k年度中正常工作時(shí)間只占6/10；uk=0.4時(shí)，就表示一臺(tái)機(jī)床在 k年度只有4/10的時(shí)間于高負(fù)荷下工作． 2．狀態(tài)轉(zhuǎn)移方程為 k=1，2，…,6,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,56,3．允許決策集合,在第k段為 4．目標(biāo)函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量，則gk(sk,uk)=8

54、uk+5(sk-uk),因此，目標(biāo)函數(shù) 為 k＝1,2,．．．,5 5．條件最優(yōu)目標(biāo)函數(shù)遞推方程。 令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結(jié)束這段時(shí)間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系： k=1,2,

55、3,4,5,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,,57,6.邊界條件為 下面采用逆序遞推計(jì)算法,從第5年度開(kāi)始遞推計(jì)算。 k=5時(shí)有 顯然，當(dāng)u5*=s5時(shí)，f5(s5)有最大值，相應(yīng)的有f5(s5)=8s5 k=4時(shí)有,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,= =,因此，當(dāng)u4*=s4時(shí)，有最大值f4(s4)=13.6s4,58,k=3 時(shí)有 可見(jiàn)，當(dāng)u3*=s3時(shí)，f3(s3)有最大

56、值f3(s3) =17.55s3. k=2 時(shí)有 = + =此時(shí)，當(dāng)取u2*=0時(shí)有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1),3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,,59,k=1時(shí)有 + = 當(dāng)取u1*=0時(shí), f1(s1)有最大值，即f1

57、(s1)=23.7s1,因?yàn)閟1=1000,故f1(s1)=23700個(gè)產(chǎn)品． 按照上述計(jì)算順序?qū)ほ櫟玫较率鲇?jì)算結(jié)果：,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,60,上面所討論的最優(yōu)決策過(guò)程是所謂始端狀態(tài)s1固定，終端狀態(tài)s6自由．如果終端也附加上一定的約束條件，那么計(jì)算結(jié)果將會(huì)與之有所差別．例如，若規(guī)定在第五個(gè)年度結(jié)束時(shí)，完好的機(jī)床數(shù)量為500臺(tái)(上面只有278臺(tái))，問(wèn)應(yīng)該如何安排五年的生產(chǎn)，使之在滿(mǎn)足這一終端要求的情況下產(chǎn)量最高？,3.動(dòng)態(tài)規(guī)

58、劃方法的基本步驟,61,解：由狀態(tài)轉(zhuǎn)移方程 有得 顯而易見(jiàn)，由于固定了終端的狀態(tài)s6，第五年的決策變量U5的允許決策集合U5(s5)也有了約束，上式說(shuō)明U5(s5)已退化為一個(gè)點(diǎn)，即第五年投入高負(fù)荷下生產(chǎn)的機(jī)床數(shù)只能由式U5=4.5s5-2500作出一種決策，故,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,＝500,62,當(dāng)k=5時(shí)有

59、 當(dāng)k=4時(shí)有 顯然，只有取u4*=0 ，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理類(lèi)推,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,=,=,63,k=3時(shí)有 可知,當(dāng)u3*=0時(shí),f3(s3)有最大值f4(s4)=24.5s3-7500.k=2時(shí)有 此時(shí),當(dāng)u2*=0時(shí)有最大值,即f2(s2)=27.1s2-7500,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,=

60、,=,+,64,k=1時(shí)有 只有取u1*=0時(shí),f1(s1)有最大值，即 f1(s1)=29.4s1-7500 。 由此可見(jiàn)，為了使下一個(gè)五年計(jì)劃開(kāi)始的一年有完好的機(jī)床500臺(tái)，其最優(yōu)策略應(yīng)該為：在前4年中，都應(yīng)該把全部機(jī)床投人低負(fù)荷下生產(chǎn)，在第5年，只能把部分完好機(jī)投入高負(fù)荷下生產(chǎn)。根據(jù)最優(yōu)策賂，從始端向終端遞推計(jì)算出各年的狀態(tài)，即算出每年年初的完好機(jī)床臺(tái)數(shù)，

61、因?yàn)閟1＝1000臺(tái)，于是有,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,65,因此，u5*=4.5s5-2500=425(臺(tái))，這就是說(shuō)第5年里還有204臺(tái)投入低負(fù)荷下生產(chǎn)，否則不能保證s6=0.7u5+0.9(u5-s5)=500(臺(tái))。 在上述最優(yōu)決策下，5年里所得最高產(chǎn)量為： f1(s1)＝29.4s1-7500=29400-7500＝21900(個(gè))。 可見(jiàn)，附加了終端約束條件以后，其最高產(chǎn)量f1(s

62、1)比終端自由時(shí)要低一些。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,（臺(tái)）,（臺(tái)）,（臺(tái)）,（臺(tái)）,（臺(tái)）,（臺(tái)）,66,例5.4：一個(gè)線路網(wǎng)絡(luò)圖，從A到E要修建一條石油管道，必須 在B、C、D處設(shè)立加壓站。各邊上的數(shù)為長(zhǎng)度，現(xiàn)需要找一條路使總長(zhǎng)度最短。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,67,解: 可分成4個(gè)階段： A到B、B到C、C到D、D到E； 每個(gè)階段 k 的起點(diǎn)稱(chēng)為狀態(tài)Sk ； 從 k 階段的起點(diǎn)出

63、發(fā)可以做一選擇，即決定到下一階段的哪個(gè)節(jié)點(diǎn),稱(chēng)為決策Xk ；可見(jiàn),Sk+1 是由 Sk 和Xk 所決定的。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,68,那么，從A出發(fā)經(jīng)過(guò)4個(gè)階段：A到B、B到C、C到D、D到E，逐次作出決策，構(gòu)成從A到E 的一條路線，記為 u 。 即 u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A ，S5 = E 記 d 為兩個(gè)相鄰節(jié)點(diǎn)之間的長(zhǎng)度， 如 d（A，B 3）

64、= 3 。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,69,① 記 fk(Sk)為從Sk到E的最短長(zhǎng)度,稱(chēng)為從Sk到E的距離。,那么，f1(A)是從A到E的最短距離，即最優(yōu)策略的值。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,70,② 最短路問(wèn)題的特點(diǎn)：如果從A到E的最優(yōu)策略經(jīng)過(guò)某節(jié)點(diǎn)，那么這個(gè)策略的從該節(jié)點(diǎn)到E的一段，必定是該節(jié)點(diǎn)到E的所有線路中 Sk最短的一條，即這一段的長(zhǎng)度為 fk（Sk）。 （1）逆序法：從E到A。 （2）順序法：對(duì)節(jié)點(diǎn)

65、Sk，從A到Sk 所有線路中，最短的一條的長(zhǎng)度記為 φk（S k），例如φ1（A）= 0，稱(chēng)為問(wèn)題的邊界條件。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,71,動(dòng)態(tài)規(guī)劃模型建立后，對(duì)基本方程分段求解，不像線性規(guī)劃或非線性規(guī)劃那樣有固定的解法，必須根據(jù)具體問(wèn)題的特點(diǎn)，結(jié)合數(shù)學(xué)技巧靈活求解，如動(dòng)態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用離散變量的分段窮舉法。當(dāng)動(dòng)態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取連

66、續(xù)變量的求解方法。如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計(jì)算方法等。還有連續(xù)變量的離散化解法和高維問(wèn)題的降維法及疏密格子點(diǎn)法等等。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,72,學(xué)習(xí)方法建議： 第一步 先看問(wèn)題，充分理解問(wèn)題的條件、情況及求解目標(biāo)。 第二步 結(jié)合前面講到的理論和解題過(guò)程，考慮如何著手進(jìn)行求解該問(wèn)題的工作。分析針對(duì)該動(dòng)態(tài)規(guī)劃問(wèn)題的“四大要素、一個(gè)方程”——這一步在開(kāi)始時(shí)會(huì)感到困難，但是一定要下決心去思考，

67、在思考過(guò)程中深入理解前文講到的概念和理論。,4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,73,第三步 動(dòng)手把求解思路整理出來(lái)，或者說(shuō)，把該問(wèn)題作為習(xí)題獨(dú)立的來(lái)做。 第四步 把自己的求解放到一邊，看書(shū)中的求解方法，要充分理解教材中的論述。 第五步 對(duì)照自己 的求解，分析成敗。,4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,74,1.動(dòng)態(tài)規(guī)劃的四大要素 ① 狀態(tài)變量及其可能集合 xk ? Xk ② 決策變量及其允許集合

68、 uk ? Uk ③ 狀態(tài)轉(zhuǎn)移方程 xk+1= Tk (xk ,uk ) ④ 階段效應(yīng) rk ( xk , uk ),4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,75,2. 動(dòng)態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 (邊界條件) fk(xk) = opt u{rk ( xk , uk ) + fk+1(xk+1) }