[经济学]第五章 动态规划jsp.ppt

思考： 五、二维动态规划 五、二维动态规划 五、二维动态规划 n=1时： n1时： 六、高维动态规划 “维数灾”——对于高维动态规划问题，由于离散型动态规划用递推方程进行择优计算时，计算机高速存贮中至少需存放相邻二个阶段的各状态点的优化结果，而一个阶段的离散状态点数为： 式中：m为问题的维数（状态变量数或转移方程数） 为m维空间中的一个坐标（即一个状态变量），在任一阶段i的离散状态点数； 为任一阶段n的状态点数。 六、高维动态规划 当维数m稍大时，往往超过现有计算机的存贮能力，致使无法求解，或因计算时间太长而费用昂贵。 “维数灾”主要是由离散化引起的，现有的改进方法按照其解决问题的途径主要分为以下几类： （1）降低维数m：如拉格朗日乘子法，动态规划逐次渐进法，聚合法等。 （2）减少离散状态点数　：如状态增量动态规划法，离散微分动态规划法，双状态动态规划法等。 （3）不进行离散化：如微分动态规划法，渐进优化法等。 第五章 动态规划(Dynamic Programming)及其应用 第一节　概述 动态规划（Dynamic Programming，简称DP）是解决多阶段决策过程最优化的一种有效的数学方法。它是美国学者Richard.bellman 在1951年提出的，1957年他的专著《动态规划》的问世标志着运筹学的一个重要分支——动态规划的诞生。 多阶段决策问题是指这样一类问题，该问题的决策过程是一种在多个相互联系的阶段分别作出决策以形成序列决策的过程，而这些决策均是根据总体最优化这一共同的目标而采取的。 基本思路：多阶段决策——单阶段决策 第一节　概述 1、动态系统——当一个系统中含有时间变量或与时间有关的变量，且其现时的状态与过去和未来的状态有关联的，称为~。 2、动态规划法——在时间过程中，依次采用一系列最适当的决策，来求得整个动态过程最优化问题的解，这种动态过程寻优的数学方法称为~。 从概念看，实际上动态规划要做的是把解n个变量问题转化为解n个单变量问题，它用于分析系统的多阶段决策过程，以求得整个系统的最优决策方案。 动态规划法的适用 （1）“随时间变化的动态过程”（时间动态规划），例如：①水资源系统中的河流流量的季节变化问题与水库调度问题；②工程施工和企业运行系统中的施工与生产计划的最优调度安排问题；③公路、铁路运输系统中车辆运行最优调度的问题。 动态规划法的适用 （2）只要根据时间、空间或性质的特点，可把过程分为若干阶段，在“静态”模型中人为引入“时间”因素，把它当作多阶段决策过程求解，可称为“空间动态规划” 动态规划法的优点 （1）适用性强。寻优的思路与函数极值的微分法、单纯形法有明显的区别，它不要求所规划的问题是连续的、可微的，也不要求它们是线性的或凸性的，因此，对于众多的非线性规划问题，不连续不可导，古典的优化技术不能解的问题，可用动态规划法求解。 （2）应用动态规划时可以把一个n维最优化问题转化为n个一维最优化问题，一个一个求解，是古典优化方法做不到的。 （3）它能确定出全局最优解。 动态规划法的缺点 （1）最优化原理得出递推方程后，没有一个象单纯形法那样的统一解法，必须按照问题的性质结合其它数学技巧来求解。 （2）“维数灾”，计算机贮存容量及计算速度的限制。 第二节　动态规划的基本原理和方法 基本原理： 贝尔曼提出的最优性原理：“一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，对以第一个决策所形成的状态作为初始状态的过程而言，余下的诸决策必须构成最优策略”。根据最优性原理，把问题表述为一种数学形式——递推方程，可逐次递推求得最优解。 第二节　动态规划的基本原理和方法 方法： 把一个复杂的系统分析问题分解形成一个多阶段的决策过程，并按一定的顺序或时序，从第一阶段开始，逐段求出每段的最优决策，并经历各阶段，从而求得整个系统的最优策略。 一、基本概念 例5-1：漫游数学家问题 　一个智慧比钱多的应用数学家渴望进行一次旅行。假定他住在城市１，而希望到城市10，这是一次长途旅行，而且他还必须进行三次中间停留，对他旅程中三个中间停留站的每一站，都有两到三个不同的城市供他选择。选择不同的中间站，旅行的花费是不同的。由于他希望这次旅行付出的总费用最小，他将确定哪些城市作为他的中间站？ 一、基本概念 阶段：把所给定的问题发展变化的全过程恰当的离散化，划分为若干相互联系的序列单元，称为~，“级”或“步”。一个问题需要作出决策的步数。 阶段变量：阶段的序列编号n=1,2,…,N表示，称为阶段变量。 （1）若问题的变化过程本身是离散的，如例5-1，可按离散的空间位置划分若干位置阶段，n=1,2,3,4。 （2）若问题的变化过程是按时间连续的，阶段可用t表示，把连续的阶段变量按相等的时间增量离散化