文档介绍：第三章动态规划
运筹学
Operational Research
整理课件
动态规划（Dynamic Programming）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶的基本思想。
整理课件
最短路径问题
以表示在阶段k的状态变量为、决策变量为时点与间的距离；记为在阶段k由点到终点E的最短路径的长度。本例中要求的是。
在阶段1：可以取中任意一个，对应的有
在阶段2：可以取中任意一个，对应的有
整理课件
最短路径问题
从出发到终点E最短路径为“ ”，决策变量；
从出发到终点E最短路径为“ ”，决策变量；
在阶段3：可以取中任意一个，对应的有
整理课件
最短路径问题
从出发到终点E最短路径为“ ”，决策变量；
从出发到终点E最短路径为“ ”，决策变量；
从出发到终点E最短路径为“ ”，决策变量或；
最后，在阶段4：只可以取S，于是
整理课件
最短路径问题
因此，由起点S到终点E的最短路径为
最短路径长度为21单位长度。
整理课件
最短路径问题
由上述计算过程可知，对有n个阶段的最短路径问题，可以逐段逆向地求出各点到终点的最短路径，且在求解的每一步都利用阶段k和阶段k-1间的递推关系：
此关系被称为求最短路径的动态规划基本方程。求解最短路径问题的过程，本质上是解上述基本方程的过程。
整理课件
最短路径问题
本节学****要点
，了解什么是动态规划，了解动态规划在管理中的几类应用例子

整理课件
贝尔曼最优化原理
整理课件
贝尔曼最优化原理
将求解最短路径问题的思路推广到一般多阶段决策问题时，可以表述成：
贝尔曼最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，今后的诸决策，对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。
这个原理是动态规划的理论基础。
整理课件
贝尔曼最优化原理
应用动态规划方法解决一般多阶段决策问题时，其求解过程如下：
（1）把实际问题适当地划分成k个阶段，阶段变量为；
（2）在每个阶段k，确定状态变量为及此阶段可能的状态集合；
（3）确定决策变量及每个阶段k的允许决策集合；
（4）列出递推关系即动态规划基本方程并计算：
整理课件
贝尔曼最优化原理
【】（石油输送管道铺设优选问题）某石油公司计划从A地到E地铺设一条石油输送管道，为此在A地与E地之间必须建立三个油泵加压站，，其中分别为必须建站的地区，而分别为可供选择的各站点，各点连线上的数字表示相邻站点间铺设输送管道所需费用. 问：如何铺设石油输送管道，能使总费用最少？
整理课件
贝尔曼最优化原理
(a)
(b)
整理课件
贝尔曼最优化原理
解划分成4个阶段：阶段变量依次为4，3，2，1，. 设阶段k的状态变量为。
在阶段1：
在阶段2：可以取中任意一个，对应的有
整理课件
贝尔曼最优化原理
从出发到终点E最短路径为“ ”，决策变量；
从出发到终点E最短路