3.2運籌學動態(tài)規(guī)劃ppt課件

1、動態(tài)規(guī)劃 Dynamic Programmingv 多階段決策過程的最優(yōu)化v 動態(tài)規(guī)劃的基本概念和基本原理v 動態(tài)規(guī)劃模型的建立與求解v 動態(tài)規(guī)劃方法應用舉例1 多階段決策過程的最優(yōu)化v概述v多階段決策過程及其最優(yōu)化v多階段決策過程舉例v動態(tài)規(guī)劃求解的多階段決策問題的特點v動態(tài)規(guī)劃方法導引2概述v動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。由美國數(shù)學家貝爾曼(R Bellman)等人于20世紀50年代初提出，貝爾曼于1957年出版專著。v動態(tài)規(guī)劃用于解決最優(yōu)路徑問題、資源分配問題、生產計劃與庫存、投資、裝載、排序等問題及生產過程的最優(yōu)控制。v動態(tài)規(guī)劃分為離散確定型、離散隨機型、連續(xù)確定型

2、、連續(xù)隨機型等類型。v主要介紹離散確定型動態(tài)規(guī)劃。3多階段決策過程及其最優(yōu)化v多階段決策過程指這樣一類特殊的活動過程，多階段決策過程指這樣一類特殊的活動過程，它們可以按時間順序分解成若干相互聯(lián)系的它們可以按時間順序分解成若干相互聯(lián)系的階段，稱為時段，在每一個時段都要做出決階段，稱為時段，在每一個時段都要做出決策，全部過程的決策是一個決策序列。故多策，全部過程的決策是一個決策序列。故多階段決策問題屬序貫決策問題。階段決策問題屬序貫決策問題。v多階段決策過程最優(yōu)化的目標是要達到整個多階段決策過程最優(yōu)化的目標是要達到整個活動過程的總體效果最優(yōu)。決策者在每段決活動過程的總體效果最優(yōu)。決策者在每段決策時

3、不僅考慮本階段最優(yōu)，還考慮對最終目策時不僅考慮本階段最優(yōu)，還考慮對最終目標的影響，從而做出全局最優(yōu)決策。標的影響，從而做出全局最優(yōu)決策。v動態(tài)規(guī)劃方法雖與時間關系緊密，但問題中動態(tài)規(guī)劃方法雖與時間關系緊密，但問題中引入時段因素即可看出多階段決策過程。引入時段因素即可看出多階段決策過程。4多階段決策過程舉例v屬于多階段決策類的問題很多，例如： v例1：工廠生產過程。由于市場需求是一隨著時間而變化的因素，因而，為了取得全年最佳經濟效益，就要在全年的生產過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產計劃安排。5v例2：設備更新問題。一般企業(yè)用于生產活動的設備，剛買來時故障少，經濟效益高，即使進行

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

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

6、頂點之間連線上的數(shù)字表示兩地距離(也可以是運費、時間等)，要求從v1至v10的最短路線。v這種運輸網絡問題也是靜態(tài)決策問題。但是，按照網絡中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。v該圖中圓圈里是網絡頂點，帶箭頭的是網絡上的弧(應該全部是弧)，弧上的數(shù)字是兩個頂點之間的距離。頂點處括號內的值是各頂點到v10的最短距離。v最短距離=18；最短路=v1-v3-v7-v9-v10。1011動態(tài)規(guī)劃求解的多階段決策問題的特點v通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(xiàn)的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉移除與本階段的狀態(tài)和決策有關外，還可能與系統(tǒng)過去經歷的狀態(tài)和決策有關

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

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

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

10、上，雖然到v8是8，到v9是9，但是綜合考慮后繼過程整體最優(yōu)，取最優(yōu)決策是到v9，最優(yōu)后繼過程是v5v9v10，最短距離是12。同理，狀態(tài)v6的最優(yōu)決策是至v8；v7的最優(yōu)決策是到v9。16v同樣，當階段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。v圖中粗實線表示各點到的最優(yōu)路線，每點上方括號內的數(shù)字表示該點到終點的最短路距離。17v綜上所述，全枚舉法雖可找出

