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

1第四章動態(tài)規(guī)劃多階段決策過程的最優(yōu)化動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃方法的基本步驟動態(tài)規(guī)劃方法應(yīng)用舉例本章內(nèi)容重點2一、多階段決策問題 (Multi-Stagedecisionprocess)多階段決策過程特點:狀態(tài)

x1階段1T1決策u1狀態(tài)

x2決策u2階段2T2狀態(tài)

x3...狀態(tài)

xk決策uk階段kTk狀態(tài)

xk+1...狀態(tài)

xn決策un階段nTn狀態(tài)

xn+11.多階段決策過程的最優(yōu)化31.多階段決策過程的最優(yōu)化

動態(tài)規(guī)劃方法與“時間”關(guān)系很密切，隨著時間過程的發(fā)展而決定各時段的決策，產(chǎn)生一個決策序列，這就是“動態(tài)”的意思。然而它也可以處理與時間無關(guān)的靜態(tài)問題，只要在問題中人為地引入“時段”因素，就可以將其轉(zhuǎn)化為一個多階段決策問題。在本章中將介紹這種處理方法。41.多階段決策過程的最優(yōu)化

二、多階段決策問題舉例屬于多階段決策類的問題很多，例如：

1)工廠生產(chǎn)過程：由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經(jīng)濟(jì)效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計劃安排。51.多階段決策過程的最優(yōu)化

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ì)效益最好。61.多階段決策過程的最優(yōu)化

3)連續(xù)生產(chǎn)過程的控制問題：一般化工生產(chǎn)過程中，常包含一系列完成生產(chǎn)過程的設(shè)備，前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入，因此，應(yīng)該如何根據(jù)各工序的運(yùn)行工況，控制生產(chǎn)過程中各設(shè)備的輸入和輸出，以使總產(chǎn)量最大。71.多階段決策過程的最優(yōu)化

以上所舉問題的發(fā)展過程都與時間因素有關(guān)，因此在這類多階段決策問題中，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關(guān)，這就使它具有了“動態(tài)”的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。不過，實際中尚有許多不包含時間因素的一類“靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當(dāng)作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。81.多階段決策過程的最優(yōu)化

4）資源分配問題：便屬于這類靜態(tài)問題。如：某工業(yè)部門或公司，擬對其所屬企業(yè)進(jìn)行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素?zé)o關(guān)，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題(后面我們將詳細(xì)討論這個問題)。91.多階段決策過程的最優(yōu)化

5）運(yùn)輸網(wǎng)絡(luò)問題：如圖5-1所示的運(yùn)輸網(wǎng)絡(luò)，點間連線上的數(shù)字表示兩地距離(也可是運(yùn)費(fèi)、時間等)，要求從fk(sk)至v10的最短路線。這種運(yùn)輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。101.多階段決策過程的最優(yōu)化圖5-1運(yùn)輸網(wǎng)絡(luò)圖示111.多階段決策過程的最優(yōu)化

三、動態(tài)規(guī)劃求解的多階段決策問題的特點

通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(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)。121.多階段決策過程的最優(yōu)化

四、動態(tài)規(guī)劃方法導(dǎo)引例5.1：為了說明動態(tài)規(guī)劃的基本思想方法和特點，下面以圖5-1所示為例討論的求最短路問題的方法。第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從v1到v10的路程可以分為4個階段。第一段的走法有三種，第二三兩段的走法各有兩種，第四段的走法僅一種，因此共有3×2×2×1＝12條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是v1→v3→

v7→

v9→v10

,最短距離是18．131.多階段決策過程的最優(yōu)化

顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復(fù)計算．第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1→v3→v5→

v8→

v10

，全程長度是20；顯然，這種方法的結(jié)果常是錯誤的．141.多階段決策過程的最優(yōu)化

第三種方法是動態(tài)規(guī)劃方法。動態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，首先將問題劃分為4個階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。151.多階段決策過程的最優(yōu)化

具體說，此問題先從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,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

。161.多階段決策過程的最優(yōu)化

