《運籌學(xué)》 課件 第6章-動態(tài)規(guī)劃

7/16/2024第6章動態(tài)規(guī)劃1CONTENTS目錄6.1多階段決策問題6.2動態(tài)規(guī)劃的基本慨念和基本方程6.3最優(yōu)性原理和最優(yōu)性定理6.4動態(tài)規(guī)劃問題的求解6.5動態(tài)規(guī)劃的應(yīng)用舉例7/16/202421951年美國數(shù)學(xué)家（R.Bellman）提出同時提出解決的方法“最優(yōu)化原理”應(yīng)用范圍十分廣泛。在企業(yè)管理方面：最優(yōu)路徑問題，資源分配問題，生產(chǎn)調(diào)度問題，庫存問題，裝載問題，排序問題，設(shè)備更新問題優(yōu)點：通常比線性規(guī)劃和非線性規(guī)劃更有效。特別是離散性問題。缺點：沒有標準的數(shù)學(xué)表達式，沒有統(tǒng)一的處理方法。若變數(shù)的維數(shù)太大，則無法求解；最致命缺點是最優(yōu)化原理沒有經(jīng)過理論證明，其適用范圍還不清楚。

前言7/16/20246.1多階段決策問題

動態(tài)規(guī)劃是把多階段決策問題作為研究對象。

所謂多階段決策問題，是指這樣一類活動過程，即根據(jù)問題本身的特點，可以將其求解的全過程劃分為若干個相互聯(lián)系的階段(即將問題劃分為許多個相互聯(lián)系的子問題)，在它的每一階段都需要作出決策；并且在一個階段的決策確定以后再轉(zhuǎn)移到下一個階段。當各個階段的決策確定后，它們就構(gòu)成一個決策序列，常稱之為策略。由于每個階段可選決策的不唯一性，這些相互聯(lián)系的決策組成的策略也就不止一個，那么這些可供選擇的策略構(gòu)成一個集合，我們稱之為允許策略集合（簡稱策略集合）。

多階段決策問題概念7/16/2024靜態(tài)決策一次性決策動態(tài)決策多階段決策決策x1x2Zu輸入決策輸出決策效應(yīng)第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多階段決策問題模型7/16/2024

往往前一個階段的決策要影響到后一個階段的決策，從而影響整個過程。人們把這樣的決策過程稱做多階段決策過程(Multi-Stagedecisionprocess)。第一月x1x2r1u1第二月x3r2u2第三月x4r3u3

各個階段所確定的決策就構(gòu)成了一個決策序列，稱為一個策略。一般來說，由于每一階段可供選擇的決策往往不止一個，因此，對于整個過程，就會有許多可供選擇的策略。7/16/2024多階段決策問題模型例：從A運送物資到D。AB1DC2C1B244532652階段1階段3階段2劃分階段單階段決策策略量化指標最優(yōu)策略7/16/2024多階段決策問題模型

多階段決策過程最優(yōu)化的目標是要達到整個活動過程的總體效果最優(yōu)。

不應(yīng)僅考慮本階段最優(yōu)，還應(yīng)考慮對最終目標的影響，從而作出對全局來講是最優(yōu)的決策。動態(tài)規(guī)劃就是符合這種要求的一種決策方法。7/16/2024多階段決策問題模型1)工廠生產(chǎn)過程：由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經(jīng)濟效益，就要在全年的生產(chǎn)過程中，逐月或者逐季度地根據(jù)庫存和需求情況決定生產(chǎn)計劃安排。

第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多階段決策問題舉例7/16/2024

2)設(shè)備更新問題：一般企業(yè)用于生產(chǎn)活動的設(shè)備，剛買來時故障少，經(jīng)濟效益高，即使進行轉(zhuǎn)讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙啵S修費用增加，可正常使用的工時減少，加工質(zhì)量下降，經(jīng)濟效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費．因此就需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟效益最好。

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

以上所舉問題的發(fā)展過程都與時間因素有關(guān)，因此在這類多階段決策問題中，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關(guān)，這就使它具有了“動態(tài)”的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。