11、最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法較科學有效。v動態(tài)規(guī)劃方法基本思想是，把一個比較復雜的問題分解為一系列同類型的更易求解的子問題，便于應用計算機。v整個求解過程分為兩個階段，先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。182 動態(tài)規(guī)劃的基本概念和基本原理v基本概念v階段和階段變量v狀態(tài)、狀態(tài)變量和可能狀態(tài)集v決策、決策變量和允許決策集合v策略和允許策略集合v狀態(tài)轉移方程v指標函數(shù)v最優(yōu)解v基本原理v多階段決策問題的數(shù)學模型v動態(tài)規(guī)劃方法的基本思想19階段和階段變量v為了便于求解和表示

12、決策及過程的發(fā)展順序，而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段(stage)。一個階段，就是需要作出一個決策的子問題，通常階段是按決策進行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量。階段數(shù)等于多段決策過程從開始到結束所需作出決策的數(shù)目。v例5所示的最短路問題就是一個四階段決策過程。k=1,2,3,4。20狀態(tài)、狀態(tài)變量和可能狀態(tài)集v用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)(state)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。v

13、按照過程進行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止狀態(tài)記為sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。21v一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集?？赡軤顟B(tài)集實際上是關于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，skSk。可能狀態(tài)集可以是離散取值的集合，也可以為連續(xù)取值區(qū)間，視具體問題而定。v在例5所示的最短路問題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1=v1；第二階段S2=v2,v3,v4；第三階段S3=v5,v6,v7；第四階段S4=v8,v9

14、。22決策、決策變量和允許決策集合v所謂決策(decision)，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質是關于狀態(tài)的選擇。v用以描述決策變化的量稱之決策變量。和狀態(tài)變量一樣，決策變量可以用一個數(shù)、一組數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以uk= uk(sk)，表示于階段k狀態(tài)sk時的決策變量。v決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示，uk(sk)Uk(sk)。允許決策集合實際是決策的約束條件。23策略和允許策略集合v策略有全過程策略和k部子策略之分。全過程策略是指具有n個階段的全部過程。由依次進行的n個階段決策構成的決

15、策序列，簡稱策略(policy)，表示為p1,n=u1,u2,un。從第k階段到第n階段依次進行階段決策構成的決策序列稱為k部子策略，pk,n=uk,uk+1,un。v各個階段可供選擇的決策的不同組合構成決策序列(戰(zhàn)略)，由它們組成的集合，稱為允許策略集合，記作P1,n，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。24狀態(tài)轉移方程v系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1。多階段決策過程的發(fā)展用階段狀態(tài)的相繼演變來描述。v對于具有無后效性的多階段決策過程，系統(tǒng)由階段k到階段k+1的狀態(tài)轉移完全由階段k的狀態(tài)

16、sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2,sk-1及其決策u1(s1),u2(s2),uk-1(sk-1)無關。v通常稱sk+1=Tk(sk,uk(sk)為多階段決策過程的狀態(tài)轉移方程，可以簡寫為sk+1=T(sk,uk)。25指標函數(shù)v用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。v對不同問題，指標函數(shù)可以是諸如費用、本錢、產值、利潤、產量、耗量、間隔、時間、效用，等等。v例5的指標函數(shù)就是各弧上的運費。26v(1)階段指標函數(shù)(也稱階段效應)。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(s

17、k)時的指標，則它就是第k段指標函數(shù)，簡記為gk。v例5的gk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，gk(v2,v5)=3，即v2到v5的距離為3。v(2)過程指標函數(shù)(也稱目標函數(shù))。用Rk(sk,uk)表示第k子過程的指標函數(shù)。v例5的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數(shù)。27v 適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)(即目標函數(shù))，必須具有關于階段指標的可分離形式。v 對于子過程的指標函數(shù)可以表示為：v Rk,n=

