资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 动态规划,第七章 动态规划,1,动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。,动态规划是求解问题的一种方法和思想，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题要具体分析。,动态规划（Dynamic Programmi,2,第一节 多阶段决策问题,一、多阶段决策问题,在生产实践中，某些问题的决策过程可以划分为若干相互联系的阶段，每个阶段都需要做出决策，目标是使整个过程达到最优（全局最优）。,当每个阶段的决策确定以后，全过程的决策就是这些阶段决策所组成的一个决策序列。,多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展产生了各阶段的决策，从而形成决策序列，这就是“动态”的含义。,第一节 多阶段决策问题 一、多阶段决策问题,3,某些与时间无关的静态问题，可以根据问题的特点，人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。,二、多阶段决策问题举例,1.最短路线问题,2.机器负荷问题,3.资源分配问题,4.生产计划问题,某些与时间无关的静态问题，可以根据问题的特点,4,第二节 动态规划的基本概念和基本原理,一、动态规划的基本概念,用动态规划求解多阶段决策问题，首先要建立动态规划模型，模型中涉及是概念和符号有：,1.阶段,阶段变量k，k=1，2，n,2.状态和允许状态集合,状态特指某阶段的初始状态。,第二节 动态规划的基本概念和基本原理 一、动,5,状态变量s,k,允许状态集合S,K,动态规划中的状态应满足,无后效性,（马尔柯夫性）,：当某阶段状态给定以后，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。也就是说：过程的过去历史只能通过当前的状态去影响过程的未来发展，当前的状态是过去历史的一个完整总结。,3.决策和允许决策集合,决策变量u,k,（s,k,）,允许决策集合D,k,（s,k,）,状态变量sk,6,4.策略和允许策略集合,k部子策略p,k，n,（s,k,）,p,k，n,（s,k,）=u,k,（s,k,），u,k1,（s,k1,），u,n,（s,n,）,全过程策略p,1，n,（s,1,）,p,1，n,（s,1,）=u,1,（s,1,），u,2,（s,2,），u,n,（s,n,）,允许策略集合P,k,最优策略,：使全过程达到最优效果的策略。,4.策略和允许策略集合,7,5.状态转移方程,s,k1,=T,k,（s,k,，u,k,）,6.指标函数和最优指标函数,过程指标函数：V,k，n,=V,k，n,（s,k,，u,k,，s,k1,，s,n1,）,过程指标函数应具有可分离性，并满足递推关系，即：,V,k，n,（s,k,，u,k,，s,k1,，s,n1,）=,k,s,k,，u,k,，V,k1，n,（s,k1,，s,n1,）,阶段指标函数：v,k,（s,k,，u,k,）,5.状态转移方程,8,指标函数的两种形式：,过程指标为各阶段指标“和”的形式,V,k，n,（s,k,，u,k,，s,k1,，s,n1,）=,v,j,（s,j,，u,j,）,写成递推关系：,V,k，n,=v,k,（s,k,，u,k,）V,k1，n,（s,k1,，u,k1,，s,n1,）,过程指标为各阶段指标“积”的形式,V,k，n,（s,k,，u,k,，s,k1,，s,n1,）=,v,j,（s,j,，u,j,）,写成递推关系：,V,k，n,=v,k,（s,k,，u,k,）V,k1，n,（s,k1,，u,k1,，s,n1,）,n,j=k,n,j=k,指标函数的两种形式：nj=knj=k,9,最优指标函数：,f,k,（s,k,）=opt V,k，n,（s,k,，u,k,，s,k1,，s,n1,）,=opt V,k，n,（s,k,，P,k，n,（s,k,）,u,k,，u,n,p,k,P,k,二、动态规划的基本思想与基本原理,1.举例,2.动态规划的基本思想,将多阶段决策问题按照时间或空间特点划分成相互联系的阶段，即把一个大问题分解成一族同类型的子,最优指标函数：uk，unpk,10,问题。选取恰当的状态变量和决策变量，确定状态转移方程，定义最优指标函数，写出递推关系式和边界条件。,从边界条件开始，逆序递推寻优。每一阶段的计算都要用到前一阶段的最优结果，最后一个子问题的最优解就是整个问题的最优解。,在多阶段决策过程中，确定阶段k的最优决策时，不是只考虑本阶段的最优，而是要考虑本阶段及其所有后部子过程的一并最优，也就是说，它是把当前效益和未来效益结合起来考虑的一种方法。,问题。选取恰当的状态变量和决策变量，确定状态转移方程，定义最,11,3.动态规划的基本原理,贝尔曼最优化原理：“一个全过程最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略”。也就是说，一个最优策略的子策略也是最优的，即：,若 p*,1，n,（s,1,）=u,1,*（s,1,），u,2,*（s,2,），u,k,*（s,k,），u,n,*（s,n,）为一个全过程最优策略，则对此策略中所隐含的任一状态s,k,而言，k子过程的最优策略必然包含在上述全过程最优策略之中，即：,p*,k，n,（s,k,）=u,k,*（s,k,），u,k1,*（s,k1,），u,n,*（s,n,）,3.动态规划的基本原理,12,根据最优化原理可以将一个多阶段决策过程转化为若干个单阶段决策过程，然后递推求解。,根据最优化原理可以将一个多阶段决策过程转化为,13,第三节 动态规划模型及求解方法,一、动态规划的数学模型,动态规划模型没有统一的模式，建模时要具体问题具体分析。,1.建立动态规划模型的步骤,划分阶段；,正确选择状态变量s,k,；,确定决策变量u,k,及允许决策集合D,k,（s,k,）；,第三节 动态规划模型及求解方法 一、动态规划的,14,确定状态转移方程；,确定阶段指标函数和最优指标函数，建立动态规划基本方程。,2.动态规划的基本方程,动态规划求解的递推关系式称为动态规划的基本方程，即：,f,k,（s,k,）=opt v,k,（s,k,，u,k,）f,k1,（s,k1,）,f,n1,（s,n1,）=0或1 k=n，n-1，1,表示“”或“”。当“”时，边界条件等于0；当“”时，边界条件等于1。,u,k,D,k,确定状态转移方程；uk Dk,15,二、动态规划的求解,逆序解法是求解线性规划问题的一般方法，即由k=n递推至k=1得到问题的最优解。,举例:,二、动态规划的求解,16,
展开阅读全文