1、主要内容主要内容 :5.1多阶段决策过程的最优化多阶段决策过程的最优化 5.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理5.3 动态规划方法的基本步骤动态规划方法的基本步骤 5.4 动态规划应用举例动态规划应用举例第第 五五 章章 动动 态态 规规 划划5.1 多阶段决策过程的最优化多阶段决策过程的最优化 动态规划是解决多阶段最优决策的方法 , 由美国数学家贝尔曼 (R. Bellman) 于 1951年首先提出 ; 1957年贝尔曼发表动态规划方面的第一部专著 “动态规划 ”, 标志着运筹学的一 个新分支的创立。例例 5 .1 求解最短路问题 动态规划将复杂的多阶段决策问题分
2、解为一系列简单的、离散的单阶段决策问题 , 采用顺序求解方法 , 通过解一系列小问题达到求解整个问题目的 ; 动态规划的各个决策阶段不但要考虑本阶段的决策目标 , 还要兼顾整个决策过程的整体目标 , 从而实现整体最优决策 .动态规划的分类动态规划的分类 : 离散确定型 离散随机型 连续确定型 连续随机型动态规划的特点动态规划的特点 : 动态规划没有准确的数学表达式和定义动态规划没有准确的数学表达式和定义精确的算法精确的算法 , 它强调具体问题具体分析它强调具体问题具体分析 , 依赖分析者的经验和技巧。依赖分析者的经验和技巧。 与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互补关系 ,
3、 尤其在处理非线性、离散性问题时有其尤其在处理非线性、离散性问题时有其独到的特点。独到的特点。通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有 “ 无后效性” 的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策 (历史 )无关。具有无后效性的多阶段决策过程的特点是系统过去的历史，只能通过现阶段的状态去影响系统的未来，当前的状态就是后过程发展的初始条件。动态规划的应用动态规划的应用 动态规划在工程技术 , 企业管理 , 军事部门有广泛的应用 ; 可解决资源分配 , 生产调度 , 库存管理 , 路径优化 , 设备更新 , 投资规划 , 排序问题和生产过程的最优控制等问题 ;拾火柴游戏 : 桌子上放 30根火柴 , 每人一次可拾起 1 3根 , 谁拾起最后一根火柴谁输 , 如果你先选择 , 如何保证你能赢得游戏？29 25 21 17 13 9 5 1动态规划与倒推求解动态规划与倒推求解 :
