運(yùn)籌學(xué) 動態(tài)規(guī)劃

運(yùn)籌學(xué)動態(tài)規(guī)劃1第一頁，共六十七頁，編輯于2023年，星期三1多階段決策過程的最優(yōu)化概述多階段決策過程及其最優(yōu)化多階段決策過程舉例動態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn)動態(tài)規(guī)劃方法導(dǎo)引2第二頁，共六十七頁，編輯于2023年，星期三概述動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。由美國數(shù)學(xué)家貝爾曼(RBellman)等人于20世紀(jì)50年代初提出，貝爾曼于1957年出版《動態(tài)規(guī)劃》專著。動態(tài)規(guī)劃用于解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)計(jì)劃與庫存、投資、裝載、排序等問題及生產(chǎn)過程的最優(yōu)控制。動態(tài)規(guī)劃分為離散確定型、離散隨機(jī)型、連續(xù)確定型、連續(xù)隨機(jī)型等類型。主要介紹離散確定型動態(tài)規(guī)劃。3第三頁，共六十七頁，編輯于2023年，星期三多階段決策過程及其最優(yōu)化多階段決策過程指這樣一類特殊的活動過程，它們可以按時間順序分解成若干相互聯(lián)系的階段，稱為時段，在每一個時段都要做出決策，全部過程的決策是一個決策序列。故多階段決策問題屬序貫決策問題。多階段決策過程最優(yōu)化的目標(biāo)是要達(dá)到整個活動過程的總體效果最優(yōu)。決策者在每段決策時不僅考慮本階段最優(yōu)，還考慮對最終目標(biāo)的影響，從而做出全局最優(yōu)決策。動態(tài)規(guī)劃方法雖與時間關(guān)系緊密，但問題中引入時段因素即可看出多階段決策過程。4第四頁，共六十七頁，編輯于2023年，星期三多階段決策過程舉例屬于多階段決策類的問題很多，例如：例1：工廠生產(chǎn)過程。由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計(jì)劃安排。5第五頁，共六十七頁，編輯于2023年，星期三例2：設(shè)備更新問題。一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來時故障少，經(jīng)濟(jì)效益高，即使進(jìn)行轉(zhuǎn)讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費(fèi)用增加，可正常使用的工時減少，加工質(zhì)量下降，經(jīng)濟(jì)效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費(fèi)。因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好。6第六頁，共六十七頁，編輯于2023年，星期三例3：連續(xù)生產(chǎn)過程的控制問題。一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。7第七頁，共六十七頁，編輯于2023年，星期三以上所舉問題的發(fā)展過程都與時間因素有關(guān)，因此在這類多階段決策問題中，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關(guān)，這就使它具有了“動態(tài)”的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。不過，實(shí)際中尚有許多不包含時間因素的一類“靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。8第八頁，共六十七頁，編輯于2023年，星期三例4：資源分配問題。某工業(yè)部門或公司，擬對其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素?zé)o關(guān)，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題。9第九頁，共六十七頁，編輯于2023年，星期三例5：運(yùn)輸網(wǎng)絡(luò)最短路問題。如圖所示的運(yùn)輸網(wǎng)絡(luò)，頂點(diǎn)之間連線上的數(shù)字表示兩地距離(也可以是運(yùn)費(fèi)、時間等)，要求從v1至v10的最短路線。這種運(yùn)輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個階段，而作為多階段決策問題來研究。該圖中圓圈里是網(wǎng)絡(luò)頂點(diǎn)，帶箭頭的是網(wǎng)絡(luò)上的弧(應(yīng)該全部是弧)，弧上的數(shù)字是兩個頂點(diǎn)之間的距離。頂點(diǎn)處括號內(nèi)的值是各頂點(diǎn)到v10的最短距離。最短距離=18；最短路=v1-v3-v7-v9-v10。10第十頁，共六十七頁，編輯于2023年，星期三11第十一頁，共六十七頁，編輯于2023年，星期三動態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn)通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問題的求解就比較困難復(fù)雜。而適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。12第十二頁，共六十七頁，編輯于2023年，星期三動態(tài)規(guī)劃方法導(dǎo)引例6：為了說明動態(tài)規(guī)劃的基本思想方法和特點(diǎn)，下面以例5圖所示為例討論求最短路問題的方法。第一種方法：全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有3×2×2×1＝12條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1→v3→

v7→

