運(yùn)籌學(xué)OR1-Ch8-動(dòng)態(tài)規(guī)劃

1、第八章 動(dòng)態(tài)規(guī)劃Ch8 Dynamic Programming8-1 多階段決策過程最優(yōu)化8-2 動(dòng)態(tài)規(guī)劃基本概念8-3 動(dòng)態(tài)規(guī)劃基本原理8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用8-1 多階段決策過程最優(yōu)化一、多階段決策問題動(dòng)態(tài)規(guī)劃是把多階段決策問題作為研究對象。多階段決策問題：根據(jù)問題本身的特點(diǎn)，可以將其求解的全過程劃分為若干個(gè)相互聯(lián)系的階段(即將問題劃分為許多個(gè)相互聯(lián)系的子問題)，在它的每一階段都需要作出決策，并且在一個(gè)階段的決策確定以后再轉(zhuǎn)移到下一個(gè)階段。多階段決策過程(Multi-Stagedecision process)： 前一個(gè)階段的決策要影響到后一個(gè)階段的決策，從而影響整個(gè)過程。各個(gè)階段所確定的

2、決策就構(gòu)成了一個(gè)決策序列，稱為一個(gè)策略。一般來說，由于每一階段可供選擇的決策往往不止一個(gè)，因此，對于整個(gè)過程，就會有許多可供選擇的策略。*Page 2 of 77 8-1 多階段決策過程最優(yōu)化最優(yōu)策略：若對應(yīng)于一個(gè)策略，可以由一個(gè)量化的指標(biāo)來確定這個(gè)策略所對應(yīng)的活動(dòng)過程的效果，那么不同的策略就有各自的效果。在所有可供選擇的策略中，對應(yīng)效果最好的策略稱為最優(yōu)策略。把一個(gè)問題劃分成若干個(gè)相互聯(lián)系的階段選取其最優(yōu)策略，這類問題就是多階段決策問題。多階段決策過程最優(yōu)化的目標(biāo)是要達(dá)到整個(gè)活動(dòng)過程的總體效果最優(yōu)。由于各段決策間有機(jī)地聯(lián)系著，本段決策的執(zhí)行將影響到下一段的決策，以至于影響總體效果，所以決策者

3、在每段決策時(shí)不應(yīng)僅考慮本階段最優(yōu)，還應(yīng)考慮對最終目標(biāo)的影響，從而作出對全局來講是最優(yōu)的決策。動(dòng)態(tài)規(guī)劃就是符合這種要求的一種決策方法。*Page 3 of 77 8-1 多階段決策過程最優(yōu)化二、多階段決策問題舉例 1)工廠生產(chǎn)過程：由于市場需求是一隨著時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計(jì)劃安排。2)設(shè)備更新問題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買來時(shí)故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價(jià)值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長

4、、處理價(jià)值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。*Page 4 of 77 8-1 多階段決策過程最優(yōu)化3)連續(xù)生產(chǎn)過程的控制問題：一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。以上所舉問題的發(fā)展過程都與時(shí)間因素有關(guān)，因此在這類多階段決策問題中，階段的劃分常取時(shí)間區(qū)段來表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)”的含義，所以把處理這類動(dòng)態(tài)問題的方法稱為動(dòng)態(tài)規(guī)劃方法。不

5、過，實(shí)際中尚有許多不包含時(shí)間因素的一類“靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，是非動(dòng)態(tài)決策問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。*Page 5 of 77 8-1 多階段決策過程最優(yōu)化4）資源分配問題：屬于這類靜態(tài)問題。如：某工業(yè)部門或公司，擬對其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時(shí)間因素?zé)o關(guān)，不屬動(dòng)態(tài)決策，但是，我們可以人為地規(guī)定一個(gè)資源分配的階段和順序，從而使其變成一個(gè)多階段決策問題(后面我們將詳細(xì)討論這個(gè)問題)。5）運(yùn)輸網(wǎng)絡(luò)問題： 如下頁圖1所示的運(yùn)輸網(wǎng)絡(luò)，

6、點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從v1 至v10的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個(gè)階段，而作為多階段決策問題來研究。*Page 6 of 77 8-1 多階段決策過程最優(yōu)化圖8-1 運(yùn)輸網(wǎng)絡(luò)圖示*Page 7 of 77 8-1 多階段決策過程最優(yōu)化三、動(dòng)態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn) 通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特

