第七章動(dòng)態(tài)規(guī)劃

1、 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種特殊算法。必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。 動(dòng)態(tài)規(guī)劃的方法應(yīng)用廣泛，在企業(yè)管理方面，可以解決最優(yōu)路徑問(wèn)題，資源分配問(wèn)題，生產(chǎn)調(diào)度問(wèn)題，庫(kù)存問(wèn)題，裝載問(wèn)題，排序問(wèn)題，設(shè)備更新問(wèn)題，生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等等。所以，它是現(xiàn)代企業(yè)管理中的一種重要的決策方法。引例建模原理資源分配問(wèn)題背包問(wèn)題生產(chǎn)庫(kù)存問(wèn)題本章內(nèi)容重點(diǎn) 動(dòng)態(tài)規(guī)劃模型的分類：（1）根據(jù)多階段決策過(guò)程的時(shí)間參量是離散的還是連續(xù)的變量，過(guò)程分為離散決策過(guò)程和連續(xù)決策過(guò)程。（2）根據(jù)多階段決策過(guò)程的演變是確定性還是隨機(jī)性的，過(guò)程又可分為確定性決策過(guò)程和隨機(jī)性決策

2、過(guò)程。組合起來(lái)就有離散確定性，離散隨機(jī)性，連續(xù)確定性，連續(xù)隨機(jī)性四種決策過(guò)程模型。 動(dòng)態(tài)規(guī)劃所研究的對(duì)象是多階段決策問(wèn)題，是指一類活動(dòng)過(guò)程，它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決策，這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。當(dāng)每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱為策略。 7.1 7.1 引例引例 這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有聯(lián)狀結(jié)構(gòu)的多階段過(guò)程，就稱為多階段決策過(guò)程，也稱為序貫決策過(guò)程。這種問(wèn)題就稱為多階段決策問(wèn)題（Multi-Stage decision process ）。 多階段決策問(wèn)題就是尋求一個(gè)策略，使問(wèn)題的整體效益達(dá)到最優(yōu)。 在

3、多階段決策問(wèn)題中，各階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)，決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”含義。因此，把處理的方法稱為動(dòng)態(tài)規(guī)劃方法。狀態(tài)狀態(tài) s s1 1階段階段1 1T T1 1決策決策u u1 1狀態(tài)狀態(tài) s s2 2決策決策u u2 2階段階段2 2T T2 2狀態(tài)狀態(tài) s s3 3.狀態(tài)狀態(tài) s sk k決策決策u uk k階段階段k kT Tk k狀態(tài)狀態(tài) s sk k+1+1.狀態(tài)狀態(tài) s sn n決策決策u un n階段階段n nTnTn狀態(tài)狀態(tài) s sn n+1+1一、多階段決策過(guò)程特點(diǎn)一、多階段決策過(guò)程特點(diǎn):

4、動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。然而它也可以處理與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題，只要在問(wèn)題中人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題。在本章中將介紹這種處理方法。二、多階段決策問(wèn)題舉例二、多階段決策問(wèn)題舉例 屬于多階段決策類的問(wèn)題很多，例如： 1)1)工廠生產(chǎn)過(guò)程工廠生產(chǎn)過(guò)程：由于市場(chǎng)需求是一隨著時(shí)間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過(guò)程中，逐月或者逐季度地根據(jù)庫(kù)存和需求情況決定生產(chǎn)計(jì)劃安排。 2)2)設(shè)備更新問(wèn)題：設(shè)備更新問(wèn)題：一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備，剛買來(lái)時(shí)故障少，經(jīng)濟(jì)效

5、益高，即使進(jìn)行轉(zhuǎn)讓，處理價(jià)值也高，隨著使用年限的增加，就會(huì)逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時(shí)減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長(zhǎng)、處理價(jià)值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。 3)3)連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題：一般化工生產(chǎn)過(guò)程中，常包含一系列完成生產(chǎn)過(guò)程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。 以上所舉問(wèn)題的發(fā)展過(guò)程都與時(shí)間因素有關(guān)，因此在這類多階段決策問(wèn)題中，階段的劃分常取時(shí)間區(qū)

