文档介绍：动态规划
动态规划模型
Opt表示求优
Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合
Uk是一个集合，表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因程
动态规划基本方程也可以直接由条件最优目标函数的定义导出，即：
动态规划方法基本原理
动态规划方法基本原理
rk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函数
需要首先求关于xk的所有k+1段状态的fk+1(xk+1)
逆序地求出条件最优目标函数值集合和条件最优决策集合
状态xk+1是由前面阶段的状态决定的
用问题给定的初始条件，即可顺序地求出整个多段决策问题的最优目标函数值、最优策略和最优路线
动态规划问题求解的一般步骤
k=n 时
动态规划基本方程是
边界条件
k=n时的动态规划基本方程成为
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
动态规划问题求解的一般步骤
k=n-1 时
动态规划基本方程是
所有的fn(xn)都已求出，因此根据xn=Tn-1(xn-1,un-1)就阶段n-1每个可能状态xn-1∈Xn-1求条件最优决策及相应的条件最优目标函数值fn－1(xn－1)
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
动态规划问题求解的一般步骤
k=1 时
动态规划基本方程是
所有的f2(x2)都已求出，因此根据x2=T1(x1,u1)就阶段1每个可能状态x1∈X1求条件最优决策及相应的条件最优目标函数值f1(x1)
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
动态规划问题求解的一般步骤
整个过程可以表示为
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
动态规划问题求解的一般步骤
若x1唯一确定时（始端固定问题），则
阶段1的条件最优决策就是阶段1的关于整个过程的最优决策
顺序地求出最优目标值、最优策略和最优路线
2
动态规划问题求解的一般步骤
若x1不是唯一时，则
顺序地求出最优目标值、最优策略和最优路线
2
动态规划四大要素、一个方程
四大要素
①状态变量及其可能集合
②决策变量及其允许集合
③状态转移方程
④阶段效应
动态规划基本方程：
动态规划应用举例
工程路线问题
资源分配问题
动态规划应用举例
动态规划应用举例——工程路线问题
某旅行者希望从s地起到t地，其间的道路系统如图4－1所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路
a
d
b
e
t
c
f
s
9
7
5
7
8
4
5
6
4
6
5
4
7
a
d
b
e
t
c
f
s
9
7
5
7
8
4
5
6
4
6
5
4
7
第一阶段 第二阶段 第三阶段
划分阶段 k=1,2,3 代表三个阶段
动态规划应用举例——工程路线问题
a
d
b
e
t
c
f
s
9
7
5
7
8
4
5
6
4
6
5
4
7
状态变量xk取为k阶段所在地，则有：
动态规划应用举例——工程路线问题
k阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点
a
d
b
e
t
c
f
s
9
7
5
7
8
4
5
6
4
6
5
4
7
动态规划应用举例——工程路线问题
第3阶段末已到达t，因此f4(t)=0
对3阶段所有可能的状态X3={d, e, f}计算f3( )如下
动态规划应用举例——工程路线问题
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
对2阶段所有可能的状态X2={a, b, c}计算f2( )如下
动态规划应用举例——工程路线问题
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
对2阶段所有可能的状态X2={a, b, c}计算f2( )如下
动态规划应用举例——工程路线问题
1
逆序地求出条件最优目标函数值集合和条件最优决策集合
对1阶段所有可能的状态X1={s}计算f1( )如下
动态规划应用举例——工程路线问题
1
逆序地求出