则 最优化原理 ：作为整个过程的最优策略具有这样
的性质，无论过去的状态和决策如何，对先前决 策
2.动态规划的数学模型(逆序法时)
(8.3a) (8.3b)
或
(8.3c) (8.3d)
(8.3b)和(8.3d)称为边界条件。
五、动态规划方法的基本步骤 1. 阶段的划分 2.正确地定义状态变量sk
A1
2 Q 4 3 7 4
B1
4 B2
1 C1 3 T C2 4
6 4 A2 2 4 4 2 A3 5
6 3
3 B3
3
4.策略和子策略(Policy) （1）全过程策略指具有n个阶段全部过程，简 称策略。表示为 {x1(s1),x2(s1),…,xn(sn)}。
k后部子过程策略,表示为pk(xk)
二、动态规划解题 标号法：
11,B1 ,B2
4,C1 7 4
A1
11,A3 Q 2 4 3
B1
4 7,C2 B2
1
3,T C1 3 0， T T 4,T C2
8,B1 6 4 A2 2 4 8,B1 4 2 A3 5
阶段1 阶段2
6 3
6,C1 3 B3 3
阶段3
4
阶段4
最短路径：Q→ A3→ B1→ C1→T
◆动态规划求解的问题的过程指标函数(指 标函数)，必须具有关于阶段指标的可分离 形式(和、积或其他形式) ：
表示某种运算，可为加、减、乘、除、开方 等。
◆常见有:
和
7.最优指标函数：fk(sk)
相应的子策略称为 sk状态下的最优子策略， 记为pk*(sk) ；而构成该子策略的各段决策称 为该过程上的最优决策，记为
阶段数k的编号法有两种： (1)顺序编号；(2)逆序编号法。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T 6 4 A2 2 4 4 2 A3 5
4
3
2.状态(state)、状态变量和可能状态集 (1)状态与状态变量。表示每个阶段开始所 处的自然状况或客观条件。
3.决策(decision)、决策变量和允许决策集合 (1)决策。表示当过程处于某一阶段的某个状 态，可以作出不同的决定（选择），从而确 定下一阶段的状态。
A1 2 Q 4 3 7 4 B1 4 B2 1
6 4 A2 2 4 4 2 A3 5
C1 3
T C2 4
6
3 3
B3
3
(2)决策变量:xk=xk(sk) 决策ห้องสมุดไป่ตู้量 xk(sk) 的允许决策集用 Dk(sk) 表示 , xk(sk)∈Dk(sk) 允许决策集合实际是决策的约 束条件。
2.“局部最优路径”法：选择当前最短途径， “逢近便走”。 所取决策必是Q→ A1→ B2→ C2→T，全程长度 是13。 7 A B 1
1
4
1
2
Q 4 3
6 4 A2 2 4 4 2 A3 5
4 B2 6 3
C1 3 T C2 4
3 B3
3
◆全枚举法计算工作量将会十分庞大。
◆局部最优求出的解不一定是最优解。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T
4
3
6 4 A2 2 4 4 2 A3 5
(2)动态规划维数。 (3)可能状态集：用S(sk)表示。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T
4
3
6 4 A2 2 4 4 2 A3 5
三、动态规划的基本概念。 1.阶段(stage)和阶段变量。 把所给问题恰当地划分为若干个相互联系又有 区别的子问题，称之为多段决策问题的阶段。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T
4
3
6 4 A2 2 4 4 2 A3 5
用以描述阶段的变量叫作阶段变量，一般以 k表示阶段量．
离散 决策过程
连续 决策过程
离散确定性 决策过程
连续确定性 决策过程
离散随机性 决策过程
连续随机性 决策过程
七、学习方法建议 第一步 先看问题，充分理解问题的条件、 情况及求解目标。
第二步 分析针对该动态规划问题的“四大 要素、一个方程”。 第三步 动手把求解思路整理出来，或者 说，把该问题作为习题独立的来做。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T 6 4 A2 2 4 4 2 A3 5
4
3
(2)允许策略集合记作P。 最优策略:从允许策略集中，找出的具有最 优效果的策略。
A1
2 Q 4 3 7 4
B1
4 B2
1 C1 3 T C2 4
6 4 A2 2 4 4 2 A3 5
6 3
3 B3
3
5.状态转移方程(状态转移律) ：多阶段决策 过程的发展就是用阶段状态的相继演变来描 述的。
从上阶段的某一状态值到下阶段某一状态值 的转移规律成为状态转移律
或简写为
6.指标函数 (1)阶段指标函数(也称阶段收益)（是对应某一 阶段状态和从该状态出发的一个阶段的决策的 某种效益度量。）vk(sk,xk) 简记为vk 。 (2)过程指标函数(指标函数)。(它所包含的 各阶段指标函数的函数。） Vk,n(sk,xk, sk+1,xk+1,…, sn,xn)。简记为Vk,n 。
有 简记为
8. 概念的关系。
决策xk(sk)
状态 sk
决策xk+1(sk+1) 阶段k+1 状态 T(sk+1,xk+1) sk+2
vk+1(sk+1,xk+1)
阶段k 状态 T(sk,xk) sk+1
vk(sk,xk)
四、最优化原理与动态规划的数学模型 1.最优化原理 (贝尔曼最优化原理) 若某一全过程最优策略为：
(1)要能够正确地描述受控过程的变化特征。 (2)包含到达这个状态前的足够信息，且满足 无后效性。 (3)要满足可知性。
3.正确地定义决策变量及各阶段的允许决策 集合Dk(sk)
4. 能够正确地写出状态转移方程，至少要 能正确反映状态转移规律。
5.根据题意,正确地构造出指标函数，应满 足下列性质： (1)可分性， (2)为了进行动态规划计算满足递推性，
第二节 最优化原理与动态规划的数学模型
◆理解动态规划的基本概念和基本原理
一、动态规划方法导引 1. 全枚举法或穷举法。共有 18 条可能路线， 进行比较，求得最优路线Q→ A3→ B1→ C1→T。
A1 2 Q 7 4 B1 4 B2 6 3 3 B3 3 C2 4 1 C1 3 T
4
3
6 4 A2 2 4 4 2 A3 5
或
6.确立边界条件写出动态规划函数基本方程。
决 策 x1 状态S1
决 策 x2 状态S2
决 策 xk 状态S3
决 策 xk+1 状态Sk+1
决 策 xn
阶段1
阶段2
… 阶段k
阶段k+1
… 阶段n
v1
v2
vk
寻求最优解的方向
vk+1
vn
六、动态规划的分类
根据多阶段决策过程的 时间参量
根据决策过程的 演变 确定性 决策过程 随机性 决策过程
第四步 把自己的求解放到一边，看书中的 求解方法，要充分理解教材中的论述。 第五步 对照自己的求解，分析成败。 ◆动态规划的四大要素 ① 状态变量及其可能集合 sk Sk ② 决策变量及其允许集合 xk Dk ③ 状态转移方程 sk+1= Tk (sk ,xk ) ④ 阶段收益 vk ( sk , xk )
3.动态规划方法就是从终点逐段向始点方向寻 找最短路线的方法。解题步骤如下： ●把问题划分为几个阶段。 ●按阶段顺序首先考虑最后阶段如第四阶段
的最优决策，也就是走哪条路线最短。
●按阶段顺序依次考虑第三、第二，第一阶 段的最优决策，为此只需确定每一阶段上 各初始点的最优决策即可。
◆用动态规划方法逐段求解时，每个阶段上 的求优方法基本相同，而且比较简单，每 一阶段的计算都要利用上一阶段的计算结 果，因而减少了很多计算量。阶段数愈多， 这种效果愈明显。