管理运筹学5动态规划课件.ppt

《管理运筹学5动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章：动态规划3.1动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划(D.P.–DynamicProgram)：多阶段决策问题最优化的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，著名《动态规划》，于1957年出版。四、动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型

2、动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。五、名词术语AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、阶段(stage)n：作出决策的若干轮次。n=1、2、3、4、5。2、状态(state)Sn：每一阶段的出发位置。构成状态集，记为SnS1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。阶段的起点。3、决策(decision)Xn：从一个阶段某

3、状态演变到下一个阶段某状态的选择。构成决策集，记为Dn(Sn)。阶段的终点。D1(S1)={X1(A)}={B1,B2,B3}=S2，D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2,C3}=S3，D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2,D3}=S4，D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2}=S5D5(S5)={X5(E1),X5(E2)}={F;F}={F}。AB1B2B3C1C2C3D1D2D3E1E2F354954

4、35171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、策略(policy)：全过程中各个阶段的决策Xn组成的有序总体{Xn}。如AB2C1D1E2F5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。如C1D1E2F上例从AF共有38种走法，即有38条路线，38个策略。6、状态转移方程：前一阶段的终点(决策)是后前一阶段的起点(状态)。Xn=Sn+17、指标函数：各个

5、阶段的数量指标，记为rn(sn,xn)。如上例中，用dn(sn,xn)表示距离。d2(B3,C2)=1,d3(C2,D3)=6等。8、目标函数：策略的数量指标值，记为Z=opt[r1(s1,x1)**rn(sn,xn)]。其中：opt为max或min，*为运算符号。如上例中Z=min[d1(s1,x1)++dn(sn,xn)]=min[d1+d2+…+dn]AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143.2最优化原理一、R.Bellman最优化原

6、理：作为整个过程的最优策略，无任过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。AMB二、指标递推方程：fn*(Sn)=opt[r1(s1,x1)**rn(sn,xn)]xn∈Dn(Sn)如上例：fn*(Sn)=min[rn(sn,xn)+fn+1*(Sn+1)]，n=4、3、2、1xn∈Dn(Sn)f5*(S5)=min[r5(s5,x5)]x5∈D5(S5)AMB三、求解过程：用反向嵌套递推法：

7、从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，形成最优策略，获得最优策略指标值。3.3DP建模及求解一、建模条件：决策过程本身具有时顺序性或可以转化为具有时顺序性的决策问题，均可建立动态规划数学模型求解。二、典型动态决策问题建模及其求解1、最短路线问题例：求下列图中A到F的最短路线及最短路线值。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、

8、阶段(stage)n：n=1、2、3、4、5。2、状态(state)Sn：S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。3、决策(decision)Xn：决策集Dn(Sn)。D1(S1)={X1(A)}={B1,B2,B3}=S2，D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C