v9→v10，最短距離是18。13第十三頁，共六十七頁，編輯于2023年，星期三顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時，用窮舉法求最優(yōu)路線的計(jì)算工作量將會十分龐大，而且其中包含著許多重復(fù)計(jì)算．第二種方法：即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1→v3→v5→v8→v10，全程長度是20；顯然，這種方法的結(jié)果常是錯誤的。14第十四頁，共六十七頁，編輯于2023年，星期三第三種方法：動態(tài)規(guī)劃方法。動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，首先將問題劃分為4個階段，每次的選擇總是綜合后繼過程的最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實(shí)際過程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。15第十五頁，共六十七頁，編輯于2023年，星期三從v10開始，因?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)后繼過程是v5→v9→v10，最短距離是12。同理，狀態(tài)v6的最優(yōu)決策是至v8；v7的最優(yōu)決策是到v9。16第十六頁，共六十七頁，編輯于2023年，星期三同樣，當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后，便可以開始考慮階段2上所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過程，如v2的最優(yōu)決策是到v5，最優(yōu)路線是v2→v5→v9→v10，最短距離是15?！来祟愅?，最后可以得到從初始狀態(tài)v1的最優(yōu)決策是到v3最優(yōu)路線是v1→v3→v7→v9→v10，全程最短距離是18。圖中粗實(shí)線表示各點(diǎn)到的最優(yōu)路線，每點(diǎn)上方括號內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。17第十七頁，共六十七頁，編輯于2023年，星期三綜上所述，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法較科學(xué)有效。動態(tài)規(guī)劃方法基本思想是，把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計(jì)算機(jī)。整個求解過程分為兩個階段，先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。18第十八頁，共六十七頁，編輯于2023年，星期三2動態(tài)規(guī)劃的基本概念和基本原理基本概念階段和階段變量狀態(tài)、狀態(tài)變量和可能狀態(tài)集決策、決策變量和允許決策集合策略和允許策略集合狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)最優(yōu)解基本原理多階段決策問題的數(shù)學(xué)模型動態(tài)規(guī)劃方法的基本思想19第十九頁，共六十七頁，編輯于2023年，星期三階段和階段變量為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段(stage)。一個階段，就是需要作出一個決策的子問題，通常階段是按決策進(jìn)行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量。階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目。例5所示的最短路問題就是一個四階段決策過程。k=1,2,3,4。20第二十頁，共六十七頁，編輯于2023年，星期三狀態(tài)、狀態(tài)變量和可能狀態(tài)集用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運(yùn)動特征的量，稱為狀態(tài)(state)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過程進(jìn)行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。21第二十一頁，共六十七頁，編輯于2023年，星期三一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通常可能狀態(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk?？赡軤顟B(tài)集可以是離散取值的集合，也可以為連續(xù)取值區(qū)間，視具體問題而定。在例5所示的最短路問題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1={v1}；第二階段S2={v2,v3,v4}；第三階段S3={v5,v6,v7}；第四階段S4={v8,v9}。22第二十二頁，共六十七頁，編輯于2023年，星期三決策、決策變量和允許決策集合所謂決策(decision)，就是確定系統(tǒng)過程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇。用以描述決策變化的量稱之決策變量。和狀態(tài)變量一樣，決策變量可以用一個數(shù)、一組數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以uk=uk(sk)，表示于階段k狀態(tài)sk時的決策變量。決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示，uk(sk)∈Uk(sk)。允許決策集合實(shí)際是決策的約束條件。23第二十三頁，共六十七頁，編輯于2023年，星期三策略和允許策略集合策略有全過程策略和k部子策略之分。全過程策略是指具有n個階段的全部過程。由依次進(jìn)行的n個階段決策構(gòu)成的決策序列，簡稱策略(policy)，表示為p1,n={u1,u2,…,un}。從第k階段到第n階段依次進(jìn)行階段決策構(gòu)成的決策序列稱為k部子策略，pk,n={uk,uk+1,…,un}。各個階段可供選擇的決策的不同組合構(gòu)成決策序列(策略)，由它們組成的集合，稱為允許策略集合，記作P1,n，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。24第二十四頁，共六十七頁，編輯于2023年，星期三狀態(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。多階段決策過程的發(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及其決策u1(s1),u2(s2),…,uk-1(sk-1)無關(guān)。通常稱sk+1=Tk(sk,uk(sk))為多階段決策過程的狀態(tài)轉(zhuǎn)移方程，可以簡寫為sk+1=T(sk,uk)。25第二十五頁，共六十七頁，編輯于2023年，星期三指標(biāo)函數(shù)用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。例5的指標(biāo)函數(shù)就是各弧上的運(yùn)費(fèi)。26第二十六頁，共六十七頁，編輯于2023年，星期三(1)階段指標(biāo)函數(shù)(也稱階段效應(yīng))。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡記為gk。例5的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ù)。例5的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點(diǎn)到終點(diǎn)v10的距離。由此可見，Rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)。27第二十七頁，共六十七頁，編輯于2023年，星期三適于用動態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)(即目標(biāo)函數(shù))，必須具有關(guān)于階段指標(biāo)的可分離形式。對于子過程的指標(biāo)函數(shù)可以表示為：Rk,n=Rk,n(sk,uk,sk+1,uk+1,…,sn,un)=gk(sk,uk)gk+1(sk+1,uk+1)…gn(sn,un)。式中，表示某種運(yùn)算，可以是加、減、乘、除、開方等。28第二十八頁，共六十七頁，編輯于2023年，星期三多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即：Rk=∑gi(si,ui)|i=k,…,n有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如：Rk=Πgi(si,ui)|i=k,…,n總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。29第二十九頁，共六十七頁，編輯于2023年，星期三最優(yōu)解用fk(sk)表示第k子過程指標(biāo)函數(shù)在狀態(tài)sk下的最優(yōu)值，即fk(sk)=opt{Rk(sk,Pk(sk))},k=1,2,…,n,pk∈Pk(sk)稱fk(sk)為第k子過程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為pk*(sk)={uk*(sk),uk+1*(sk+1),…,un*(sn)},k=1,2,…,n；簡記為pk*={uk*,uk+1*,…,un*},k=1,2,…,n30第三十頁，共六十七頁，編輯于2023年，星期三特別當(dāng)k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例5只有唯一始點(diǎn)v1即s1取值唯一，故f1(s1)=18就是最優(yōu)值，而p1*={v3,v7,v9,v10}就是最優(yōu)策略。但若取值不唯一，則問題的最優(yōu)值記為f0，最優(yōu)策略即為s1=s1*。我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。按上述定義，所謂最優(yōu)決策是指它們在全過程上整體最優(yōu)(即所構(gòu)成的全過程策略為最優(yōu))，而不一定在各階段上單獨(dú)最優(yōu)。31第三十一頁，共六十七頁，編輯于2023年，星期三多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式：f=optR=R(s1,u1,s2,u2,…,sn,un)sk+1=Tk(sk,uk)sk∈Skuk∈Ukk=1,2,…,n式中opt表示最優(yōu)化，取max或min。上述數(shù)學(xué)模型求取一個(或多個)最優(yōu)策略{u1*,u2*,…,un*}，最優(yōu)路線{s1*,s2*,…,sn*,sn+1*}32第三十二頁，共六十七頁，編輯于2023年，星期三動態(tài)規(guī)劃方法的基本思想(1)將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)。(2)求解時從邊界條件開始，逆(或順)過程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解就是整個問題的最優(yōu)解。(3)動態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益與未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的。33第三十三頁，共六十七頁，編輯于2023年，星期三3動態(tài)規(guī)劃模型的建立與求解建立動態(tài)規(guī)劃模型的步驟逆序解法順序解法標(biāo)號解法基本方程分段求解時的幾種常用算法34第三十四頁，共六十七頁，編輯于2023年，星期三建立動態(tài)規(guī)劃模型的步驟(1)分析問題，識別問題的多階段特性，按時間或空間的順序適當(dāng)劃分為滿足遞推關(guān)系的若干階段，對非時序的靜態(tài)問題要人為賦予時段概念。(2)正確選擇狀態(tài)變量，使之具備兩個必要特征：可知性和無后效性。(3)根據(jù)狀態(tài)變量和決策變量的含義，寫出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)或狀態(tài)轉(zhuǎn)移規(guī)則。(4)明確指標(biāo)函數(shù)Vk,n，最優(yōu)指標(biāo)函數(shù)fk(sk)以及k階段指標(biāo)vk(sk,uk)，寫出最優(yōu)指標(biāo)函數(shù)的遞推關(guān)系及邊界條件。35第三十五頁，共六十七頁，編輯于2023年，星期三例7：投資分配問題。某公司有資金10萬元，若投資于項(xiàng)目i(i=1,2,3)時的投資額為xi時收益分別為g1(x1)=4x1、g2(x2)=9x2、g3(x3)=2x32。問如何分配投資額可使總收益最大？解答：(1)這是一個靜態(tài)最優(yōu)化問題，模型為maxz=4x1+9x2+2x32x1+x2+x3≤10xi≥0(i=1,2,3)(2)可以人為賦予時段概念，分為對項(xiàng)目1投資、對項(xiàng)目2投資和對項(xiàng)目3投資這三個階段。設(shè)uk=xk(k=1,2,3)。s1=10，sk+1=sk-uk。Rk,3=∑gi(xi)，fk(sk)=max{gk(xk)+fk+1(sk+1)}，f4(s4)=0。余略。36第三十六頁，共六十七頁，編輯于2023年，星期三例8：最短路問題。用動態(tài)規(guī)劃求如圖從A到F的最短路。AB1B2C1C3C2C4D1D3E1E2D2F45236877433615235438854437第三十七頁，共六十七頁，編輯于2023年，星期三逆序解法k=6時，s6={F}，則f6(F)=0，u6(F)=Fk=5時，s5∈{E1,E2}，則f5(E1)=d(E1,F)+f6(F)=4+0=4，u5(E1)=Ff5(E2)=d(E2,F)+f6(F)=3+0=3，u5(E2)=Fk=4時，s4∈{D1,D2,D3}，則f4(D1)=min(3+4,5+3)=7，u4(D1)=E1f4(D2)=min(6+4,2+3)=5，u4(D2)=E2f4(D3)=min(1+4,3+3)=5，u4(D3)=E138第三十八頁，共六十七頁，編輯于2023年，星期三k=3時，s3∈{C1,C2,C3,C4}，則f3(C1)=min(5+7,8+5)=12，u3(C1)=D1f3(C2)=min(4+7,5+5)=10，u3(C2)=D2f3(C3)=min(3+5,4+5)=8，u3(C3)=D2,D3f3(C4)=min(8+5,4+5)=9，u3(C4)=D2,D3k=2時，s2∈{B1,B2}，則f2(B1)=min(2+12,3+10,6+18)=13,u2(B1)=C2f2(B2)=min(8+10,7+8,7+9)=15，u2(B2)=C3k=1時，s1={A}，則f1(A)=min{4+13,5+15}=17，u1(A)=B1結(jié)論：最短路長=17，最短路=A-B1-C2-D2-E2-F39第三十九頁，共六十七頁，編輯于2023年，星期三順序解法k=0時，f0(s1)=f0(A)=0，這是邊界條件。k=1時，s2∈{B1,B2}，則f1(B1)=4，u1(B1)=Af1(B2)=5，u1(B2)=Ak=2時，s3∈{C1,C2,C3,C4}，則f2(C1)=2+4=6，u2(C1)=B1f2(C2)=min{3+4,8+5}=7，u2(C2)=B1f2(C3)=min{6+4,7+5}=10，u2(C3)=B1f2(C4)=7+5=12，u2(C4)=B240第四十頁，共六十七頁，編輯于2023年，星期三k=3時，s4∈{D1,D2,D3}，則f3(D1)=11，u3(D1)=C1或C2f3(D2)=12，u3(D2)=C2f3(D3)=14，u3(D3)=C3k=4時，s5∈{E1,E2}，則f4(E1)=14，u4(E1)=D1f4(E2)=14，u4(E2)=D2k=5時，s6={F}，則f5(F)=17，u5(F)=E2結(jié)論：最短路長=17，最短路為A-B1-C2-D2-E2-F41第四十一頁，共六十七頁，編輯于2023年，星期三標(biāo)號法為進(jìn)一步闡明動態(tài)規(guī)劃方法的基本思路，我們介紹一種只適用于這類最優(yōu)路線問題的特殊解法——標(biāo)號法。標(biāo)號法是借助網(wǎng)絡(luò)圖通過分段標(biāo)號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標(biāo)號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。例5圖顯示了標(biāo)號解法的全過程。42第四十二頁，共六十七頁，編輯于2023年，星期三標(biāo)號法的一般步驟：1.從最后一段標(biāo)起，該段各狀態(tài)(即各始點(diǎn))到終點(diǎn)的距離用數(shù)字分別標(biāo)在各點(diǎn)上方的方格內(nèi)，并用粗箭線連接各點(diǎn)和終點(diǎn)。2.向前遞推，給前一階段的各個狀態(tài)標(biāo)號。每個狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點(diǎn)的最短距離。將剛標(biāo)號的點(diǎn)沿著最短距離所對應(yīng)的已標(biāo)號的點(diǎn)用粗箭線連接起來。3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點(diǎn))也標(biāo)號。43第四十三頁，共六十七頁，編輯于2023年，星期三AB1B2C1C3C2C4D1D3E1E2D2F452368774336152354388544(0)(4)(3)(7)(5)(5)(12)(10)(8)(9)(13)(15)(17)用標(biāo)號法計(jì)算例8的最短路。下圖就是完整計(jì)算過程。結(jié)果：與前相同。44第四十四頁，共六十七頁，編輯于2023年，星期三用標(biāo)號法來求解下例例9：最短路問題。如下網(wǎng)絡(luò)圖表示某城市的局部道路分布圖。一貨運(yùn)汽車從S出發(fā)，最終到達(dá)目的地E。其中Ai(i=1,2,3),Bj(j=1,2)和Ck(k=1,2)是可供汽車選擇的途經(jīng)站點(diǎn)，各點(diǎn)連線上的數(shù)字表示兩個站點(diǎn)問的距離。問此汽車應(yīng)走哪條路線，使所經(jīng)過的路程最短?45第四十五頁，共六十七頁，編輯于2023年，星期三46第四十六頁，共六十七頁，編輯于2023年，星期三解答第一步：k=4，s4∈{C1,C2}，邊界條件f5(E)=0，f4(C1)=5，f4(C2)=8。對E、C1、C2標(biāo)號。第二步：k=3，s3∈{B1,B2}。(1)s3=B1：指標(biāo)函數(shù)d3(B1,C1)=6，d3(B1,C2)=5。因此有f3(B1)=min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}=min(6+5,5+8)=11。最短路是11，對應(yīng)的決策u3(B1)=C1。(2)s3=B2：f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}=min(9+5,8+8)=14。最短路是14，且u3(B2)=C1。對B1和B2分別標(biāo)號為11和14。47第四十七頁，共六十七頁，編輯于2023年，星期三第三步：k=2，s2∈{Al,A2,A3}。(1)s2=A1：f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}=min{6+11,5+14}=17，最短路為17，且u3(A1)=B1。(2)s2=A2：f2(A2)=min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)}=min{8+11,6+14}=19，最短路為19，且u3(A2)=B1。(3)s2=A3：f2(A3)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}=min{7+11,4+14}=18，最短路為18，對應(yīng)的u2(A3)=B1或B2。分別給A1,A2,A3標(biāo)號17、19、18。48第四十八頁，共六十七頁，編輯于2023年，星期三第四步：k＝1，s1=S。f1(S)=min{d1(S,A1)+f2(A1),d1(S,A2)+f2(A2),d1(S,A3)+f2(A3)}=min{4+17,3+19,3+18}=21，最短路為21，且u1(S)=A1或A3。給S標(biāo)號21。結(jié)論：從S到E共有三條最短路線：S-A1-B1-C1-E、S-A3-B1-C1-E、S-A3-B2-C1-E。最短距離為21。標(biāo)號結(jié)果見下圖。49第四十九頁，共六十七頁，編輯于2023年，星期三50第五十頁，共六十七頁，編輯于2023年，星期三基本方程分段求解時的幾種常用算法離散變量的分段枚舉法連續(xù)變量的逆序解法、順序解法、離散化解法高維問題的降維法、疏密格子點(diǎn)法(以上方法有的已經(jīng)在前面的例子中有所體現(xiàn)，有的尚未提及，從略。)51第五十一頁，共六十七頁，編輯于2023年，星期三4動態(tài)規(guī)劃方法應(yīng)用舉例動態(tài)規(guī)劃學(xué)習(xí)建議生產(chǎn)計(jì)劃問題求最短路問題(自己完成)資源分配問題背包問題設(shè)備負(fù)荷問題生產(chǎn)庫存問題設(shè)備更新問題52第五十二頁，共六十七頁，編輯于2023年，星期三動態(tài)規(guī)劃學(xué)習(xí)建議第一步：理解條件、情況及求解目標(biāo)第二步：分析“四大要素、一個方程”①狀態(tài)變量及其可能集合xkXk；②決策變量及其允許集合ukUk；③狀態(tài)轉(zhuǎn)移方程xk+1=Tk(xk,uk)；④階段效應(yīng)rk(xk,uk)。一個方程：fn+1(xn+1)=0(邊界條件)；fk(xk)=opt{rk(xk,uk)+fk+1(xk+1)}，k=n,…,1。第三步：整理求解思路第四步：求解第五步：對照理論分析成敗53第五十三頁，共六十七頁，編輯于2023年，星期三生產(chǎn)計(jì)劃問題例10：設(shè)備利用計(jì)劃。某種機(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)行時，機(jī)器完好率為0.9，單臺產(chǎn)量為5噸。設(shè)開始時有1000臺完好機(jī)器，要制訂五年計(jì)劃，每年年初將完好的機(jī)器一部分分配到高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。54第五十四頁，共六十七頁，編輯于2023年，星期三解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。1.變量設(shè)置(1)設(shè)階段變量k表示年度，階段總數(shù)n=5。(2)狀態(tài)變量sk表示k年度初完好機(jī)床臺數(shù)。(3)決策變量uk表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)。于是sk-uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)。Sk=0.6可以表示一臺機(jī)器在k年度中正常工作時間只占6/10；uk=0.4就表示一臺機(jī)床在k年度只有4/10的時間于高負(fù)荷下工作。55第五十五頁，共六十七頁，編輯于2023年，星期三2.狀態(tài)轉(zhuǎn)移方程sk+1=0.7uk+0.9(sk-uk)，k=1,2,…,63.允許決策集合在第k段為Uk(sk)={uk|0≤uk≤xk}4.目標(biāo)函數(shù)設(shè)gk(sk,uk)為第k年度的產(chǎn)量，則gk(sk,uk)=8uk+5(sk-uk)，目標(biāo)函數(shù)Rk=∑gk(sk,uk)，最優(yōu)值fk(sk)=max(xk)，k=1,2,3,4,55.條件最優(yōu)目標(biāo)函數(shù)遞推方程sk+1=max{8uk+5(sk-uk)+fk+1[0.7uk+0.9(sk-uk)]}，k=1,2,3,4,5。6.邊界條件：f6(s6)=056第五十六頁，共六十七頁，編輯于2023年，星期三采用逆序遞推計(jì)算法當(dāng)k=5時有f5(s5)=max{8u5+5(s5-u5)}。當(dāng)u5*=s5時，有最大值f5(s5)=8s5。當(dāng)k=4時有f4(s4)=max{8u4+5(s4-u4)+f5(0.7u4+0.9(s4-u4))}=max{8u4+5(s4-u4)+8(0.7u4+0.9(s4-u4))}=max{1.4u4+12.2s4}。當(dāng)u4*=s4時，有最大值f4(s4)=13.6s4。當(dāng)k=3時有f3(s3)=max{8u3+5(s3-u3)+13.6(0.7u3+0.9(s3-u3))}=max{0.28u3+17.24s3}。當(dāng)u3*=s3時，有最大值f3(s3)=17.52s3。57第五十七頁，共六十七頁，編輯于2023年，星期三當(dāng)k=2時有f2(s2)=max{8u2+5(s2-u2)+17.52(0.7u2+0.9(s2-u2))}=max{20.768s2-0.504u2}。當(dāng)取u2*=0時有最大值f2(s2)=20.768s2，其中s2=0.7u1+0.9(s1-u1)當(dāng)k=1時有f1(s1)=max{5s1+3u1+20.768(0.9s1-0.2u1)}=max{23.6912s1-1.1536u1}。u1*=0時有最大值f1(s1)=23.6912s1。又因?yàn)閟1=1000，故f1(s1)=23691.2個產(chǎn)品。按照上述計(jì)算順序?qū)ほ櫩傻孟鄳?yīng)計(jì)算結(jié)果。58第五十八頁，共六十七頁，編輯于2023年，星期三求最短路徑(自己完成)59第五十九頁，共六十七頁，編輯于2023年，星期三資源分配問題例11：有資金4萬元，投資A、B、C三個項(xiàng)目，每個項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個項(xiàng)目A、B、C的投資效益(萬噸)和投入資金(萬元)關(guān)系見下表。求對三個項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。投入資金ABC1萬元15萬噸13萬噸11萬噸2萬元28萬噸29萬噸30萬噸3萬元40萬噸43萬噸45萬噸4萬元51萬噸55萬噸58萬噸60第六十頁，共六十七頁，編輯于2023年，星期三階段k：每投資一個項(xiàng)目作為一個階段；狀態(tài)變量xk：投資第k個項(xiàng)目前的資金數(shù)；決策變量dk：第k個項(xiàng)目的投資；決策允許集合：0≤dk≤xk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk,dk)見表中所示；遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}終端條件：f4(x4)=0分階段計(jì)算：k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3k=2，0≤d2≤x2，x3=x2-d2k=1，0≤d1≤x1，x2=x1-d161第六十一頁，共六十七頁，編輯于2023年，星期三x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=00010100+0=0111101111+0=1120200+0=0302111111+0=11203030+0=303