其中离散确定型是最基本的，本章主要针对这种 类型的问题，介绍动态规划的基本思想、原理和 方法，这些对其它类型的问题也适用。然后通过 几个典型的动态规划模型来介绍它的应用。
二、多阶段决策过程问题实例
例1 最短路线问题5源自B16 3A
4 B2 4 6
2
5
B3 6
C1
1 2
2
C2 2
3 C3 3
D1 2
D2 3
例2 投资决策问题
某公司现有资金Q万元．在今后5年内考虑 给A,B,C,D 4个项目投资，这些项目投资的回收 期限、回报率均不相同，问该公司应如何确定 这些项目每年的投资额，使到第5年末拥有资金 的本利总额最大。
这是一个5阶段决策问题。
例3 设备更新问题
企业在使用设备时都要考虑设备的更新问题， 因为设备越陈旧所需的维修费用越多，但购买新 设备则要一次性支出较大的费用；现某企业要决 定一台设备未来8年的更新计划．已预测了第 j 年 购买设备的价格为Kj，设Gj为设备经过 j 年后的 残值，Cj为设备连续使用 j一1年后在第 j 年的维 修费(j＝1,2,…,8)，问应在哪些年更新设备可使总 费用最小。
构的多阶段过程就称为多阶段决策过程。这种问题
就称为多阶段决策问题。
决策
决策
状态
状态
状态
1
2
决策
状态
状态
n
决策
决策
状态
状态
状态
1
2
决策
状态
状态
n
在多阶段决策问题中，各个阶段采取的决 策，一般来说是与时间有关的。决策依赖于当 前的状态，又随即引起状态的转移，一个决策 序列就是在变化的状态中产生出来的，故有 “动态”的含义。因此，把处理它的方法称为 动态规划方法。
2
5
B3 6
C1
1 2
2
C2 2
3
C3
3
D1 2
D2 3
E
4
D3
阶段1
A
阶段2
阶段3
阶段4
B
C
D
E
在阶段2，从B3点出发，只有C1、C3两种可选 择的点，
如选C1,则C1就是阶段2在B3点的决策结果； C1点既是阶段2铺设管道的终点，又是阶段3 铺设管道的起点；
5
B1
6 3
A
4 B2 4 6
2
5
B3 6
8.1 多阶段决策过程及实例
一、多阶段决策问题
多阶段决策问题，是指一类活动过程，它可分
为若干个互相联系的阶段，在每一个阶段都需要作
出决策，从而使整个过程达到最好的活动效果。
因此，各个阶段决策的选取不是任意确定的，
它依赖于当前面临的状态，又影响以后的发展。
每个阶段的决策确定以后，过程也就随之确定。
这种把一个问题可看作是一个前后关联具有链状结
同时，他提出了解决这类问题的“最优性原 理”,并成功地解决了生产管理、工程技术等方面 的许多实际问题,从而建立了运筹学的一个新分支, 即动态规划.
动态规划具有广泛应用，是现代企业管理 中一种重要的决策方法。应用动态规划可以解 决诸如最优路径问题、资源分配问题、生产调 度问题、库存问题、装载问题、排序问题、设 备更新问题以及最优控制问题等。
E
4
D3
从A点到E点要铺设一条天然气管道，中间必须经过 三个中间站，
第一站可在B1、B2、B3中选择， 第二站可在C1、C2、C3中选择， 第三站可在D1、D2、D3中选择， 要求选择一条由A 到E的铺管路线，使总长度最短。
其中两点连线上的数字表示两点间管线的长度。
5
B1
6 3
A
4 B2 4 6
2
1 2
2
C2 2
3 C3 3
D1 2
D2 3
E
4
D3
阶段1
A
阶段2
阶段3
阶段4
B
C
D
E
在阶段1中，A点是起点，B点是终点，其中
B有B1、B2、B3三个可选择的点。 如选B3点，则B3就是阶段1在A点的决策结果； B3点既是阶段1铺设管道的终点，又是阶段2
铺设管道的起点。
5
B1
6 3
A
4 B2 4 6
C1
1 2
2
C2 2
3
C3
3
D1 2
D2 3
E
4
D3
阶段1
A
阶段2
阶段3
阶段4
B
C
D
E
同样的理由，可以递推得其余阶段的铺设路线，
如阶段3在C1点的决策是D1，阶段4在D1点的决 策只有E点；由于到E点是整个铺设管道的终点， 至此，决策过程完成.
铺设一条A点到E点的管道是由四个阶段的管道组 成的,如A---B3---C1---D1---E，它也称为一个策略.
许多问题用动态规划的方法去处理，常比 线性规划或非线性规划方法更有效。特别对于 离散性的问题。
特别注意：动态规划是求解某类问题的一种 方法，是考察问题的一种途径，而不是一种算法 （如线性规划是一种算法）。
因而，动态规划没有标准的数学表达式和明 确定义的一组规则，而必须对具体问题进行具体 分析处理．
一些与时间没有关系的静态规划（如线性 规划，非线性规划）问题，只要人为地引进 “时间”因素，也可把它视为多阶段决策问题， 用动态规划方法去处理。
当建立问题的数学模型后，如果时间参数是 离散的，则它就是数学规划问题；如果时间参数 是连续的，则属于最优控制问题。
动态规划模型的分类：①离散确定型；②离散随 机型，③连续确定型；④连续随机型。
5
B1
6 3
A
4 B2 4 6
2
5
B3 6
C1
1 2
2
C2 2
3
C3
3
D1 2
D2 3
E
4
D3
可以看出，各个阶段的决策不同，铺设的管 道也不同，并且当某个阶段的 始点给定后，它直 接影响着后面各阶段的行进路线和管道的长短， 而后面各阶段的路线 的选取不受这点以前各阶段 路线的影响。
因此，最短路线问题可简化为四个阶段决策 问题，使由这四个阶段决策组成决策序列，也称 为策略，所决定的一条路线的总长度最短。
动态规划
8.1 多阶段决策过程及实例 8.2 动态规划的基本概念和
基本方程 8.3 动态规划的最优性定理 8.4 动态规划与静态规划关系
综述
动态规划是运筹学的一个分支，是解决多 阶段决策过程最优化问题的一种数学方法。
该方法是由美国数学家贝尔曼(R.Bellman)等 人在本世纪50年代初提出的。
他们针对多阶段决策问题的特点，把多阶段 决策问题变换为一系列互相联系单阶段问题，然 后逐个加以解决。
这是一个8阶段决策问题，每年年初要作出 决策，是继续使用旧设备，还是购买新设备.
5
B3 6
C1
1 2
2
C2 2
3
C3
3
D1 2
D2 3
E
4
D3
从A点到E点铺设管道，可以按其地理特点自然 地分成四个阶段：（如下图所示） 从A到B是第一阶段，从B到C是第二阶段， 从C到D是第三阶段，从D到E是第四阶段，
阶段1
A
阶段2
阶段3
阶段4
B
C
D
E
5
B1
6 3
A
4 B2 4 6
2
5
B3 6
C1