動態(tài)規(guī)劃PPT教學(xué)課件

1、動態(tài)規(guī)劃第三章 動態(tài)規(guī)劃 3.1 動態(tài)規(guī)劃的基本概念和方法基本概念與名詞解釋最優(yōu)化原理與動態(tài)規(guī)劃的基本方法 3.2 動態(tài)規(guī)劃模型的建立與求解步驟 建立動態(tài)規(guī)劃模型的基本要求動態(tài)規(guī)劃的求解步驟 3.3 動態(tài)規(guī)劃的應(yīng)用舉例定價問題資源分配問題生產(chǎn)存儲問題第一節(jié) 動態(tài)規(guī)劃的基本概念與方法1 動態(tài)規(guī)劃的基本概念一、動態(tài)決策問題： 決策過程具有階段性和時序性(與時間有關(guān))的決策問題。即決策過程可劃分為明顯的階段。二、什么叫動態(tài)規(guī)劃(D.P. Dynamic Program)： 多階段決策問題最優(yōu)化的一種方法。 廣泛應(yīng)用于工業(yè)技術(shù)、生產(chǎn)管理、企業(yè)管理、經(jīng)濟(jì)、軍事等領(lǐng)域。三、動態(tài)規(guī)劃(D.P.)的起源： 1

2、951年,美國數(shù)學(xué)家R.Bellman(貝爾曼)等人提出最優(yōu)化原理，從而建立動態(tài)規(guī)劃，他的名著動態(tài)規(guī)劃于1957年出版。四、動態(tài)決策問題分類：1、按數(shù)據(jù)給出的形式分為： 離散型動態(tài)決策問題。 連續(xù)型動態(tài)決策問題。2、按決策過程演變的性質(zhì)分為： 確定型動態(tài)決策問題。 隨機(jī)型動態(tài)決策問題。名詞解釋 例3-1 某公司欲將一批貨物從城市A運(yùn)到城市E去，如圖所示，走哪條路線最好？1、階段(stage)k： 把所給問題的過程，恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段。描述階段的變量稱為階段變量，常用k表示。k = 1、2、3、4。2、狀態(tài)(state)Sk：狀態(tài)表示每個階段開始所處的自然狀態(tài)，即是每一階段的出發(fā)位置

3、。階段的起點(diǎn)。通常一個階段有多個狀態(tài)。記為Sk S1=A，S2=B1,B2,B3，S3=C1,C2,C3， S4=D1,D2。3、決策(decision) uk(sk) ：從一個階段某狀態(tài)演變到下一個階段某狀態(tài)的選擇。常用uk(sk) 表示第k階段當(dāng)狀態(tài)處于sk時的決策變量。決策集用Dn(Sk)表示。就是階段的終點(diǎn)。 D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=U2(B1),U2(B2),U2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=U3(C1),U3(C2),U3(C3)=D1,D2;D1,D2,D3; D1,D2

4、,D3=D1,D2,D3=S4， D4(S4)=U4(D1),U4(D2),U4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=X5(E1),X5(E2)=F;F=F。4、策略(policy)：策略是一個按順序排列的決策組成的集合。即是全過程中各個階段的決策Un組成的有序總體Un。 如 A B2 C1 D1 E 5、子策略(sub-policy) ：由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程，即是剩下的M個階段構(gòu)成M子過程，相應(yīng)的決策系列叫M子策略。 如 C1 D1 E6、狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，如果給定第k階段的狀態(tài)

5、Sk ，本階段決策為Uk( Sk) ，則第k+1階段的狀態(tài)Sk+1也就完全確定，它們的關(guān)系可表示為Sk+1Tk(Sk ,Uk),它描述了由k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。即是前一階段的終點(diǎn)(決策)是后一階段的起點(diǎn)(狀態(tài))。 如 Uk( Sk) Sk+1 7、指標(biāo)函數(shù)：用來衡量各個階段優(yōu)劣的數(shù)量指標(biāo)，它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。記為Vk,n(sk,Uk)。如上例中，用dk(sk,Uk)表示距離。d2(B3,C2)=8, d3(C2,D2)=2 等。8、目標(biāo)函數(shù)：策略的數(shù)量指標(biāo)值，記為 Z=optv1(s1,u1)* vn(sn,un)。其中：opt為ma

6、x或min，*為運(yùn)算符號。如上例中，Z=mind1(s1,u1)+dn(sn,un)=mind1+d2+ dn最優(yōu)化原理 一、R.Bellman最優(yōu)化原理： 作為整個過程的最優(yōu)策略，無論過去的狀態(tài)和決策如何，對前面的決策形成狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。 即：若M是從A到B最優(yōu)路線上的任一點(diǎn)，則從M到B的路線也是最優(yōu)路線。A MB二、指標(biāo)遞推方程： fn*(Sn) = opt vn(sn,un) * vn(sn,un) xnDn(Sn) 如上例：fn*(Sn) = min vn(sn,un)+ fn+1*(Sn+1) ， n=3、2、1 xnDn(Sn) f4*(S4) = min v

