版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1,運(yùn)籌學(xué).,運(yùn)籌學(xué),動(dòng)態(tài)規(guī)劃,2,多階段決策過程的最優(yōu)化動(dòng)態(tài)規(guī)劃的基本概念和基本原理動(dòng)態(tài)規(guī)劃方法的基本步驟動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,本章內(nèi)容重點(diǎn),3,一、多階段決策問題(Multi-Stage decision process)多階段決策過程特點(diǎn):,1.多階段決策過程的最優(yōu)化,4,1.多階段決策過程的最優(yōu)化,動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切,隨著時(shí)間過程的發(fā)展而決定各時(shí)段的決策,產(chǎn)生一個(gè)決策序列,這就是“動(dòng)態(tài)”的意思。然而它也
2、可以處理與時(shí)間無關(guān)的靜態(tài)問題,只要在問題中人為地引入“時(shí)段”因素,就可以將其轉(zhuǎn)化為一個(gè)多階段決策問題。在本章中將介紹這種處理方法。,5,1.多階段決策過程的最優(yōu)化,二、多階段決策問題舉例 屬于多階段決策類的問題很多,例如: 1)工廠生產(chǎn)過程:由于市場需求是一隨著時(shí)間而變化的因素,因此,為了取得全年最佳經(jīng)濟(jì)效益,就要在全年的生產(chǎn)過程中,逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計(jì)劃安排。,6,1.多階段決
3、策過程的最優(yōu)化,2)設(shè)備更新問題:一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備,剛買來時(shí)故障少,經(jīng)濟(jì)效益高,即使進(jìn)行轉(zhuǎn)讓,處理價(jià)值也高,隨著使用年限的增加,就會(huì)逐漸變?yōu)楣收隙?,維修費(fèi)用增加,可正常使用的工時(shí)減少,加工質(zhì)量下降,經(jīng)濟(jì)效益差,并且,使用的年限越長、處理價(jià)值也越低,自然,如果賣去舊的買新的,還需要付出更新費(fèi).因此就需要綜合權(quán)衡決定設(shè)備的使用年限,使總的經(jīng)濟(jì)效益最好。,7,1.多階段決策過程的最優(yōu)化,3)連續(xù)生產(chǎn)過程的控制問題:一般化工生產(chǎn)過程中
4、,常包含一系列完成生產(chǎn)過程的設(shè)備,前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入,因此,應(yīng)該如何根據(jù)各工序的運(yùn)行工況,控制生產(chǎn)過程中各設(shè)備的輸入和輸出,以使總產(chǎn)量最大。,8,1.多階段決策過程的最優(yōu)化,以上所舉問題的發(fā)展過程都與時(shí)間因素有關(guān),因此在這類多階段決策問題中,階段的劃分常取時(shí)間區(qū)段來表示,并且各個(gè)階段上的決策往往也與時(shí)間因素有關(guān),這就使它具有了“動(dòng)態(tài)”的含義,所以把處理這類動(dòng)態(tài)問題的方法稱為動(dòng)態(tài)規(guī)劃方法。不過,實(shí)際中尚有許多不包含時(shí)
5、間因素的一類“靜態(tài)”決策問題,就其本質(zhì)而言是一次決策問題,是非動(dòng)態(tài)決策問題,但是也可以人為地引入階段的概念當(dāng)作多階段決策問題,應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。,9,1.多階段決策過程的最優(yōu)化,4)資源分配問題:便屬于這類靜態(tài)問題。如:某工業(yè)部門或公司,擬對(duì)其所屬企業(yè)進(jìn)行稀缺資源分配,為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對(duì)各企業(yè)的資源分配量,它與時(shí)間因素?zé)o關(guān),不屬動(dòng)態(tài)決策,但是,我們可以人為地規(guī)定一個(gè)資源分配的階段和
6、順序,從而使其變成一個(gè)多階段決策問題(后面我們將詳細(xì)討論這個(gè)問題)。,10,1.多階段決策過程的最優(yōu)化,5)運(yùn)輸網(wǎng)絡(luò)問題:如圖5-1所示的運(yùn)輸網(wǎng)絡(luò),點(diǎn)間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時(shí)間等),要求從fk(sk)至v10的最短路線。 這種運(yùn)輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是,按照網(wǎng)絡(luò)中點(diǎn)的分布,可以把它分為4個(gè)階段,而作為多階段決策問題來研究。,11,1.多階段決策過程的最優(yōu)化,圖5-11 運(yùn)輸網(wǎng)絡(luò)圖示,12,1.多階段
7、決策過程的最優(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ī)劃方法求解的只是一類特殊的多階段決策問題,即具有“無后效性”的多階段決策過程。所謂無后效性,又稱馬爾柯夫性,是指系統(tǒng)從某個(gè)階段往后的發(fā)展,僅由本階段所處的狀態(tài)及其
8、往后的決策所決定,與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。,13,1.多階段決策過程的最優(yōu)化,四、動(dòng)態(tài)規(guī)劃方法導(dǎo)引 例5.1:為了說明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn),下面以圖5-1所示為例討論的求最短路問題的方法。 第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果,再對(duì)它們一一進(jìn)行比較,求出最優(yōu)方案。這里從v1到v10的路程可以分為4個(gè)階段。第一段的走法有三種,第二三兩段的走法各有兩種,
9、第四段的走法僅一種,因此共有3×2×2×1=12條可能的路線,分別算出各條路線的距離,最后進(jìn)行比較,可知最優(yōu)路線是v1 →v3 → v7 → v9 →v10 ,最短距離是18.,14,1.多階段決策過程的最優(yōu)化,顯然,當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí),用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大,而且其中包含著許多重復(fù)計(jì)算. 第二種方法即所謂“局部最優(yōu)路徑”法,是說某人從k出發(fā),他并不顧及全線是否最短,
10、只是選擇當(dāng)前最短途徑,“逢近便走”,錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu),在這種想法指導(dǎo)下,所取決策必是v1 →v3 →v5 → v8 → v10 ,全程長度是20;顯然,這種方法的結(jié)果常是錯(cuò)誤的.,15,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)路線便也隨之
11、得到。 為了找出所有可能狀態(tài)的最優(yōu)后繼過程,動(dòng)態(tài)規(guī)劃方法總是從過程的最后階段開始考慮,然后逆著實(shí)際過程發(fā)展的順序,逐段向前遞推計(jì)算直至始點(diǎn)。,,16,1.多階段決策過程的最優(yōu)化,具體說,此問題先從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
12、和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 。,17,1.多階段決策過程的最優(yōu)化,同樣,當(dāng)階段3上所有可能狀態(tài)的最優(yōu)后繼過程都已求得后,便可以開始考慮階段2上所有可能狀
13、態(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。圖5—1中粗實(shí)線表示各點(diǎn)到的最優(yōu)路線,每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。,18,1.多階段決策過程的最優(yōu)化,綜上所述可見,全枚舉法雖可找出最優(yōu)方案,但不是個(gè)好算法,局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法,只有
14、動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是,把一個(gè)比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題,便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過程分為兩個(gè)階段,先按整體最優(yōu)的思想逆序地求出各個(gè)子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值,然后再順序地求出整個(gè)問題的最優(yōu)策略和最優(yōu)路線。計(jì)算過程中,系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合,從而使計(jì)算工作量比窮舉法大為減少。,19,2.動(dòng)態(tài)規(guī)劃的基本概念,一、動(dòng)態(tài)規(guī)劃的基本概念 使用動(dòng)態(tài)規(guī)劃方法解
15、決多階段決策問題,首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型,同時(shí)也為了今后敘述和討論方便,這里需要對(duì)動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義:,20,2.動(dòng)態(tài)規(guī)劃的基本概念,(一) 階段和階段變量 為了便于求解和表示決策及過程的發(fā)展順序,而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題,稱之為多段決策問題的階段。一個(gè)階段,就是需要作出一個(gè)決策的子問題,通常,階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量
16、叫作階段變量,一般以k表示階段變量.階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目,圖5—1所示的最短路問題就是一個(gè)四階段決策過程。,21,2.動(dòng)態(tài)規(guī)劃的基本概念,(二)狀態(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)
17、可分為初始狀態(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)。,22,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表示,sk∈Sk,可能狀態(tài)集可以是一離散取值的集合,也可以為一連續(xù)的取值區(qū)間
18、,視具體問題而定.在圖5—1所示的最短路問題中,第一階段狀態(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} ;,23,(三)決策、決策變量和允許決策集
19、合 所謂決策,就是確定系統(tǒng)過程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇,是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 用以描述決策變化的量稱之決策變量和狀態(tài)變量一樣,決策變量可以用一個(gè)數(shù),一組數(shù)或一向量來描述,也可以是狀態(tài)變量的函數(shù),記以u(píng)k= uk(sk),表示于階段k狀態(tài)sk時(shí)的決策變量。 決策變量的取值往往也有一定的允許范圍,稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)
20、表示, uk(sk)∈ Uk(sk)允許決策集合實(shí)際是決策的約束條件。,2.動(dòng)態(tài)規(guī)劃的基本概念,24,(四)、策略和允許策略集合 策略(Policy)也叫決策序列.策略有全過程策略和k部子策略之分,全過程策略是指具有n個(gè)階段的全部過程,由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列,簡稱策略,表示為p1,n{u1,u2,…,un}。從k階段到第n階段,依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…
21、,un} ,顯然當(dāng)k=1時(shí)的k部子策略就是全過程策略。 在實(shí)際問題中,由于在各個(gè)階段可供選擇的決策有許多個(gè),因此,它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略),由它們組成的集合,稱之允許策略集合,記作P1,n ,從允許策略集中,找出具有最優(yōu)效果的策略稱為最優(yōu)策略。,2.動(dòng)態(tài)規(guī)劃的基本概念,25,(五)狀態(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)
22、移到終止?fàn)顟B(tài)sk+1 ,或者說,系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1 ,多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。 對(duì)于具有無后效性的多階段決策過程,系統(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)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移,用數(shù)學(xué)公式描述即有:,2.動(dòng)態(tài)規(guī)劃的基本
23、概念,,(5-1),26,通常稱式(5-1)為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式,但是它們的狀態(tài)轉(zhuǎn)移,還是有一定規(guī)律可循的。 (六) 指標(biāo)函數(shù) 用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo),就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問題,指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時(shí)間、效用,等等。例如:圖5—1的指標(biāo)就是運(yùn)費(fèi)。
24、,2.動(dòng)態(tài)規(guī)劃的基本概念,27,(1)階段指標(biāo)函數(shù)(也稱階段效應(yīng))。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo),則它就是第k段指標(biāo)函數(shù),簡記為gk 。圖5-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ù)。如圖5-1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作
25、決策為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)表示為:,2.動(dòng)態(tài)規(guī)劃的基本概念,,28,不過實(shí)際應(yīng)用中往往表示為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)累積形
26、成的,適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)(即目標(biāo)函數(shù)),必須具有關(guān)于階段指標(biāo)的可分離形式.對(duì)于部子過程的指標(biāo)函數(shù)可以表示為: 式中,?表示某種運(yùn)算,可以是加、減、乘、除、開方等。,2.動(dòng)態(tài)規(guī)劃的基本概念,,(5-2),29,多階段決策問題中,常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式,即:
27、 (5-3) 有些問題,如系統(tǒng)可靠性問題,其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式,如: (5-4) 總之,具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。,2.動(dòng)態(tài)規(guī)劃的基本概念,,,30,(七) 最優(yōu)解 用fk(sk)表示第k子過
28、程指標(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)決策,記為 ;有 簡記為,2.動(dòng)態(tài)規(guī)劃的基本概念,,,,,31,特別當(dāng)k=1且s1取值唯一時(shí),f1(s1)就是問題的最優(yōu)值,而p1*就是最優(yōu)策略。如例只有唯一始點(diǎn)v1即s1取值唯一
29、,故f1(s1)=18就是例的最優(yōu)值,而 就是例的最優(yōu)策略。 但若取值不唯一,則問題的最優(yōu)值記為f0有 最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略: 我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最 優(yōu)解。,2.動(dòng)態(tài)規(guī)劃的基本概念,,,,,,,,32,按上述定義,所謂最優(yōu)決策是指它們?cè)谌^程上整體最優(yōu)(即所構(gòu)成的全過程策略為最優(yōu)),而不一定在各階段上單獨(dú)最優(yōu)。 (八) 多階段決策問題的數(shù)學(xué)模型
30、 綜上所述,適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題,亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:,2.動(dòng)態(tài)規(guī)劃的基本概念,(5-5),33,式中“OPT”表示最優(yōu)化,視具體問題取max或min。 上述數(shù)學(xué)模型說明了對(duì)于給定的多階段決策過程,求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列 ,使之既滿足式(5-5)給出的全部約束條件,又使式(5-5
31、)所示的目標(biāo)函數(shù)取得極值,并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí),過程狀態(tài)演變序列即最優(yōu)路線,2.動(dòng)態(tài)規(guī)劃的基本概念,34,二、動(dòng)態(tài)規(guī)劃的最優(yōu)化原理與基本方程 1.標(biāo)號(hào)法 為進(jìn)一步闡明動(dòng)態(tài)規(guī)劃方法的基本思路,我們介紹一種只適用于例這類最優(yōu)路線問題的特殊解法——標(biāo)號(hào)法。標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過分段標(biāo)號(hào)來求出最優(yōu)路線的一種簡便、直觀的方法。通常標(biāo)號(hào)法采取“逆序求解”的方法來尋找問題的最優(yōu)解,即從最后階段開始,逐次向階段數(shù)小的方向
32、推算,最終求得全局最優(yōu)解。,2.動(dòng)態(tài)規(guī)劃的基本原理,35,下面給出標(biāo)號(hào)法的一般步驟: 1.從最后一段標(biāo)起,該段各狀態(tài)(即各始點(diǎn))到終點(diǎn)的距離用數(shù)字分別標(biāo)在各點(diǎn)上方的方格內(nèi),并用粗箭線連接各點(diǎn)和終點(diǎn)。 2.向前遞推,給前一階段的各個(gè)狀態(tài)標(biāo)號(hào)。每個(gè)狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點(diǎn)的最短距離。即為該狀態(tài)到該階段已標(biāo)號(hào)的各終點(diǎn)的段長,再分別加上對(duì)應(yīng)終點(diǎn)上方的數(shù)字而取其最小者。將剛標(biāo)號(hào)的點(diǎn)沿著最短距
33、離所對(duì)應(yīng)的已標(biāo)號(hào)的點(diǎn)用粗箭線連接起來,表示出各剛標(biāo)號(hào)的點(diǎn)到終點(diǎn)的最短路線。,2.動(dòng)態(tài)規(guī)劃的基本原理,36,3.逐次向前遞推,直到將第一階段的狀態(tài)(即起點(diǎn))也標(biāo)號(hào),起點(diǎn)方格內(nèi)的數(shù)字就是起點(diǎn)到終點(diǎn)的最短距離,從起點(diǎn)開始連接終點(diǎn)的粗箭線就是最短路線。 用標(biāo)號(hào)法來求解下例 例5.2:網(wǎng)絡(luò)圖5—2表示某城市的局部道路分布圖。一貨運(yùn)汽車從S出發(fā),最終到達(dá)目的地E。其中Ai(i=1,2,3),Bj(j=1,2)和Ck(k=1,2
34、)是可供汽車選擇的途經(jīng)站點(diǎn),各點(diǎn)連線上的數(shù)字表示兩個(gè)站點(diǎn)問的距離。問此汽車應(yīng)走哪條路線,使所經(jīng)過的路程距離最短?,2.動(dòng)態(tài)規(guī)劃的基本原理,37,2.動(dòng)態(tài)規(guī)劃的基本原理,圖5-2 某城市的局部道路分布圖,38,第一步:先考慮第四階段,即k=4,該階段共有兩個(gè)狀態(tài):C1、C2,設(shè)f4(C1)和f4(C2)分別表示C1、C2到E的最短距離,顯然有f4(C1)=5和f4(C2)=8,邊界條件f5(E)=0 。 第二步:即k
35、=3,該階段共有兩個(gè)狀態(tài):B1 , B2 (1) 從B1出發(fā)有兩種決策:B1→C1,B1→C2 。記d3(B1,C1)表示B1到C1的距離,即,這里的每一種決策的階段指標(biāo)函數(shù)就是距離,所以,B1→C1的階段指標(biāo)函數(shù)為d3(B1,C1)=6,B1→C2的階段指標(biāo)函數(shù)為d3(B1,C2)=5。因此有, f3(B1)=min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}=min(6+5,
36、5+8)=11。那么,從出發(fā)到E的最短路線是B1→C1→E,對(duì)應(yīng)的決策u3(B1) = C1 。,2.動(dòng)態(tài)規(guī)劃的基本原理,39,(2)從B2出發(fā)也有兩種決策:B2→C1,B2→C2同理, 有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}=min(9+5,8+87)=14,那么,從B2出發(fā)到E的最短路線是B2→C1→E,且u3(B2)=C1 。 第三步:即k=2,該階段共有三個(gè)
37、狀態(tài):Al,A2,A3 (1)從Al出發(fā)有兩種決策:A1→B1,A1→B2。則 f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}=min{6+11,5+14}=17,即A1到E的最短路線為A1→B1→C1→E,且u3(A1)=B1 。 (2)從A2出發(fā)也有兩種決策:A2→B1,A2→B2。此時(shí), f2(A2)=min{d2(A2,B1)+f3(B1),d2(A2
38、,B2)+f3(B2)}=min{8+11,6+14}=19,即A2到E的最短路線為A2→B1→C1→E,且u3(A2)=B1。,2.動(dòng)態(tài)規(guī)劃的基本原理,40,(3)從A3出發(fā)也有兩種決策:A3→B1,A3→B2 此時(shí) f2(A2)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}=min{7+11,4+14}=18,即A3到E的最短路線為A3→B1→C1→E ,對(duì)應(yīng)的u2(A3)=B2 。
39、第四步:即k=1,該階段只有一個(gè)狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么, f1(S)=min{d1(S,A1)+f2(A1),d2(S,B2)+f3(B2)}=min{8+11,6+14}=19,即A2到E的最短路線為A2→B1→C1→E ,且u3(A2)=B1 。 那么,從S到E共有三條最短路線: 此時(shí),u1(S)=A1題 和 此時(shí),u1(S)=A3 ,最短距離為21。,
40、2.動(dòng)態(tài)規(guī)劃的基本原理,,,,,,,41,結(jié)果如圖5-3所示。 每個(gè)狀態(tài)上方的方格內(nèi)的數(shù)字表示該狀態(tài)到E的最短距離,首尾相連的粗箭線構(gòu)成每一狀態(tài)到E的最短路線。因此,標(biāo)號(hào)法不但給出起點(diǎn)到終點(diǎn)的最短路線和最短距離,同時(shí)也給出每一狀態(tài)到終點(diǎn)的最短路線及其最短距離。如,A1到E的最短路線是 ,最短矩離是17 圖見下頁,2.動(dòng)態(tài)規(guī)劃的基本原理,42,2.動(dòng)態(tài)規(guī)劃的基本原理,圖5-3某城
41、市局部道路求最短路徑的過程,43,2.最優(yōu)化原理 (貝爾曼最優(yōu)化原理) 作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì):對(duì)于最優(yōu)策略過程中的任意狀態(tài)而言,無論其過去的狀態(tài)和決策如何,余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是,若某一全過程最優(yōu)策略為:,2.動(dòng)態(tài)規(guī)劃的基本原理,則對(duì)上述策略中所隱含的任一狀態(tài)而言, 第k子過程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然 包含在上述全過程最優(yōu)策略p1*中,即為,44,如第一節(jié)所述,基于上
42、述原理,提出了一 種逆序遞推法;這里可以指出,該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。 3.函數(shù)基本方程 在例中,用標(biāo)號(hào)法求解最短路線的計(jì) 算公式可以概括寫成:(5-6) 其中, 在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離,是邊界條件,表示全過程到第四階段終點(diǎn)結(jié)束。,2.動(dòng)態(tài)規(guī)劃的基本原理,,,,45,一般地,對(duì)于
43、n個(gè)階段的決策過程,假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式,第k階段和第k+1階段間的遞推公式可表示如下: (1)當(dāng)過程指標(biāo)函數(shù)為下列“和”的形式時(shí), 相應(yīng)的函數(shù)基本方程為 (5—7),2.動(dòng)態(tài)規(guī)劃的基本原理,,,,46,(2) 當(dāng)過程指標(biāo)函數(shù)為下列“積”的形式時(shí), 相應(yīng)的函數(shù)基本方程為 (5—8) 可以看出,和、積函數(shù)的基本方程中邊界 條件(即
44、 的取值)是不同的。,2.動(dòng)態(tài)規(guī)劃的基本原理,,,,,47,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,標(biāo)號(hào)法僅適用于求解象最短路線問題那樣可以用網(wǎng)絡(luò)圖表示的多階段決策問題。但不少多階段決策問題不能用網(wǎng)絡(luò)圖表示。此時(shí),應(yīng)該用函數(shù)基本方程來遞推求解.一般來說,要用函數(shù)基本方程逆推求解,首先要有效地建立動(dòng)態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個(gè)實(shí)際問題用動(dòng)態(tài)規(guī)劃方法來求解,還必須首先根據(jù)問題的要求。把它
45、構(gòu)造成動(dòng)態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個(gè)動(dòng)態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個(gè)正確的動(dòng)態(tài)規(guī)劃模型,應(yīng)該滿足哪些條件呢?,48,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,1.應(yīng)將實(shí)際問題恰當(dāng)?shù)胤指畛蒼個(gè)子問題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的,或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí),常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n,即k=n。 2.正確地定義狀態(tài)變量sk,使它既能正確地描述過程的狀態(tài),又能滿足無后
46、效性.動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的,動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征:,49,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,(1)要能夠正確地描述受控過程的變化特征。 (2)要滿足無后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定,那么在該階段以后,過程的發(fā)展不受前面各段狀態(tài)的影響,如果所選的變量不具備無后效性,就不能作為狀態(tài)變量來構(gòu)造動(dòng)態(tài)規(guī)劃的模型。 (3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值,
47、可以直接或間接地測(cè)算得到。一般在動(dòng)態(tài)規(guī)劃模型中,狀態(tài)變量大都選取那種可以進(jìn)行累計(jì)的量。此外,在與靜態(tài)規(guī)劃模型的對(duì)應(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)容。,50,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,3.正確地定義決策變量及各階段的允許決策集合Uk(sk),根據(jù)經(jīng)驗(yàn),一般將問題中待求的量,選作動(dòng)態(tài)規(guī)劃模型中的決策變量。或者在把靜態(tài)規(guī)劃模
48、型(如線性與非線性規(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的值,則該段的決策變量uk一經(jīng)確定,第k+1段的狀態(tài)變量sk+1的值也就完全確定,即有sk+1=Tk(sk ,uk),51,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,5.根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù),目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì):
49、(1)可分性,即對(duì)于所有k后部子過程,其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策 uk ,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。 (2)要滿足遞推關(guān)系,即 (3)函數(shù) 對(duì)其變?cè)猂k+1來說要嚴(yán)格單調(diào)。,,,,52,6.寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式 其中 表示第i階段
50、的指標(biāo),它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成 :,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,,53,二.動(dòng)態(tài)規(guī)劃方法的基本步驟 為進(jìn)一步說明動(dòng)態(tài)規(guī)劃模型建立的基本方法及其求解過程,下面通過實(shí)際例子用上述方法具體給出求解動(dòng)態(tài)規(guī)劃方法的基本步驟: 例5.3:有某種機(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ī)床完好
51、臺(tái)數(shù)將為au1,(a為機(jī)床完好率,0<a<1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機(jī)床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應(yīng)的機(jī)床完好率為b(0<b<1,設(shè)b=0,9),一般情況下a<b。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,54,假設(shè)某廠開始有x=1000臺(tái)完好的機(jī)床,現(xiàn)要制定一個(gè)五年生產(chǎn)計(jì)劃,問每年開始時(shí)如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量,以使在5年內(nèi)產(chǎn)品的總產(chǎn)
52、量為最高。 解:首先構(gòu)造這個(gè)問題的動(dòng)態(tài)規(guī)劃模型。 1.變量設(shè)置 (1)設(shè)階段變量k表示年度,因此,階段總數(shù)n=5。 (2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺(tái)數(shù),同時(shí)也是第k-1年度末時(shí)的完好機(jī)床數(shù)量。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,55,(3)決策變量uk,表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù)。于是sk- uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù). 這里sk與uk均
53、取連續(xù)變量,當(dāng)它們有非整數(shù)數(shù)值時(shí).可以這樣理解:如sk=0.6,就表示一臺(tái)機(jī)器在k年度中正常工作時(shí)間只占6/10;uk=0.4時(shí),就表示一臺(tái)機(jī)床在 k年度只有4/10的時(shí)間于高負(fù)荷下工作. 2.狀態(tài)轉(zhuǎn)移方程為 k=1,2,…,6,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,56,3.允許決策集合,在第k段為 4.目標(biāo)函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量,則gk(sk,uk)=8
54、uk+5(sk-uk),因此,目標(biāo)函數(shù) 為 k=1,2,...,5 5.條件最優(yōu)目標(biāo)函數(shù)遞推方程。 令fk(sk)表示由第k年的狀態(tài)sk出發(fā),采取最優(yōu)分配方案到第5年度結(jié)束這段時(shí)間的產(chǎn)品產(chǎn)量,根據(jù)最優(yōu)化原理有以下遞推關(guān)系: k=1,2,
55、3,4,5,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,,57,6.邊界條件為 下面采用逆序遞推計(jì)算法,從第5年度開始遞推計(jì)算。 k=5時(shí)有 顯然,當(dāng)u5*=s5時(shí),f5(s5)有最大值,相應(yīng)的有f5(s5)=8s5 k=4時(shí)有,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,,,,= =,因此,當(dāng)u4*=s4時(shí),有最大值f4(s4)=13.6s4,58,k=3 時(shí)有 可見,當(dāng)u3*=s3時(shí),f3(s3)有最大
56、值f3(s3) =17.55s3. k=2 時(shí)有 = + =此時(shí),當(dāng)取u2*=0時(shí)有最大值,即f2(s2)=20.8s2,其中s2=0.7u1+0.9(s1-u1),3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,,59,k=1時(shí)有 + = 當(dāng)取u1*=0時(shí), f1(s1)有最大值,即f1
57、(s1)=23.7s1,因?yàn)閟1=1000,故f1(s1)=23700個(gè)產(chǎn)品. 按照上述計(jì)算順序?qū)ほ櫟玫较率鲇?jì)算結(jié)果:,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,60,上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)s1固定,終端狀態(tài)s6自由.如果終端也附加上一定的約束條件,那么計(jì)算結(jié)果將會(huì)與之有所差別.例如,若規(guī)定在第五個(gè)年度結(jié)束時(shí),完好的機(jī)床數(shù)量為500臺(tái)(上面只有278臺(tái)),問應(yīng)該如何安排五年的生產(chǎn),使之在滿足這一終端要求的情況下產(chǎn)量最高?,3.動(dòng)態(tài)規(guī)
58、劃方法的基本步驟,61,解:由狀態(tài)轉(zhuǎn)移方程 有得 顯而易見,由于固定了終端的狀態(tài)s6,第五年的決策變量U5的允許決策集合U5(s5)也有了約束,上式說明U5(s5)已退化為一個(gè)點(diǎn),即第五年投入高負(fù)荷下生產(chǎn)的機(jī)床數(shù)只能由式U5=4.5s5-2500作出一種決策,故,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=500,62,當(dāng)k=5時(shí)有
59、 當(dāng)k=4時(shí)有 顯然,只有取u4*=0 ,f4(s4)有最大值,即f4(s4)=21.7s4-7500。同理類推,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,=,=,63,k=3時(shí)有 可知,當(dāng)u3*=0時(shí),f3(s3)有最大值f4(s4)=24.5s3-7500.k=2時(shí)有 此時(shí),當(dāng)u2*=0時(shí)有最大值,即f2(s2)=27.1s2-7500,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,=
60、,=,+,64,k=1時(shí)有 只有取u1*=0時(shí),f1(s1)有最大值,即 f1(s1)=29.4s1-7500 。 由此可見,為了使下一個(gè)五年計(jì)劃開始的一年有完好的機(jī)床500臺(tái),其最優(yōu)策略應(yīng)該為:在前4年中,都應(yīng)該把全部機(jī)床投人低負(fù)荷下生產(chǎn),在第5年,只能把部分完好機(jī)投入高負(fù)荷下生產(chǎn)。根據(jù)最優(yōu)策賂,從始端向終端遞推計(jì)算出各年的狀態(tài),即算出每年年初的完好機(jī)床臺(tái)數(shù),
61、因?yàn)閟1=1000臺(tái),于是有,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,=,=,65,因此,u5*=4.5s5-2500=425(臺(tái)),這就是說第5年里還有204臺(tái)投入低負(fù)荷下生產(chǎn),否則不能保證s6=0.7u5+0.9(u5-s5)=500(臺(tái))。 在上述最優(yōu)決策下,5年里所得最高產(chǎn)量為: f1(s1)=29.4s1-7500=29400-7500=21900(個(gè))。 可見,附加了終端約束條件以后,其最高產(chǎn)量f1(s
62、1)比終端自由時(shí)要低一些。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,(臺(tái)),(臺(tái)),(臺(tái)),(臺(tái)),(臺(tái)),(臺(tái)),66,例5.4:一個(gè)線路網(wǎng)絡(luò)圖,從A到E要修建一條石油管道,必須 在B、C、D處設(shè)立加壓站。各邊上的數(shù)為長度,現(xiàn)需要找一條路使總長度最短。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,67,解: 可分成4個(gè)階段: A到B、B到C、C到D、D到E; 每個(gè)階段 k 的起點(diǎn)稱為狀態(tài)Sk ; 從 k 階段的起點(diǎn)出
63、發(fā)可以做一選擇,即決定到下一階段的哪個(gè)節(jié)點(diǎn),稱為決策Xk ;可見,Sk+1 是由 Sk 和Xk 所決定的。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,68,那么,從A出發(fā)經(jīng)過4個(gè)階段:A到B、B到C、C到D、D到E,逐次作出決策,構(gòu)成從A到E 的一條路線,記為 u 。 即 u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A ,S5 = E 記 d 為兩個(gè)相鄰節(jié)點(diǎn)之間的長度, 如 d(A,B 3)
64、= 3 。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,69,① 記 fk(Sk)為從Sk到E的最短長度,稱為從Sk到E的距離。,那么,f1(A)是從A到E的最短距離,即最優(yōu)策略的值。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,70,② 最短路問題的特點(diǎn):如果從A到E的最優(yōu)策略經(jīng)過某節(jié)點(diǎn),那么這個(gè)策略的從該節(jié)點(diǎn)到E的一段,必定是該節(jié)點(diǎn)到E的所有線路中 Sk最短的一條,即這一段的長度為 fk(Sk)。 (1)逆序法:從E到A。 (2)順序法:對(duì)節(jié)點(diǎn)
65、Sk,從A到Sk 所有線路中,最短的一條的長度記為 φk(S k),例如φ1(A)= 0,稱為問題的邊界條件。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,71,動(dòng)態(tài)規(guī)劃模型建立后,對(duì)基本方程分段求解,不像線性規(guī)劃或非線性規(guī)劃那樣有固定的解法,必須根據(jù)具體問題的特點(diǎn),結(jié)合數(shù)學(xué)技巧靈活求解,如動(dòng)態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值,則可采用離散變量的分段窮舉法。當(dāng)動(dòng)態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量,就要根據(jù)方程的具體情況靈活選取連
66、續(xù)變量的求解方法。如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計(jì)算方法等。還有連續(xù)變量的離散化解法和高維問題的降維法及疏密格子點(diǎn)法等等。,3.動(dòng)態(tài)規(guī)劃方法的基本步驟,72,學(xué)習(xí)方法建議: 第一步 先看問題,充分理解問題的條件、情況及求解目標(biāo)。 第二步 結(jié)合前面講到的理論和解題過程,考慮如何著手進(jìn)行求解該問題的工作。分析針對(duì)該動(dòng)態(tài)規(guī)劃問題的“四大要素、一個(gè)方程”——這一步在開始時(shí)會(huì)感到困難,但是一定要下決心去思考,
67、在思考過程中深入理解前文講到的概念和理論。,4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,73,第三步 動(dòng)手把求解思路整理出來,或者說,把該問題作為習(xí)題獨(dú)立的來做。 第四步 把自己的求解放到一邊,看書中的求解方法,要充分理解教材中的論述。 第五步 對(duì)照自己 的求解,分析成敗。,4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,74,1.動(dòng)態(tài)規(guī)劃的四大要素 ① 狀態(tài)變量及其可能集合 xk ? Xk ② 決策變量及其允許集合
68、 uk ? Uk ③ 狀態(tài)轉(zhuǎn)移方程 xk+1= Tk (xk ,uk ) ④ 階段效應(yīng) rk ( xk , uk ),4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例,75,2. 動(dòng)態(tài)規(guī)劃基本方程 fn+1(xn+1) = 0 (邊界條件) fk(xk) = opt u{rk ( xk , uk ) + fk+1(xk+1) }
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 第五章-整數(shù)規(guī)劃運(yùn)籌學(xué)教程
- 第五章運(yùn)籌學(xué) 線性規(guī)劃在管理中的應(yīng)用案例
- 《運(yùn)籌學(xué)教程》胡云權(quán) 第五版 運(yùn)籌學(xué)復(fù)習(xí)
- 運(yùn)籌學(xué)第五版習(xí)題答案
- 運(yùn)籌學(xué)第五版習(xí)題答案解析
- 運(yùn)籌學(xué)第7章
- 第五章
- 運(yùn)籌學(xué)第2章
- 運(yùn)籌學(xué)胡運(yùn)權(quán)第五版課后答案,運(yùn)籌作業(yè)
- 第五章課件 第五章 營運(yùn)資金管理
- 稅收學(xué)教程第五章課件
- 石油地質(zhì)學(xué)-第五章
- 運(yùn)籌學(xué)》習(xí)題答案運(yùn)籌學(xué)答案
- 運(yùn)籌學(xué)
- 經(jīng)濟(jì)學(xué)第五章練習(xí)
- 生物統(tǒng)計(jì)學(xué)第五章
- 金融市場學(xué)第五章
- 第五章摩擦
- 通風(fēng)第五章
- 第五章 混凝土
評(píng)論
0/150
提交評(píng)論