同樣，當(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。圖5—1中粗實線表示各點到的最優(yōu)路線，每點上方括號內(nèi)的數(shù)字表示該點到終點的最短路距離。171.多階段決策過程的最優(yōu)化

綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計算機(jī)。整個求解過程分為兩個階段，先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。計算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計算工作量比窮舉法大為減少。18

2.動態(tài)規(guī)劃的基本概念

一、動態(tài)規(guī)劃的基本概念

使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，同時也為了今后敘述和討論方便，這里需要對動態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義：

(一)階段和階段變量

為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進(jìn)行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目，圖5—1所示的最短路問題就是一個四階段決策過程。19

2.動態(tài)規(guī)劃的基本概念

（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集

1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運(yùn)動特征的量，稱為狀態(tài)。反映狀態(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)。20

2.動態(tài)規(guī)劃的基本概念

2．可能狀態(tài)集一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定．在圖5—1所示的最短路問題中，第一階段狀態(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}

；21

（三）決策、決策變量和允許決策集合所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質(zhì)是關(guān)于狀態(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)允許決策集合實際是決策的約束條件。

2.動態(tài)規(guī)劃的基本概念

22

（四）、策略和允許策略集合策略(Policy)也叫決策序列．策略有全過程策略和k部子策略之分，全過程策略是指具有n個階段的全部過程，由依次進(jìn)行的n個階段決策構(gòu)成的決策序列，簡稱策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}，顯然當(dāng)k=1時的k部子策略就是全過程策略。在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n

，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。

2.動態(tài)規(guī)劃的基本概念

23