7、殊的多階段決策問題，即具有“無后效性”的多階段決策過程。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。狀態(tài) x1階段1T1決策u1狀態(tài) x2決策u2階段2T2狀態(tài) x3.狀態(tài) xk決策uk階段kTk狀態(tài) xk+1.狀態(tài) xn決策un階段nTn狀態(tài) xn+1要點(diǎn)：階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)移方程，k-后部子過程多階段決策過程特點(diǎn):*Page 8 of 77 8-1 多階段決策過程最優(yōu)化四、動(dòng)態(tài)規(guī)劃方法導(dǎo)引：為了說明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖8-1所示為例討論的求最短路問題的方法。 第一種方法

8、稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有322112條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1 v3 v7 v9 v10 ,最短距離是18顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會十分龐大，而且其中包含著許多重復(fù)計(jì)算 第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會致整體最優(yōu)，在

9、這種想法指導(dǎo)下，所取決策必是v1 v3 v5 v8 v10 ，全程長度是20；顯然，這種方法的結(jié)果常是錯(cuò)誤的*Page 9 of 77 8-1 多階段決策過程最優(yōu)化第三種方法是動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，首先將問題劃分為4個(gè)階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動(dòng)態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實(shí)際過程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。*Page 10 of 77 8-1 多階段決策過程最優(yōu)化具體說，此問題先從v10開

10、始，因?yàn)関10是終點(diǎn)。再無后繼過程，故可以接著考慮第4階段上所有可能狀態(tài)v8 ,v9的最優(yōu)后續(xù)過程因?yàn)閺膙8 ,v9 到v10的路線是唯一的，所以v8 ,v9 的最優(yōu)決策和最優(yōu)后繼過程就是到v10 ，它們的最短距離分別是5和3。 接著考慮階段3上可能的狀態(tài)v5 ,v6 , v7 , 到v10的最優(yōu)決策和最優(yōu)后繼過程在狀態(tài)V5上，雖然到v8是8，到v9是9，但是綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決策是到v9,最優(yōu)后繼過程是v5v9 v10 ，最短距離是12同理，狀態(tài)v6的最優(yōu)決策是至v8 ；v7的最優(yōu)決策是到v9 。同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后，便可以開始考慮階段2上所有可

11、能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如v2的最優(yōu)決策是到v5,最優(yōu)路線是v2v5v9v10 ，最短距離是15依此類推，最后可以得到從初始狀態(tài)v1的最優(yōu)決策是到v3最優(yōu)路線是v1v3v7v9v10 ，全程的最短距離是18。圖1中粗實(shí)線表示各點(diǎn)到的最優(yōu)路線，每點(diǎn)上方括號內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。*Page 11 of 77 8-1 多階段決策過程最優(yōu)化結(jié)論：全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法；局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法；動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法：它的基本思想是，把一個(gè)比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過程分為兩個(gè)階段，先按整體最優(yōu)的思想

12、逆序地求出各個(gè)子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個(gè)問題的最優(yōu)策略和最優(yōu)路線。計(jì)算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。*Page 12 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義： *Page 13 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念(一) 階段和階段變量 為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段

13、。一個(gè)階段，就是需要作出一個(gè)決策的子問題，通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目，圖51所示的最短路問題就是一個(gè)四階段決策過程。（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集 1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過程進(jìn)行的先后，每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1

14、。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。*Page 14 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念2可能狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，skSk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定在圖51所示的最短路問題中，第一階段狀態(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)變量

15、s3的狀態(tài)集合S3=v5 ,v6 ,v7 ；第四階段則有二個(gè)狀態(tài)： v8 ,v9 , 狀態(tài)變量s4的狀態(tài)集合S4=v8 ,v9 ；*Page 15 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念（三）決策、決策變量和允許決策集合 所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以uk= uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許

16、決策集用Uk(sk)表示, uk(sk) Uk(sk)允許決策集合實(shí)際是決策的約束條件。*Page 16 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念（四）、策略和允許策略集合 策略(Policy)也叫決策序列策略有全過程策略和k部子策略之分，全過程策略是指具有n個(gè)階段的全部過程，由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列，簡稱策略，表示為p1,nu1,u2,un。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時(shí)的k部子策略就是全過程策略。 在實(shí)際問題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的

17、決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。*Page 17 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念（五）狀態(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)移到終止?fàn)顟B(tài)sk+1 ，或者說，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1 ，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。 對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2, ,sk-1及

