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

1、關于運籌學動態(tài)規(guī)劃第一張，PPT共二十八頁，創(chuàng)作于2022年6月多階段決策問題：是動態(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)這時

2、，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au, 0a1。12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策第二張，PPT共二十八頁，創(chuàng)作于2022年6月在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關系為h=h(u2)相應的機器年完好率b, 0 b1。 假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 3 航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機飛行在不同環(huán)境中的情況，不斷地決定航天飛機的飛行方向（姿態(tài)）和速度，使之

3、能最省燃料和實現(xiàn)目的（如軟著落問題）。 不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。 4 線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應用動態(tài)規(guī)劃方法加以解決，后面將詳細介紹。第三張，PPT共二十八頁，創(chuàng)作于2022年6月 5 最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。我們將用此例來說明所有動態(tài)規(guī)劃問題的理論和方法。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333

4、5526643123456第四張，PPT共二十八頁，創(chuàng)作于2022年6月 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)允許集合。 第二

5、節(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階段的允許決策集合。第五張，PPT共二十八頁，創(chuàng)作于2022年6月 4 多階段決策過程：就是可以在各個階段進行決策，去控制過程發(fā)展的多段過程。多階段決策

6、過程的發(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)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1圖示如下：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。第六張，PPT共二十八頁，創(chuàng)作于2022年6月 無后效性或馬爾可夫性：如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來

7、的發(fā)展，這個性質(zhì)稱為無后效性。在構(gòu)造決策過程的動態(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)移方程的形式。第七張，PPT共二十八頁，創(chuàng)作于2022年6月 5 策略：策略是一個按順序排列的決策組成的集合。由過程的第k階段開始到終止狀態(tài)為止的過程，稱為問題的后部子過程（或稱為k子過程）。由每段的決策按順序排列組成的決策函數(shù)序

8、列稱為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表示之。即第八張，PPT共二十八頁，創(chuàng)作于2022年6月 動態(tài)規(guī)劃模型的指標函數(shù)，應具有可分離性，并滿足遞推關系。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。常見的指標函數(shù)的形式是：

9、過程和它的任一子過程的指標是它所包含的各階段的指標和。即其中vj(sj,uj)表示第j階段的階段指標。這時上式可寫成無后效性的結(jié)果。第九張，PPT共二十八頁，創(chuàng)作于2022年6月 過程和它的任意子過程的指標是它所包含的各階段的指標的乘積。即則可改寫成 最優(yōu)值函數(shù)：表示從第k階段的狀態(tài)sk開始到第n階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數(shù)值。即第十張，PPT共二十八頁，創(chuàng)作于2022年6月多階段決策過程的數(shù)學模型：（具有無后效性的多階段決策過程）所謂求解多階段決策過程問題，就是要求出（1） 最優(yōu)策略，即最優(yōu)決策序列（2） 最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列第十一張，PPT共二十八頁，

10、創(chuàng)作于2022年6月（3）最優(yōu)目標函數(shù)值 f1(s1)從k到終點最優(yōu)子策略的最優(yōu)目標函數(shù)值第十二張，PPT共二十八頁，創(chuàng)作于2022年6月第三節(jié)：動態(tài)規(guī)劃的基本思想和基本方程以最短路問題的解法為例來說明。（窮舉法48條路線）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第十三張，PPT共二十八頁，創(chuàng)作于2022年6月最短路的特性：如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明:用反證法）當k=6時,由F1到終點G只有一條路線，故f6(F1)=4.同理，f6(

11、F2)=3.當k=5時，出發(fā)點有E1,E2,E3三個。u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F3 G第十四張，PPT共二十八頁，創(chuàng)作于2022年6月當k=4時，有當k=3時，有當k=2時，有第十五張，PPT共二十八頁，創(chuàng)作于2022年6月當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)策略。最短路線為AB1C2D1E2F2G。

