文档介绍：动态规划
郭菊娥教授
******@.
西安交通大学
2018/7/27
第五章:动态规划
动态规划求解
2
动态规划应用举例
3
3
动态规划概念与模型
3
1
动态规划概念与模型
引言
多阶段决策过程
动态规划概念与模型
动态规划模型
动态规划建模
动态规划概念与模型——引言
决策
x1
x2
Z
u
输入
决策
输出
决策效应
第一月
x1
x2
r1
u1
第二月
x3
r2
u2
第三月
x4
r3
u3
静态决策一次性决策
动态决策多阶段决策
多阶段决策过程
T1
x1
x2
r1
u1
T2
x3
r2
u2
Tk
xk
xk+1
rk
uk
Tn
xn
xn+1
rn
un
…
…
n个决策子问题;K称为阶段变量
xk描述k阶段初的状态,称为状态变量。一般把输入状态称为该阶段的阶段状态
uk的取值代表k阶段对第k子问题所进行的决策,称为k阶段的决策变量
rk为k阶段从状况xk出发,做决策uk之后的后果,称为k阶段的阶段效应
具有无后效性的多段决策过程
x2
T1
x1
r1 (x1, u1)
u1(x1)
T2
x3
r2 (x2 ,u2)
u2 (x2)
Tk
xk
xk+1
rk (xk,uk)
uk (xk)
…
…
Tn
xn
xn+1
rn (xn,un)
un (xn)
Xk+1=Tk (xk, uk)
系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系统以前的决策无关,则称为具有无后效性的多段决策过程。
动态规划建模
1
确定阶段与阶段变量
阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的,阶段数等于多段决策过程中从开始到结束所需要作出决策的数目,阶段变量用k表示。
明确状态变量和状态可能集合
2
状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性,因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件,因此为了求解必须正确地确定状态可能集
动态规划建模
与静态问题相同,决策变量应能够反映对问题所作的决策,决策变量也应有其相应的约束条件,在建模时应明确决策允许集合Uk(xk)
系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移,这一结果直接影响系统往后的决策过程,因此必须明确状态的转移过程,即根据问题的内在关系,明确xk+1=Tk(xk,uk)中的函数Tk( )
确定决策变量和决策允许集合
3
确定状态转移方程
4