（五）狀態(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

，或者說，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(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)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：

2.動態(tài)規(guī)劃的基本概念

(5-1)通常稱式(5-1)為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。24

(六)指標(biāo)函數(shù)用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。例如：圖5—1的指標(biāo)就是運(yùn)費(fèi)。

2.動態(tài)規(guī)劃的基本概念

25

(1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標(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)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴(yán)格說來，應(yīng)表示為:

2.動態(tài)規(guī)劃的基本概念

26

不過實際應(yīng)用中往往表示為Rk(sk,uk)或Rk(sk)。還跟第k子過程上各段指標(biāo)函數(shù)有關(guān)，過程指標(biāo)函數(shù)Rk(sk)通常是描述所實現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)gk(sk,uk)累積形成的，適于用動態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式．對于k后部子過程的指標(biāo)函數(shù)可以表示為：式中，

表示某種運(yùn)算，可以是加、減、乘、除、開方等。

2.動態(tài)規(guī)劃的基本概念

(5-2)27

多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:

(5-3)

有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如：

(5-4)

總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。

2.動態(tài)規(guī)劃的基本概念

28

(七)最優(yōu)解用fk(sk)表示第k子過程指標(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.動態(tài)規(guī)劃的基本概念

29

特別當(dāng)k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例只有唯一始點v1即s1取值唯一,故f1(s1)=18就是例1的最優(yōu)值，而就是例1的最優(yōu)策略。但若取值不唯一,則問題的最優(yōu)值記為f0有

最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略：

我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。

2.動態(tài)規(guī)劃的基本概念30

按上述定義，所謂最優(yōu)決策是指它們在全過程上整體最優(yōu)(即所構(gòu)成的全過程策略為最優(yōu))，而不一定在各階段上單獨最優(yōu)。

(八)多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:

2.動態(tài)規(guī)劃的基本概念

（5-5）31

式中“OPT”表示最優(yōu)化，視具體問題取max或min。

上述數(shù)學(xué)模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列，使之既滿足式(5-5)給出的全部約束條件，又使式(5-5)所示的目標(biāo)函數(shù)取得極值，并且同時指出執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即最優(yōu)路線

2.動態(tài)規(guī)劃的基本概念32

二、動態(tài)規(guī)劃的最優(yōu)化原理與基本方程

1．標(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)解。

2.動態(tài)規(guī)劃的基本原理

33

下面給出標(biāo)號法的一般步驟：

1.從最后一段標(biāo)起，該段各狀態(tài)(即各始點)到終點的距離用數(shù)字分別標(biāo)在各點上方的方格內(nèi)，并用粗箭線連接各點和終點。

2.向前遞推，給前一階段的各個狀態(tài)標(biāo)號。每個狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點的最短距離。即為該狀態(tài)到該階段已標(biāo)號的各終點的段長，再分別加上對應(yīng)終點上方的數(shù)字而取其最小者。將剛標(biāo)號的點沿著最短距離所對應(yīng)的已標(biāo)號的點用粗箭線連接起來，表示出各剛標(biāo)號的點到終點的最短路線。

2.動態(tài)規(guī)劃的基本原理34

3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標(biāo)號，起點方格內(nèi)的數(shù)字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。用標(biā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)是可供汽車選擇的途經(jīng)站點，各點連線上的數(shù)字表示兩個站點問的距離。問此汽車應(yīng)走哪條路線，使所經(jīng)過的路程距離最短?

2.動態(tài)規(guī)劃的基本原理35

2.動態(tài)規(guī)劃的基本原理圖5-2某城市的局部道路分布圖36

第一步：先考慮第四階段，即k=4，該階段共有兩個狀態(tài)：C1、C2，設(shè)f4(C1)和f4(C2)分別表示C1、C2到E的最短距離，顯然有f4(C1)=5和f4(C2)=8，邊界條件f5(E)=0。第二步：即k=3,該階段共有兩個狀態(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，5＋8)＝11。那么，從出發(fā)到E的最短路線是B1→C1→E，對應(yīng)的決策u3(B1)=C1

。

2.動態(tài)規(guī)劃的基本原理37

(2)從B2出發(fā)也有兩種決策:B2→C1,B2→C2同理,有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+8)＝14，那么，從B2出發(fā)到E的最短路線是B2→C1→E，且u3(B2)=C1。

第三步：即k＝2,該階段共有三個狀態(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。此時，f2(A2)＝min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E，且u3(A2)＝B1。

2.動態(tài)規(guī)劃的基本原理38

(3)從A3出發(fā)也有兩種決策:A3→B1,A3→B2

此時

f2(A3)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}＝min{7+11，4+14}＝18，即A3到E的最短路線為A3→B1→C1→E

，對應(yīng)的u2(A3)＝B2

。第四步：即k＝1，該階段只有一個狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么,f1(S)=min{d1(S,A1)+f2(A1),d2(S,A2)+f2(A2)，d3(S,A3)+f2(A3)}＝min{4+17，3+19,3+18}＝21，那么,從S到E共有三條最短路線：

此時,u1(S)＝A1,u1(S)＝A3

，最短距離為21。

2.動態(tài)規(guī)劃的基本原理39

結(jié)果如圖5-3所示。每個狀態(tài)上方的方格內(nèi)的數(shù)字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構(gòu)成每一狀態(tài)到E的最短路線。因此，標(biāo)號法不但給出起點到終點的最短路線和最短距離，同時也給出每一狀態(tài)到終點的最短路線及其最短距離。如,A1到E的最短路線是,最短矩離是17

圖見下頁

2.動態(tài)規(guī)劃的基本原理40

2.動態(tài)規(guī)劃的基本原理圖5-3某城市局部道路求最短路徑的過程41

2．最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：

2.動態(tài)規(guī)劃的基本原理

則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為42

如第一節(jié)所述，基于上述原理，提出了一種逆序遞推法；這里可以指出，該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動態(tài)規(guī)劃的函數(shù)基本方程。

3.函數(shù)基本方程在上例中，用標(biāo)號法求解最短路線的計算公式可以概寫成：(5-6)

其中在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離,是邊界條件，表示全過程到第四階段終點結(jié)束。

2.動態(tài)規(guī)劃的基本原理43

一般地，對于n個階段的決策過程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：

(1)當(dāng)過程指標(biāo)函數(shù)為下列“和”的形式時，

相應(yīng)的函數(shù)基本方程為

（5—7）

2.動態(tài)規(guī)劃的基本原理44

(2)當(dāng)過程指標(biāo)函數(shù)為下列“積”的形式時,

相應(yīng)的函數(shù)基本方程為

（5—8）可以看出，和、積函數(shù)的基本方程中邊界條件(即的取值)是不同的。

2.動態(tài)規(guī)劃的基本原理453.動態(tài)規(guī)劃方法的基本步驟

標(biāo)號法僅適用于求解象最短路線問題那樣可以用網(wǎng)絡(luò)圖表示的多階段決策問題。但不少多階段決策問題不能用網(wǎng)絡(luò)圖表示。此時,應(yīng)該用函數(shù)基本方程來遞推求解.一般來說,要用函數(shù)基本方程逆推求解,首先要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個實際問題用動態(tài)規(guī)劃方法來求解,還必須首先根據(jù)問題的要求。把它構(gòu)造成動態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個動態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個正確的動態(tài)規(guī)劃模型,應(yīng)該滿足哪些條件呢?463.動態(tài)規(guī)劃方法的基本步驟

1．應(yīng)將實際問題恰當(dāng)?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數(shù)n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個特征：473.動態(tài)規(guī)劃方法的基本步驟

(1)要能夠正確地描述受控過程的變化特征。

(2)要滿足無后效性。即如果在某個階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃的模型。

(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進(jìn)行累計的量。此外，在與靜態(tài)規(guī)劃模型的對應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗，線性與非線性規(guī)劃中約束條件的個數(shù)，相當(dāng)于動態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)．而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。483.動態(tài)規(guī)劃方法的基本步驟

3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動態(tài)規(guī)劃模型時，常取前者的變量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)493.動態(tài)規(guī)劃方法的基本步驟

5．根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)：

(1)可分性，即對于所有k后部子過程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策uk

,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。

(2)要滿足遞推關(guān)系，即

(3)函數(shù)對其變元Rk+1來說要嚴(yán)格單調(diào)。50

6．寫出動態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式

其中表示第i階段的指標(biāo)，它顯然是滿足上述三個性質(zhì)的。所以上式可以寫成：3.動態(tài)規(guī)劃方法的基本步驟51