18、Rk,n(sk,uk,sk+1,uk+1,sn,un)v =gk(sk,uk)gk+1(sk+1,uk+1)gn(sn,un)。v 式中，表示某種運算，可以是加、減、乘、除、開方等。28v多階段決策問題中，常見的目標函數(shù)形式之一 是 取 各 階 段 效 應 之 和 的 形 式 ， 即 ：Rk=gi(si,ui)|i=k,nv有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是 取 各 階 段 效 應 的 連 乘 積 形 式 ， 如 ：Rk=gi(si,ui)|i=k,nv總之，具體問題的目標函數(shù)表達形式需要視具體問題而定。29最優(yōu)解v用fk(sk)表示第k子過程指標函數(shù)在狀態(tài)sk下的最優(yōu)值，即fk(sk)

19、=optRk(sk,Pk(sk),k=1,2,n,pkPk(sk)v稱fk(sk)為第k子過程上的最優(yōu)指標函數(shù)；與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構成該子策賂的各段決策稱為 該 過 程 上 的 最 優(yōu) 決 策 ， 記 為pk*(sk)=uk*(sk),uk+1*(sk+1),un*(sn),k=1,2,n；簡記為pk*=uk*,uk+1*,un*,k=1,2,n30v特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例5只有唯一始點v1即s1取值唯一，故f1(s1)=18就是最優(yōu)值，而p1*=v3,v7,v9,v10就是最優(yōu)策略

20、。v但若取值不唯一，則問題的最優(yōu)值記為f0，最優(yōu)策略即為s1=s1*。我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。v按上述定義，所謂最優(yōu)決策是指它們在全過程上整體最優(yōu)(即所構成的全過程策略為最優(yōu))，而不一定在各階段上單獨最優(yōu)。31多階段決策問題的數(shù)學模型v綜上所述，適于應用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學模型呈以下形式：vf=opt R=R(s1,u1,s2,u2,sn,un)vsk+1=Tk(sk,uk)vskSkvukUkvk=1,2,nv式中opt表示最優(yōu)化，取max或min。v上述數(shù)學模型求取一個(或多個)最優(yōu)策略u1*,u2*,un*，最優(yōu)路

21、線s1*,s2*,sn*,sn+1*32動態(tài)規(guī)劃方法的基本思想v(1)將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標函數(shù)。v(2)求解時從邊界條件開始，逆(或順)過程行進方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結果，最后一個子問題的最優(yōu)解就是整個問題的最優(yōu)解。v(3)動態(tài)規(guī)劃方法是既把當前一段與未來各段分開，又把當前效益與未來效益結合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的。333 動態(tài)規(guī)劃模型的建立與求解v建立動態(tài)規(guī)劃模型的步驟v逆序解法v順序解法v標號解法v基本方程分段求解時的幾種常用算法34建立動態(tài)規(guī)劃模型的

22、步驟v(1)分析問題，識別問題的多階段特性，按時間或空間的順序適當劃分為滿足遞推關系的若干階段，對非時序的靜態(tài)問題要人為賦予時段概念。v(2)正確選擇狀態(tài)變量，使之具備兩個必要特征：可知性和無后效性。v(3)根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)轉移方程sk+1=Tk(sk,uk)或狀態(tài)轉移規(guī)則。v(4)明確指標函數(shù)Vk,n，最優(yōu)指標函數(shù)fk(sk)以及k階段指標vk(sk,uk)，寫出最優(yōu)指標函數(shù)的遞推關系及邊界條件。35v例7：投資分配問題。某公司有資金10萬元，若投資于項目i(i=1,2,3)時的投資額為xi時收益分別為g1(x1)=4x1、g2(x2)=9x2、g3(x3)=2x32。

