《－動態(tài)規(guī)劃》ppt課件

《《－動態(tài)規(guī)劃》ppt課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、管理運(yùn)籌學(xué)動態(tài)規(guī)劃綜述動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種方法。動態(tài)規(guī)劃所研究的對象是多階段決策問題。它把困難的多階段決策問題變換成一系列互相聯(lián)系較容易的單階段問題。綜述多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達(dá)到最優(yōu)。綜述動態(tài)規(guī)劃可以解決管理中的最短路徑、裝載問題、庫存問題、資源分配、生產(chǎn)過程最優(yōu)化問題。§1.多階段決策過程最優(yōu)化問題舉例最短路徑問題:最短路徑問題的應(yīng)用找出

2、A到E的最短路徑階段劃分IIVIIIII將A到E的最短路徑問題，轉(zhuǎn)化為三個性質(zhì)完全相同，但規(guī)模較小的子問題求解策略記S(x)為節(jié)點x到E的最短路求解S(D1)=5，S(D2)=2S(C1)=8；S(C2)=7；S(C3)=12D1?ED2?ES(C1)=8；S(C2)=7；S(C3)=12S(B1)=20；S(B2)=14；S(B3)=19最優(yōu)解BACBDBCDEC212312312511214106104131211396581052052871220141919§2.基本概念、基本方程與最優(yōu)化原理一、基本概念1.階段:用動態(tài)規(guī)劃方法求解問題時,首先將問題的全過程適當(dāng)?shù)胤殖扇舾蓚€互相聯(lián)系的階

3、段,以便能按一定的次序去解.劃分的標(biāo)準(zhǔn)是時間或空間.§2.基本概念、基本方程與最優(yōu)化原理2.狀態(tài).狀態(tài)是指每個階段開始時所處的自然狀態(tài)或客觀條件.在例1中某個階段的狀態(tài)就是某個階段的始點.S2={B1,B2,B3,B4}北京上海廣州指標(biāo)值(收益)V1(s1,x1)指標(biāo)值(收益)V2(s2,x2)指標(biāo)值(收益)V3(s3,x3)s1s2s3s4x1x2x3§2.基本概念、基本方程與最優(yōu)化原理3.決策.決策是某一階段內(nèi)的抉擇,第N階段的決策與第N個階段的狀態(tài)有關(guān),通常用Xn(Sn)表示第n階段處于Sn狀態(tài)時的決策量,而這個決策量又決定第n+1階段的狀態(tài).北京上海廣州指標(biāo)值(收益)V1(s1,x1)

4、指標(biāo)值(收益)V2(s2,x2)指標(biāo)值(收益)V3(s3,x3)S1s2s3s4x1x2x3§2.基本概念、基本方程與最優(yōu)化原理4.策略.由所有各階段的決策函數(shù)序列稱為全過程策略,簡稱策略,記為p1,n(s1),能夠達(dá)到總體最優(yōu)的策略叫做最優(yōu)策略.從第K個階段開始到最后階段的決策組成的決策函數(shù)序列稱為K子過程策略,簡稱K子策略,記為Pk,N(Sk)§2.基本概念、基本方程與最優(yōu)化原理5.指標(biāo)函數(shù):指標(biāo)函數(shù)是衡量全過程策略或K子過程策略優(yōu)劣的數(shù)量指標(biāo),指標(biāo)函數(shù)的最優(yōu)值稱之為最優(yōu)指標(biāo)函數(shù),記作f1(S1)或fk(Sk)最短距離f1(s1),最大收益fk(sk)§2.基本概念、基本方程與最優(yōu)化原理6

5、.狀態(tài)轉(zhuǎn)移方程:已知第N+1階段的狀態(tài)是由第N階段的狀態(tài)和第N階段的決策所決定的,用方程表示為:Sn+1=Tn(Sn,Xn)狀態(tài)轉(zhuǎn)移方程.§2.基本概念、基本方程與最優(yōu)化原理二、基本方程：動態(tài)規(guī)劃遞歸方程§2.基本概念、基本方程與最優(yōu)化原理二、基本方程：動態(tài)規(guī)劃遞歸方程§2.基本概念、基本方程與最優(yōu)化原理二、基本方程：動態(tài)規(guī)劃遞歸方程三、最優(yōu)化原理與動態(tài)規(guī)劃的基本方法Bellman原理動態(tài)規(guī)劃的基本方法逆向順序法前向順序法Bellman原理示意圖Bellman最優(yōu)性原理“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面決策所形成的狀態(tài)，余下的決策必然形成最優(yōu)子策略”.

6、最優(yōu)策略的子策略也是最優(yōu)的.Bellman最優(yōu)性原理最短路徑的子路徑仍然是最短路徑。全長最優(yōu)，那么部分仍然是最優(yōu)。BACBDBCDEC212312312511214106104131211396581052052871220141919A?B2?C1?D1?EA?B2?C1?D1A到E的最優(yōu)是：是A到D1的最優(yōu)四、動態(tài)規(guī)劃建模與求解步驟建立動態(tài)規(guī)劃模型的基本要求動態(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)滿足無后效性要求

7、。明確指標(biāo)函數(shù)，給出最優(yōu)函數(shù)遞推方程，遞推方程的形式應(yīng)當(dāng)與遞推順序一致。二、動態(tài)規(guī)劃的求解步驟正確劃分階段。確定狀態(tài)變量和決策變量，并給出狀態(tài)變量和決策變量的可行集合。確定求解的遞推順序，給出狀態(tài)轉(zhuǎn)移方程。確定階段、子過程(子策略)的指標(biāo)函數(shù)，確定最優(yōu)值函數(shù)的遞推方程和邊界條件。遞推求解。與遞推過程反向求出最優(yōu)策略(最優(yōu)決策變量值系列)和最優(yōu)狀態(tài)變化路線。建立動態(tài)規(guī)劃模型及求解步驟劃分階段確定狀態(tài)