第8章 動態(tài)規(guī)劃11-5-8

第八章動態(tài)規(guī)劃北京物資學(xué)院運籌學(xué)教學(xué)課件北京物資學(xué)院信息學(xué)院2011-5-8動態(tài)規(guī)劃多階段決策問題最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型動態(tài)規(guī)劃模型的建立與求解多階段決策問題

動態(tài)規(guī)劃是一種研究多階段決策問題的理論和方法。

多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。

策略：每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的總效益達(dá)到最優(yōu)。例1最短路問題設(shè)有一個旅行者從下圖中的A點出發(fā)，途中要經(jīng)過B、C、D等處，最后到達(dá)終點E。從A到E有很多條路線可以選擇，各點之間的距離如圖所示，問該旅行者應(yīng)該選擇哪一條路線，才能使從A到達(dá)E的總行程最短？AB1B2B3C3C2C1D1D2E25375632451514633334狀態(tài)A決策階段1狀態(tài)B1階段2決策狀態(tài)D1狀態(tài)C3階段3決策階段4決策狀態(tài)E行程1行程2行程3行程4例2多階段資源分配問題

設(shè)有某種機器設(shè)備，可用于完成兩類工作A和B。若第k年初完好機器的數(shù)量為sk,若以數(shù)量xk用于工作A，余下的sk-xk用于工作B，則該年的預(yù)期收入為g(xk)+h(sk-xk)，其中g(shù)(xk)

和h(sk-xk)

是已知函數(shù)，并且g(0)=h(0)=0。又機器設(shè)備在使用中會有損壞，設(shè)機器用于工作A時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的a倍（0<a<1），若用于工作B時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的b倍(0<b<1)，即下一年初能繼續(xù)用于完成這兩項工作的機器數(shù)為sk+1=axk+b(sk-xk)。設(shè)第一年初完好的機器數(shù)為s1，問在連續(xù)三年內(nèi)，每年應(yīng)如何分配用于A、B兩項工作的機器數(shù)，才能使三年的總收益達(dá)到最大。狀態(tài)S1決策第一年階段1狀態(tài)S2第二年階段2決策狀態(tài)S4狀態(tài)S3第三年階段3決策收益1收益2收益3最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型動態(tài)規(guī)劃問題的解題思路動態(tài)規(guī)劃的基本概念最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型動態(tài)規(guī)劃模型的分類動態(tài)規(guī)劃問題的解題思路思路：將一個n階段的決策問題轉(zhuǎn)化為依次求n個具有遞推關(guān)系的單階段決策問題，從而簡化計算。在例1中，這種轉(zhuǎn)化的實現(xiàn)是從終點E出發(fā)一步步進行反推（逆序算法）（1）考慮一個階段的選擇。到達(dá)E之前，上一步必然到達(dá)D1或D2，D1到E的最優(yōu)策略是：D1E，距離d(D1,E)=3,記f(D1)=3.D2到E的最優(yōu)策略是：D2E，距離d(D2,E)=4,記f(D2)=4.1AB1B2B3C3C2C1D1D2E2537563245154633334(2)聯(lián)合考慮兩個階段的最優(yōu)選擇。當(dāng)旅行者離終點還有兩站時，他必然處在C1，C2或C3的某一點上。C1到終點的路有兩條：C1D1E，C1D2E，旅行者從這兩條路線中選最短的一條，并且不管是經(jīng)過D1或D2，到達(dá)該點后，他應(yīng)循著從D1或D2到E的最短路線繼續(xù)走。因此從C1到E的最短路程為：即從C1到E的最短路線為C1D1E，記如果從C2出發(fā)如果從C3出發(fā)（3）再聯(lián)合起來考慮三個階段的最優(yōu)選擇。從B1點出發(fā)的最優(yōu)選擇為從B2點出發(fā)的最優(yōu)選擇為從B3點出發(fā)的最優(yōu)選擇為（4）四個階段聯(lián)合考慮時從A到E的最優(yōu)選擇。從A到E的最短路線為AB3C2D2E，距離為11。1AB1B2B3C3C2C1D1D2E253756324515463333434476117811以上計算過程可以在圖上通過標(biāo)號法實現(xiàn)動態(tài)規(guī)劃的基本概念1.階段(stage)：指一個問題需要作出決策的步數(shù)。