18、其決策u1(s1), u2(s2)uk-1(sk-1)無關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：通常稱式(1)為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。(1)*Page 18 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念(六) 指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。例如：圖10-1的指標(biāo)就是運(yùn)費(fèi)。 (1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用gk(sk,

19、uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡記為gk 。圖1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3,即v2到v5的距離為3。 (2)過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。用Rk(sk,uk)表示第k子過程的指標(biāo)函數(shù)。如圖10-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時(shí)，從sk點(diǎn)到終點(diǎn)v10的距離。由此可見，Rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴(yán)格說來，應(yīng)表示為:*Page 19 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念不過實(shí)際應(yīng)用中往往

20、表示為Rk(sk,uk)或Rk(sk)。還跟第k子過程上各段指標(biāo)函數(shù)有關(guān)，過程指標(biāo)函數(shù)Rk(sk)通常是描述所實(shí)現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)gk(sk,uk)累積形成的，適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式對于部子過程的指標(biāo)函數(shù)可以表示為： 式中，表示某種運(yùn)算，可以是加、減、乘、除、開方等。多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。 (2)（3）(4)*Page 20 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念(七) 最優(yōu)解 用f

21、k(sk)表示第k子過程指標(biāo)函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱fk(sk)為第k子過程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk) ；而構(gòu)成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為 : 簡記為*Page 21 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念特別當(dāng)k=1且s1取值唯一時(shí)，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例10-1只有唯一始點(diǎn)v1即s1取值唯一,故f1(s1)=18就是例10-1的最優(yōu)值，而: 就是例10-1的最優(yōu)策略。 但若取值不唯一,則問題的最優(yōu)值記為f0有 最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略： 我們把最優(yōu)策略和最優(yōu)值

22、統(tǒng)稱為問題的最優(yōu)解。*Page 22 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念按上述定義，所謂最優(yōu)決策 是指它們在全過程上整體最優(yōu)(即所構(gòu)成的全過程策略為最優(yōu))，而不一定在各階段上單獨(dú)最優(yōu)。(八) 多階段決策問題的數(shù)學(xué)模型 綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:（5）*Page 23 of 77 8-2 動(dòng)態(tài)規(guī)劃基本概念式中“OPT”表示最優(yōu)化，視具體問題取max或min。 上述數(shù)學(xué)模型說明了對于給定的多階段決策過程，求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列，使之既滿足式(5)給出的全部約束條件，又使式(5)所示的目標(biāo)函數(shù)取得

23、極值，并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí)，過程狀態(tài)演變序列即最優(yōu)路線*Page 24 of 77 8-3 動(dòng)態(tài)規(guī)劃基本原理一。最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略p1*中，即為：*Page 25 of 77 8-3 動(dòng)態(tài)規(guī)劃基本原理二。動(dòng)態(tài)規(guī)劃方法的基本步驟應(yīng)將實(shí)際問題恰當(dāng)?shù)胤指畛蒼個(gè)子問題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而

24、劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。 正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征： (1)要能夠正確地描述受控過程的變化特征。 (2)要滿足無后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動(dòng)態(tài)規(guī)劃的模型。 (3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動(dòng)態(tài)規(guī)劃模型中，狀態(tài)

25、變量大都選取那種可以進(jìn)行累計(jì)的量。此外，在與靜態(tài)規(guī)劃模型的對應(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)容。*Page 26 of 77 8-3 動(dòng)態(tài)規(guī)劃基本原理3正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗(yàn)，一般將問題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。4. 能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策

26、變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk ,uk)5根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)： (1)可分性，即對于所有k后部子過程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策 uk ,uk+1,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。 (2)要滿足遞推關(guān)系，即 (3)函數(shù) 對其變元Rk+1來說要嚴(yán)格單調(diào)。*Page 27 of 77 8-3 動(dòng)態(tài)規(guī)劃基本原理6寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式 其中 表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成 ：

27、*Page 28 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題一.求最短路徑問題例8-2*Page 29 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題將問題分成五個(gè)階段，第k階段到達(dá)的具體地點(diǎn)用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達(dá)位置B3，等等。這里狀態(tài)變量取字符值而不是數(shù)值。將決策定義為到達(dá)下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時(shí)決策允許集合包含三個(gè)決策，它們是D2(x2)=D2(B3)=B3C1,B3C2,B3C3最優(yōu)指標(biāo)函數(shù)fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為 f5(x5)=f5(E)=0其含義是從E到E的最短路徑為0。第四階段的遞推方程為:*P

