第四章 动 态 规 划
4-1 引言及内容框架
本节要点
? 动态规划的研究对象和特点
? 静态决策问题的动态处理
? 动态规划部分内容框架
一、动态规划的研究对象
─ 多阶段决策问题
1、多阶段决策问题
1) 动态决策 ──将时间作为变量的决策问题称
为动态决策, 其基本特点是多次决策 。
2) 多阶段决策问题是一类特殊形式的动态决策
问题。是指这样一类活动过程：系统的动态
过程可以按照时间进程分为状态相互联系而
又相互区别的各个阶段，而且在每个阶段都
要进行决策，当每一阶段的决策确定以后，
就完全确定了一个过程的活动路线。
多阶段决策问题的典型例子：
?企业在生产过程中, 由于需求是随着时间变
化的因素, 因此企业为了获得全年最佳经济效
益, 就要在整个生产过程中逐月或逐季的根据
库存和需求决定生产计划 。
?某种机器, 可以在高, 低两种负荷下生产 。
高负荷下生产的产量多, 但每生产一个阶段后
机器的完好率低；低负荷下生产时的情况则相
反 。 现在需要安排该种机器在多个阶段内的生
产, 问应该如何决定各阶段中机器的使用, 使
整个计划期内的总产量最大 。
?某台设备，例如汽车，刚买来时故障少，耗
油低，出车时间长，处理价值和经济效益高。
随着使用时间的增加则变为故障多，耗油高，
维修费用增加，经济效益差。使用时间愈长，
处理价值也愈低。另外，每次更新都要付出
更新费用。因此，应当如何决定设备的使用
年限，使总的效益最佳。
?化工生产过程包含一系列的过程设备，如
反应器、蒸馏塔、吸收器等等，前一设备的
输出是后一设备的输入。因此，应该如何控
制生产过程中各个设备的输出和输入，使总
产量最大。
?发射一枚火箭去击中运动中的目标。由于
目标的行动是不断改变的，因此应如何根据
目标运动情况，不断调整火箭飞行的方向与
速度，使之最快地命中目标，等等。
2.什么是动态规划？
DP是运筹学 OR的一个分支, 是解决多阶
段决策过程最优化的一种方法或是一种分析多
阶段决策过程的数学方法, 这种方法可根据人
们所采取的措施, 一步步地控制过程的发展,
以实现预定的要求 。
这一运筹学分支最初是由美国数学家
Bellman等人根据一类多阶段决策问题的特性,
提出了解决这类问题的最优化原理, 并研究了
许多实际问题而建立起来的 。
3.动态规划方法的特点
? 优点,
① 许多问题用动态规划研究求解比线性规
划, 非线性规划更有效, 特别是离散性问题,
解析数学无用武之地, 而动态规划成为得力
工具；
② 某些情况下, 用动态规划处理不仅能作
定性描述分析, 且可利用计算机给出求其数
值解的方法 。
?缺点：
①没有统一的处理方法，求解时要根据问
题的性质，结合多种数学技巧。因此，实践
经验及创造性思维将起重要的引导作用。
②,维数障碍”：当变量个数太多时，由
于计算机内存和速度的限制导致问题无法解
决。有些问题由于涉及的函数没有理想的性
质使问题只能用动态规划描述，而不能用动
态规划方法求解。
二、静态决策问题的动态处理
不包含时间因素的决策问题称为静态决策
问题，是一次性决策（如线性规划）。但若
能恰当地人为引入“时段”概念，就可以把
问题转化成一个多阶段决策问题，这样就能
用动态规划去处理了。
这样的例子是大量的（如最短路线问题，
资源分配问题等等）。
三、动态规划部分内容框架
如何建模？ 四个条件
一个方程
研究对象及特点 DP 模型
？
优 弱
点 点
？？
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
之乘积函数的形式是阶段效应可靠性问题：注意目标
许决策集的特点设备更新问题：注意允
二维背包
一维背包
背包问题
量允许取值范围解，注意状态与决策变生产库存问题：列表求
技巧性与非线性函数求极值多段分配：注意运用线
多元分配：列表求解
资源分配问题
策略迭代法
函数迭代法
一般网络
二次标号法
化为定步数问题
无回路有向网络
不定步数问题
标号法
表格法
分步计算法
定步数问题
工程路线问题
应用
求出最优目标函数值
态序列）求出最优路线（最优状
策序列）求出最优策略（最优决
求解要求
最优化原理
函数
论
集、策略决策念
基本方程
B e l l m a n
基本理论
阶段效应和目标函数
状态转移方程
决策与决策变量、允许
状态与状态变量
阶段与阶段变量
基本概念
4-1 引言及内容框架
本节要点
? 动态规划的研究对象和特点
? 静态决策问题的动态处理
? 动态规划部分内容框架
一、动态规划的研究对象
─ 多阶段决策问题
1、多阶段决策问题
1) 动态决策 ──将时间作为变量的决策问题称
为动态决策, 其基本特点是多次决策 。
2) 多阶段决策问题是一类特殊形式的动态决策
问题。是指这样一类活动过程：系统的动态
过程可以按照时间进程分为状态相互联系而
又相互区别的各个阶段，而且在每个阶段都
要进行决策，当每一阶段的决策确定以后，
就完全确定了一个过程的活动路线。
多阶段决策问题的典型例子：
?企业在生产过程中, 由于需求是随着时间变
化的因素, 因此企业为了获得全年最佳经济效
益, 就要在整个生产过程中逐月或逐季的根据
库存和需求决定生产计划 。
?某种机器, 可以在高, 低两种负荷下生产 。
高负荷下生产的产量多, 但每生产一个阶段后
机器的完好率低；低负荷下生产时的情况则相
反 。 现在需要安排该种机器在多个阶段内的生
产, 问应该如何决定各阶段中机器的使用, 使
整个计划期内的总产量最大 。
?某台设备，例如汽车，刚买来时故障少，耗
油低，出车时间长，处理价值和经济效益高。
随着使用时间的增加则变为故障多，耗油高，
维修费用增加，经济效益差。使用时间愈长，
处理价值也愈低。另外，每次更新都要付出
更新费用。因此，应当如何决定设备的使用
年限，使总的效益最佳。
?化工生产过程包含一系列的过程设备，如
反应器、蒸馏塔、吸收器等等，前一设备的
输出是后一设备的输入。因此，应该如何控
制生产过程中各个设备的输出和输入，使总
产量最大。
?发射一枚火箭去击中运动中的目标。由于
目标的行动是不断改变的，因此应如何根据
目标运动情况，不断调整火箭飞行的方向与
速度，使之最快地命中目标，等等。
2.什么是动态规划？
DP是运筹学 OR的一个分支, 是解决多阶
段决策过程最优化的一种方法或是一种分析多
阶段决策过程的数学方法, 这种方法可根据人
们所采取的措施, 一步步地控制过程的发展,
以实现预定的要求 。
这一运筹学分支最初是由美国数学家
Bellman等人根据一类多阶段决策问题的特性,
提出了解决这类问题的最优化原理, 并研究了
许多实际问题而建立起来的 。
3.动态规划方法的特点
? 优点,
① 许多问题用动态规划研究求解比线性规
划, 非线性规划更有效, 特别是离散性问题,
解析数学无用武之地, 而动态规划成为得力
工具；
② 某些情况下, 用动态规划处理不仅能作
定性描述分析, 且可利用计算机给出求其数
值解的方法 。
?缺点：
①没有统一的处理方法，求解时要根据问
题的性质，结合多种数学技巧。因此，实践
经验及创造性思维将起重要的引导作用。
②,维数障碍”：当变量个数太多时，由
于计算机内存和速度的限制导致问题无法解
决。有些问题由于涉及的函数没有理想的性
质使问题只能用动态规划描述，而不能用动
态规划方法求解。
二、静态决策问题的动态处理
不包含时间因素的决策问题称为静态决策
问题，是一次性决策（如线性规划）。但若
能恰当地人为引入“时段”概念，就可以把
问题转化成一个多阶段决策问题，这样就能
用动态规划去处理了。
这样的例子是大量的（如最短路线问题，
资源分配问题等等）。
三、动态规划部分内容框架
如何建模？ 四个条件
一个方程
研究对象及特点 DP 模型
？
优 弱
点 点
？？
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
之乘积函数的形式是阶段效应可靠性问题：注意目标
许决策集的特点设备更新问题：注意允
二维背包
一维背包
背包问题
量允许取值范围解，注意状态与决策变生产库存问题：列表求
技巧性与非线性函数求极值多段分配：注意运用线
多元分配：列表求解
资源分配问题
策略迭代法
函数迭代法
一般网络
二次标号法
化为定步数问题
无回路有向网络
不定步数问题
标号法
表格法
分步计算法
定步数问题
工程路线问题
应用
求出最优目标函数值
态序列）求出最优路线（最优状
策序列）求出最优策略（最优决
求解要求
最优化原理
函数
论
集、策略决策念
基本方程
B e l l m a n
基本理论
阶段效应和目标函数
状态转移方程
决策与决策变量、允许
状态与状态变量
阶段与阶段变量
基本概念