7、4(s4,u4) x4D4(S4) 三、求解過程： 用反向嵌套遞推法：從最后一個階段開始，依次對各子過程尋優(yōu)，直至獲得全過程的最優(yōu)， 形成最優(yōu)策略，獲得最優(yōu)策略指標(biāo)值。第二節(jié) 動態(tài)規(guī)劃模型的建立與求解步驟一、建立動態(tài)規(guī)劃模型的基本要求 將問題劃分成若干階段。有的問題階段性很明顯，有的則不明顯，需要分析后人為假設(shè)。 確定各階段的狀態(tài)變量，并給出狀態(tài)轉(zhuǎn)移方程，狀態(tài)轉(zhuǎn)移方程的形式應(yīng)當(dāng)與遞推順序一致。 狀態(tài)變量應(yīng)當(dāng)滿足無后效性要求。 明確指標(biāo)函數(shù)，給出最優(yōu)函數(shù)遞推方程，遞推方程的形式應(yīng)當(dāng)與遞推順序一致。二、動態(tài)規(guī)劃的求解步驟 正確劃分階段。 確定狀態(tài)變量和決策變量，并給出狀態(tài)變量和決策變量的可行集合。

8、 確定求解的遞推順序，給出狀態(tài)轉(zhuǎn)移方程。 確定階段、子過程(子策略)的指標(biāo)函數(shù)，確定最優(yōu)值函數(shù)的遞推方程和邊界條件。 遞推求解。 與遞推過程反向求出最優(yōu)策略(最優(yōu)決策變量值系列)和最優(yōu)狀態(tài)變化路線。例2：求圖中A到F的最短路線及最短路線值。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、階段(stage)n： n = 1、2、3、4、5。2、狀態(tài)(state)Sn： S1=A，S2=B1,B2,B3，S3=C1,C2,C3，S4=D1,D2

9、,D3，S5=E1,E2。3、決策(decision)un：決策集Dn(Sn)。 D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=u2(B1),u2(B2),u2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=u3(C1),u3(C2),u3(C3) =D1,D2;D1,D2,D3; D1,D2,D3=D1,D2,D3=S4， D4(S4)=u4(D1),u4(D2),u4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=u5(E1),u5(E2)=F;F=F。AB1B2B3C1C2C3D1D2D

10、3E1E2F354954351715846442226975144、狀態(tài)轉(zhuǎn)移方程：un = Sn+15、指標(biāo)函數(shù)(距離)：dn(sn,un)。 d2(B3,C2)=1, d3(C2,D3)=6 等。6、指標(biāo)遞推方程：fn*(Sn) = min rn(sn,un)+ fn+1*(Sn+1) ， n=4、3、2、1 UnDn(Sn) f5*(S5) = min V5(s5,u5) X5D5(S5)AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=5 f5(s5)=d5(s5,u5) u5 S5 F f5*(s5) U*5 E1 E2 11F22

11、Fn=4 f4(s4)=d4(s4,u4)+ f5*(s5) u4 S4 E1 E2 f4*(s4) U*4 D1 D2 D3 4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77E2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=3 f3(s3)=d3(s3,u3)+ f4*(s4) u3 S3 D1 D2 D3 f3*(s3) u3* C1 C2 C3 1 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 =

12、 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D1n=2 f2(s2)=d2(s2,u2)+ f3*(s3) u2 S2 C1 C2 C3 f2*(s2) u2* B1 B2 B3 9+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11 = 127+ 8 = 15 12C2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=1 f1(s1)=d1(s1,u1)+ f2*(s2) u1 S1 B1 B2 B3 f1*(s1) u1* A 3

13、+ 14 = 175+ 9 = 144+ 12 = 16 14B2最短路線值為：f1*(s1) = 14最短路線求解如下：n= 5 f5(s5)=d5(s5,U5) U5 S5 F f5*(s5) U5 E1 E2 n= 1 f1(s1)=d1(s1,U1)+ f2*(s2) U1 S1 B1 B2 B3 f1*(s1) U1* A 11F22Fn= 4 f4(s4)=d4(s4,U4)+ f5*(s5) U4 S4 E1 E2 f4*(s4) U4 D1 D2 D3 4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77

14、E2n= 3 f3(s3) =d3(s3,U3) + f4*(s4) U3 S3 D1 D2 D3 f3*(s3) U3* C1 C2 C3 1 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 = 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D1n= 2 f2(s2) =d2(s2,U2) + f3*(s3) U2 S2 C1 C2 C3 f2*(s2) U2* B1 B2 B3 9+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11