二：動態(tài)規(guī)劃問題求解的一般步驟

逆序求條件最優(yōu)目標(biāo)函數(shù)順序求最優(yōu)策略、最優(yōu)路線和最優(yōu)目標(biāo)函數(shù)值。具體過程描述如下:1.逆序地求出條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集

k=n時，動態(tài)規(guī)劃基本方程是

因為是η段決策過程，不存在η+1階段，是階段η的終止?fàn)顟B(tài)，也是整個n段決策過程的最終狀態(tài)。在階段n之后不再作出決策，因而也不會再發(fā)生階段效應(yīng)。因此

52這是一個已知的條件，稱為動態(tài)規(guī)劃基本方程的邊界條件，于是

k=η時的動態(tài)規(guī)劃基本方程成為

上式表明，階段n相應(yīng)于狀態(tài)的后部子過程的最優(yōu)決策，就是使階段n的階段效應(yīng)為最優(yōu)的決策，其條件最優(yōu)目標(biāo)函數(shù)值就是階段n處于時執(zhí)行該最優(yōu)決策的階段效應(yīng)，即需要注意的是，和中的是階段n的初始狀態(tài)，又是階段n-1的終止?fàn)顟B(tài)，因此它的取值要由階段n-1的狀態(tài)和決策確定，它們的值在計算和

時還是未知的。53因此，這里必須就階段n的所有可能狀態(tài)

，計算和，即求出第η階段的條件最優(yōu)目標(biāo)函數(shù)值集合和條件最優(yōu)決策集合

由于此時所有的已經(jīng)求出，故可以根據(jù)就階段n-1的每個可能狀態(tài)求關(guān)于

的條件最優(yōu)決策54可以象上面一樣就階段1的各個可能狀態(tài)

求出第一階段的條件最優(yōu)決策集合和條件最優(yōu)目標(biāo)函數(shù)值集合

及相應(yīng)的條件最優(yōu)目標(biāo)函數(shù)值552.順序地求最優(yōu)決策序列

這一階段的工作是順著決策進(jìn)行的次序進(jìn)行的，即從階段1開始，依次進(jìn)行。

當(dāng)階段1的初始狀態(tài)Xl是唯一確定時(稱為始端固定問題)，上面求得的階段1的條件最優(yōu)集合也有唯一確定的元素和。按定義是從階段1的狀態(tài)起執(zhí)行最優(yōu)策

略時的條件最優(yōu)目標(biāo)函數(shù)值，由于是唯一確定的，因而也就是

整個過程的最優(yōu)目標(biāo)函數(shù)值，即

相應(yīng)地，階段1的條件最優(yōu)決策

就是階段1的關(guān)于整個

過程的最優(yōu)決策，即

56當(dāng)階段1的初始狀態(tài)不是唯一的時候，

式中

是

的狀態(tài)可能集，是中使整個過程取得最優(yōu)

目標(biāo)函數(shù)值

的初始狀態(tài)，即整個多段決策過程的最優(yōu)初始狀

態(tài)(始端固定問題可以解釋為)。階段1的最優(yōu)決策是

根據(jù)階段1的最優(yōu)初始狀態(tài)

和最優(yōu)決策，按狀態(tài)轉(zhuǎn)

移方程可求得階段2的最優(yōu)初始狀態(tài)，進(jìn)而從階

段2的條件最優(yōu)集合中又可找到關(guān)于

的最優(yōu)決策

57余可類推，直至階段η。其時已知于是即可求出和如下

整個求解過程可如下描述，即所求多段決策過程的最優(yōu)目標(biāo)函數(shù)是

最優(yōu)策略或最優(yōu)決策序列是最優(yōu)路線或最優(yōu)狀態(tài)序列是58