實際中尚有許多不包含時間因素的一類“靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當作多階段決策問題，應(yīng)用動態(tài)規(guī)劃方法加以解決。7/16/2024多階段決策問題舉例

4）資源分配問題：便屬于這類靜態(tài)問題。如：某工業(yè)部門或公司，擬對其所屬企業(yè)進行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素無關(guān)，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題?？傎Y源部門1x1x2r1u1部門2x3r2u2部門3x4r3u3部門1的分配量多階段決策問題舉例7/16/2024

5）運輸網(wǎng)絡(luò)問題：如圖所示的運輸網(wǎng)絡(luò)，點間連線上的數(shù)字表示兩地距離(也可是運費、時間等)，要求從v1至v10的最短路線。這種運輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。多階段決策問題舉例7/16/2024

通常多階段決策過程的發(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ī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。

第一月x1x2r1u1第二月x3r2u2第三月x4r3u3動態(tài)規(guī)劃求解特點7/16/2024Xk+1=Tk(xk,uk)T1x1x2r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1……rn(xn,un)un(xn)

所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。動態(tài)規(guī)劃求解特點7/16/2024多階段決策過程特點:要點：階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)移方程，k-后部子過程狀態(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+1動態(tài)規(guī)劃求解特點7/16/2024多段決策過程中從第k階段到最終階段的過程稱為k-后部子過程，簡稱k-子過程。Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1…rn(xn,un)un(xn)動態(tài)規(guī)劃求解特點7/16/2024例1：為了說明動態(tài)規(guī)劃的基本思想方法和特點，下面以圖1所示為例討論的求最短路問題的方法。動態(tài)規(guī)劃方法導(dǎo)引案例7/16/2024第一種方法稱做全枚舉法或窮舉法。

它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進行比較，求出最優(yōu)方案。最優(yōu)路線是v1→v3→

v7→

v9→v10,最短距離是18．

顯然，當組成交通網(wǎng)絡(luò)的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復(fù)計算．

第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是v1→v3→v5→

v8→

v10

，全程長度是20；顯然，這種方法的結(jié)果常是錯誤的．動態(tài)規(guī)劃方法導(dǎo)引案例7/16/2024

第三種方法是動態(tài)規(guī)劃方法。

基本思想:

首先將問題劃分為4個階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進行考慮，

在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。

動態(tài)規(guī)劃方法導(dǎo)引案例7/16/2024

整個求解過程分為兩個階段：

先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。動態(tài)規(guī)劃方法導(dǎo)引案例7/16/20246.2動態(tài)規(guī)劃的基本概念和基本方程6.2.1動態(tài)規(guī)劃的基本概念階段

狀態(tài)

決策

策略

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

指標函數(shù)

最優(yōu)解

邊界條件動態(tài)規(guī)劃模型7/16/2024為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目。從第

k個階段到最后一個階段的過程被稱為

k后部子過程。階段和階段變量7/16/2024v1v6v5v4v3v2v7v8444656332415k=1k=2k=3k=4階段和階段變量7/16/2024用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量,記作sk

。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集.可能狀態(tài)集實際上是關(guān)于狀態(tài)的約束條件。通常可能狀態(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定狀態(tài)，狀態(tài)變量和可能狀態(tài)集合7/16/2024

在上述最短路問題中第一階段狀態(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}

；狀態(tài)，狀態(tài)變量和可能狀態(tài)集合7/16/2024

所謂決策，就是確定系統(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)允許決策集合實際是決策的約束條件。決策，決策變量和允許決策集合7/16/2024v1v6v5v4v3v2v7v8444656332415u1(v1)=v2U1(v1)={v2,v3}u2(v3)=v4U2(v3)={v4,v5}決策，決策變量和允許決策集合7/16/2024

策略(Policy)也叫決策序列．策略有全過程策略和k部子策略之分.

全過程策略是指具有n個階段的全部過程，由依次進行的n個階段決策構(gòu)成的決策序列，簡稱策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}

，顯然當k=1時的k部子策略就是全過程策略。在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n,從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。

策略和允許策略集合7/16/2024

系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止狀態(tài)sk+1

，或者說，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1

，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。第一月x1x2r1u1第二月x3r2u2第三月x4r3u3狀態(tài)轉(zhuǎn)移方程7/16/20242024/7/16對于具有無后效性的多階段決策過程,系統(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é)公式描述即有這一關(guān)系式指明了由第階段到第階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程或狀態(tài)轉(zhuǎn)移函數(shù)如果狀態(tài)轉(zhuǎn)移方程是確定性的，則該過程稱為確定性多階段決策過程。如果這種轉(zhuǎn)移關(guān)系是以某種概率實現(xiàn)的，則稱這種過程為隨機性多階段決策過程。狀態(tài)轉(zhuǎn)移方程7/16/2024

用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。指標函數(shù)有階段指標函數(shù)和過程指標函數(shù)之分(1)階段指標函數(shù)（也稱階段效應(yīng)）。

用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數(shù)，簡記為gk

。例如g2(v2,v5)=3,即v2到v5的距離為3。指標函數(shù)和最優(yōu)值函數(shù)7/16/2024

(2)過程指標函數(shù)（也稱目標函數(shù)）。

用Rk(sk,uk)表示第k子過程的指標函數(shù)。如例1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，嚴格說來，應(yīng)表示為:

實際應(yīng)用中指標函數(shù)往往表示為Rk(sk,uk)或Rk(sk)。它與第k子過程上各段指標函數(shù)有關(guān)，過程指標函數(shù)Rk(sk)通常是描述k后部子過程效果優(yōu)劣的數(shù)量指標，它是由各階段的階段指標函數(shù)gk(sk,uk)累積形成的指標函數(shù)和最優(yōu)值函數(shù)7/16/2024

適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)（即目標函數(shù)），必須具有關(guān)于階段指標的可分離形式．對于k部子過程的指標函數(shù)可以表示為：式中，