15、 = 127+ 8 = 15 12C23+ 14 = 175+ 9 = 144+ 12 = 16 14B2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即： A B2 C1 D1 E2 F 第三節(jié) 動態(tài)規(guī)劃的應(yīng)用舉例 定價問題 資源分配問題 生產(chǎn)存儲問題一、定價問題 某公司考慮為某新產(chǎn)品定價，該產(chǎn)品的單價擬從每件5元、6元、7元和8元這四個中選取一個，每年允許價格有1元幅度的變動，該產(chǎn)品預(yù)計(jì)暢銷五年，據(jù)預(yù)測不同價格下各年的利潤如表3-1所示。 表3-2 每年預(yù)計(jì)利潤額單價第一年 第二年 第三年 第四年 第五年5元6元7元8元10121416

16、12131415151616152020181425241814建立數(shù)學(xué)模型 按年劃分階段，k=1,2,.,5 每階段的狀態(tài)變量為本年(上一年已確定)的價格，狀態(tài)變量的可行集合Sk=(5,6,7,8)。 決策變量為每年依據(jù)當(dāng)年價格為下一年度決定價格，根據(jù)題意決策變量的可行集合是： 采用逆序算法，因此狀態(tài)轉(zhuǎn)移方程是 最優(yōu)值函數(shù)遞推方程為) 1, 1(kkkkSSSu)(1kkkSuS)()(max)(11kkkkukkSfudSfk進(jìn)行各階段的計(jì)算 采用逆序法，設(shè) 當(dāng)k=5時，S5=(5,6,7,8)，由表3-1得到 當(dāng)k=4時， S4=(5,6,7,8)，由遞推方程 得0)(66Sf14)8(

17、,18)7(,24)6(,25)5(5555ffff)()(max)(5544444SfudSfu5)5(,4524202520max)6()6()5()5(max)5(454544ufdfdf繼續(xù)求解 同理得其它各階段的最優(yōu)解8) 8 (,92) 8 (, 8) 7 (,90) 7 (, 7) 6 (,87) 6 (6) 5 (,84) 5 (,17) 8 (,76) 8 (, 7 , 6) 7 (,75) 7 (, 7 , 6) 6 (,74) 6 (6) 5 (,73) 5 (,27) 8 (,57) 8 (, 6) 7 (,61) 7 (, 6 , 5) 6 (,61) 6 (6 ,

18、5) 5 (,60) 5 (,37) 8 (,32) 8 (, 6) 7 (,42) 7 (, 5) 6 (,45) 6 (111111112222222233333333444444ufufufufkufufufufkufufufufkufufuf時當(dāng)時當(dāng)時當(dāng)反推得最優(yōu)路線 按照與求最優(yōu)值函數(shù)方向相反的順序求最優(yōu)狀態(tài)路線：最優(yōu)決策變量。即從第一年單價應(yīng)為8元開始，向后推算。 得第二年定價8元，第三年定價7元，第四年定價6元，第五年定價5元。 最大利潤值為92萬元。也可用決策圖求解二、資源分配問題 某公司將5臺加工中心分配給甲、乙、丙、丁四個工廠，各工廠得設(shè)備后可產(chǎn)生如表3-2所示的利潤，應(yīng)怎

19、么分配設(shè)備可使公司總利潤最大？ 工廠設(shè)備數(shù)甲乙丙丁012345067101215037912130510111111046111212建立數(shù)學(xué)模型 按工廠次序劃分階段，k=1，2，3，4 狀態(tài)變量為各階段可用于分配的設(shè)備總臺數(shù) 決策變量是分配給第k工廠的設(shè)備數(shù) 采用逆序算法，狀態(tài)轉(zhuǎn)移方程 最優(yōu)值函數(shù)遞推方程kkkxSS10)()()(max)(5511SfSfudSfkkkkukkk第4階段的最優(yōu)解 當(dāng)k=4時，S4=(0,1,2,3,4,5)0123450123450461112120461112120123454S4u),(444Sud)(44Sf)(4*4Su第3階段的最優(yōu)解 當(dāng)k=3時

20、，S3=(0,1,2)0000000101054045512012051064069101023S3u),(333Sud)(334uSf*3u33fd )(33Sf第3階段的最優(yōu)解（續(xù)） 當(dāng)k=3時，S3=33012305101111640111114111423S3u),(333Sud)(334uSf*3u33fd )(33Sf第3階段的最優(yōu)解（續(xù)） 當(dāng)k=3時，S3=44012340510111112116401216161511161，23S3u),(333Sud)(334uSf*3u33fd )(33Sf第3階段的最優(yōu)解（續(xù)） 當(dāng)k=3時，S3=55012345051011111112

21、12116401217211715112123S3u),(333Sud)(334uSf*3u33fd )(33Sf第2階段的最優(yōu)解 當(dāng)k=2時，S2=(0,1,2)0000000101035053502012037105010871002S2u),(222Sud)(223uSf*2u22fd )(22Sf第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時，S2=330123037914105014131291402S2u),(222Sud)(223uSf*2u22fd )(22Sf第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時，S2=4401234037912161410501617171412171，22S2u),(222

22、Sud)(223uSf*2u22fd )(22Sf第2階段的最優(yōu)解（續(xù)）當(dāng)k=2時，S2=55012345037912132116141050211921191715210，22S2u),(222Sud)(223uSf*2u22fd )(22Sf第1階段的最優(yōu)解（續(xù)）當(dāng)k=1時，S1=5 50123450671012152117141050212321201715231 1S1u),(111Sud)(112uSf*1u11fd )(11Sf反向求最佳狀態(tài)路線0 , 10 , 122 , 32 , 141*44*33*22*1uSuSuSu由方案一方案二工廠名分配設(shè)備數(shù)工廠名分配設(shè)備數(shù)甲乙丙丁1

23、121甲乙丙丁1220三、生產(chǎn)存儲問題 某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場預(yù)測，今后四個月的市場需求量如表3-7所示。時期（月）需求量（dk）12342324三、生產(chǎn)存儲問題 某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場預(yù)測，今后四個月的市場需求量如表3-7所示。時期（月）需求量（dk）12342324已知的其它條件 已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品的生產(chǎn)準(zhǔn)備成本是3千元，每月僅能生產(chǎn)一批，每批6件。每件存儲成本為0.5千元，且第一個月初無存貨，第四個月末的存貨要求為零。求最優(yōu)生產(chǎn)計(jì)劃。 設(shè)第k月的生產(chǎn)量uk，存儲量為Sk,則總成本為kkkkkSuuSC5 . 003),(建立數(shù)學(xué)模型 以月劃分階段

24、，k=1,2,3,4 各階段決策變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段存儲量Sk。 采用逆序算法，則狀態(tài)轉(zhuǎn)移方程為 最低成本遞推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkk第四階段的最優(yōu)解 當(dāng)k=4時，d4=4,因第四階段末無存貨，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存儲01234432107654000.511.5276.565.52000000000076.565.52第三階段最優(yōu)解 當(dāng)k=3時，由于 ，且第三階段需求量d3=2，S3=(0,1,2,3,4,5,6)44SS3

25、u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲0234565678900000567890123476.565.521212.51313.511第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲2012340456711111156780123476.565.52811.512.012.510.0第三階段最優(yōu)解:S3=3,4S3u3

26、本期成本C3S4f4(S4) f3(S3)生產(chǎn)存儲3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三階段最優(yōu)解:S3=5,6S3u3本期成本C3S4f4(S4) f3(S3)生產(chǎn)存儲501042.52.52.56.5345.5288.560033425第二階段最優(yōu)解 當(dāng)k=2時，d2=3，由于最生產(chǎn)能力為6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲03456678900006789012311.010.58.08.

27、01717.51617第二階段最優(yōu)解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二階段最優(yōu)解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二階段最優(yōu)解:S2=3S2u2本期成本C2S3f3(S3) f2(S2)生產(chǎn)存儲30123456045

28、67891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二階段最優(yōu)解:S2=4S2u2本期成本C2S3f3(S3) f2(S2)生產(chǎn)存儲4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一階段最優(yōu)解 當(dāng)k=1時，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生產(chǎn)存儲0234565678900000567890123416.015.515.0

29、12.512.52121.52220.521.5最優(yōu)解 從第一階段向后反推最優(yōu)路線，總結(jié)可得時期K期初存貨期末存貨最優(yōu)生產(chǎn)量該期成本總成本SkSk+1123403043040506081.59220.512.5112已知的其它條件 已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品的生產(chǎn)準(zhǔn)備成本是3千元，每月僅能生產(chǎn)一批，每批6件。每件存儲成本為0.5千元，且第一個月初無存貨，第四個月末的存貨要求為零。求最優(yōu)生產(chǎn)計(jì)劃。 設(shè)第k月的生產(chǎn)量uk，存儲量為Sk,則總成本為kkkkkSuuSC5 . 003),(建立數(shù)學(xué)模型 以月劃分階段，k=1,2,3,4 各階段決策變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段存

30、儲量Sk。 采用逆序算法，則狀態(tài)轉(zhuǎn)移方程為 最低成本遞推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkk第四階段的最優(yōu)解 當(dāng)k=4時，d4=4,因第四階段末無存貨，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存儲01234432107654000.511.5276.565.52000000000076.565.52第三階段最優(yōu)解 當(dāng)k=3時，由于 ，且第三階段需求量d3=2，S3=(0,1,2,3,4,5,6)44SS3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲0234565678900000567890123476.565.521212.51313.511第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲2012340456711111156780123476.565.52811.512.012.510.