通常用k表示問題的階段數(shù)。階段一般是根據(jù)時間和空間的自然特征來劃分的。2.狀態(tài)(state)：表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況，是動態(tài)規(guī)劃中最關(guān)鍵的一個參數(shù)。它既反映前面各個階段決策的結(jié)局，又是本階段決策的出發(fā)點和依據(jù)。它是動態(tài)規(guī)劃問題各個階段信息的傳遞點和結(jié)合點。通常一個階段有多個狀態(tài)。如例1中第一階段有1個狀態(tài)，A.第三階段有三個狀態(tài)C1,C2,C3。狀態(tài)變量：描述狀態(tài)的變量?？梢允菙?shù)、數(shù)組或向量。通常用Sk表示k階段的狀態(tài)集。如例1中S3={C1,C2,C3}.狀態(tài)的性質(zhì)：無后效性。3.決策(decision)

是指某階段初從給定的狀態(tài)出發(fā)，決策者在面臨的若干種不同方案中做出的選擇。決策變量xk(sk)表示第k階段狀態(tài)為sk時對方案的選擇。用Dk(sk)表示在第k階段狀態(tài)為sk時決策允許的取值范圍，稱為允許決策集合。即xk(sk)Dk(sk)。

D2(B1)={C1,C2,C3}

xk*(sk)表示第k階段狀態(tài)為sk時的最優(yōu)決策。決策的性質(zhì)：第k階段某一狀態(tài)下的決策直接決定第k+1階段的狀態(tài)。4.策略（policy）和子策略（subpolicy）:策略：多階段決策過程中，由各階段決策組成的序列總體稱作一個策略（全過程策略）。

{x1(s1),x2(s2),…,xn(sn)}從過程的某一階段開始到過程最終階段結(jié)束的決策序列稱為問題的子過程策略或子策略。從k階段起的子策略可以寫為{xk(sk),xk+1(sk+1),…,xn(sn)}每一階段有若干狀態(tài)，每個狀態(tài)又有若干不同的決策，從而形成許多可供選擇的策略（子策略），能使預(yù)期目標(biāo)達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略（子策略）。

5.狀態(tài)轉(zhuǎn)移方程從第k階段的狀態(tài)sk到第k+1階段的狀態(tài)sk+1的演變過程的解析表達(dá)式。記為：或簡寫為

狀態(tài)轉(zhuǎn)移方程6.指標(biāo)函數(shù)階段的指標(biāo)函數(shù)：用來衡量每一階段決策效果優(yōu)劣的數(shù)量指標(biāo)。階段指標(biāo)函數(shù)是狀態(tài)變量和決策變量的函數(shù)，即vk(sk,xk)。過程的指標(biāo)函數(shù)：從第k階段的狀態(tài)sk

出發(fā)到過程的最后階段結(jié)束，當(dāng)采取某種子策略時，按預(yù)定標(biāo)準(zhǔn)得到的效益值，稱為過程指標(biāo)函數(shù)。過程指標(biāo)函數(shù)值取決于從第k階段到最后階段所采取的子策略，它是sk和子策略的函數(shù)值。記作根據(jù)實際問題的性質(zhì)，過程指標(biāo)函數(shù)可以是各個階段指標(biāo)函數(shù)的和或積。最優(yōu)指標(biāo)函數(shù)：從狀態(tài)sk出發(fā)，選取最優(yōu)子策略所得到的指標(biāo)函數(shù)值稱為最優(yōu)指標(biāo)函數(shù)值，記作fk(sk).

Opt代表最優(yōu)化，可以是min或max狀態(tài)s1決策x1(s1)階段1T(S1,x1)狀態(tài)s2階段2T(S2,x2)決策x2(s2)階段nT(Sn,xn)狀態(tài)sn決策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論過去的狀態(tài)和決策如何，對先前決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。作為全過程的最優(yōu)策略的組成部分的任一后部子策略一定是從該狀態(tài)出發(fā)至終點的最優(yōu)子策略。逆序解法：逆著階段順序的方向，由后向前推算。求解思路：從最后一個階段開始，逆著過程的進展方向依次求出各階段的各個狀態(tài)對應(yīng)的最優(yōu)子策略。每一階段的求解過程都是在其后部子過程最優(yōu)子策略的基礎(chǔ)上，再考慮本階段的指標(biāo)函數(shù)，求出本階段的最優(yōu)策略。直到求出整個過程的最優(yōu)策略為止?；具f推方程據(jù)最優(yōu)性原理，階段k的階段指標(biāo)值vk(sk)加上(或乘以)從下一階段k+1開始到過程結(jié)束采取最優(yōu)策略取得的最優(yōu)指標(biāo)函數(shù)值fk+1(sk+1)