23、問如何分配投資額可使總收益最大？v解答：(1)這是一個靜態(tài)最優(yōu)化問題，模型為vmax z=4x1+9x2+2x32vx1+x2+x310vxi0(i=1,2,3)v(2)可以人為賦予時段概念，分為對項目1投資、對項目2投資和對項目3投資這三個階段。設uk=xk(k=1,2,3)。s1=10，sk+1=sk-uk。Rk,3=gi(xi)，fk(sk)=maxgk(xk)+fk+1(sk+1)，f4(s4)=0。余略。36v例8：最短路問題。用動態(tài)規(guī)劃求如圖從A到F的最短路。AB1B2C1C3C2C4D1D3E1E2D2F45236877433615235438854437逆序解法vk=6時，s6

24、=F，那么vf6(F)=0，u6(F)=Fvk=5時，s5E1,E2，那么vf5(E1)=d(E1,F)+f6(F)=4+0=4，u5(E1)=Fvf5(E2)=d(E2,F)+f6(F)=3+0=3，u5(E2)=Fvk=4時，s4D1,D2,D3，那么vf4(D1)=min(3+4,5+3)=7，u4(D1)=E1vf4(D2)=min(6+4,2+3)=5，u4(D2)=E2vf4(D3)=min(1+4,3+3)=5，u4(D3)=E138vk=3時，s3C1,C2,C3,C4，那么vf3(C1)=min(5+7,8+5)=12，u3(C1)=D1vf3(C2)=min(4+7,5+5

25、)=10，u3(C2)=D2vf3(C3)=min(3+5,4+5)=8，u3(C3)=D2,D3vf3(C4)=min(8+5,4+5)=9，u3(C4)=D2,D3vk=2時，s2B1,B2，那么vf2(B1)=min(2+12,3+10,6+18)=13,u2(B1)=C2vf2(B2)=min(8+10,7+8,7+9)=15，u2(B2)=C3vk=1時，s1=A，那么vf1(A)=min4+13,5+15=17，u1(A)=B1v結論：最短路長=17，最短路=A-B1-C2-D2-E2-F39順序解法vk=0時，f0(s1)=f0(A)=0，這是邊界條件。vk=1時，s2B1,B2

26、，那么vf1(B1)=4，u1(B1)=Avf1(B2)=5，u1(B2)=Avk=2時，s3C1,C2,C3,C4，那么vf2(C1)=2+4=6，u2(C1)=B1vf2(C2)=min3+4,8+5=7，u2(C2)=B1vf2(C3)=min6+4,7+5=10，u2(C3)=B1vf2(C4)=7+5=12，u2(C4)=B240vk=3時，s4D1,D2,D3，那么vf3(D1)=11，u3(D1)=C1或C2vf3(D2)=12，u3(D2)=C2vf3(D3)=14，u3(D3)=C3vk=4時，s5E1,E2，那么vf4(E1)=14，u4(E1)=D1vf4(E2)=14，

27、u4(E2)=D2vk=5時，s6=F，那么vf5(F)=17，u5(F)=E2v結論：最短路長=17，最短路為A-B1-C2-D2-E2-F41標號法v為進一步闡明動態(tài)規(guī)劃方法的基本思路，我們介紹一種只適用于這類最優(yōu)路線問題的特殊解法標號法。v標號法是借助網絡圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。v例5圖顯示了標號解法的全過程。42v標號法的一般步驟：v1.從最后一段標起，該段各狀態(tài)(即各始點)到終點的距離用數(shù)字分別標在各點上方的方格內，并用粗箭線連接各點和終點。v