6、段來(lái)表示，并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān)，這就使它具有了“動(dòng)態(tài)”的含義，所以把處理這類動(dòng)態(tài)問(wèn)題的方法稱為動(dòng)態(tài)規(guī)劃方法。不過(guò)，實(shí)際中尚有許多不包含時(shí)間因素的一類“靜態(tài)”決策問(wèn)題，就其本質(zhì)而言是一次決策問(wèn)題，是非動(dòng)態(tài)決策問(wèn)題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。 4 4）資源分配問(wèn)題：）資源分配問(wèn)題：便屬于這類靜態(tài)問(wèn)題。如：某工業(yè)部門或公司，擬對(duì)其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問(wèn)題原本要求一次確定出對(duì)各企業(yè)的資源分配量，它與時(shí)間因素?zé)o關(guān)，不屬動(dòng)態(tài)決策，但是，我們可以人為地規(guī)定一個(gè)資源分配的階段和順序，從而使其變

7、成一個(gè)多階段決策問(wèn)題(后面我們將詳細(xì)討論這個(gè)問(wèn)題)。 5 5）運(yùn)輸網(wǎng)絡(luò)問(wèn)題）運(yùn)輸網(wǎng)絡(luò)問(wèn)題：如圖7-1所示的運(yùn)輸網(wǎng)絡(luò)，點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等)，要求從v1至v10的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問(wèn)題也是靜態(tài)決策問(wèn)題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個(gè)階段，而作為多階段決策問(wèn)題來(lái)研究。圖7-1 運(yùn)輸網(wǎng)絡(luò)圖示前進(jìn)1三、動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題的特三、動(dòng)態(tài)規(guī)劃求解的多階段決策問(wèn)題的特點(diǎ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)題的求

8、解就比較困難復(fù)雜。而適合于 用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的 多階段決策問(wèn)題。即具有具有“無(wú)后效性無(wú)后效性”的多階段決策過(guò)的多階段決策過(guò)程程。所謂無(wú)后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無(wú)關(guān)。 四、動(dòng)態(tài)規(guī)劃方法導(dǎo)引四、動(dòng)態(tài)規(guī)劃方法導(dǎo)引 例例7.17.1：為了說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以圖7-1所示為例討論的求最短路問(wèn)題的方法。 第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對(duì)它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一段的走

9、法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有322112條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1 v3 v7 v9 v10 ,最短距離是18 顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算 第二種方法即所謂“局部最優(yōu)路徑”法，是說(shuō)某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1 v3 v5 v8 v10 ，全程長(zhǎng)度是20；顯然，這種方法的結(jié)果常是錯(cuò)誤的 第三種方法是動(dòng)態(tài)規(guī)劃方法。利用動(dòng)態(tài)規(guī)劃方法尋

