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

1、精選優(yōu)質文檔-傾情為你奉上第11章 動態(tài)規(guī)劃一個隨事件或階段推移的系統(tǒng)叫做動態(tài)系統(tǒng)，動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種數學方法。一個系統(tǒng)依據某種方式分為許多個不同的階段，這些階段不僅有著次序推移性，而且相互間有著依賴和影響。這樣，在多階段決策過程中，每個階段決策的選擇，不僅要依據次序來考查某階段的效果，而且要顧及此決策對以后各階段決策的影響。一般情況下，為得到整個系統(tǒng)的最優(yōu)選擇，必須放棄對某個階段來說最佳的決策。對各個階段所做的決策形成確定整個系統(tǒng)的決策序列，稱這樣的決策序列為系統(tǒng)的一個策略。對應某一確定的策略，整個系統(tǒng)依據某種數量指標衡量其決策的優(yōu)劣。多階段決策過程就是在所有允許策略集

2、合中。確定一個達到最有指標的最優(yōu)策略。這種衡量系統(tǒng)的指標一般取最大值或最小值的策略。因此，多階段決策過程也是一個可以構成多個變量的最優(yōu)化問題。動態(tài)規(guī)劃就是解決此類多階段決策過程的最優(yōu)化方法。雖然動態(tài)規(guī)劃主要解決多階段決策的動態(tài)系統(tǒng)，但是可分階段的靜態(tài)系統(tǒng)問題也能作為特例用它有效地求解。§11.1 動態(tài)規(guī)劃的基本原理 本章通過構造數學模型，形成具有特殊的動態(tài)系統(tǒng)過程，將基于某種方式把整個過程分成若干個互相聯系的階段，在其每個階段都需要作出決策，從而使整個過程達到最佳效果。同時，各個階段決策的選擇依賴于該階段的狀態(tài)以及前階段或后階段的變化。各個階段決策確定后，組成一個決策序列，從而形成了

3、整個過程具有前后關聯的鏈狀結構的多階段決策過程，稱為序貫決策過程。先用下面的最短路問題（問題可分成階段性）來說明動態(tài)規(guī)劃的基本思想。例 1，最短路問題。圖111所示是一個路線網絡圖，連線上的數字表示兩點之間的距離（或費用），要求尋找一條由A到E的路線，使距離最短（或費用最?。?。對于這樣的一個比較簡單的問題，可直接使用枚舉法例舉所有從A到E得路線，確定出所應走的路線是距離最短或費用最少，用動態(tài)規(guī)劃的思想，如果已找到由A到E得最短路線是AB1C2D2E（記作L），那么當尋求L中的任何一點（如C2）到E得最短路時，它必然是L子路線 C2D2E(記作L1)。否則，如D2到E的最短路是另一條路線L2，則

4、把AB1C2與L2連接起來，就會得到一條不同于L的從A到E得最短路，根據最短路的這一特性，可以從最后一段開始，用逐步向前遞推的方法，一次求出路段上各點到E的最短路，最后得到A到E得最短路。上述這種由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的過程稱為動態(tài)規(guī)劃的解法。該過程揭示了動態(tài)規(guī)劃的基礎思想，為便于對動態(tài)規(guī)劃的思想和方法進行數學描述，下面先引入動態(tài)規(guī)劃的基本概念并建立最優(yōu)目標函數。（1）分階段：適當地依據具體情況將系統(tǒng)分成若干個相互聯系的階段，并將各個段按順序或逆序加以編號（常用K），描述階段的變量稱為階段變量。如例1可分為5個階段，k=1，2，3，4，5. （2）狀態(tài)：狀態(tài)表示系統(tǒng)在某一階段所處

5、的位置。描述過程狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示，狀態(tài)變量的集合用Sk表示。如在例1中，第一階段有一個狀態(tài)就是初始位置A，第三階段有3個狀態(tài)，即集合S3=.(3)決策：當系統(tǒng)處于某一階段的某個狀態(tài)時，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。如在例1第二階段中，從狀態(tài)B2出發(fā)，其允許決策集合為D2（B2）=(4)策略：由系統(tǒng)各階段確定的決策所形成的決策序列稱為策略。從初始狀態(tài)s1出發(fā)，由系統(tǒng)的所有n個階段的決策所形成的策略成為全過程策略，從允許策略集合中找出達到最有效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉移方程：狀態(tài)轉移方程是確定過程有一個狀態(tài)到