28、2.向前遞推，給前一階段的各個狀態(tài)標號。每個狀態(tài)上方方格內的數(shù)字表示該狀態(tài)到終點的最短距離。將剛標號的點沿著最短距離所對應的已標號的點用粗箭線連接起來。v3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標號。43AB1B2C1C3C2C4D1D3E1E2D2F452368774336152354388544(0)(4)(3)(7)(5)(5)(12)(10)(8)(9)(13)(15)(17)v用標號法計算例8的最短路。v下圖就是完整計算過程。結果：與前相同。44用標號法來求解下例v例9：最短路問題。如下網絡圖表示某城市的局部道路分布圖。一貨運汽車從S出發(fā)，最終到達目的地E。其中Ai(i=1

29、,2,3),Bj(j=1,2)和Ck(k=1,2)是可供汽車選擇的途經站點，各點連線上的數(shù)字表示兩個站點問的距離。問此汽車應走哪條路線，使所經過的路程最短?4546解答v第一步：k=4，s4C1,C2，邊界條件f5(E)=0，f4(C1)=5，f4(C2)=8。對E、C1、C2標號。v第二步：k=3，s3B1,B2。v(1)s3=B1：指標函數(shù)d3(B1,C1)=6，d3(B1,C2)=5。因此有f3(B1)=mind3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)=min(6+5,5+8)=11。最短路是11，對應的決策u3(B1) = C1。v(2)s3=B2：f3(B2)

30、=mind3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)=min(9+5,8+8)=14。最短路是14，且u3(B2)=C1。v對B1和B2分別標號為11和14。47v第三步：k=2，s2Al,A2,A3。v(1)s2=A1：f2(A1)=mind2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)=min6+11,5+14=17，最短路為17，且u3(A1)=B1。v(2)s2=A2：f2(A2)=mind2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)=min8+11,6+14=19，最短路為19，且u3(A2)=B1。v(3)s2=A3：f2

31、(A3)=mind2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)=min7+11,4+14=18，最短路為18，對應的u2(A3)=B1或B2。v分別給A1,A2,A3標號17、19、18。48v第四步：k1，s1=S。f1(S)=mind1(S,A1)+f2(A1),d1(S,A2)+f2(A2),d1(S,A3)+f2(A3)=min4+17,3+19,3+18=21，最短路為21，且u1(S)=A1或A3。給S標號21。v結論：從S到E共有三條最短路線：S-A1-B1-C1-E、S-A3-B1-C1-E、S-A3-B2-C1-E。最短距離為21。標號結果見下圖。4950

32、基本方程分段求解時的幾種常用算法v離散變量的分段枚舉法v連續(xù)變量的逆序解法、順序解法、離散化解法v高維問題的降維法、疏密格子點法v(以上方法有的已經在前面的例子中有所體現(xiàn)，有的尚未提及，從略。)514 動態(tài)規(guī)劃方法應用舉例v動態(tài)規(guī)劃學習建議v生產計劃問題v求最短路問題(自己完成)v資源分配問題v背包問題v設備負荷問題v生產庫存問題v設備更新問題52動態(tài)規(guī)劃學習建議v第一步：理解條件、情況及求解目標v第二步：分析“四大要素、一個方程”v狀態(tài)變量及其可能集合 xk Xk；v決策變量及其允許集合ukUk ；v狀態(tài)轉移方程xk+1=Tk(xk,uk) ；v階段效應rk (xk,uk)。 v一個方程：f

33、n+1(xn+1)=0(邊界條件)；fk(xk)=optrk(xk,uk) +fk+1(xk+1)，k=n,1。v第三步：整理求解思路v第四步：求解v第五步：對照理論分析成敗53生產計劃問題v例10：設備利用計劃。某種機器可以在高、低兩種負荷下生產。高負荷生產條件下機器完好率為0.7，即如果年初有u臺完好機器投入生產，則年末完好的機器數(shù)量為0.7u臺。系數(shù)0.7稱為完好率。年初投入高負荷運行的u臺機器的年產量為8u噸。系數(shù)8稱為單臺產量。低負荷運行時，機器完好率為0.9，單臺產量為5噸。設開始時有1000臺完好機器，要制訂五年計劃，每年年初將完好的機器一部分分配到高負荷生產，剩下的機器分配到低

