一、多阶段决策问题
根据问题本身的特点，可以将其求解的全过 程划分为若干个相互联系的阶段（即将问题 划分为许多个相互联系的子问题），在它的 每一阶段都需要做出决策，并且在一个阶段 的决策确定以后再转移到下一阶段。往往前 一个阶段的决策要影响到后一个阶段的决策， 从而影响整个过程。这样的决策过程称作多 阶段决策过程。
描述决策变化的量称为决策变量。
常用uk uk sk 表示 k 阶段状策变量的取值的容许范围。
决策变量uk sk 的允许决策集用Uk sk 表示， uk sk Uk sk ，
允许决策集合实际是决策的约束条件。
三、动态规划求解的多阶段决策问题的特点
（2）设备更新问题 企业在使用设备时都要考虑设备的更新问题。现某企业要决定 一台设备未来 8 年的更新计划，已预测了第 j 年购买设备的价
格为 K j ，设Gj 为设备经过 j 年后的残值，C j 为设备连续使用
j 1年后在第 j 年的维修费 j 1, 2, ,8，问应在哪些年更
新设备可使总费用最小。
（4）资源分配问题 某工业部门或公司，拟对其所属企业进行稀缺 资源分配，为此需要制订出收益最大的资源分 配方案。
（5）运输网络问题
图5-11 运输网络图示
多阶段决策过程最优化的目标： 要达到整个活动过程的总体效果最优。
v1
第二节 动态规划的基本概念和基本 原理
一、动态规划的基本概念 （1）阶段；（2）状态；（3）决策和策略； （4）状态转移；（5）指标函数
二、多阶段决策问题举例
（1）生产与存贮过程。
某工厂每月需供应市场一定数量的产品，并 将所余产品存入仓库。一般某月适当增加产 品可降低生产成本，但超产部分存入仓库会 增加库存费用。要求确定一个逐月的生产计 划，在满足需求条件下，使一年的生产与存 贮费用之和最小。
可以把每个月作为一个阶段，全年分为12 个阶段逐次决策。
一个 8 阶段决策问题，每年年初要作出决策， 是继续使用旧设备，还是购买新设备
上述问题的发展过程都与时间因素有关，因 此在这类多阶段决策问题中，阶段的划分常取时 间区段来表示，并且各个阶段上的决策往往也与 时间有关，这就使它具有了“动态”的含义，所 以把处理这类动态问题的方法称为动态规划方法。
但在实际中，一些不含时间的一类“静态” 决策问题，其本质是一次决策问题，是非动态决 策问题，但可以人为地引入阶段的概念，当作阶 段决策问题，应用动态规划方法加以解决。
第五章 动态规划
动态规划是解决多阶段决策过程最优化 问题的一种方法。 根据决策变量时间上的变化—连续型,离散型 根据决策过程性质—确定型,随机型 根据决策的相互关系—动态型，静态型 此外还有阶段的个数是有限的与无限的， 确定与不确定等。
本章研究：动态与静态确定型的决策过程
第一节 多阶段决策过程的最优化
可能状态集—状态变量的取值范围，
即状态变量 sk 的取值集合，用 Sk 表示
可能状态集是关于状态的约束条件
可能状态集可以是一离散取值的集合， 也可以为一连续的取值区间。
3.决策、决策变量和允许决策集合 决策：就是指当过程处于某一阶段的某个状态时，就可以做出不同 的决定，从而确定下一阶段的状态，这种决定称为决策
构成的决策序列，简称策略，表示为 p1 u1,u2 , ,un 。
k 部子策略是指从 k 阶段到第 n 阶段，依次进行的阶段决策构成的决策
序列，表示为 pk uk ,uk1, ,un 。
在实际问题中，由于在各个阶段可供选择的决策有很多， 因此，它们的不同组合就构成了许多可供选择的决策序列
描述阶段的变量叫做阶段变量，一般以k表示 阶段变量。
2.状态、状态变量和可能状态集 （1）状态、状态变量。
状态—各阶段开始时的客观条件 状态变量—描述状态变化的量，
常用 sk 表示第 k 阶段的状态变量
用以描述事物在某特定的时间与空间域中所处位置 及运动特征的量
图5-11 运输网络图示
（2）可能状态集
(1)阶段指标函数（也称阶段效应） 第 k 段指标函数是指第 k 段，从 sk 状态且所作决策为 uk(sk)时的效益，用 gk(sk,uk)表示简记为 gk 。
(2)过程指标函数（也称目标函数）
程用效R果k(优sk劣,u的k)数表量示指k部标子过程的指标函数，指k部子过 Rp应kk((表sskk示,)u有为k)关:不，仅因跟此当它前是状s态k和spk有k(s关k)，的还函跟数该，子严过格程说策来略，
例 最短路线问题
如图 5-11 说示，给定一个线路网络图，要从 v1向 v10
铺设一条输油管道，各点间连线上的数字表示距离，问应选 择什么路线，可使总距离最短？
图5-11 运输网络图示
1.阶段和阶段变量
阶段—把所给问题按时间或空间先后顺序划分 为若干个相互联系又有区别的子问题
一个阶段就是需要作出一个决策的子问题。
Rk (sk , pk (sk ))
实际应用中往往表示为Rk(sk,uk)或Rk(sk) 过g可k(以程sk表指,u示标k)为累函：积数形Rk(成sk的) ，是对由于各k阶部段子的过阶程段的指指标标函函数数
Rk,n Rk,n (sk ,uk , sk1,uk1, , sn ,un )
(5-2)
gk (s k ,uk ) gk1(sk1,uk1) gn (sn ,un )
（策略）。由它们组成的集合，称为允许策略集合，记作 Pk
从允许策略集合，找出具有最优效果的策略称为最优策略。
5.状态转移方程：
sk1 Tk (sk ,uk (sk )) (5-1)
6. 指标函数
指标函数—用来衡量策略或子策略或决策的效 果优劣的某种数量指标 它分为阶段指标函数和过程指标函数两种。
1.无后效性又称马尔柯夫性，是指系统从某个阶 段往后的发展，仅由本阶段所处的状态及其往 后的决策所决定，与系统以前经历的状态和决 策无关。 2. 适合于用动态规划方法求解的只是这类“无 后效性”的多阶段决策过程。
4.策略和允许策略集合
全过程策略是指具有 n 个阶段的全过程，由依次进行的 n 个阶段决策