28、age 30 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題其中*表示最優(yōu)值，在上表中，由于決策允許集合D4(x4)中的決策是唯一的，因此這個(gè)值就是最優(yōu)值。由此得到f4(x4)的表達(dá)式。由于這是一個(gè)離散的函數(shù)，取值用列表表示：*Page 31 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題第三階段的遞推方程為：*Page 32 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題由此得到f3(x3)的表達(dá)式：從f3(x3)到f2(x2)的遞推過程用表格表示如下： *Page 33 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題*Page 34 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題由此得到f2(x2)

29、的表達(dá)式：第一階段的遞推方程為：*Page 35 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用最短路問題從f2(x2)到f1(x1)的遞推過程用表格表示如下： 由此得到f1(x1)的表達(dá)式從表達(dá)式f1(x1)可以看出，從A到E的最短路徑長度為19。由f1(x1)向f4(x4)回朔，得到最短路徑為：A B2 C1 D1 E *Page 36 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用資源分配問題二.資源分配問題所謂資源分配問題，就是將供應(yīng)量有限的一種或若干種資源（例如原材料、資金、機(jī)器設(shè)備、勞動(dòng)、食品等），分配給若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。 問題的提出：設(shè)有某種原材料，總量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量

30、為yi的原材料生產(chǎn)第i種產(chǎn)品，其效益為g(yi)。問應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大?問題的求解：在應(yīng)用動(dòng)態(tài)規(guī)劃方法求解資源分配問題時(shí)，通常以把資源分配給一個(gè)或幾個(gè)使用者的過程作為一個(gè)階段；把規(guī)劃問題中的變量取為決策變量；把累計(jì)的量或隨遞推過程變化的量選為狀態(tài)變量。 *Page 37 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用資源分配問題例8-3: 有資金4萬元，投資A、B、C三個(gè)項(xiàng)目，每個(gè)項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：求對三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段；狀態(tài)變量xk：投資

31、第k個(gè)項(xiàng)目前的資金數(shù)；決策變量dk：第k個(gè)項(xiàng)目的投資；決策允許集合：0dkxk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk ,dk)見表中所示；遞推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)終端條件：f4(x4)=0*Page 38 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用資源分配問題k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3*Page 39 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用資源分配問題K=2:*Page 40 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用資源分配問題k=1，0d1x1，x2=x1-d1最優(yōu)解為x1=4, d1*=1, x2=x1-d1=

32、3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，即項(xiàng)目A投資1萬元，項(xiàng)目B投資0萬元，項(xiàng)目C投資3萬元，最大效益為60萬噸。 *Page 41 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題三. 生產(chǎn)與庫存問題問題的提出：一個(gè)生產(chǎn)項(xiàng)目，在生產(chǎn)批量、生產(chǎn)成本費(fèi)用、存儲費(fèi)用以及市場對產(chǎn)品的要求情況都是確定數(shù)值的條件下，為了根據(jù)需要制訂計(jì)劃，必須正確決定不同時(shí)期的生產(chǎn)量和庫存量，以期在滿足市場需求的條件下使生產(chǎn)與庫存的費(fèi)用最低。 一般的解決方法：以計(jì)劃的不同時(shí)期為不同的階段 k；狀態(tài)變量 xk 取為第k階段開始時(shí)的庫存量；決策變量k為第k階段（時(shí)期）的生產(chǎn)量； 狀態(tài)

33、轉(zhuǎn)移方程為： 為第k階段的階段指標(biāo)，代表這一時(shí)期的成本。則此問題的動(dòng)態(tài)規(guī)劃遞推關(guān)系式為： *Page 42 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題例8-4:一個(gè)工廠生產(chǎn)某種產(chǎn)品,1- 7月份生產(chǎn)成本和產(chǎn)品需求量的變化情 況如下表：為了調(diào)節(jié)生產(chǎn)生產(chǎn)和需求，工廠設(shè)有一個(gè)產(chǎn)品倉庫，庫容量H=9。已知期初庫存量為2，要求期末（七月低）庫存量為0。每個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng)月需求發(fā)貨。求七個(gè)月的生產(chǎn)量，能滿足各月的需求，并使生產(chǎn)成本最低。 *Page 43 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題階段k：月份，k=1,2,7,8；狀態(tài)變量xk：第k個(gè)月初（發(fā)貨以前）的庫存量

