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

關于運籌學動態(tài)規(guī)劃多階段決策問題：是動態(tài)決策問題的一種特殊形式。在多階段決策過程中，系統(tǒng)的動態(tài)過程可以按照時間進程分為相互聯(lián)系而又相互區(qū)別的各個階段，而且在每個階段都要進行決策。目的是使整個過程的決策達到最優(yōu)效果。多階段決策問題的典型例子：

1生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。2機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關系為g=g(u1)這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au,0<a<1。12n

狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策第2頁,共28頁，2024年2月25日，星期天在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關系為h=h(u2)相應的機器年完好率b,0<b<1。假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。3航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向（姿態(tài)）和速度，使之能最省燃料和實現(xiàn)目的（如軟著落問題）。

不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。

4線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應用動態(tài)規(guī)劃方法加以解決，后面將詳細介紹。第3頁,共28頁，2024年2月25日，星期天5最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最小）。我們將用此例來說明所有動態(tài)規(guī)劃問題的理論和方法。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第4頁,共28頁，2024年2月25日，星期天1階段、階段變量：把所給問題的過程，適當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，目的是能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是分為時間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。(逆序模型、順序模型)

2狀態(tài)、狀態(tài)變量：狀態(tài)表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過程的狀況。通常一個階段有若干個狀態(tài)。描述過程狀態(tài)的變量稱為狀態(tài)變量。常用sk來表示第k階段的狀態(tài)變量。一般來說，狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為是狀態(tài)允許集合。第二節(jié)：動態(tài)規(guī)劃的基本概念和定義

3決策、決策變量：決策表示當過程處于某一階段的某個狀態(tài)時，可以做出不同的決定（或選擇），從而決定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。常用uk(sk)表示第k階段當狀態(tài)為sk時的決策變量。在實際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk(sk)

Dk(sk)Dk表示第k階段的允許決策集合。第5頁,共28頁，2024年2月25日，星期天4多階段決策過程：就是可以在各個階段進行決策，去控制過程發(fā)展的多段過程。多階段決策過程的發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的，一般來說，系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但于系統(tǒng)的當前（或本階段）的狀態(tài)和決策有關，而且還于系統(tǒng)過去的歷史狀態(tài)和決策有關。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12k

s1u1s2u2s3skuksk+1圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。第6頁,共28頁，2024年2月25日，星期天

無后效性或馬爾可夫性：如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展，這個性質(zhì)稱為無后效性。在構造決策過程的動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求。如果狀態(tài)不能滿足無后效性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)定方法，以使狀態(tài)變量能滿足無后效性的要求。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下

能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。第7頁,共28頁，2024年2月25日，星期天5策略：策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止狀態(tài)為止的過程，稱為問題的后部子過程（或稱為k子過程）。由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，簡稱子策略，記為pk,n(sk)，即

當k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n(s1).即在實際問題中，可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用p表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。6指標函數(shù)和最優(yōu)值函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)，它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。Vk,n表示之。即第8頁,共28頁，2024年2月25日，星期天

動態(tài)規(guī)劃模型的指標函數(shù)，應具有可分離性，并滿足遞推關系。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。常見的指標函數(shù)的形式是：過程和它的任一子過程的指標是它所包含的各階段的指標和。即其中vj(sj,uj)表示第j階段的階段指標。這時上式可寫成無后效性的結果。第9頁,共28頁，2024年2月25日，星期天

過程和它的任意子過程的指標是它所包含的各階段的指標的乘積。即則可改寫成

最優(yōu)值函數(shù)：表示從第k階段的狀態(tài)sk開始到第n階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數(shù)值。即第10頁,共28頁，2024年2月25日，星期天多階段決策過程的數(shù)學模型：（具有無后效性的多階段決策過程）所謂求解多階段決策過程問題，就是要求出（1）最優(yōu)策略，即最優(yōu)決策序列（2）最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列第11頁,共28頁，2024年2月25日，星期天（3）最優(yōu)目標函數(shù)值f1(s1)從k到終點最優(yōu)子策略的最優(yōu)目標函數(shù)值第12頁,共28頁，2024年2月25日，星期天第三節(jié)：動態(tài)規(guī)劃的基本思想和基本方程以最短路問題的解法為例來說明。（窮舉法48條路線）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第13頁,共28頁，2024年2月25日，星期天最短路的特性：如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明:用反證法）當k=6時,由F1到終點G只有一條路線，故f6(F1)=4.同理，f6(F2)=3.當k=5時，出發(fā)點有E1,E2,E3三個。u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F3G第14頁,共28頁，2024年2月25日，星期天當k=4時，有當k=3時，有當k=2時，有第15頁,共28頁，2024年2月25日，星期天當k=1時，有且u1(A)=B1，于是得到從起點A到終點G的最短距離為18。為了找到最短路線,再按計算的順序反推之,可求出最優(yōu)決策函數(shù)序列{uk}：u1(A)=B1,u2(B1)=C2,u3=(C2)=D1,u4(D1)=E2,u5(E2)=F2,u6(F2)=G，即最優(yōu)策略。最短路線為A

