《运筹学》课程教学课件（PPT讲稿）动态规划

第八章 动态规划 8.1多阶段决策问题 8.2最优化原理与动态规划的数学模型 8.3离散确定性动态规划模型的求解 8.4离散随机性动态规划模型的求解 8.5一般数学规划模型的动态规划解法 1

第八章 动态规划 8.1 多阶段决策问题 8.2 最优化原理与动态规划的数学模型 8.3 离散确定性动态规划模型的求解 8.4 离散随机性动态规划模型的求解 8.5 一般数学规划模型的动态规划解法 1

学习要点： 理解动态规划基本概念、最优化原理 和基本方程，逆序法和顺序解法，学习应 用动态规划解决多阶段决策问题。 重点：掌握动态规划模型结构、逆序 法算法原理、资源分配、设备更新、生产 与存贮等问题

理解动态规划基本概念、最优化原理 和基本方程，逆序法和顺序解法，学习应 用动态规划解决多阶段决策问题。 重点 :掌握动态规划模型结构、逆序 法算法原理、资源分配、设备更新、生产 与存贮等问题。 学习要点： 2

第一节多阶段的决策问题

第一节 多阶段的决策问题 3

动态规划 (Dynamic Programming) R.Bellman:50年代执教于普林斯顿和斯坦福大学， 后进入兰德（Rand)研究所。1957年发表“Dynamic Programming”一书，标识动态规划的正式诞生。 动态规划是解决复杂系统优化问题的一种方法。 是解决动态系统多阶段决策过程的基本方法之一。 动态规划的基本概念和定义 动态规划的研究对象和引例

动态规划（Dynamic Programming） R. Bellman50年代执教于普林斯顿和斯坦福大学， 后进入兰德（Rand）研究所。1957年发表“Dynamic Programming”一书，标识动态规划的正式诞生。 动态规划的基本概念和定义 动态规划的研究对象和引例 动态规划是解决复杂系统优化问题的一种方法。 是解决动态系统多阶段决策过程的基本方法之一。 4

动态规划：是解决多阶段决策过程最优 化问题的一种方法，无特定的数学模型。 可解决 与时间有关的动态问题 与时间无关的静态问题

动态规划：是解决多阶段决策过程最优 化问题的一种方法，无特定的数学模型。 可解决 与时间有关的动态问题 与时间无关的静态问题 5

多阶段决策问题 ·1)动态决策一将时间作为变量的决策问题称 为动态决策。其基本特点是多次决策。 ·2)多阶段决策问题是一类特殊形式的动态决 策问题。是指这样一类活动过程：系统的动态 过程可以按照时间进程分为状态互相联系而又 互相区别的各个阶段，而且在每个阶段都要进 行决策，当每一个阶段的决策确定以后，就完 全确定了一个过程的活动路线

多阶段决策问题 ◼ 1）动态决策—将时间作为变量的决策问题称 为动态决策。其基本特点是多次决策。 ◼ 2）多阶段决策问题是一类特殊形式的动态决 策问题。是指这样一类活动过程：系统的动态 过程可以按照时间进程分为状态互相联系而又 互相区别的各个阶段，而且在每个阶段都要进 行决策，当每一个阶段的决策确定以后，就完 全确定了一个过程的活动路线。 6

引例1最短路线问题 B 5 6 6 2 4 3 3 5 3 2 3 4 5

1 2 3 4 5 引例1 最短路线问题 2 5 3 7 5 6 3 2 4 5 5 1 1 4 6 3 3 3 3 4 C1 C3 D1 A B1 B3 B2 D2 C2 E 7

引例2生产与存贮问题 要求确定一个逐月的生产计划，在满足需求条件下， 使一年的生产与存贮费用之和最小？ 引例3投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A,B, C,D4个项目投资？ 引例4设备更新问题 现企业要决定一台设备未来8年的更新计划，问应在 哪些年更新设备可使总费用最小？

引例2 生产与存贮问题 要求确定一个逐月的生产计划，在满足需求条件下， 使一年的生产与存贮费用之和最小？ 引例3 投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A，B， C，D 4个项目投资？ 引例4 设备更新问题 现企业要决定一台设备未来8年的更新计划，问应在 哪些年更新设备可使总费用最小？ 8

动态规划方法的特点 ■©优点： 1)许多问题用动态规划求解比线性规划、非线 性规划更有效，特别是离散性问题，解析数学 无用武之地，而动态规划成为得力工具。 2)某些情况下，用动态规划处理不仅能作定性 描述分析，且可利用计算机给出求其数值解的 方法

动态规划方法的特点 ◼ ☻优点： 1）许多问题用动态规划求解比线性规划、非线 性规划更有效，特别是离散性问题，解析数学 无用武之地，而动态规划成为得力工具。 2）某些情况下，用动态规划处理不仅能作定性 描述分析，且可利用计算机给出求其数值解的 方法。 9

动态规划方法的特点 缺点： ■1)没有统一的处理方法，求解时要根据问题 的性质，结合多种数学技巧。因此， 实践经验 及创造性思维将起重要作用。 2)“维数障碍”：当变量个数太多时，由于 计算机内存和速度的限制导致问题无法解决。 有些问题由于涉及的函数没有理想的性质使问 题只能用动态规划描述，而不能用动态规划方 法求解。 10

动态规划方法的特点 缺点： ◼ 1）没有统一的处理方法，求解时要根据问题 的性质，结合多种数学技巧。因此，实践经验 及创造性思维将起重要作用。 ◼ 2）“维数障碍”：当变量个数太多时，由于 计算机内存和速度的限制导致问题无法解决。 有些问题由于涉及的函数没有理想的性质使问 题只能用动态规划描述，而不能用动态规划方 法求解。 10