动态规划及其在数学模型中的应用教育文档.docx

《动态规划及其在数学模型中的应用教育文档.docx》由会员分享，可在线阅读，更多相关《动态规划及其在数学模型中的应用教育文档.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划及其在数学模型中应用1动态规划起源与开展 动态规划是解决多阶段决策过程最优化一种方法，大约产生于20世纪50年代。1951年，美国数学家理查德贝尔曼根据一类多阶段决策问题特点，把多阶段决策问题表示为一系列单阶段问题，即把一个N-变量问题作为一系列N个问题而逐个加以解决，提出了解决这类问题“最优化原理，并将其应用于很多实际问题研究，从而建立了运筹学一个分支-动态规划。1957年理查德贝尔曼在美国普林斯顿大学发表了第一本正式著作。随后理查德贝尔曼及其他科学工作者发表了一些列动态规划应用著作，包括动态规划在最正确控制论、资源理论、工业工程、经济学、管理科学、变分法和马尔柯夫过程中应用。动态规

2、划开展始终伴随着它广泛应用而不断臻善。 2动态规划优点与局限 动态规划核心思想是贝尔曼提出最优化原理，这个原理导致了分阶段决策方法。分阶段决策方法是建立在整体最优化根底上，在寻求某一阶段决策时，不仅要考虑局部利益，而且应考虑总体最优。 动态规划通过将一个N维变量复杂问题进展分阶段处理，把N维变量问题变成求解N个单变量问题，大大简化求解过程，节省巨大计算量，这是经典求解极值方法所做不到。 动态规划几乎超越了所有现在计算方法，特别是经典最优化方法，它能确定出绝对全局极大或极小，而不是相对局部极值，使得我们不再需要关心伤脑筋局部极大或极小问题。 动态规划另一特点是泛函方程“嵌入特性。动态规划方法求出

3、不仅是对整个过程某一特定状态一个解，而且也是对所有后部子过程所有可能出现状态一族解。 动态规划方法局限性表现有以下几个方面： 第一，到目前为止，动态规划还没有一个统一标准模型可供使用。实际问题不同，其动态规划模型可能各异，虽然理论上说可以把其他数学规划问题化为动态规划模型求解，但是这种转化过程对于复杂数学规划问题将变得十分困难。 第二，构造动态规划模型时，状态变量必须满足“无后效性条件，这是一个相当强条件。因为它不仅依赖于状态转移规律，还与允许决策集合和指标构造有关，不少实际问题在取自然特征作为状态变量时，往往不满足这个条件，减低了动态规划通用性，当然原那么上说，采用适当增多状态变量方法，总能

4、人为地把过程变为无后效，但动态规划还存在下述局限，所以这种作法实际意义不大。 第三，用动态规划方法进展数值求解时主要问题是所谓“维数障碍，这里状态变量与决策变量不是一回事。假设状态变量大于2或3，计算时涉及较大存储量和计算量。状态空间维数越高，即描述状态空间向量分量越多，所遇到计算困难将变得越大。 3动态规划术语 研究系统优化时，遇到系统可以是一个物理系统，也可能是可操作系统，也可以是一个概念系统。但是，使用动态规划来研究系统时，必须将系统现实而具体术语变为数学统一术语。 3.1 阶段 阶段是指系统需要做出决策步骤，即把系统顺序地向前开展划分为假设干个相互联系阶段，使能按阶段次序求解。描述阶段

5、变量称为阶段变量。在多数情况下，阶段变量是离散，用k表示。离散动态规划问题应理解为，阶段过程构造是离散，而不是状态变量构造是离散。阶段变量连续情况也是存在。当阶段变量为时间，且可在任意时间做决策时，阶段变量是连续。阶段变量主要作用是按顺序编出所研究过程划分编号。 3.2 状态 状态表示每个阶段开场面临自然状况或客观条件，它不以人们主观意识为转移，也称为不可控因素。 过程状态通常可以用一个或一组变数描述，称为状态变量。常用k表示第k阶段某一状态。状态变量可以是离散，也可以是连续。但是，在现实世界中，实际上没有连续变量，或者是由于我们所遇到就是离散实体，或者是由于所有物理测量中所固有准确度限制。然

6、而，在处理某些问题时，数学连续性那么是一种有益假设。状态可以是单变量，也可以是向量，它可以用假设干分量在任何阶段上对系统进展描述。状态变量取值集合称为状态集合。 我们要求状态具有下面性质：当前与未来收益或代价，将仅仅取决于当前状态，并不依赖于过去状态和决策历史，即，不依赖于所论过程那些过去状态下所做决策。这个性质称为无后效性。这正是在多阶段决策过程中表现出来动态规划根本理论与特征。 3.3 决策 在每一阶段状态给定后，往往可以作出不同决定，从而确定下一阶段状态，这种决定称为决策。在最优控制中，也称为控制。描述决策变量称为决策变量控制变量。那么，系统状态必须包含在某个给定阶段上确定全部允许决策所

7、需全部信息。在第k阶段用xk (k)表示处于状态k时决策变量，决策变量限制范围称为允许决策集合。用Xk (k)表示第k阶段从k出发决策集合，那么xk (k)Xk (k)。 3.4 策略 由每一阶段决策 组成决策函数序列称为全过程策略，简称策略，用p表示，即 换句话说，策略是在任意阶段做出决策决策规那么集合。 从k阶段开场到终点过程称为原过程后部子过程或称k子过程，其决策函数序列 称为k子过程策略，简称子策略。用表示，即 对于每个实际多阶段决策过程，可供选取策略有一定范围限制，这个范围称为允许策略集合，允许策略集合中到达最优效果策略称为最优策略。 3.5 状态转移 利用动态规划解决优化问题时，所

8、研究是逐阶段决策过程。给定第k阶段状态变量 k值后，如果这一阶段决策变量一经确定，第k+1阶段状态变量k+1也就完全确定，即k+1值随k和x k (k)值变化而变化，可以把这一关系看成 与k+1确定对应关系，用 表示。这是从k阶段到k+1阶段状态转移规律，称为状态转移方程。 是k和x k (k) 确定函数，状态转移是完全确定。这种状态转移完全确定多阶段决策过程称为确定型多阶段决策过程。 3.6 历程 从开场到完毕总阶段数称为历程，如果阶段变量从0变到n，那么历程是n+1，在离散情形中，根据历程将多阶段决策过程分为： 定期多阶段决策过程，在决策之前就历程是确定有限值，进展最优化时确定阶段数。 不定期多阶段决策过程，预先知道历程是有限、确定，但是在得到最优策略之前并不知道它数值。 随机多阶段决策过程。历程是与策略和外部条件有关随机变量，它特点是在方程中没有阶段变量。 无限期多阶段决策过程。历程无限或在实践中历程很大。 3.7 指标函数和最优值函数 用来衡量所实现过程优劣一种数量指标，称为指标函数。在确定型过程中，设过程由0开场，由任一k阶段开场(k=1,2,)过程是原过程后部子过程。这时，指标函数V是定义在原过程和后部子过程上确定数量函数，即对任一k，