《－动态规划》ppt课件

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

1、管理运筹学动态规划综述动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划所研究的对象是多阶段决策问题。它把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题。综述多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。综述动态规划可以解决管理中的最短路径、装载问题、库存问题、资源分配、生产过程最优化问题。§1.多阶段决策过程最优化问题举例最短路径问题:最短路径问题的应用找出

2、A到E的最短路径阶段划分IIVIIIII将A到E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题求解策略记S(x)为节点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最优解BACBDBCDEC212312312511214106104131211396581052052871220141919§2.基本概念、基本方程与最优化原理一、基本概念1.阶段:用动态规划方法求解问题时,首先将问题的全过程适当地分成若干个互相联系的阶

3、段,以便能按一定的次序去解.划分的标准是时间或空间.§2.基本概念、基本方程与最优化原理2.状态.状态是指每个阶段开始时所处的自然状态或客观条件.在例1中某个阶段的状态就是某个阶段的始点.S2={B1,B2,B3,B4}北京上海广州指标值(收益)V1(s1,x1)指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)s1s2s3s4x1x2x3§2.基本概念、基本方程与最优化原理3.决策.决策是某一阶段内的抉择,第N阶段的决策与第N个阶段的状态有关,通常用Xn(Sn)表示第n阶段处于Sn状态时的决策量,而这个决策量又决定第n+1阶段的状态.北京上海广州指标值(收益)V1(s1,x1)

4、指标值(收益)V2(s2,x2)指标值(收益)V3(s3,x3)S1s2s3s4x1x2x3§2.基本概念、基本方程与最优化原理4.策略.由所有各阶段的决策函数序列称为全过程策略,简称策略,记为p1,n(s1),能够达到总体最优的策略叫做最优策略.从第K个阶段开始到最后阶段的决策组成的决策函数序列称为K子过程策略,简称K子策略,记为Pk,N(Sk)§2.基本概念、基本方程与最优化原理5.指标函数:指标函数是衡量全过程策略或K子过程策略优劣的数量指标,指标函数的最优值称之为最优指标函数,记作f1(S1)或fk(Sk)最短距离f1(s1),最大收益fk(sk)§2.基本概念、基本方程与最优化原理6

5、.状态转移方程:已知第N+1阶段的状态是由第N阶段的状态和第N阶段的决策所决定的,用方程表示为:Sn+1=Tn(Sn,Xn)状态转移方程.§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程§2.基本概念、基本方程与最优化原理二、基本方程：动态规划递归方程三、最优化原理与动态规划的基本方法Bellman原理动态规划的基本方法逆向顺序法前向顺序法Bellman原理示意图Bellman最优性原理“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略”.

6、最优策略的子策略也是最优的.Bellman最优性原理最短路径的子路径仍然是最短路径。全长最优，那么部分仍然是最优。BACBDBCDEC212312312511214106104131211396581052052871220141919AB2C1D1EAB2C1D1A到E的最优是：是A到D1的最优四、动态规划建模与求解步骤建立动态规划模型的基本要求动态规划的求解步骤一、建立动态规划模型的基本要求将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求

7、。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。二、动态规划的求解步骤正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。建立动态规划模型及求解步骤划分阶段确定状态