34、；決策變量dk：第k個(gè)月的生產(chǎn)量；狀態(tài)轉(zhuǎn)移方程：xk+1=xk-rk+dk；決策允許集合：Dk(xk)=dk | dk0, rk+1xk+1H =dk | dk0, rk+1xk-rk+dkH ；階段指標(biāo)：vk(xk ,dk)=ckdk；終端條件：f8(x8)=0,x8=0；遞推方程：fk(xk)=minvk(xk ,dk)+fk+1(xk+1) dkDk(xk) =minckdk+fk+1(xk-rk+dk) dkDk(xk)*Page 44 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=7因?yàn)?x8=0 有: d7=0遞推方程為: f7(x7)=minc7d7+f8(x8)=0

35、d7=0對于k=6 因?yàn)閐7=0，所以x7=r7=4 而x6-r6+d6=x7=4 因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的決策。因此遞推方程為：f6(x6)=minc6d6+f7(x7) d6=11-x6=10d6=10(11-x6)=110-10 x6*Page 45 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=5f5(x5)=minc5d5+f6(x6) =min20d5+110-10 x6 =min20d5+110-10(x5-r5+d5) =min20d5+110-10(x5-2+d5) =min10d5-10 x5+130 d5D5(x5)D5(

36、x5) =d5| d50, r6x5-r5+d5H =d5|d50, r6+r5-x5d5H+r5-x5 =d5| d50, 9-x5d511-x5因?yàn)閤5H=9，因此9-x50，決策允許集合可以簡化為 D5(x5)=d5| 9-x5d511-x5遞推方程成為f5(x5)=min10d5-10 x5+130 9-x5d511-x5 =10(9-x5)-10 x5+130 =220-20 x5 d5*=9-x5*Page 46 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=4f4(x4)=minc4d4+f5(x5)=min17d4+220-20 x5 =min17d4+220-20(

37、x4-r4+d4) =min17d4+220-20(x4-3+d4) =min-3d4-20 x4+280 d4D4(x4) D4(x4)=d4| d40, r5x4-r4+d4H=d4| d40, r5+r4-x4d4H+r4-x4=d4| d40, 5-x4d412-x4=d4| max0,5-x4d412-x4 由于 在f4(x4)的表達(dá)式中d4的系數(shù)是-3，因此d4在決策允許集合中應(yīng)取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244*Page 47 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=3f3(x3)=

38、min c3d3+f4(x4) =min 13d3+244-17x4 =min 13d3+244-17(x3-r3+d3) =min -4d3-17x3+329 其中d3D3(x3) D3(x3)=d3| d30,r4x3-r3+d3H=d3| d30,r4+r3-x3d3H+r3-x3=d3| d30,8-x3d314-x3=d3| max0,8-x3d314-x3 d3*=14-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273, *Page 48 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=2f2(x2)=minc2d2+f3(x3) =min

39、18d2+273-13x3 =min18d2+273-13(x2-r2+d2) =min18d2+273-13(x2-8+d2) =min5d2-13x2+377 其中 d2D2(x2) D2(x2)=d2|d20,r3x2-r2+d2H =d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2因?yàn)?13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2*Page 49 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題對于k=1f1(x1)=minc1d

40、1+f2(x2) =min11d1+442-18x2 =min11d1+442-18(x1-r1+d1) =min11d1+442-18(x1-0+d1) =min-7d1-18x1+442 d1D1(x1) D1(x1)=d1|d10,r2x1-r1+d1H =d1|d10,r2+r1-x1d1H+r1-x1 =d1|d10,8-x1d19-x1根據(jù)題意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357*Page 50 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用生產(chǎn)與庫存問題將以上結(jié)果總結(jié)成下表：*Page 51 of

41、 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題四. 背包問題 設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi，每件價(jià)值ci?，F(xiàn)有一只可裝載重量為W的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。這個(gè)問題可以用整數(shù)規(guī)劃模型來描述。設(shè)第i種物品取xi件（i=1,2,n，xi為非負(fù)整數(shù)），背包中物品的價(jià)值為z，則 則 Max z=c1x1+c2x2+cnxn s.t. w1x1+w2x2+wnxnW x1,x2,xn為正整數(shù)*Page 52 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題1.階段k：第k次裝載第k種物品（k=1,2,n）2.狀態(tài)變量xk：第k次裝載時(shí)背包還可以裝載的重