12、AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687683533842212333552664360437597681310912131618第十六張，PPT共二十八頁，創(chuàng)作于2022年6月用動態(tài)規(guī)劃（逆序法求解的）基本特性：（1）將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變量、決策變量、及定義最優(yōu)指標函數(shù)，正確寫出基本的遞推關系式和恰當?shù)倪吔鐥l件（簡言之為基本方程）。從而把問題化成一族同類的子問題，（2）求解時從邊界條件開始，逆（或順）過程行進方向，逐段遞推尋優(yōu)。在每個問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后問題的最優(yōu)解，就是整個問題的最優(yōu)解。（3）動態(tài)規(guī)

13、劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。每段決策的選取都是從全局考慮的，與該段的最優(yōu)選擇答案一般是不同的。（4）在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過的各段狀態(tài)便可確定了最優(yōu)路線。第十七張，PPT共二十八頁，創(chuàng)作于2022年6月（5）求解的各個階段,我們利用了k階段與k+1階段之間的遞推關系:一般情況,k階段與k+1階段的遞推關系式（動態(tài)規(guī)劃基本方程）邊界條件為練習：寫出乘積形式指標函數(shù)的動態(tài)規(guī)劃基本方程。第十八張，PPT共二十八頁，創(chuàng)作于2022年6月用動態(tài)規(guī)劃求解時的幾點注意：（1）將

14、問題的過程劃分成恰當?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)。第十九張，PPT共二十八頁，創(chuàng)作于2022年6月順序解法的階段變量k，決策變量xk，以及決策變量允許集合Qk的含義和逆序解法模型中相應變量的含義相同，而狀態(tài)變量sk表示第k階段結(jié)束時的狀態(tài)，其中k

15、=0,1,2,n。記狀態(tài)轉(zhuǎn)移方程為 sk=g(sk-1,xk) k=1,2,n則 s k-1=g-1(sk,xk)記第k階段末狀態(tài)為sk，第k階段決策為xk的直接指標（或稱階段指標）為dk(sk,xk)，并記從第1階段到第k階段末狀態(tài)為sk所得到的最大效益為fk(sk)，則順序解法的基本方程（或稱指標遞推方程及邊界條件）為其中 opt=Max or Min順序解法第二十張，PPT共二十八頁，創(chuàng)作于2022年6月AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456 最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)

16、字表示距離（或花費），試求從A點到G點的最短距離（總費用最小）。第二十一張，PPT共二十八頁，創(chuàng)作于2022年6月按照順序動態(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（C 1）=Min d2（B1，C1）+ f1（B1）=Min 1+5=6 其相應決策為x2：B1 C1 f2（C 2）=Min d2（B1，C2）+ f1（B1），d2（B2，C2）+ f1（B2） =Min 3+5，8+

17、3=8 其相應決策為x2：B1 C2 f2（C 3）=Min d2（B1，C3）+ f1（B1），d2（B2，C3）+ f1（B2） = Min 6+5，7+3=10 其相應決策為x2：B2 C3 f2（C 4）=Min d2（B2，C4）+ f1（B2）=Min 6+3=9 其相應決策為x2：B2 C4第二十二張，PPT共二十八頁，創(chuàng)作于2022年6月類似地，可計算得當k=3時，S3=D1，D 2，D 3 ，有 f3（D 1）=11 x3：C 2 D1 f3（D 2）=13 x3：C 2 D2 or C 3 D2 f3（D 3）=13 x3：C 3 D3 or C 4 D3當k=4時，S4=

18、E1，E 2，E 3 ，有 f4（E 1）=13 x4：D1 E 1 f4（E 2）=13 x4：D 1 E 2 f4（E 3）=15 x4：D 2 E 3 當k=5時，S5=F1，F(xiàn) 2 ，有 f5（F 1）=16 x5：E 1 F 1 f5（F 2）=15 x5：E 2 F 2 當k=6時，S5=G ，有 f6（G）=18 x6：F 2 G再按計算的順序反推，可得相應的最短線路為：A B1 C2 D1 E 2 F 2 G第二十三張，PPT共二十八頁，創(chuàng)作于2022年6月第四節(jié)：動態(tài)規(guī)劃的理論基礎 適應于用動態(tài)規(guī)劃方法求解的是具有無后效性的多階段決策過程。 動態(tài)規(guī)劃方法的理論基礎是基于R. Bellman提出的最優(yōu)性原理：“一個過程的最優(yōu)策略具有這樣的性質(zhì)：