二．動態(tài)規(guī)劃方法的應(yīng)用舉例為進(jìn)一步說明動態(tài)規(guī)劃模型建立的基本方法及其求解過程,下面通過實際例子用上述方法具體給出求解動態(tài)規(guī)劃方法的基本步驟：例5.3:有某種機(jī)床,可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn),在高負(fù)荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機(jī)床數(shù)量u1的關(guān)系為g=g(u1)=8u1,這時,年終機(jī)床完好臺數(shù)將為au1,(a為機(jī)床完好率，0<a<1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時,產(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.動態(tài)規(guī)劃方法的基本步驟59

假設(shè)某廠開始有x=1000臺完好的機(jī)床，現(xiàn)要制定一個五年生產(chǎn)計劃，問每年開始時如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高。

解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。

1．變量設(shè)置

(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=5。

(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺數(shù)，同時也是第k-1年度末時的完好機(jī)床數(shù)量。3.動態(tài)規(guī)劃方法的基本步驟60

(3)決策變量uk，表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)。于是sk-uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺數(shù)．這里sk與uk均取連續(xù)變量，當(dāng)它們有非整數(shù)數(shù)值時．可以這樣理解：如sk＝0.6，就表示一臺機(jī)器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機(jī)床在

k年度只有4/10的時間于高負(fù)荷下工作．

2．狀態(tài)轉(zhuǎn)移方程為

k=1，2，…,63.動態(tài)規(guī)劃方法的基本步驟61

3．允許決策集合,在第k段為

4．目標(biāo)函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量，則gk(sk,uk)=8uk+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é)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系：

k=1,2,3,4,53.動態(tài)規(guī)劃方法的基本步驟62

6.邊界條件為下面采用逆序遞推計算法,從第5年度開始遞推計算。

k=5時有顯然，當(dāng)u5*=s5時，f5(s5)有最大值，相應(yīng)的有f5(s5)=8s5

k=4時有

3.動態(tài)規(guī)劃方法的基本步驟

,=

=

因此，當(dāng)u4*=s4時，有最大值f4(s4)=13.6s463

k=3時有

可見，當(dāng)u3*=s3時，f3(s3)有最大值f3(s3)=17.55s3.

k=2時有

=+=此時，當(dāng)取u2*=0時有最大值，即f2(s2)=20.8s2，其中s2=0.7u1+0.9(s1-u1)3.動態(tài)規(guī)劃方法的基本步驟

=64

k=1時有

+

=

當(dāng)取u1*=0時,f1(s1)有最大值，即f1(s1)=23.7s1,因為s1=1000,故f1(s1)=23700個產(chǎn)品．按照上述計算順序?qū)ほ櫟玫较率鲇嬎憬Y(jié)果：3.動態(tài)規(guī)劃方法的基本步驟65

上面所討論的最優(yōu)決策過程是所謂始端狀態(tài)s1固定，終端狀態(tài)s6自由．如果終端也附加上一定的約束條件，那么計算結(jié)果將會與之有所差別．例如，若規(guī)定在第五個年度結(jié)束時，完好的機(jī)床數(shù)量為500臺(上面只有278臺)，問應(yīng)該如何安排五年的生產(chǎn)，使之在滿足這一終端要求的情況下產(chǎn)量最高？3.動態(tài)規(guī)劃方法的基本步驟66

解：由狀態(tài)轉(zhuǎn)移方程有得

顯而易見，由于固定了終端的狀態(tài)s6，第五年的決策變量U5的允許決策集合U5(s5)也有了約束，上式說明U5(s5)已退化為一個點，即第五年投入高負(fù)荷下生產(chǎn)的機(jī)床數(shù)只能由式U5=4.5s5-2500作出一種決策，故3.動態(tài)規(guī)劃方法的基本步驟＝50067

當(dāng)k=5時有

當(dāng)k=4時有

顯然，只有取u4*=0，f4(s4)有最大值，即f4(s4)=21.7s4-7500。同理類推3.動態(tài)規(guī)劃方法的基本步驟=

=

=

=68k=3時有

可知,當(dāng)u3*=0時,f3(s3)有最大值f4(s4)=24.5s3-7500.k=2時有此時,當(dāng)u2*=0時有最大值,即f2(s2)=27.1s2-75003.動態(tài)規(guī)劃方法的基本步驟

=

=

=

=

+

69

k=1時有

只有取u1*=0時,f1(s1)有最大值，即

f1(s1)=29.4s1-7500。由此可見，為了使下一個五年計劃開始的一年有完好的機(jī)床500臺，其最優(yōu)策略應(yīng)該為：在前4年中，都應(yīng)該把全部機(jī)床投人低負(fù)荷下生產(chǎn)，在第5年，只能把部分完好機(jī)投入高負(fù)荷下生產(chǎn)。根據(jù)最優(yōu)策賂，從始端向終端遞推計算出各年的狀態(tài)，即算出每年年初的完好機(jī)床臺數(shù)，因為s1＝1000臺，于是有3.動態(tài)規(guī)劃方法的基本步驟==70

因此，u5*=4.5s5-2500=425(臺)，這就是說第5年里還有204臺投入低負(fù)荷下生產(chǎn)，否則不能保證s6=0.7u5+0.9(u5-s5)=500(臺)。在上述最優(yōu)決策下，5年里所得最高產(chǎn)量為：

f1(s1)＝29.4s1-7500=29400-7500＝21900(個)?？梢?，附加了終端約束條件以后，其最高產(chǎn)量f1(s1)比終端自由時要低一些。3.動態(tài)規(guī)劃方法的基本步驟（臺）（臺）（臺）（臺）（臺）（臺）71

例5.4：一個線路網(wǎng)絡(luò)圖，從A到E要修建一條石油管道，必須在B、C、D處設(shè)立加壓站。各邊上的數(shù)為長度，現(xiàn)需要找一條路使總長度最短。B3B2B1C3C2C1D3D2D1EA4563434547426571097863.動態(tài)規(guī)劃方法的基本步驟72

解:可分成4個階段：

A到B、B到C、C到D、D到E；每個階段k

的起點稱為狀態(tài)Sk

；從k

階段的起點出發(fā)可以做一選擇，即決定到下一階段的哪個節(jié)點,稱為決策Xk

；可見,Sk+1是由Sk

和Xk

所決定的。3.動態(tài)規(guī)劃方法的基本步驟73

那么，從A出發(fā)經(jīng)過4個階段：A到B、B到C、C到D、D到E，逐次作出決策，構(gòu)成從A到E

的一條路線，記為u

。

即

u=S1X1

S2X2

S3X3S4X4S5

其中S1=A

，S5=E

記d

為兩個相鄰節(jié)點之間的長度，如d（A，B

3）=3。3.動態(tài)規(guī)劃方法的基本步驟74

①

記fk(Sk)為從Sk到E的最短長度,稱為從Sk到E的距離。

那么，f1(A)是從A到E的最短距離，即最優(yōu)策略的值。3.動態(tài)規(guī)劃方法的基本步驟75

②最短路問題的特點：如果從A到E的最優(yōu)策略經(jīng)過某節(jié)點，那么這個策略的從該節(jié)點到E的一段，必定是該節(jié)點到E的所有線路中Sk最短的一條，即這一段的長度為fk（Sk）。（1）逆序法：從E到A。（2）順序法：對節(jié)點Sk，從A到Sk

所有線路中，最短的一條的長度記為φk（Sk），例如φ1（A）=0，稱為問題的邊界條件。3.動態(tài)規(guī)劃方法的基本步驟76

動態(tài)規(guī)劃模型建立后，對基本方程分段求解，不像線性規(guī)劃或非線性規(guī)劃那樣有固定的解法，必須根據(jù)具體問題的特點，結(jié)合數(shù)學(xué)技巧靈活求解，如動態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用離散變量的分段窮舉法。當(dāng)動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取連續(xù)變量的求解方法。如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計算方法等。還有連續(xù)變量的離散化解法和高維問題的降維法及疏密格子點法等等。3.動態(tài)規(guī)劃方法的基本步驟77

學(xué)習(xí)方法建議：第一步先看問題，充分理解問題的條件、情況及求解目標(biāo)。第二步結(jié)合前面講到的理論和解題過程，考慮如何著手進(jìn)行求解該問題的工作。分析針對該動態(tài)規(guī)劃問題的“四大要素、一個方程”——這一步在開始時會感到困難，但是一定要下決心去思考，在思考過程中深入理解前文講到的概念和理論。4.動態(tài)規(guī)劃方法應(yīng)用舉例78

第三步動手把求解思路整理出來，或者說，把該問題作為習(xí)題獨立的來做。第四步把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述。第五步對照自己的求解，分析成敗。4.動態(tài)規(guī)劃方法應(yīng)用舉例79

1.動態(tài)規(guī)劃的四大要素

①狀態(tài)變量及其可能集合xk

Xk②決策變量及其允許集合uk

Uk

③狀態(tài)轉(zhuǎn)移方程

xk+1=Tk

(xk,uk

)④階段效應(yīng)rk

(xk,uk

)

4.動態(tài)規(guī)劃方法應(yīng)用舉例80

2.動態(tài)規(guī)劃基本方程

fn+1(xn+1)=0(邊界條件)

fk(xk)=opt

u{rk

(xk,uk

)+fk+1(xk+1)}

k=n,…,14.動態(tài)規(guī)劃方法應(yīng)用舉例81求最短路徑

82

求最短路徑1：定步數(shù)問題例4.183

將問題分成四個階段，第k階段到達(dá)的具體地點用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達(dá)位置B3，等等。這里狀態(tài)變量取字符值而不是數(shù)值。

將決策定義為到達(dá)下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時決策允許集合包含三個決策，它們是D2(x2)=D2(B3)={B3

C1,B3

C2,B3

C3}求最短路徑

84

最優(yōu)指標(biāo)函數(shù)fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。

第四階段的遞推方程為 : 求最短路徑

85

其中*表示最優(yōu)值，在上表中，由于決策允許集合D4(x4)中的決策是唯一的，因此這個值就是最優(yōu)值。

由此得到f4(x4)的表達(dá)式。由于這是一個離散的函數(shù)，取值用列表表示：求最短路徑

86第三階段的遞推方程為：

求最短路徑

87由此得到f3(x3)的表達(dá)式：

求最短路徑

88求最短路徑

89由此得到f2(x2)的表達(dá)式：求最短路徑

90第一階段的遞推方程為：求最短路徑

91由此得到f1(x1)的表達(dá)式求最短路徑

922.不定步數(shù)問題

不定步數(shù)問題是指從起點到終點的路線所經(jīng)過的步數(shù)不完全相同的工程路線問題?，F(xiàn)舉例說明動態(tài)規(guī)劃解決此類問題的方法。

例4-2今有一最短路問題如圖4-8所示，其中符號含義與例

4-1中的相同，求由s到t的最短距離和最短路線。

93解從圖中可知，從s到t的路線中有步數(shù)為三步的，如從s到a，c到t，也有5步的，如s到b，a，c，d再到t。因此，該問題屬于不定步數(shù)問題。對于這種問題，由于無法劃分階段，因而不能嚴(yán)格按例4-1中的求解方法來加以求解，然而，若用r(i，j)表示從

節(jié)點i到節(jié)點j的距離，用f(i)表示i節(jié)點到t節(jié)點的最短距離，則根據(jù)動態(tài)規(guī)劃原理，應(yīng)該有:

其中j的取值范圍是所有從i可以一步到達(dá)的節(jié)點。94在一定的條件下，依據(jù)此遞推關(guān)系就可以逐一求解f()在各點上的值(由t往前倒退)。

同時，這一關(guān)系給出了函數(shù)f()的一個函數(shù)方程，其求解也可以通過迭代的方法來實現(xiàn)。

迭代可以針對f()來進(jìn)行，稱為函數(shù)迭代法，也可以針對策略{u(i)}(i=s，a，b，c，d)來進(jìn)行，稱為策略迭代法，現(xiàn)分別討論如下。95(1)用函數(shù)迭代法求解

函數(shù)迭代法步驟:①先選定一初始函數(shù)

②然后用遞推關(guān)系求如下:這里可以看出，為從i點出發(fā)走k步到t的最短距離。96可以證明，若對于某個k，有，對所有節(jié)點i成立，則即為條件最優(yōu)目標(biāo)函數(shù)。

則為s到t的最短距離。

按函數(shù)迭代法把本例數(shù)據(jù)代入得

97上述計算可以繼續(xù)下去，其結(jié)果整理如表4-498

isabCdt

240

84240

1284240

1284240

表4-4函數(shù)迭代法計算結(jié)果表可見各點到t的最短距離如表中,從計算過程可以逆序找出最短路線，例如，s到t的最短路線是先經(jīng)過b，見計算的過程而b到t的最短路線長為4，是經(jīng)過C到t的。見計算的過程，即s→b→c→t。99(2)用策略迭代法求解

策略迭代法步驟:（1）給每個點i選擇一個下一步到達(dá)的點，

i=s，α，b，

c，d取k=O100代入本例數(shù)據(jù)計算如下：101102103104105策略迭代法的中間結(jié)果匯總?cè)绫?-5所示:

表4-5策略選代法結(jié)果表

a18b12b

a

d9C8Cbd8C4CCt2t2tdt4t4tt0

0

106資源分配問題107

例5.6:有資金4萬元，投資A、B、C三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目A、B、C的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：求對三個項目的最優(yōu)投資分配，使總投資效益最大。

資源分配問題108階段k：每投資一個項目作為一個階段；狀態(tài)變量xk：投資第k個項目前的資金數(shù)；決策變量uk：第k個項目的投資；決策允許集合：0≤uk≤xk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-uk階段指標(biāo)：vk(xk

,uk)見表中所示；遞推方程：fk(xk)=max{vk(xk

,uk)+fk+1(xk+1)}終端條件：f4(x4)=0資源分配問題109k=4，f4(x4)=0

k=3，0≤u3≤x3，x4=x3-u3

資源分配問題110k=2，0≤u2≤x2，x3=x2-u2資源分配問題111k=1，0≤u1≤x1，x2=x1-u1資源分配問題112背包問題113背包問題114則Max

z= c1x1+c2x2+…+cnxn

s.t.w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn為正整數(shù)

階段k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量xk：第k次裝載時背包還可以裝載的重量；決策變量dk：第k次裝載第k種物品的件數(shù)；背包問題1154.決策允許集合： Dk(xk)={dk|0

dk

xk/wk，dk為整數(shù)}；5.狀態(tài)轉(zhuǎn)移方程：xk+1=xk-wkdk6.階段指標(biāo)：vk=ckdk7.遞推方程

fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.終端條件：fn+1(xn+1)=0背包問題116

例5.7:對于一個具體問題c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5

用動態(tài)規(guī)劃求解f4(x4)=0

對于k=3背包問題117118119120121

機(jī)器負(fù)荷分配問題122123

構(gòu)造動態(tài)規(guī)劃模型如下：

階段k：運(yùn)行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次類推；k=6表示第五年末（即第六年初）。

狀態(tài)變量xk：第k年初完好的機(jī)器數(shù)（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好機(jī)器數(shù)。

決策變量dk：第k年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)；

狀態(tài)轉(zhuǎn)移方程：xk+1=0.7dk+0.9(xk-dk)

決策允許集合：Dk(xk)={dk|0

dk

xk}

階段指標(biāo)：vk(xk

,dk)=8dk+5(xk-dk)

終端條件：f6(x6)=0

機(jī)器負(fù)荷分配問題124遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}

dk

Dk(xk)

=max{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}

0

dk

xk

機(jī)器負(fù)荷分配問題125f5(x5)=max{8d5+5(x5-d5)+f6(x6)}

0

d5

x5

=max{3d5+5x5}=8x5, d5*=x5

0

d5

x5

f4(x4)=max{8d4+5(x4-d4)+f5(x5)}

0

d4

x4