42、量；3.決策變量dk：第k次裝載第k種物品的件數(shù)；4. 決策允許集合：Dk(xk)=dk|0 dkxk/wk，dk為整數(shù)；5. 狀態(tài)轉(zhuǎn)移方程：xk+1=xk-wkdk6. 階段指標(biāo)：vk=ckdk7. 遞推方程 fk(xk)=maxckdk+fk+1(xk+1) =maxckdk+fk+1(xk-wkdk)8. 終端條件：fn+1(xn+1)=0*Page 53 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題 例8.7:對于一個(gè)具體問題c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5【解】用動(dòng)態(tài)規(guī)劃求解邊界條件： f4(x4)=0 對于k=3列出f3(x3)的數(shù)值表如下

43、： *Page 54 of 77 *Page 55 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題對于k=2 列出f2(x2)的數(shù)值表 *Page 56 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題對于k=1*Page 57 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用背包問題由題意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，經(jīng)回朔可得：d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0即應(yīng)取第一種物品2件,第三種物品1件,最高價(jià)值為160元,背包沒有余量。由f1(x1)得列表可以看出，如果背包得容量為W=4，W=3，W=2和W=1時(shí)，相應(yīng)

44、的最優(yōu)解立即可以得到。 *Page 58 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用機(jī)器負(fù)荷分配問題五。機(jī)器負(fù)荷分配問題 最短路徑問題和背包問題的狀態(tài)變量和決策變量都只能取離散的整數(shù)值。當(dāng)狀態(tài)變量和決策變量的取值范圍很大，或者這些變量是連續(xù)的，用列舉的方法就比較困難或者根本不可能了。這就需要用連續(xù)變量的處理方法。例8.8:某種機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷生產(chǎn)條件下機(jī)器完好率為0.7，即如果年初有u臺完好機(jī)器投入生產(chǎn)，則年末完好的機(jī)器數(shù)量為0.7u臺。系數(shù)0.7稱為完好率。年初投入高負(fù)荷運(yùn)行的u臺機(jī)器的年產(chǎn)量為8u噸。系數(shù)8稱為單臺產(chǎn)量。低負(fù)荷運(yùn)行時(shí)，機(jī)器完好率為0.9，單臺產(chǎn)量為5噸。設(shè)開始

45、時(shí)有1000臺完好機(jī)器，要制訂五年計(jì)劃，每年年初將完好的機(jī)器一部分分配到高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。 *Page 59 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用機(jī)器負(fù)荷分配問題 構(gòu)造動(dòng)態(tài)規(guī)劃模型如下： 階段k：運(yùn)行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，依次類推；k=6表示第五年末（即第六年初）。 狀態(tài)變量xk：第k年初完好的機(jī)器數(shù)（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好機(jī)器數(shù)。 決策變量dk：第k年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)； 狀態(tài)轉(zhuǎn)移方程：xk+1=0.7dk+0.9(xk-dk) 決策允許集合：Dk(xk)=dk

46、|0dkxk 階段指標(biāo)：vk(xk ,dk)=8dk+5(xk-dk) 終端條件：f6(x6)=0遞推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1) = max8dk+5(xk- dk)+fk+10.7dk+0.9(xk-dk) 0dkxkdkDk(xk)*Page 60 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用機(jī)器負(fù)荷分配問題 根據(jù)題意，本題的決策允許集合應(yīng)該是一個(gè)整數(shù)集合，但由于決策允許集合中可取的決策數(shù)量很大，一一列舉計(jì)算量很大，不妨認(rèn)為狀態(tài)變量和決策變量都是連續(xù)的，得到最優(yōu)解后，再作取整處理。f5(x5)=max8d5+5(x5-d5)+f6(x6) 0d5x5 =max

47、3d5+5x5=8x5, d5*=x5 0d5x5f4(x4)=max8d4+5(x4-d4)+f5(x5) 0d4x4 =max8d4+5(x4-d4)+8x5 0d4x4 =max8d4+5(x4-d4)+80.7d4+0.9(x4-d4) 0d4x4 =max1.4d4+12.3x4=13.7x4, d4*=x4*Page 61 of 77 8-4 動(dòng)態(tài)規(guī)劃的應(yīng)用機(jī)器負(fù)荷分配問題f3(x3)=max8d3+5(x3-d3)+f4(x4) 0d3x3=max8d3+5(x3-d3)+13.7x4 0d3x3=max8d3+5(x3-d3)+13.70.7d3+0.9(x3-d3) 0d3x3=max0.28d3+17.24x3=17.52x3, d3*=x3 0d3x3f2(x2)=max8d2+5(x2-d2)+f3(x3) 0d2x2 =max8d2+5(x2-d2)+17.52x3 0d2x2 =ma