表示某種運算，可以是加、減、乘、除、開方等。

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

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

總之，具體問題的目標函數(shù)表達形式需要視具體問題而定。指標函數(shù)和最優(yōu)值函數(shù)7/16/2024

用fk(sk)表示第k子過程指標函數(shù)在狀態(tài)sk下的最優(yōu)值,即

稱fk(sk)為第k子過程上的最優(yōu)值函數(shù)；與它相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)

；而構(gòu)成該子策賂的各段決策稱為該過程上的最優(yōu)決策記為

指標函數(shù)和最優(yōu)值函數(shù)7/16/2024簡記為

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

就是例1的最優(yōu)策略。

我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。指標函數(shù)和最優(yōu)值函數(shù)7/16/2024多階段決策問題的數(shù)學(xué)模型

綜上所述，適于應(yīng)用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:式中“OPT”表示最優(yōu)化，視具體問題取max或min。

上述數(shù)學(xué)模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列

7/16/20246.2.2動態(tài)規(guī)劃的基本方程標號法動態(tài)規(guī)劃的建模實例動態(tài)規(guī)劃問題的建模函數(shù)基本方程動態(tài)規(guī)劃的基本方程7/16/2024

標號法適用于例1這類最優(yōu)路線問題的特殊解法——標號法。

標號法是借助網(wǎng)絡(luò)圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。標號法7/16/2024下面給出標號法的一般步驟：

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

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

用標號法來求解下例

例：網(wǎng)絡(luò)圖表示某城市的局部道路分布圖。一貨運汽車從S出發(fā)，最終到達目的地E。其中Ai(i＝1，2，3),Bj(j＝1，2)和Ck(k＝1，2)是可供汽車選擇的途經(jīng)站點，各點連線上的數(shù)字表示兩個站點問的距離。問此汽車應(yīng)走哪條路線，使所經(jīng)過的路程距離最短?

圖2某城市的局部道路分布圖標號法-案例7/16/2024