，再從中選出最優(yōu)，便是階段k從狀態(tài)sk出發(fā)到全過程結(jié)束的最優(yōu)指標(biāo)函數(shù)值。狀態(tài)s1決策x1(s1)階段1T(S1,x1)狀態(tài)s2階段2T(S2,x2)決策x2(s2)階段nT(Sn,xn)狀態(tài)sn決策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)尋求最優(yōu)解的方向遞推方程邊界條件動態(tài)規(guī)劃的數(shù)學(xué)模型：建模步驟（小結(jié)）劃分階段，確定階段變量k。確定狀態(tài)變量sk。確定決策變量xk和允許決策集合Dk(xk)寫出狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,

xk

)寫出指標(biāo)函數(shù)的基本遞推方程明確邊界條件

動態(tài)規(guī)劃模型的分類按過程演變特征：確定性動態(tài)規(guī)劃隨機性動態(tài)規(guī)劃根據(jù)狀態(tài)變量：離散型動態(tài)規(guī)劃連續(xù)型動態(tài)規(guī)劃

過程變量確定隨機離散離散確定型離散隨機型連續(xù)連續(xù)確定型連續(xù)隨機型動態(tài)規(guī)劃模型的建立與求解例3：某一警衛(wèi)部門共有9支巡邏隊，負(fù)責(zé)3個要害部位A、B、C的警衛(wèi)巡邏。每個部位可分別派出2--4支巡邏隊，并且由于派出巡邏隊數(shù)的不同，各部位預(yù)期在一段時間內(nèi)可能造成的損失有差別，具體數(shù)字見下表1，問警衛(wèi)部門應(yīng)往各部位分別派多少支巡邏隊，才能使總的預(yù)期損失為最少？213110422351432438182CBA預(yù)期損失部位巡邏隊數(shù)表1解：把9支巡邏隊派往3個部位看成依次分三個階段（用k表示，k=1,2,3）。狀態(tài)變量sk：每個階段初擁有的可派遣的巡邏隊數(shù)。決策變量xk：每個階段對相應(yīng)部位派出的巡邏隊數(shù)。狀態(tài)轉(zhuǎn)移方程：決策變量x1x2x3狀態(tài)變量允許集95,6,72,3,4,5決策變量允許集2,3,42,3,42,3,4狀態(tài)變量S1S2S3狀態(tài)轉(zhuǎn)移方程S1=9S2=S1-x1S3=S2-x2階段123若用pk(xk)表示k階段派出巡邏隊數(shù)為xk時，該階段的部位預(yù)期損失值，則過程的指標(biāo)函數(shù)可寫成因此有k=3時，考慮對C部位派巡邏隊k=4時，k=2時，聯(lián)合考慮對B,C兩個部位派巡邏隊k=1時，對A,B,C三個部位派巡邏隊例4.投資問題現(xiàn)有資金5萬元,可對三個項目進行投資,投資額均為整數(shù)(單位為萬元),其中第二項目投資不得超過3萬元,第一和第三項目投資不得超過4萬元,第三項目投資至少要1萬元,每個項目投資五年后,預(yù)計可獲得的收益由下表給出,問如何投資可望獲得最大的利潤?

投資額收益項目01234項目10361012項目2051012項目3481115解：這個問題用動態(tài)規(guī)劃求解，可分為3個階段，k=1，2，3.狀態(tài)變量Sk:

第k階段初擁有的資金額。（可用于第k,k+1,..3項目的投資額）決策變量xk(Sk

):對第

k

個項目的投資額.狀態(tài)轉(zhuǎn)移方程:Sk+1

=Sk

-xk決策變量x1x2x3狀態(tài)變量允許集51,2,3,4,51,2,3,4,5決策變量允