34、負荷生產，使五年的總產量為最高。54v解：首先構造這個問題的動態(tài)規(guī)劃模型。v1.變量設置v(1)設階段變量k表示年度，階段總數(shù)n=5。v(2)狀態(tài)變量sk表示k年度初完好機床臺數(shù)。v(3)決策變量uk表示第k年度中分配于高負荷下生產的機床臺數(shù)。于是sk-uk便為該年度中分配于低負荷下生產的機床臺數(shù)。Sk=0.6可以表示一臺機器在k年度中正常工作時間只占6/10；uk=0.4就表示一臺機床在k年度只有4/10的時間于高負荷下工作。55v2.狀態(tài)轉移方程vsk+1=0.7uk+0.9(sk-uk)，k=1,2,6v3.允許決策集合v在第k段為Uk(sk)=uk|0ukxkv4.目標函數(shù)v設 g k

35、 ( s k , u k ) 為 第 k 年 度 的 產 量 ， 則gk(sk,uk)=8uk+5(sk-uk)，目標函數(shù)Rk=gk(sk,uk)，最優(yōu)值fk(sk)=max(xk)，k=1,2,3,4,5v5.條件最優(yōu)目標函數(shù)遞推方程vsk+1=max8uk+5(sk-uk)+fk+10.7uk+0.9(sk-uk)，k=1,2,3,4,5。v6.邊界條件：f6(s6)=056v采用逆序遞推計算法v當k=5時有f5(s5)=max8u5+5(s5-u5)。當u5*=s5時，有最大值f5(s5)=8s5。v當k=4時有f4(s4)=max8u4+5(s4-u4)+f5(0.7u4+0.9(s4

36、-u4)=max8u4+5(s4-u4)+8(0.7u4+0.9(s4-u4)=max1.4u4+12.2s4。當u4*=s4時，有最大值f4(s4)=13.6s4。v當k=3時有f3(s3)=max8u3+5(s3-u3)+13.6(0.7u3+0.9(s3-u3)=max0.28u3+17.24s3。當u3*=s3時，有最大值f3(s3) =17.52s3。57v當k=2時有f2(s2)=max8u2+5(s2-u2)+17.52(0.7u2+0.9(s2-u2)=max20.768s2-0.504u2。當取u2*=0時有最大值f2(s2)=20.768s2，其中s2=0.7u1+0.9(

37、s1-u1)v當k=1時有f1(s1)=max5s1+3u1+20.768(0.9s1-0.2u1)=max23.6912s1-1.1536u1。u1*=0時有最大值f1(s1)=23.6912s1。又因為s1=1000，故f1(s1)=23691.2個產品。v按照上述計算順序尋蹤可得相應計算結果。58求最短路徑(自己完成)BACBDBCDEC21231231251121410610413121139658105259資源分配問題v例11：有資金4萬元，投資A、B、C三個項目，每個項目的投資效益與投入該項目的資金有關。三個項目A、B、C的投資效益(萬噸)和投入資金(萬元)關系見下表。求對三個項

38、目的最優(yōu)投資分配，使總投資效益最大。投入資金ABC1萬元15萬噸13萬噸11萬噸2萬元28萬噸29萬噸30萬噸3萬元40萬噸43萬噸45萬噸4萬元51萬噸55萬噸58萬噸60v 階段k：每投資一個項目作為一個階段；v 狀態(tài)變量xk：投資第k個項目前的資金數(shù)；v 決策變量dk：第k個項目的投資；v 決策允許集合：0dkxkv 狀態(tài)轉移方程：xk+1=xk-dkv 階段指標：vk(xk ,dk)見表中所示；v 遞推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)v 終端條件：f4(x4)=0v 分階段計算：v k=4，f4(x4)=0v k=3，0d3x3，x4=x3-d3v k=2，0d2x2，x3=x2-d2v k=1，0d1x1，x2=x1-d161x3D3(x3)x4v3