k k
边界条件
gk ( sk , uk ))
f k 1 ( sk 1 )
（7-7）
f n1 ( sn1 ) f k ( sk ) opt u U
k k
gk ( sk , uk )) f k 1 ( sk 1 )
（7-8）
它表示第k阶段处于状态 sk 且所做决策为 uk 时 的阶段数量效果。 例如，设备分配问题的阶段指标函数 gk 是指第k阶段（即第k周）的收益。
过程指标函数：
Rk ( sk , uk ) --- 第k子过程的过程指标函数
例如，最短路问题中， Rk表示从第k阶段到终点 的距离。 设备分配问题中，Rk 表示从第k周到最后一周的 总收益。
第k阶段的初始状态
第k阶段的决策值 递推关系式：
f k ( sk ) opt
uk U k
对第k阶段所做的决策
f k 1 ( sk 1 )
gk ( sk , uk ))
第k阶段可供选 择的决策范围 第k+1阶段到第n阶段的最优值
第k阶段到第n阶段的最优值
动态规划基本方程
f n1 ( sn1 ) 0 f k ( sk ) opt u U
uk ( sk )表示：对初始状态为 sk 的第k 个阶段 做出的决策为 uk .
因此，决策变量 uk 是状态变量 sk 的函数． 决策都是在一定的范围内进行的，称为允许 决策集合，记为 Uk ( sk ).
还以最短线路问题为例: 第一阶段可选的方案有 A B1和 A B2 即决策变量 u1 ( A) B1 或 u1 ( A) B2 允许决策集合为 U1 ( A) {B1 ,B2 }
4、策略和允许策略集合 策略就是决策序列． 策略有全过程策略和k 部子策略之分． 全过程策略包含n 各阶段的全部过程,表示为
p1,n {u1 , u2 ,L , un }
k 部子策略是指从第k 阶段到第n 阶段的决策
序列，记为
pk ,n {uk , uk 1 ,L , un }
决策都是在一定的范围内进行的，称为允许 策略集合，记为 P1,n .
pk
C1
6
5
D1
3
E
4
D2
3 1 2 s3 C1 p3 (C1 ) { D1，D2 } R3 (C1 , D1 ) 8
R (C , D )=10
f 3 (C1 ) opt R3 (C1 , p3 ) 8
p3
s3 C2
当 k 1 且 s1 取值唯一时
有些问题的状态转移方程不能用数学式子 表达。
6、 指标函数
指标函数是定义在全过程或各子过程或各 阶段上的数量函数. 用来衡量决策效果.
对于不同的问题，指标函数可以是诸如费 用、成本、利润、时间等等。
例如最短路问题的指标就是距离.
设备分配问题的指标是收益.
阶段指标函数（也称阶段效应）：
gk ( sk , uk ) --- 第k段指标函数
Rk ( sk , uk ) gk ( sk , xk )
i k n
一般来说，过程指标函数和阶段指标函数之 间具有某种运算关系：
Rk gk gk +1 L gn
常见的是如下两种：
Rk gk
i k n
Rk gk
i 1
n
7、最优解
f k ( sk ) opt Rk ( sk , pk ( sk ))
A B2 C2 D1 E
简言之，一个最优策略的子策略总是最优的.
Hale Waihona Puke 根据最优化原理，可以把多阶段决策问题 看成是一个连续递推的过程. 一般采取从后向前推，即逆序递推法.
其关键在于建立递推关系式.这种递推关系 式也称为动态规划的基本方程。 2.动态规划基本方程
动态规划的基本方程包括边界条件和递推 公式两部分。
7.2 动态规划的基本概念和求解思路
7.2.1 动态规划的基本概念
1、阶段和阶段变量 是指一个问题需要做出决策的步数． 用阶段变量 k 来表示． 最短线路问题: 四阶段决策问题
A BC D E
设备分配问题： 四阶段决策问题
第1周 第2周 第3周 第4周
２、状态、状态变量和可能状态集 状态表示每阶段开始所处的自然状况或客观 条件．用状态变量 sk 来表示． 如最短线路问题:
5、状态转移方程 对于无后效性的多阶段决策过程： 第k 阶段初的状态为 sk u 对第k 阶段所做的决策为 k
第k +1阶段初的状态 sk 1 Tk ( sk , uk ( sk ))
状态转移方程
例如，设备分配问题的状态转移方程为
sk 1 9 1 sk xk ( k 2, 3, 4) 10 10
u1 ~ un
sk 1 Tk ( sk , uk ) sk Sk uk U k k 1, 2, L , n
（7-5）
7.2.2
动态规划的最优化原理和基本方程
1. 最优化原理 动态规划的最优化原理: 一个过程的最优策略具有这样的性质：对 于最优策略中的任意状态而言，无论其过 去的状态和决策如何，下余的诸决策必构 成一个最优子策略.
， 则 s1 =A. 第一阶段的状态为 A 第二阶段的状态有 B1 , B2 , 则 s2 B1 或 s2 B2 .
每阶段的状态有一个可供选择的范围，称为 可能状态集，用大写的Sk 表示．
S1 { A}
S2 { B1 , B2 }
小 sk 是大 Sk 的一个元素．
３、决策、决策变量和允许策略集合 每个阶段都有可供选择的多种方案，选择方 案的过程称为决策． 用决策变量 uk ( sk ) 来表示．
f1 ( s1 ) opt
p1
R1 ( s1 , p1 ( s1 ))
称为整个问题的最优值。 最优值及其对应的最优策略统称为问题 的最优解。
8、多阶段决策问题的数学模型
综上所述，具有无后效性的多阶段决策 问题的数学模型如下：
f opt R R( s1 , u1 , s2 , u2 , L , sn , un )