運籌學(動態(tài)規(guī)劃1)

一、多階段決策問題 (Multi-Stagedecisionprocess)多階段決策過程特點:狀態(tài)

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

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

s3...狀態(tài)

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

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

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

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

二、動態(tài)規(guī)劃求解的多階段決策問題的特點通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉移除與本階段的狀態(tài)和決策有關外，還可能與系統(tǒng)過去經歷的狀態(tài)和決策有關。因此，問題的求解就比較困難復雜。而適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經歷的狀態(tài)和決策(歷史)無關。2例l

設從A到E鋪設輸油管道,中間經過三個站。

AB1EB2B3C1C2C3C4D1D2435547653522256321735(3)(5)(5)(8)(5)(12)(10)(7)(12)(10)1.多階段決策過程的最優(yōu)化

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

1.動態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合sk

Xk②

決策變量及其允許集合ukUk

③

狀態(tài)轉移方程

sk+1=Tk

(sk,uk

)④

階段效應dk

(sk,uk

)

5

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

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

fk(sk)=opt

u{dk

(sk,uk

)+fk+1(sk+1)}

k=n,…,16

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

(一)階段和階段變量為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當地劃分為若干個相互聯系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數等于多段決策過程從開始到結束所需作出決策的數目。7

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

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

1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過程進行的先后，每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止狀態(tài)記為sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。8

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

2．可能狀態(tài)集一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集?？赡軤顟B(tài)集實際上是關于狀態(tài)的約束條件。通常可能狀態(tài)集用相應階段狀態(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}

；9（三）決策、決策變量和允許決策集合所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質是關于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。用以描述決策變化的量稱之決策變量。和狀態(tài)變量一樣，決策變量可以用一個數，一組數或一向量來描述，也可以是狀態(tài)變量的函數，記以uk=uk(sk)，表示于階段k狀態(tài)sk時的決策變量。決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示,uk(sk)∈Uk(sk)允許決策集合實際是決策的約束條件。

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

10

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

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

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

11（五）狀態(tài)轉移方程系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1

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

，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2,…,sk-1及其決策u1(s1),u2(s2)…uk-1(sk-1)無關。系統(tǒng)狀態(tài)的這種轉移，用數學公式描述即有：

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

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

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

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

13

(1)階段指標函數（也稱階段效應）。用dk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數，簡記為dk

。圖5-1的dk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，dk(v2,v5)=3,即v2到v5的距離為3。

(2)過程指標函數（也稱目標函數）。用Vk,n(sk,uk)表示第k子過程的指標函數。如圖5-1的Vk,n(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Vk,n(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略uk(sk)有關，因此它是sk和uk(sk)的函數，嚴格說來，應表示為:

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

14不過實際應用中往往表示為Vk,n(sk,uk)或Vk,n(sk)。還跟第k子過程上各段指標函數有關，過程指標函數Vk(sk)通常是描述所實現的全過程或k后部子過程效果優(yōu)劣的數量指標，它是由各階段的階段指標函數dk(sk,uk)累積形成的，適于用動態(tài)規(guī)劃求解的問題的過程指標函數（即目標函數），必須具有關于階段指標的可分離形式．對于部子過程的指標函數可以表示為：式中，表示某種運算，可以是加、減、乘、除、開方等。

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

(5-2)15多階段決策問題中，常見的目標函數形式之一是取各階段效應之和的形式，即:

(5-3)

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

(5-4)

總之，具體問題的目標函數表達形式需要視具體問題而定。

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

16

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

稱fk(sk)為第k子過程上的最優(yōu)指標函數；與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構成該子策賂的各段決策稱為該過程上的最優(yōu)決策，為；有簡記為

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

17特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例只有唯一始點v1即s1取值唯一,故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.動態(tài)規(guī)劃的基本概念18按上述定義，所謂最優(yōu)決策是指它們在全過程上整體最優(yōu)(即所構成的全過程策略為最優(yōu))，而不一定在各階段上單獨最優(yōu)。

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

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

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

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

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

1．標號法為進一步闡明動態(tài)規(guī)劃方法的基本思路，我們介紹一種只適用于例這類最優(yōu)路線問題的特殊解法——標號法。標號法是借助網絡圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數小的方向推算，最終求得全局最優(yōu)解。

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

21下面給出標號法的一般步驟：

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

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

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

3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標號，起點方格內的數字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。

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

設從A到E鋪設輸油管道,中間經過三個站。

AB1EB2B3C1C2C3C4D1D2435547653522256321735(3)(5)(5)(8)(5)(12)(10)(7)(12)(10)最短路問題的特性:如果最短路通過點p，則這條路線從p至終點的部分，對于從p至終點的所有路線（稱為p的后部路線）而言，必定也是最短的路線。

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

2.動態(tài)規(guī)劃的基本原理則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為25如第一節(jié)所述，基于上述原理，提出了一種逆序遞推法；這里可以指出，該法的關鍵在于給出一種遞推關系。一般把這種遞推關系稱為動態(tài)規(guī)劃的函數基本方程。

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

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

2.動態(tài)規(guī)劃的基本原理26一般地，對于n個階段的決策過程，假設只考慮指標函數是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：

(1)當過程指標函數為下列“和”的形式時，

相應的函數基本方程為

（5—7）

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

(2)當過程指標函數為下列“積”的形式時,

相應的函數基本方程為

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

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

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

1．應將實際問題恰當地分割成n個子問題(n個階段)。通常是根據時間或空間而劃分的，或者在經由靜態(tài)的數學規(guī)劃模型轉換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．303.動態(tài)規(guī)劃方法的基本步驟

3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據經驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量。或者在把靜態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉換為動態(tài)規(guī)劃模型時，常取前者的變量xj為后者的決策變量uk。

4.能夠正確地寫出狀態(tài)轉移方程，至少要能正確反映狀態(tài)轉移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk

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

5．根據題意,正確地構造出目標與變量的函數關系——目標函數，目標函數應滿足下列性質：

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

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

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

(3)函數對其變元Vk+1,n，來說要嚴格單調。32

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

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

例5.3:有某種機床,可以在高低兩種不同的負荷下進行生產,在高負荷下生產時,產品的年產量為g,與年初投入生產的機床數量u1的關系為g=g(u1)=8u1,這時,年終機床完好臺數將為au1,(a為機床完好率，0<a<1,設a=0.7).在低負荷下生產時,產品的年產量為h,和投入生產的機床數量u2的關系為h=h(u2)=5u2,相應的機床完好率為b(0<b<1,設b=0,9),一般情況下a<b。假設某廠開始有x=1000臺完好的機床，現要制定一個五年生產計劃，問每年開始時如何重新分配完好的機床在兩種不同的負荷下生產的數量，以使在5年內產品的總產量為最高。34

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

1．變量設置

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

(2)狀態(tài)變量sk表示第k年度初擁有的完好機床臺數，同時也是第k-1年度末時的完好機床數量。

(3)決策變量uk，表示第k年度中分配于高負荷下生產的機床臺數。于是sk-uk便為該年度中分配于低負荷下生產的機床臺數．35

這里sk與uk均取連續(xù)變量，當它們有非整數數值時．可以這樣理解：如sk＝0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機床在

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

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

k=1，2，…,636

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

4．目標函數。設dk(sk,uk)為第k年度的產量，則dk(sk,uk)=8uk+5(sk-uk),因此，目標函數為k＝1,2,．．．,5

5．條件最優(yōu)目標函數遞推方程。令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結束這段時間的產品產量，根據最優(yōu)化原理有以下遞推關系：

k=1,2,3,4,537

6.邊界條件為下