6、另一個狀態(tài)的演變過程。若給定第k階段狀態(tài)的演變過程，并且若該階段的決策變量dk一經確定，第k+1階段的狀態(tài)變量sk+1也就完全確定。如例1中，狀態(tài)轉移方程為 sk+1=dk(sk).（6）階段收益：若確定某一階段的系統(tǒng)狀態(tài)，執(zhí)行某一階段決策所得的效益稱為階段效益，他是整個系統(tǒng)總收益的一部分。階段效益是階段狀態(tài)和決策變量的函數。如在例1中階段效益為走完一段路程所走過的距離。（7）指標函數和最優(yōu)值函數：系統(tǒng)執(zhí)行某策略所產生效果的優(yōu)劣可用數學指標來衡量，它是各個階段狀態(tài)和決策的函數，稱為指數函數。（8）邊值條件：在系統(tǒng)決策的狀態(tài)推移進程中最初的條件稱為邊值條件。由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的

7、過程稱為速推解法，由系統(tǒng)的最前階段逐段向終結階段求最優(yōu)的過程稱為順序推解法。如例1顯然有邊值條件： fn+1(sn+1)=0.根據上述確定的階段編號。狀態(tài)變量、決策變量、狀態(tài)轉移方程、邊值條件及指標函數。確定例1的最短路線，計算步驟如下：根據最短路線特性，尋找最短路線的方法，將從最后一段開始，用后向前逐步地推的方法，求出各點到點E的最短路線，最后求得由點A到點E的最短線，所以，動態(tài)規(guī)劃的方向是從各點逐段向始點方向尋找最短路線的一種方法，見圖112. 當k=4時，有D1到終點E只有一條路線，故f4（D1）=4，同理，f4（D2）=3.當k=3時，出發(fā)點有C1,C2,C33個，若從C1出發(fā)，則有兩

