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

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

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

3、多階段決策問題中，各階段采取的決策，一般來說是與時間有關，決策依賴于當前的狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”含義。因此，把處理的方法稱為動態(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一、多階段決策過程特點一、多階段決策過程特點:

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

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

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

7、成一個多階段決策問題(后面我們將詳細討論這個問題)。 5 5）運輸網(wǎng)絡問題）運輸網(wǎng)絡問題：如圖7-1所示的運輸網(wǎng)絡，點間連線上的數(shù)字表示兩地距離(也可是運費、時間等)，要求從v1至v10的最短路線。 這種運輸網(wǎng)絡問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。圖7-1 運輸網(wǎng)絡圖示前進1三、動態(tài)規(guī)劃求解的多階段決策問題的特三、動態(tài)規(guī)劃求解的多階段決策問題的特點點 通常多階段決策過程的發(fā)展是通過 狀態(tài)的一系列變換來實現(xiàn)的。一般情況 下，系統(tǒng)在某個階段的狀態(tài)轉移除與本 階段的狀態(tài)和決策有關外，還可能與系 統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關。因此， 問題的求

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

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

10、求該最短路問題的基本思想是，首先將問題劃分為4個階段，每次的選擇總是綜合后繼過程的最優(yōu)，在各階段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。 具體說，此問題先從v10開始，因為v10是終點。再無后繼過程，故可以接著考慮第4階段上所有可能狀態(tài)v8 ,v9的最優(yōu)后續(xù)過程因為從v8 ,v9 到v10的路線是唯一的，所以v8 ,v9 的最優(yōu)決策和最優(yōu)后繼過程就是到v10 ，它們的最短距離分別是5和3。 接著考慮階段3上可能的狀態(tài)v5 ,v6

11、, 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 。 同樣，當階段3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后，便可以開始考慮階段2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如v2的最優(yōu)決策是到v5,最優(yōu)路線是v2v5v9v10 ，最短距離是15依此類推，最后可以得到從初始狀態(tài)v1的 最 優(yōu) 決 策 是 到v3最 優(yōu) 路 線 是v1v3v7v9v10 ，全程的最短距離是18。圖51中粗實線表示各點到的最優(yōu)路

12、線，每點上方括號內(nèi)的數(shù)字表示該點到終點的最短路距離。 綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法屬較科學有效的算法。它的基本思想是它的基本思想是，把一個比較復雜的問題分解為一系列同類型的更易求解的子問題，便于應用計算機。整個求解過程分為兩個階段，先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。計算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計算工作量比窮舉法大為減少。 7.2 7.2 建模原理建模原理 7.2.1 2.1 概念和術語概念和術語（1 1）階

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

14、間與空間域中所處位置及運動特征的量，稱為狀態(tài)及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過程進行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段階段k k的初始狀態(tài)記作的初始狀態(tài)記作s sk k ，終止狀，終止狀態(tài)記為態(tài)記為s sk+1k+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。 2 2可達狀態(tài)集可達狀態(tài)集 一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集?？赡軤顟B(tài)集實際上是關于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，skSk，

15、可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定在圖51所示的最短路問題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1=v1；第二階段則有三個狀態(tài)：v2 ,v3 ,v4 ,狀態(tài)變量s2的狀態(tài)集合S2=v2 ,v3 ,v4 ；第三階段也有三個狀態(tài):v5 ,v6 ,v7 ，狀態(tài)變量s3的狀態(tài)集合S3=v5 ,v6 ,v7 ；第四階段則有二個狀態(tài)： v8 ,v9 , 狀態(tài)變量s4的狀態(tài)集合S4=v8 ,v9 ；后退 （3）決策、決策變量和允許決策集合）決策、決策變量和允許決策集合 所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質是關于狀

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

17、序列，簡稱策略，表示為p1,nu1,u2,un。從k階段到第n階段，依次進行的階段決策構成的決策序列稱為k部子策略,表示為pk,nuk,uk+1,un ，顯然當k=1時的k部子策略就是全過程策略。 在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n ，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。（5 5）狀態(tài)轉移方程狀態(tài)轉移方程 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1 ，或者說，系統(tǒng)由k階段的狀態(tài)

18、sk轉移到了階段k+1的狀態(tài)sk+1 ，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。 對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2, ,sk-1及其決策u1(s1), u2(s2)uk-1(sk-1)無關。系統(tǒng)狀態(tài)的這種轉移，用數(shù)學公式描述即有：1(,()kkkkksT s us(7-1) 通常稱式(7-1)為多階段決策過程的狀態(tài)轉移方程。有些問題的狀態(tài)轉移方程不一定存在數(shù)學表達式，但是它們的狀態(tài)轉移，還是有一定規(guī)律可循的。 (6) (6) 指標函數(shù)指標函數(shù) 用來衡量策略或子策略或決策的

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

20、且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數(shù)，嚴格說來，應表示為:(,()kkkkRsps 不過實際應用中往往表示為Rk(sk,uk)或Rk(sk)。還跟第k 子過程上各段指標函數(shù)有關，過程指標函數(shù)Rk(sk)通常是描述所實現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標，它是由各階段的階段指標函數(shù)gk(sk,uk)累積形成的，適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)（即目標函數(shù)），必須具有關于階段指標的可分離形式對于部子過程的指標函數(shù)可以表示為： 式中，表示某種運算，可以是加、減

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

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

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

24、usSs tuUkn（8-5） 式中“OPT”表示最優(yōu)化，視具體問題取max或min。 上述數(shù)學模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列 ，使之既滿足式(7-5)給出的全部約束條件，又使式(7-5)所示的目標函數(shù)取得極值，并且同時指出執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即最優(yōu)路線12,nu uu121 ,nnssss 1最優(yōu)化原理 （貝爾曼最優(yōu)化原理） 作為一個全過程的最優(yōu)策略具有這樣的性質：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構成一個最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：111122( ) ( ),(

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

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

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

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

29、nsuRss例如常見的指標函數(shù)是取各段指標和的形式 其中 表示第i階段的指標，它顯然是滿足上述三個性質的。所以上式可以寫成 ：Step6寫出動態(tài)規(guī)劃函數(shù)基本方程()(,)nkkiiiikRsgsu(,)iiigsu111( ,)(,)kkkkkknRg s uRss 學習方法建議： 第一步 先看問題，充分理解問題的條件、情況及求解目標。 第二步 結合前面講到的理論和解題過程，考慮如何著手進行求解該問題的工作。分析針對該動態(tài)規(guī)劃問題的“四大要素、一個方程”這一步在開始時會感到困難，但是一定要下決心去思考，在思考過程中深入理解前文講到的概念和理論。 第三步 動手把求解思路整理出來，或者說，把該問題

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

31、效益（萬噸）和投 入 資 金 （ 萬 元 ） 關 系 見 下 表 ： 項目 投入資金 A B C 1 萬元 15 萬噸 13 萬噸 11 萬噸 2 萬元 28 萬噸 29 萬噸 30 萬噸 3 萬元 40 萬噸 43 萬噸 45 萬噸 4 萬元 51 萬噸 55 萬噸 58 萬噸 求對三個項目的最優(yōu)投資分配，使總投資效益最大。1.階段k：每投資一個項目作為一個階段；狀態(tài)變量xk：投資第k個項目前的資金數(shù)；2.決策變量dk：第k個項目的投資；3.決策允許集合：0dkxk4.狀態(tài)轉移方程：xk+1=xk-dk5.階段指標：vk(xk ,dk)見表中所示；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，即項目A投資1萬元，項目B投資0萬元，項目C投資3萬元，最大效益為60萬噸。 例例7.4:7.4:有某種機床,可以在高低兩種不同的負荷下進行生產(chǎn),在高負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機床數(shù)量u1的關系為g=g(u1)=8u1,這時,年終機床完好臺數(shù)將為au1,(a為機床完好率，0a1,設a=0.7).在低負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機床數(shù)量u2的關系為h=h(u2)=5u

33、2,相應的機床完好率為b(0b1,設b=0,9),一般情況下a0所以所以 d2(x2)=d2|13-x2 d2 17-x2由此由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2對于對于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將以上結果總結成下表：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 一臺設備的價格為P，運行壽命為n年，每年的維修費用是設備役齡的函

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

36、kk) 1()() 1 ()()0(min)()()()()0(min)(111111 終端條件： fn(t)=-R(t) 設設 備備 更更 新新 問問 題題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 由上表開始，終端條件為： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 設設 備備 更更 新新 問問 題題 對于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