=max{8d4+5(x4-d4)+8x5}

0

d4

x4

=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}

0

d4

x4

=max{1.4d4+12.3x4}=13.7x4, d4*=x4

0

d4

x4

機(jī)器負(fù)荷分配問題126f3(x3)=max{8d3+5(x3-d3)+f4(x4)}

0

d3

x3

=max{8d3+5(x3-d3)+13.7x4}

0

d3

x3

=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}

0

d3

x3

=max{0.28d3+17.24x3}=17.52x3, d3*=x3

0

d3

x3

機(jī)器負(fù)荷分配問題127f2(x2)=max{8d2+5(x2-d2)+f3(x3)}

0

d2

x2

=max{8d2+5(x2-d2)+17.52x3}

0

d2

x2

=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}

0

d2

x2

=max{-0.504d2+20.77x2}=20.77x2,d2*=0

0

d2

x2

機(jī)器負(fù)荷分配問題128f1(x1)=max{8d1+5(x1-d1)+f2(x2)}

0

d1

x1

=max{8d1+5(x1-d1)+20.77x2}

0

d1

x1

=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}

0

d1

x1

=max{-0.05d1+23.69x1}=23.69x1,d1*=0

0

d1

x1

機(jī)器負(fù)荷分配問題129由此可以得到：f1(x1)=23.69x1, d1*=0f2(x2)=20.77x2, d2*=0f3(x3)=17.52x3, d3*=x3f4(x4)=13.60x4, d4*=x4f5(x5)=8x5

d5*=x5用x1=1000代入，得到五年最大產(chǎn)量為f1(x1)=f1(1000)=23690

機(jī)器負(fù)荷分配問題130每年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)以每年初完好的機(jī)器數(shù)為：x1=1000d1*=0,x2=0.7d1+0.9(x1-d1)=900d2*=0,x3=0.7d2+0.9(x2-d2)=810d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278

機(jī)器負(fù)荷分配問題131

在這個例子中，狀態(tài)變量的終端值x6是未加約束的，如果要求在第五年末（即第六年初）完好的機(jī)器數(shù)不少于500臺，這時決策變量d5的決策允許集合將成為：

D5(x5)={d5|0.7d5+0.9(x5-d5)

500,d5

0}

即0.9x5-0.2d5

500

d5

0或0

d5

4.5x5-2500

容易想象，這時的最大產(chǎn)量將比x6是自由的情況下小。這個例子可以推廣到一般情況。設(shè)高負(fù)荷生產(chǎn)時機(jī)器的完好率為k1，單臺產(chǎn)量為p1；低負(fù)荷完好率為k2，單臺產(chǎn)量為p2。若有t滿足:

機(jī)器負(fù)荷分配問題132則從1—t-1年，年初將全部完好機(jī)器投入低負(fù)荷運(yùn)行，從t—n年，年初將全部完好機(jī)器投入高負(fù)荷運(yùn)行，這樣的決策，將使總產(chǎn)量達(dá)到最大。

機(jī)器負(fù)荷分配問題133生產(chǎn)庫存問題134

例5.9：一個工廠生產(chǎn)某種產(chǎn)品,1-

7月份生產(chǎn)成本和產(chǎn)品需求量的變化情

況如下表：

生產(chǎn)庫存問題135階段k：月份，k=1,2,…,7,8；狀態(tài)變量xk：第k個月初（發(fā)貨以前）的庫存量；決策變量dk：第k個月的生產(chǎn)量；狀態(tài)轉(zhuǎn)移方程：xk+1=xk-rk+dk；決策允許集合：Dk(xk)={dk

|dk

0,rk+1

xk+1

H} ={dk

|dk

0,rk+1

xk-rk+dk

H}；階