B1

C2

D1

E2

F2

G。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687683533842212333552664360437597681310912131618第16頁,共28頁，2024年2月25日，星期天用動態(tài)規(guī)劃（逆序法求解的）基本特性：（1）將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變量、決策變量、及定義最優(yōu)指標函數(shù)，正確寫出基本的遞推關系式和恰當?shù)倪吔鐥l件（簡言之為基本方程）。從而把問題化成一族同類的子問題，（2）求解時從邊界條件開始，逆（或順）過程行進方向，逐段遞推尋優(yōu)。在每個問題求解時，都要使用它前面已求出的子問題的最優(yōu)結果，最后問題的最優(yōu)解，就是整個問題的最優(yōu)解。（3）動態(tài)規(guī)劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結合起來考慮的一種最優(yōu)化方法。每段決策的選取都是從全局考慮的，與該段的最優(yōu)選擇答案一般是不同的。（4）在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過的各段狀態(tài)便可確定了最優(yōu)路線。第17頁,共28頁，2024年2月25日，星期天（5）求解的各個階段,我們利用了k階段與k+1階段之間的遞推關系:一般情況,k階段與k+1階段的遞推關系式（動態(tài)規(guī)劃基本方程）邊界條件為練習：寫出乘積形式指標函數(shù)的動態(tài)規(guī)劃基本方程。第18頁,共28頁，2024年2月25日，星期天用動態(tài)規(guī)劃求解時的幾點注意：（1）將問題的過程劃分成恰當?shù)碾A段；（2）正確選擇狀態(tài)變量sk,使它既能描述過程的變量，又要滿足無后效應；（3）確定決策變量uk及每一階段的允許決策集合Dk(sk)；（4）正確寫出狀態(tài)轉(zhuǎn)移方程；（5）正確寫出指標函數(shù)Vk,n，它應滿足下面三個性質(zhì)：

a)是定義在全過程和所有后部子過程上的數(shù)量函數(shù)；

b)要具有可分離性，并滿足遞推關系。即c）函數(shù)

k（sk，uk，Vk+1,n）對于變量Vk+1，n要嚴格單調(diào)。第19頁,共28頁，2024年2月25日，星期天順序解法的階段變量k，決策變量xk，以及決策變量允許集合Qk的含義和逆序解法模型中相應變量的含義相同，而狀態(tài)變量sk表示第k階段結束時的狀態(tài)，其中k=0,1,2,┅,n。記狀態(tài)轉(zhuǎn)移方程為

sk=g(sk-1,xk)k=1,2,┅,n則sk-1=g-1(sk,xk)記第k階段末狀態(tài)為sk，第k階段決策為xk的直接指標（或稱階段指標）為dk(sk,xk)，并記從第1階段到第k階段末狀態(tài)為sk所得到的最大效益為fk(sk)，則順序解法的基本方程（或稱指標遞推方程及邊界條件）為其中

opt=MaxorMin順序解法第20頁,共28頁，2024年2月25日，星期天AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456

最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。第21頁,共28頁，2024年2月25日，星期天按照順序動態(tài)規(guī)劃求解方法，從第1階段開始計算，由前向后逐步推移至G點，計算過程為當k=0時，S0={A}，f0（A）=0當k=1時，S1={B1，B2}，由A到B1只有一條路線，故f1（B1）=5

同理得：f1（B2）=3當k=2時，S2={C1，C2，C3，C4}f2（C1）=Min{d2（B1，C1）+f1（B1）}=Min{1+5}=6

其相應決策為x2：B1→C1f2（C2）=Min{d2（B1，C2）+f1（B1），d2（B2，C2）+f1（B2）}=Min{3+5，8+3}=8

其相應決策為x2：B1→C2f2（C3）=Min{d2（B1，C3）+f1（B1），d2（B2，C3）+f1（B2）}=Min{6+5，7+3}=10

其相應決策為x2：B2→C3f2（C4）=Min{d2（B2，C4）+f1（B2）}=Min{6+3}=9

其相應決策為x2：B2→C4第22頁,共28頁，2024年2月25日，星期天類似地，可計算得當k=3時，S3={D1，D2，D3}，有

f3（D1）=11x3：C2→D1f3（D2）=13x3：C2→D2orC3→D2f3（D3）=13x3：C3→D3orC4→D3當k=4時，S4={E1，E2，E3}，有

f4（E1）=13x4：D1→E1f4（E2）=13x4：D1→E2

f4（E3）=15x4：D2→E3

當k=5時，S5={F1，F(xiàn)2}，有

f5（F1）=16x5：E1→F1f5（F2）=15x5：E2→F2

當k=6時，S5={G}，有

f6（G）=18x6：F2→G再按計算的順序反推，可得相應的最短線路為：A→B1→C2→D1→E2→F2→G第23頁,共28頁，2024年2月25日，星期天第四節(jié)：動態(tài)規(guī)劃的理論基礎

適應于用動態(tài)規(guī)劃方法求解的是具有無后效性