10、求該最短路問(wèn)題的基本思想是，首先將問(wèn)題劃分為4個(gè)階段，每次的選擇總是綜合后繼過(guò)程的最優(yōu)，在各階段所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過(guò)程，動(dòng)態(tài)規(guī)劃方法總是從過(guò)程的最后階段開(kāi)始考慮，然后逆著實(shí)際過(guò)程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。 具體說(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和3。 接著考慮階段3上可能的狀態(tài)v5 ,v6

11、, v7 , 到v10的最優(yōu)決策和最優(yōu)后繼過(guò)程在狀態(tài)V5上，雖然到v8是8，到v9是9，但是綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到v9,最優(yōu)后繼過(guò)程是v5v9 v10 ，最短距離是12同理，狀態(tài)v6的最優(yōu)決策是至v8 ；v7的最優(yōu)決策是到v9 。 同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如v2的最優(yōu)決策是到v5,最優(yōu)路線是v2v5v9v10 ，最短距離是15依此類推，最后可以得到從初始狀態(tài)v1的 最 優(yōu) 決 策 是 到v3最 優(yōu) 路 線 是v1v3v7v9v10 ，全程的最短距離是18。圖51中粗實(shí)線表示各點(diǎn)到的最優(yōu)路

12、線，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。 綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是它的基本思想是，把一個(gè)比較復(fù)雜的問(wèn)題分解為一系列同類型的更易求解的子問(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ì)算工作量比窮舉法大為減少。 7.2 7.2 建模原理建模原理 7.2.1 2.1 概念和術(shù)語(yǔ)概念和術(shù)語(yǔ)（1 1）階

13、段階段 把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾砂阉o問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序個(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，去求解。描述階段的變量稱為階段變量，常用常用k表示。階段的劃分，一般根據(jù)時(shí)間和表示。階段的劃分，一般根據(jù)時(shí)間和空間的自然特征來(lái)劃分。但要便于把問(wèn)題空間的自然特征來(lái)劃分。但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策過(guò)程。的過(guò)程能轉(zhuǎn)化為多階段決策過(guò)程。（2 2）狀態(tài)、狀態(tài)變量和可達(dá)狀態(tài)集）狀態(tài)、狀態(tài)變量和可達(dá)狀態(tài)集 1.狀態(tài)與狀態(tài)變量。用以描述事物用以描述事物( (或或系統(tǒng)系統(tǒng)) )在某特定的時(shí)間與空間域中所處位置在某特定的時(shí)

14、間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)及運(yùn)動(dòng)特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過(guò)程進(jìn)行的先后，每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段階段k k的初始狀態(tài)記作的初始狀態(tài)記作s sk k ，終止?fàn)?，終止?fàn)顟B(tài)記為態(tài)記為s sk+1k+1。但為了清楚起見(jiàn)，通常定義階段的狀態(tài)即指其初始狀態(tài)。 2 2可達(dá)狀態(tài)集可達(dá)狀態(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，

15、可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問(wèn)題而定在圖51所示的最短路問(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 ；后退 （3）決策、決策變量和允許決策集合）決策、決策變量和允許決策集合 所謂決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀

16、態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k=uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示, uk(sk)Uk(sk)允許決策集合實(shí)際是決策的約束條件。 （4 4）、策略和允許策略集合、策略和允許策略集合 策略(Policy)也叫決策序列策略有全過(guò)程策略和k部子策略之分，全過(guò)程策略是指具有n個(gè)階段的全部過(guò)程，由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策

17、序列，簡(jiǎn)稱策略，表示為p1,nu1,u2,un。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當(dāng)k=1時(shí)的k部子策略就是全過(guò)程策略。 在實(shí)際問(wèn)題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。（5 5）狀態(tài)轉(zhuǎn)移方程狀態(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 ，或者說(shuō)，系統(tǒng)由k階段的狀態(tài)

18、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é)公式描述即有：1(,()kkkkksT s us(7-1) 通常稱式(7-1)為多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程。有些問(wèn)題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。 (6) (6) 指標(biāo)函數(shù)指標(biāo)函數(shù) 用來(lái)衡量策略或子策略或決策的

19、效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過(guò)程或各子過(guò)程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問(wèn)題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。例如：圖71的指標(biāo)就是運(yùn)費(fèi)。 (1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為gk 。圖7-1的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3,即v2到v5的距離為3。 (2)過(guò)程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。用Rk(sk,uk)表示第k子過(guò)程的指標(biāo)函數(shù)。如圖7-1的Rk(sk,uk)表示處于第k段sk狀態(tài)

20、且所作決策為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)表示為:(,()kkkkRsps 不過(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)累積形成的，適于用動(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)算，可以是加、減

21、、乘、除、開(kāi)方等。,11111( ,)(,)(,)( ,)k nk nkkkknnkkkkkknnnRRs u sus ug sugsug s u (8-2) 多階段決策問(wèn)題中，常見(jiàn)的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即: (7-3) 有些問(wèn)題，如系統(tǒng)可靠性問(wèn)題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如： (7-4) 總之，具體問(wèn)題的目標(biāo)函數(shù)表達(dá)形式需要視具體問(wèn)題而定。(,)nkiiiikRgsu(,)nkiiiikRgsu (7) (7) 最優(yōu)解最優(yōu)解 用fk(sk)表示第k子過(guò)程指標(biāo)函數(shù) 在狀態(tài)sk下的最優(yōu)值,即 稱fk(sk)為第k子過(guò)程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略稱為sk

22、狀態(tài)下的最優(yōu)子策略，記為pk*(sk) ；而構(gòu)成該子策賂的各段決策稱為該過(guò)程上的最優(yōu)決策，記為 簡(jiǎn)記為)(,(kkkkspsR()( )( ,( ),1,2,kKkkkkkkkpPsf soptR s p skn)(,),(),(11nnkkkksususu11( ) ( ),(), , ( ),1,2, ,kkkkkknnp su s usu skn1,1,2,kkknpuuukn 特別當(dāng)k=1且s1取值唯一時(shí)，f1(s1)就是問(wèn)題的最優(yōu)值，而p1*就是最優(yōu)策略。如例只有唯一始點(diǎn)v1即s1取值唯一,故f1(s1)=18就是例的最優(yōu)值，而 就是例的最優(yōu)策略。 但若s1取值不唯一,則問(wèn)題的最優(yōu)值

23、記為f0有 最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略： 我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問(wèn)題的最 優(yōu)解。137910,pvvvv11011111()()sSfoptfsfss111112()(),npssusuu 按上述定義，所謂最優(yōu)決策是指它們?cè)谌^(guò)程上整體最優(yōu)(即所構(gòu)成的全過(guò)程策略為最優(yōu))，而不一定在各階段上單獨(dú)最優(yōu)。 ( (八八) ) 多階段決策問(wèn)題的數(shù)學(xué)模型多階段決策問(wèn)題的數(shù)學(xué)模型 綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問(wèn)題，亦即具有無(wú)后效性的多階段決策問(wèn)題的數(shù)學(xué)模型呈以下形式:111221(,)(,). .1,2,nnnuukkkkkkkkfopt RR s usususTs

24、usSs tuUkn（8-5） 式中“OPT”表示最優(yōu)化，視具體問(wèn)題取max或min。 上述數(shù)學(xué)模型說(shuō)明了對(duì)于給定的多階段決策過(guò)程，求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列 ，使之既滿足式(7-5)給出的全部約束條件，又使式(7-5)所示的目標(biāo)函數(shù)取得極值，并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí)，過(guò)程狀態(tài)演變序列即最優(yōu)路線12,nu uu121 ,nnssss 1最優(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)策略為：111122( ) ( ),(

25、 ),( ),( )kknnp su su su su s 則對(duì)上述策略中所隱含的任一狀態(tài)而言，第k子 過(guò)程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上 述全過(guò)程最優(yōu)策略p1*中，即為11()(),(),()kkkkkknnpsususus 如第一節(jié)所述，基于上述原理，提出了一 種逆序遞推法；這里可以指出，該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。 3.函數(shù)基本方程 在例中，用標(biāo)號(hào)法求解最短路線的計(jì) 算公式可以概括寫成：(7-6) 其中， 在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離. 是邊界條件，表示全過(guò)程到第四階段終點(diǎn)結(jié)束。5511(

26、)( ) 0( )min ( , ( )(),4,3,2,1kkkkkkkkkkku U sf sf sg s u sfsk(,() )kkkkgsus55()0fs 一般地，對(duì)于n個(gè)階段的決策過(guò)程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第k 階段和第k+1階段間的遞推公式可表示如下： (1)當(dāng)過(guò)程指標(biāo)函數(shù)為下列“和”的形式時(shí)， 相應(yīng)的函數(shù)基本方程為 （77）( )( ) ( ,( )kKkkkkkkkpP sf soptR s p s(,)knniiiuuiko p tgsu1111()0( )( ,( )(),1,2,1kknnkkkkkkkkuUfsf sopt g s u sfsk

27、n n (2) 當(dāng)過(guò)程指標(biāo)函數(shù)為下列“積”的形式時(shí), 相應(yīng)的函數(shù)基本方程為 （78） 可以看出，和、積函數(shù)的基本方程中邊界 條件(即 的取值)是不同的。()()(,()kKkkkkkkkpPsfsoptRsps(,) )knniiiuuiko p tgsu1111() 1( ) ( ,( )(),1,2,1kknnkkkkkkkkuUfsf sopt g s u sfskn n11()nnfs Step1應(yīng)將實(shí)際問(wèn)題恰當(dāng)?shù)胤指畛蒼個(gè)子問(wèn)題(n個(gè)階段)。 Step2正確地定義狀態(tài)變量sk。動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征： (1)要能夠正確地描述受控過(guò)程的變化特征。(2)要滿足無(wú)后效性(

28、3)要滿足可知性。 Step3正確地定義決策變量及各階段的允許決策集合Uk(sk)。 Step4. 能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，sk+1=Tk(sk ,uk)。 Step5根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系目標(biāo)函數(shù)。目標(biāo)函數(shù)。目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)： (1)可分離性。即對(duì)于所有k后部子過(guò)程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策 uk ,uk+1,un,就是說(shuō)它是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)。 (2)要滿足遞推關(guān)系。即 (3)函數(shù) 對(duì)其變?cè)猂k+1來(lái)說(shuō)要嚴(yán)格單調(diào)。,111111( ,),(,)k nkkkknkkkkknRs u sussu Rss111,(,)kkkkk

29、nsuRss例如常見(jiàn)的指標(biāo)函數(shù)是取各段指標(biāo)和的形式 其中 表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成 ：Step6寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程()(,)nkkiiiikRsgsu(,)iiigsu111( ,)(,)kkkkkknRg s uRss 學(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ì)感到困難，但是一定要下決心去思考，在思考過(guò)程中深入理解前文講到的概念和理論。 第三步 動(dòng)手把求解思路整理出來(lái)，或者說(shuō)，把該問(wèn)題

30、作為習(xí)題獨(dú)立的來(lái)做。 第四步 把自己的求解放到一邊，看書(shū)中的求解方法，要充分理解教材中的論述。 第五步 對(duì)照自己的求解，分析成敗。 前進(jìn)動(dòng)態(tài)規(guī)劃的四大要素 狀態(tài)變量及其可達(dá)狀態(tài)集合 sk Sk 決策變量及其允許決策集合 uk Uk 狀態(tài)轉(zhuǎn)移方程 sk+1= Tk (sk ,uk ) 階段效應(yīng) gk ( sk , uk ) 動(dòng)態(tài)規(guī)劃基本方程 fn+1(sn+1) = 0 (邊界條件) fk(sk) = optgk ( sk , uk ) + fk+1(sk+1) k = n,1返回例7.3: 有資金4萬(wàn)元，投資A、B、C三個(gè)項(xiàng)目，每個(gè)項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資

31、效益（萬(wàn)噸）和投 入 資 金 （ 萬(wàn) 元 ） 關(guān) 系 見(jiàn) 下 表 ： 項(xiàng)目 投入資金 A B C 1 萬(wàn)元 15 萬(wàn)噸 13 萬(wàn)噸 11 萬(wàn)噸 2 萬(wàn)元 28 萬(wàn)噸 29 萬(wàn)噸 30 萬(wàn)噸 3 萬(wàn)元 40 萬(wàn)噸 43 萬(wàn)噸 45 萬(wàn)噸 4 萬(wàn)元 51 萬(wàn)噸 55 萬(wàn)噸 58 萬(wàn)噸 求對(duì)三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。1.階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段；狀態(tài)變量xk：投資第k個(gè)項(xiàng)目前的資金數(shù)；2.決策變量dk：第k個(gè)項(xiàng)目的投資；3.決策允許集合：0dkxk4.狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk5.階段指標(biāo)：vk(xk ,dk)見(jiàn)表中所示；6.遞推方程：fk(xk)=maxvk(xk

32、 ,dk)+fk+1(xk+1)7.終端條件：f4(x4)=0最優(yōu)解為x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，即項(xiàng)目A投資1萬(wàn)元，項(xiàng)目B投資0萬(wàn)元，項(xiàng)目C投資3萬(wàn)元，最大效益為60萬(wàn)噸。 例例7.4:7.4:有某種機(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ī)床完好臺(tái)數(shù)將為au1,(a為機(jī)床完好率，0a1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機(jī)床數(shù)量u2的關(guān)系為h=h(u2)=5u

33、2,相應(yīng)的機(jī)床完好率為b(0b1,設(shè)b=0,9),一般情況下a0所以所以 d2(x2)=d2|13-x2 d2 17-x2由此由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2對(duì)于對(duì)于k=1f1(x1)=minc1d1+f2(x2) d1 D1(x1) =min11d1+442-18x2 d1 D1(x1) =min11d1+442-18(x1-r1+d1) d1 D1(x1) =min11d1+442-18(x1-0+d1) d1 D1(x1) =min-7d1-18x1+442 d1 D1(x1) D1(x1)=d1|d1 0,r2 x1-r

34、1+d1 H =d1|d1 0,r2+r1-x1 d1 H+r1-x1 =d1|d1 0,8-x1 d1 9-x1根據(jù)題意根據(jù)題意 x1=2所以所以 D1(x1)=d1| 6 d1 7由此由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357將以上結(jié)果總結(jié)成下表：k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 一臺(tái)設(shè)備的價(jià)格為P，運(yùn)行壽命為n年，每年的維修費(fèi)用是設(shè)備役齡的函

35、數(shù)，記為C(t)，新設(shè)備的役齡為t=0。舊設(shè)備出售的價(jià)格是設(shè)備役齡的函數(shù)，記為S(t)。在n年末，役齡為t的設(shè)備殘值為R(t)?，F(xiàn)有一臺(tái)役齡為T的設(shè)備，在使用過(guò)程中，使用者每年都面臨“繼續(xù)使用”或“更新”的策略，設(shè)設(shè) 備備 更更 新新 問(wèn)問(wèn) 題題階段k：運(yùn)行年份； 狀態(tài)變量xk：設(shè)備的役齡t； 決策變量dk： 繼續(xù)使用更新)()(ReKeepKplaceRdk 狀態(tài)轉(zhuǎn)移方程： KdxRdxkkkk111 階段指標(biāo)： KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0( 遞推方程： KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkk

36、kk) 1()() 1 ()()0(min)()()()()0(min)(111111 終端條件： fn(t)=-R(t) 設(shè)設(shè) 備備 更更 新新 問(wèn)問(wèn) 題題T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表開(kāi)始，終端條件為： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 設(shè)設(shè) 備備 更更 新新 問(wèn)問(wèn) 題題 對(duì)于k=5: KdRdtftCftSCPtf556

37、65) 1()() 1 ()() 0(min)( KdfCfSCPf*5665, 443min)17(13)25(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( KdfCfSCPf*5665,121214min) 8(20)25(211050min) 3 () 2() 1 () 2() 0(min) 2( RdfCfSCPf*5665,244024min040)25(111050min) 4() 3() 1 () 3() 0(min) 3( RdfCfSCPf*5665,307030min070)25(51050min)5()4() 1 ()4()0(min)4(RdfCfSCPf*5665,3510035min0100)25(01050min) 6() 5 () 1 () 5 () 0(min) 5 (RdfCfSCPf*5665,3510035min0100)25