8、個選擇，一是至D1，一是至D2，則F3（C1）=min=min=7.其相應的決策為d3（C1）=D1，表示由D1,至終點E的最短距離為7，其最短距離路線是C1D1E.同理，從C2和C3出發(fā)，則有 f3（C2）=。其相應的決策為d3（C2）=D2。 f3（C3）=min且d3（C3）=D3。 類似地?？捎嬎惝攌=2時，有f2(B1)=12, d2(B1)=C2. f2(B2）=11, d2（B2）=C2， f2（B3）=9, d2（B3）=C3當k=1時，出發(fā)點只有一個點A，則f1(A)=min,且d1(A)=B1，于是獲得從始點A至終點E的最短距離為15，為便于找出最短路線，在按計算的順序推之

9、，可求出最優(yōu)決策函數序列dk，即由d1（A）=B1,d2（B）=C2,d3（C2）=D2,d4（D2）=E組成一個最優(yōu)策略。那么最短路線為 AB1C2D2E.§11.2 中學生數學知識應用競賽題舉例例2今年盛夏酷暑，能源緊張，某工廠從能源部門獲得5個單位某種能源，該工廠有3個部門需要這種能源，由于各部門所使用設備條件不同，生產的產品也不同，這樣導致是用能源所產生的收益情況也不同，所用的能源為整數單位，各部門具體產生的收益（萬元）如表111所示，為能有效地利用這種能源，工廠將如何分配能源給各部門,使工廠受益最大?表111收益（萬元）部門能源0 1 2 3 4 51230 2 4 5 5

10、 60 1 3 4 6 80 3 4 5 5 6解 設3個部門分配到的能源分別為x1，x2，x3單位，相應每個單位所產生的收益設為c1(x1),c2(x2),c3(x3）,a那么模型為 Maxc1(x1)+c2(x2)+c3(x3); s.t. x1+x2+x3 5 x1,x2,x3 0為整數。使用遞推方法來求解。按k=1，2，3為3階段，用fk（z）表示在第k階段所用能源為z單位時，獲得最大收益，即有 f3（5）=maxc1(x1)+c2(x2)+c3(x3); s.t. x1+x2+x3 5. x1,x2,x3 0為整數。于是 f3(5)=maxf2(5-x3)+c3(x3)(x3=1,1

11、,2,3.5) =maxf2(5),f2(4)+3,f2(3)+4,f2(2)+5,f2(1)+5,f2(0)+6; f2(5)=maxf1(5-x2)+c2(x2)(x2=0,1,2,.5) =maxf1(5)，f1(4)+1，f1(3)+3,f1(2)+4,f1(1)+6,f2(0)+8f2(4)=maxf1(4-x2)+c2(x2) (x2=0,1,2,4) =maxf1(4),f1(3)+1,f1(2)+3,f1(1)+4,f1(0)+6;f2(3)=maxf1(3-x2)+c2(x2)(x2=0,1,3) maxf1(3),f1(2)+1,f1(1)+3,f1(0)+4;f2(2)=

12、maxf1(2),f(1)+1,f1(0)+3；f2(1)=maxf1(1),f1(0)+1.將f1(0)=0，f1(1)=2,f1(2)=4,f1(3)=5,f1(4)=5，f1(5)=6回代得f2（1)=2f2（2）=max4，2+1,3=4，f2(3)=max5,4+1,2+3,4=5,f2(4)=max5,5+1,4+3,2+4,6=7,f2(5)=max6,5+2,5+3,4+4,2+6,8=8.f2(5)=max8,7+3,5+4,4+5,2+5,6=10于是解為x3*=1，x2*=2，x1*=2，最大收益為10（萬元），即分配給3個部門的分別為：部門1，部門2都為2單位，而部門3

13、為1單位，最大收益為10萬元。.§11.3 復合系統(tǒng)工作可靠性問題若某種機器的工作系統(tǒng)有n個部件串聯組成，只要有一個部件失靈，整個系統(tǒng)就不能工作，為提高系統(tǒng)工作的可靠性，在每一個部件上均配有主要元件的備用件，并且設計了備用元件自動投入裝置。顯然，備用元件越多，整個系統(tǒng)正常工作的可靠性越大，但備用元件多了，整個系統(tǒng)的成本、重量、體積均相應增大，工作精度也降低，因此，最優(yōu)化問題是在考慮上述限制條件下，應如何選擇個部件的備用元件數，使整個系統(tǒng)的工作可靠性最大。設部件i（i=1，2，.n）上裝有ui個備用件時，它正常工作的概率為pi（ui）。例 3 某個廠設計一種電子設備，由3種元件D1,D

14、2,D3組成，已知這3中元件的價格和可靠性如112所示。要求在設計中所使用元件的費用不超過105元，試問：應如何設計室設備的可靠性達到最大（不考慮重量的限制）？表112元件單價（元）可靠性D1D2D33015200.90.80.5解 按元件種類劃分為3各階段，設狀態(tài)變量sk表示能容許用在Dk元件至D3元件的總費用；決策變量xk表示在Dk元件上的并聯個數；Pk表示一個Dk元件正常工作的概率，則為xk個Dk元件不正常工作的概率，另最優(yōu)值函數fk（sk）表示由狀態(tài)sk開始從Dk元件至D3元件組成的系統(tǒng)的最大可靠性，因而有f3(s3)=f2(s2)=f1(s2)= 由于s1=105，故解此問題只要求出

15、f1（105）即可，而 f1(105)= f3(30)=0.5, f3(15)=0,所以 f2(75)=max0.8×0.875，0.96×0.75，0.992 ×.5，0.9984×0 =max0.7,0.72,0.496 =0.72.同理 f2(45)=max0.8f3(30),0.96f3(30)=max0.4,0=0.4, f2(15)=0.故 f2(105)=max0.9 ×.72,0.99×0.4,0.999×0 =max0.648,0.396=0.648.從而求得x1*=1,x2*=2,x3*=2為最優(yōu)方案，即

16、D1元件用2個，D3元件用2個，其總費用為100元，可靠性為0.648。§11.4 不確定性的采購問題本節(jié)敘述在生產和經營管理中，經常遇到在價格有波動時如何合理購買的問題，不確定性的采購問題的最優(yōu)化目標為制定采購策略，對不同時期的浮動借個和概率，確定采購量以使總的采購費用（數學期望值）最小。 例 4 某公司在近5周內必須一次性采購原料一批，估計在未來5周內價格有波動，期浮動價格和概率（可能性）如表113所示。試求各周中處在什么價位時應購入，使采購價格最為合理？費用數學期望值最??？單價（千元/噸）概率1816140.40.30.3解 這里價格是一個隨機變量，是按某種已知的概率分布取值的

17、。用動態(tài)規(guī)劃方法處理，按采購期限將5周分為5個階段，將每周的價格看做該階段的狀態(tài)，設yk為狀態(tài)變量，表示第k周的實際價格；xk為決策變量。當x=1，表示第k周決定采購；當xk=0，表示第k周決定等待。用ykE表示第k周決定等待，而在以后采取最優(yōu)決策時采購價格的期望值；用fk（yk）表示第k周實際價格為yk時，從第k周至第5周采取最優(yōu)策略所得的最小期望值。因而可寫出逆序遞推關系為 fk(yk)=minyk,ykE，ykSk, f5(yk)=y5, y5S5其中Sk=18，16，14，k=1，2，3，4，5.由ykE和fk（yk）的定義可知 ykE=efk+1(yk+1)=0.4fk+1(18)+0.3fk+1(16)+0.3fk+1(14). (113)并且得出最優(yōu)決策為 xk=從最后一周開始；逐步向前遞推計算，具體計算過程如下： 當k=5是，因f5(y5)=y5,y5 S5,故有 f5(18)=18;f5(16)=16;f5(14)=14,即在第5周時，若所需的原料尚未買入，則無論市場價格如何，都必須采購，不能再等。當k=5時，由ykE=0.4fk+1(18)+0.3fk+1(16)+0.3fk+1(14)可知 y4E=0.4×18+0.3&#