第一步：先考慮第四階段，即k=4，

該階段共有兩個狀態(tài)：C1、C2，設(shè)f4(C1)和f4(C2)分別表示C1、C2到E的最短距離，顯然有

f4(C1)=5和f4(C2)=8，邊界條件f5(E)=0。

58標號法-案例7/16/2024

第二步：即k=3,該階段共有兩個狀態(tài):B1,

B2

從B1出發(fā)有兩種決策:B1→C1，B1→C2

。

d3(B1,C1)表示B1到C1的距離,B1→C1的階段指標函數(shù)為d3(B1,C1)＝6，B1→C2的階段指標函數(shù)為d3(B1,C2)＝5。

f3(B1)＝min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝min(6＋5，5＋8)＝11。那么，從B1出發(fā)到E的最短路線是B1→C1→E，對應(yīng)的決策u3(B1)=C1

。5811標號法-案例7/16/2024

(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。

581114標號法-案例7/16/2024第三步：即k＝2,該階段共有三個狀態(tài):Al,A2,A3

（1）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→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。(3)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

，u2(A3)＝B1

A3→B2→C1→E對應(yīng)的u2(A3)＝B2

標號法-案例7/16/2024581114標號法-案例7/16/2024第四步：即k＝1，該階段只有一個狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么,

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，

那么,從S到E共有三條最短路線：

此時,u1(S)＝A1

u1(S)＝A3

，最短距離為21。58111417191821標號法-案例7/16/202458111417191821

每個狀態(tài)上方的方格內(nèi)的數(shù)字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構(gòu)成每一狀態(tài)到E的最短路線。

因此，標號法不但給出起點到終點的最短路線和最短距離，同時也給出每一狀態(tài)到終點的最短路線及其最短距離。

S---A1---B1---C1---E標號法-案例7/16/2024

在上例中，用標號法求解最短路線的計算公式可以概括寫成：

其中，

在這里表示從狀態(tài)sk到由

決策uk(sk)所決定的狀態(tài)sk+1之間的距離,邊界條件表示全過程到第四階段終點結(jié)束。邊界條件第k子過程的最優(yōu)指標第k+1子過程的最優(yōu)指標K階段指標逆序遞推法；這里可以指出，該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動態(tài)規(guī)劃的函數(shù)基本方程。函數(shù)基本方程7/16/20242024/7/165258函數(shù)基本方程7/16/2024

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

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

函數(shù)基本方程7/16/2024(2)當過程指標函數(shù)為下列“積”的形式時,

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

可以看出，和、積函數(shù)的基本方程中邊界條件(即的取值)是不同的。函數(shù)基本方程7/16/2024

標號法僅適用于求解象最短路線問題那樣可以用網(wǎng)絡(luò)圖表示的多階段決策問題。但不少多階段決策問題不能用網(wǎng)絡(luò)圖表示。此時,應(yīng)該用函數(shù)基本方程來遞推求解.

首先，要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.

構(gòu)造成動態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個動態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個正確的動態(tài)規(guī)劃模型,應(yīng)該滿足哪些條件呢?動態(tài)規(guī)劃問題的建模7/16/2024

1．應(yī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)變量必須具備以下三個特征：動態(tài)規(guī)劃問題的建模7/16/2024

(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)變量大都選取那種可以進行累計的量。此外，在與靜態(tài)規(guī)劃模型的對應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗，線性與非線性規(guī)劃中約束條件的個數(shù)，相當于動態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)．而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。動態(tài)規(guī)劃問題的建模7/16/20243．正確地定義決策變量及各階段的允許決策集合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)動態(tài)規(guī)劃問題的建模7/16/20245．根據(jù)題意,正確地構(gòu)造出目標與變量的函數(shù)關(guān)系——目標函數(shù)，目標函數(shù)應(yīng)滿足下列性質(zhì)：(1)可分性，即對于所有k后部子過程，其目標函數(shù)僅取決于狀態(tài)sk及其以后的決策uk,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。(2)要滿足遞推關(guān)系，即(3)函數(shù)對其變元Rk+1來說要嚴格單調(diào)。動態(tài)規(guī)劃問題的建模7/16/20246．寫出動態(tài)規(guī)劃函數(shù)基本方程例如常見的指標函數(shù)是取各段指標和的形式

