1、第八章第八章 动态规划动态规划8.1 多阶段决策问题8.2 最优化原理与动态规划的数学模型8.3 离散确定性动态规划模型的求解8.4 离散随机性动态规划模型的求解8.5 一般数学规划模型的动态规划解法1理解 动态规划基本概念、最优化原理和基本方程，逆序法和顺序解法，学习应用动态规划解决多阶段决策问题。重点 :掌握动态规划 模型结构 、 逆序法 算法原理、资源分配、设备更新、生产与存贮 等问题。学习要点：2第一节 多阶段的决策问题3动态规划 （ Dynamic Programming）R. Bellman50年代执教于普林斯顿和斯坦福大学，后进入兰德（ Rand） 研究所。 1957年发表 “D
2、ynamic Programming”一书，标识动态规划的正式诞生。 动态规划的基本概念和定义动态规划的研究对象和引例动态规划是解决复杂系统优化问题的一种方法。是解决 动态系统多阶段决策 过程的基本方法之一。4动态规划： 是解决 多阶段决策 过程 最优化问题的一种方法，无特定的数学模型。可解决 与时间有关的动态问题与时间无关的静态问题5多阶段决策问题n 1） 动态决策 将 时间作为变量 的决策问题称为动态决策。其基本特点是多次决策。n 2） 多阶段 决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态过程可以按照时间进程分为状态 互相联系而又互相区别 的各个阶段，而且在每个阶
3、段都要进行决策，当每一个阶段的决策确定以后，就完全确定了一个过程的活动路线。61 2 3 4 5引例 1 最短路线问题25375632455114633334C1C3D1AB1B3B2D2EC27引例 2 生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？ 引例 3 投资决策问题某公司现有资金 Q万元，在今后 5年内考虑给 A， B， C， D 4个项目投资？引例 4 设备更新问题现企业要决定一台设备未来 8年的更新计划，问应在哪些年更新设备可使总费用最小？ 8动态规划方法的特点n 优 点 ：1） 许 多 问题 用 动态规 划求解比 线 性 规 划、非线 性 规 划更有效，特 别 是离散性 问题 ，解析数学无用武之地，而 动态规 划成 为 得力工具。2） 某些情况下，用 动态规 划 处 理不 仅 能作定性描述分析，且可利用 计 算机 给 出求其数 值解的方法。9动态规划方法的特点缺点：n 1）没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要作用。n 2） “维数障碍 ”：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。10