其中表示第i階段的指標，它顯然是滿足上述三個性質(zhì)的。所以上式可以寫成：動態(tài)規(guī)劃問題的建模7/16/2024

例3有某種機床,可以在高低兩種不同的負荷下進行生產(chǎn),

在高負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機床數(shù)量u1的關(guān)系為g=g(u1)=8u1,

這時,年終機床完好臺數(shù)將為au1,(a為機床完好率，0<a<1,設(shè)a=0.7).

在低負荷下生產(chǎn)時,產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應(yīng)的機床完好率為b(0<b<1,設(shè)b=0,9),一般情況下a<b。動態(tài)規(guī)劃問題的建模-實例7/16/2024

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

第一年完好機器高負荷低負荷產(chǎn)量產(chǎn)量第二年剩余完好機器動態(tài)規(guī)劃問題的建模-實例7/16/2024解：首先構(gòu)造這個問題的動態(tài)規(guī)劃模型。

1．變量設(shè)置

(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=5。(2)狀態(tài)變量sk表示第k年度初擁有的完好機床臺數(shù)，同時也是第k-1年度末時的完好機床數(shù)量。

(3)決策變量uk，表示第k年度中分配于高負荷下生產(chǎn)的機床臺數(shù)。

sk-uk便為該年度中分配于低負荷下生產(chǎn)的機床臺數(shù)．動態(tài)規(guī)劃問題的建模-實例7/16/2024這里sk與uk均取連續(xù)變量，當它們有非整數(shù)數(shù)值時．可以這樣理解：如sk＝0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機床在k年度只有4/10的時間于高負荷下工作．2．狀態(tài)轉(zhuǎn)移方程為

k=1，2，…,63．允許決策集合,在第k段為動態(tài)規(guī)劃問題的建模-實例7/16/20244目標函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量，則gk(sk,uk)=8uk+5(sk-uk),因此目標函數(shù)為

k＝1,2,．．．,5

5．條件最優(yōu)目標函數(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,565動態(tài)規(guī)劃問題的建模-實例7/16/2024,=

=

因此，當u4*=s4時，有最大值f4(s4)=13.6s46.邊界條件為

下面采用逆序遞推計算法,從第5年度開始遞推計算。k=5時有顯然，當u5*=s5時，f5(s5)有最大值，相應(yīng)的有f5(s5)=8s5k=4時有動態(tài)規(guī)劃問題的建模-實例7/16/20246.3最優(yōu)化原理和最優(yōu)性定理最優(yōu)化原理：作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個最優(yōu)子策略。即若某一全過程最優(yōu)策略為：

則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為6.3最優(yōu)化原理和最優(yōu)性定理687/16/20246.4動態(tài)規(guī)劃問題的求解6.4動態(tài)規(guī)劃問題的求解動態(tài)規(guī)劃問題的狀態(tài)變量可以是離散變量或者是連續(xù)變量，可分為離散型動態(tài)規(guī)劃和連續(xù)型動態(tài)規(guī)劃。通常對于連續(xù)型動態(tài)規(guī)劃，由于變量的取值不可一一列舉，通常用解析法進行求解，而對于離散型動態(tài)規(guī)劃，尤其是當指標函數(shù)沒有明確的解析表達式（例如用數(shù)值表給出）時通常用數(shù)值法求解。下面通過舉例進行分析：7/16/2024資源分配：設(shè)有某種資源，總量為M，可以投入n種生產(chǎn)活動。已知用于活動k的資源為uk時的收益是gk(uk)，問應(yīng)如何分配資源，使n種生產(chǎn)活動的總收益最大。這種問題就是資源的多元分配問題。6.4.1離散確定性動態(tài)規(guī)劃7/16/2024如果將n種活動作為一個互相銜接的整體，對一種活動的資源分配作為一個階段，每個階段確定對一種活動的資源投放量。則該問題成為一個多階段決策問題。在資源分配問題中，決策變量選為對活動k的資源投放量，因此狀態(tài)變量可以選擇為階段k初所擁有的資源量，即將要在第k種到第n種活動間分配的資源量。狀態(tài)變量xk的選取原則是要能夠據(jù)此確定決策uk，以及滿足狀態(tài)轉(zhuǎn)移方程所要求的無后效性。資源分配7/16/2024關(guān)于狀態(tài)變量xk的約束條件是0≤xk≤M關(guān)于決策變量uk的約束條件是0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為xk+1=xk-uk顯然它滿足無后效性要求。階段效應(yīng)為對活動k投放資源uk時的收益，

rk(xk,uk)=gk(uk)目標函數(shù)是為n種活動投放資源后的總收益動態(tài)規(guī)劃基本方程資源分配7/16/2024案例：

某公司擬將50萬元資金投放下屬A、B、C三個部門，各部門在獲得資金后的收益如表所示，用動態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數(shù)以10萬元為單位）。投放資金（萬元）01020304050收益（萬元）A01520252830B0010254570C01020304050資源分配7/16/2024xk表示給部門k分配資金時擁有的資金數(shù)。uk表示給部門k分配的資金數(shù)（以10萬元為單位）。狀態(tài)轉(zhuǎn)移方程是xk+1=xk-uk。gk(uk)

階段效應(yīng)如表所示。fk(xk)目標函數(shù)是階段效應(yīng)求和。首先逆序遞推資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050從表可知g3()是單調(diào)遞增的函數(shù)，因此，當u3=x3時達到最大。即：逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。資源分配7/16/2024逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。k=2時，0≤x2≤50≤u2≤x2

資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。當k=1時，有x1=5，0≤u1≤x1=5資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024順序求最優(yōu)目標函數(shù)值和最優(yōu)策略、最優(yōu)路線資源分配7/16/2024一維背包背包問題的特征類似于往旅行背包里面裝用品的問題，要求在旅行袋容積和／或載重量的限制下，所裝物品的總價值最大。這一類問題在海運、航運以及航天等領(lǐng)域都有應(yīng)用。

例:對于一個具體問題 W=5用動態(tài)規(guī)劃求解k=3

貨物123單位重量231單位價值658030解:該問題中有三種物品需要裝載，因此可以作為三段決策問題，每階段為一個物品決定裝船的數(shù)量.k階段系統(tǒng)的狀態(tài)為在給第k物品決定裝載數(shù)量時，船上還剩余的載重能力xk7/16/2024

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024k=20≤x2≤5

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024對于k=1,x1=5

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024二維背包若只考慮重量或體積限制，則稱為一維背包問題，若同時考慮重量和體積限制,則稱為二維背包問題.考慮有N種物品需要裝船。第i種物品單位的重量為ωi，單件體積為υi，而價值為pi。最大的裝載重量為W，最大體積為V。現(xiàn)在要確定在不超過船的最大載重量和最大體積（不考慮貨物形狀）的條件下，使所載物品價值最大的裝載方案。7/16/2024例已知貨物的單位重量ωi，單位體積υi及價值pi如表所示，船的最大載重能力為W＝5，最大裝載體積為V＝8，求最優(yōu)裝載方案。iωiυipiA1230B3480C2365二維背包7/16/2024例W＝5，V＝8k階段系統(tǒng)的狀態(tài)為在給第k物品決定裝載數(shù)量時，船上還剩余的載重能力xk和剩余體積yk.因此狀態(tài)變量是二維的，記為（xk,yk）。有0≤xk≤5，0≤yk≤8決策變量uk表示裝載第k種物品的數(shù)量。二維背包7/16/2024例W＝5，V＝8解狀態(tài)轉(zhuǎn)移方程為：xk+1=xk-uk·ωkyk+1=yk-uk·υk各階段的狀態(tài)可能集與決策允許集為：

iωiυiA12B34C23二維背包7/16/2024iωiυiA12B34C23階段效應(yīng)為rk(xk,yk,uk)=pk·uk二維背包7/16/2024iωiυipiA1230B3480C2365二維背包7/16/2024解當k＝3時，由f4(x4,y4)=0(x3,y3)0/(x3,y3)1/(x3-2,y3-3)2/(x3-4,y3-6)f3()U’3(5,8)0＋065＋02×65＋01302(4,6)0＋065＋02×65＋01302(3,4)0＋065＋0×651(2,2)0＋0××00(1,0)0＋0××00(2,4)0＋065＋0×651(1,2)0＋0××00(0,0)0＋0××00iωiυipiA1230B3480C2365u3二維背包7/16/2024當k＝2時iωiυipiA1230B3480C2365二維背包7/16/2024解當k＝2時，由f3(x3,y3)已知(x2,y2)0/(x2,y2)1/(x2-3,y2-4)f2()U’2（5，8）0＋13080＋651451（4，6）0＋13080＋01300（3，4）0＋6580＋0801（2，2）0＋0×00（1，0）0＋0×00u2iωiυipiA1230B3480C2365二維背包7/16/2024(x2,y2)0/(x2,y2)1/(x2-2,y2-4)f2()U’2（5，8）0＋13080＋651451（4，6）0＋13080＋01300（3，4）0＋6580＋0801（2，2）0＋0×00（1，0）0＋0×000/(5,8)1/(4,6)2/(3,4)3/(2,2)4/(1,0)f1()u1(5,8)0＋14530＋13060＋8090＋0120＋01601解當k＝1時，W=5,V=8二維背包7/16/2024(x3,y3)0/(x3,y3)1/(x3-2,y3-3)2/(x3-4,y3-6)f3()U’3(5,8)0＋065＋02×65＋01302(4,6)0＋065＋02×65＋01302(3,4)0＋065＋0×651(2,2)0＋0××00(1,0)0＋0××00(2,4)0＋065＋0×651(1,2)0＋0××00(0,0)0＋0××00二維背包7/16/2024二維背包7/16/20246.4.2連續(xù)確定性動態(tài)規(guī)劃用動態(tài)規(guī)劃方法求解線性規(guī)劃問題：

K=3,2,1

7/16/2024當k=3時有

再用狀態(tài)轉(zhuǎn)移方程來替換上式中的

6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/2024當k=1時，有

這就是指標函數(shù)的最優(yōu)值

6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/2024即線性規(guī)劃問題的最優(yōu)解為最優(yōu)值為6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/20246.5動態(tài)規(guī)劃的應(yīng)用舉例前面已經(jīng)討論過的最短路問題、裝載問題（又稱背包問題）和資源分配問題都可以作為動態(tài)規(guī)劃應(yīng)用的實例。為了進一步擴大動態(tài)規(guī)劃的應(yīng)用范圍，我們再舉幾個應(yīng)用實例。7/16/20241066.5.1可回收資源再利用

7/16/2024107狀態(tài)轉(zhuǎn)移方程為允許決策集合

過程指標是階段指標的和，即

6.5.1可回收資源再利用7/16/2024108

依次類推，可求得：6.5.1可回收資源再利用7/16/2024109

計算結(jié)果表明最優(yōu)策略為即前兩年將全部設(shè)備都投入低負荷生產(chǎn)，后三年將全部設(shè)備都投入高負荷生產(chǎn)，這樣可以使5年的總產(chǎn)量最大，最大產(chǎn)量是23700件。有了上述最優(yōu)策略，各階段的狀態(tài)也就隨之確定了，即按階段順序計算出各年年初的完好設(shè)備數(shù)量。6.5.1可回收資源再利用7/16/2024

6.5.1可回收資源再利用7/16/2024設(shè)某廠計劃全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品產(chǎn)量的平方成正比，系數(shù)為0.005。廠內(nèi)有倉庫可以存放產(chǎn)品，存儲費為每公斤每季度1元。求最佳的生產(chǎn)安排使得年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。設(shè)sk

為第k季初的庫存量，則s1=s5=0；

設(shè)xk

為第k季的生產(chǎn)量，設(shè)yk

為第k季的訂貨量；

sk

，xk

，yk

都取實數(shù)，狀態(tài)轉(zhuǎn)移方程為sk+1=sk+xk-yk；

目標函數(shù)為6.5.2生產(chǎn)存儲問題7/16/2024第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊界條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4將x4*代入

f4(s4,x4)得：

f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得：6.5.2生產(chǎn)存儲問題7/16/2024第三步：(第二、三、四季度)總效果f2(s2,x2)=0.005x22+s2+f3*(s3)

將s3=s2+x2–700代入f2(s2,x2)得：113注意：最優(yōu)階段總效果僅是當前狀態(tài)的函數(shù)，與其后的決策無關(guān)。6.5.2生產(chǎn)存儲問題7/16/2024第四步：(第一、二、三、四季度)總效果f1(s1,x1)=0.005x12+s1+f2*(s2)

將s2=s1+x1–600=x1–600代入f1(s1,x1)得：114由此回溯，得最優(yōu)生產(chǎn)–庫存方案：

x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；

x4*=900。6.5.2生產(chǎn)存儲問題7/16/2024凈費用=維護費+更新費-殘值收益6.5.3設(shè)備更新問題7/16/20246.5.3設(shè)備更新問題7/16/2024在時刻2購買的機器可以在時刻3，時刻4，或時刻5去交易更換。因此，在時刻3購買的機器可以在時刻4或時刻5去交易更換。因此，對在時刻4購買的機器，只有一個合理的決策，就是將機器使用到時刻5然后賣掉獲得殘值。因此，6.5.3設(shè)備更新問題7/16/2024在時刻0購買的機器可以在時刻1，時刻2，或時刻3去交易更換。因此，在時刻1購買的機器可以在時刻2，時刻3，或時刻4去交易更換。因此，6.5.3設(shè)備更新問題7/16/2024對于設(shè)備更新問題，還有另外一種建立動態(tài)規(guī)劃的辦法。

階段:

時刻

t

狀態(tài):

在時刻

t機器的年齡

6.5.3設(shè)備更新問題7/16/2024某電子系統(tǒng)由若干個部件串聯(lián)而成，如果其中一個部件失靈整個系統(tǒng)便會失靈。為了提高整個系統(tǒng)的可靠性，各部件可以采用并聯(lián)相同元件的設(shè)計方案。例如部件1可以由若干個元件并聯(lián)而成。這樣部件1的可靠性就提高了，但同時成本也增加了。那么在整個系統(tǒng)成本是有定額的情況下，如何設(shè)計并聯(lián)方案（即各部件分別由多少相同元件并聯(lián)而成）才能使整個系統(tǒng)的可靠性最大，這就是一個系統(tǒng)可靠性優(yōu)化的問題。6.5.3復(fù)雜系統(tǒng)可靠性問題7/16/2024并聯(lián)元件數(shù)目部件1部件2部件3部件410.70.50.70.620.80.70.90.730.90.80.950.9各部件安裝不同數(shù)目原件的成本表并聯(lián)元件數(shù)目部件1部件2部件3部件4110201020220403030330504040某電子系統(tǒng)由四個部件串聯(lián)構(gòu)成，四個部件分別是采用不同數(shù)量元件并聯(lián)的，其工作的可靠性如表所示。若系統(tǒng)成本總定額為100，求最大可靠性的串聯(lián)方案？6.5.3復(fù)雜系統(tǒng)可靠性問題7/16/2024（1）按構(gòu)成系統(tǒng)的部件數(shù)量，確定動態(tài)規(guī)劃有4個階段，即k=4（2）各階段的狀態(tài)參數(shù)為在各階段可用的成本總值，即在第k階段允許使用的總費用（3）各階段的決策變量為第k個部件采用的元件數(shù)