动态规划
1 动态规划
基本概念 多阶段决策问题: 此问题系统的动态过程可以按照时间的 进程分为若干个相互联系的阶段,而在每 个阶段中,具有一个或多个状态,在每一个 阶段中都要针对每一个状态作出决策。这样 在各阶段的决策确定以后,就顺序构成一个 决策序列,称为一个策略
2 基本概念 多阶段决策问题： 此问题系统的动态过程可以按照时间的 进程分为若干个相互联系的阶段，而在每一 个阶段中，具有一个或多个状态，在每一个 阶段中都要针对每一个状态作出决策。这样， 在各阶段的决策确定以后，就顺序构成一个 决策序列，称为一个策略
阶段和阶段变量:阶段是按照总决策进行的时间或空 间的先后顺序来划分,用K表示,K为阶段变量 状态和状态变量:状态描述系统所处的状态或位置 阶段状态应具有“无后效性”,即过程的历史只能 通过当前的状态去影响它的未来,每一阶段(k) 状态分为初始状态(S)和终止状态(Sk+1),前 阶段的终止状态是后一阶段的初始状态 状态可能集Sk,ScSk
3 阶段和阶段变量：阶段是按照总决策进行的时间或空 间的先后顺序来划分，用K表示，K为阶段变量。 状态和状态变量：状态描述系统所处的状态或位置。 阶段状态应具有“无后效性”，即过程的历史只能 通过当前的状态去影响它的未来，每一阶段（k ） 状态分为初始状态（sk）和终止状态（sk+1），前一 阶段的终止状态是后一阶段的初始状态。 状态可能集 Sk， skєSk
决策变量和策略:ⅹ表示第k阶段的决策。 决策变量序列称为策略 全过程策略(X1,…,Xn 子策略(Xm,Xm+1
4 决策变量和策略：xk表示第k阶段的决策。 决策变量序列称为策略 全过程策略 （x1，...，xn） 子策略 （xm，xm+1，...，xn）
状态转移方程:把过程由一个状态变到另一个 状态的变化叫做状态转移。 sk,选择决策ⅹ(S)的产生的结果,便转移 到sk+1,记为sk+=Tk(sk,xk) 若Tk(Sk 0,则称s为终止状态
5 状态转移方程：把过程由一个状态变到另一个 状态的变化叫做状态转移。 sk，选择决策xk（sk）的产生的结果，便转移 到sk+1，记为sk+1=Tk（sk，xk） 若Tk（sk，xk）=0，则称sk为终止状态
阶段效益函数:S,执行决策X时,不仅带来 系统状态的转移,也必然要影响决策目标, 对应这个决策的效果值,叫做效益函数,记 为rk(sk,xk)
6 阶段效益函数：sk，执行决策xk时，不仅带来 系统状态的转移，也必然要影响决策目标， 对应这个决策的效果值，叫做效益函数，记 为 rk（ sk，xk ）
效益函数:多阶段决策过程关于目标的总效益,在 “无后效性”的条件下,由各阶段效益累计而成。 k, Xk SK+1, xk+ 'n, Xn k=1, 即k子系统的效益。 ⊙表示某种运算(+,-,*等)
7 效益函数：多阶段决策过程关于目标的总效益，在 “无后效性”的条件下，由各阶段效益累计而成。 Rk= rk（ sk，xk ）⊙ rk+1（ sk+1，xk+1 ） ⊙… ⊙ rn（ sn，xn ） k=1，…，n 即k子系统的效益。 ⊙表示某种运算（+，-，*等）
当k=1时,R*表示总目标效益函数的最优值。 R*=r1(S1,X1*)⊙r2(S 2,^2 ⊙rn(Sn,xn*) (x1*,2*,…,x)称为最优策略 fk(sk) =optik(sk, Xk) o k+1 (Sk+1 k+1 @ ⊙rn(sn,xn*)} fk(sk):由第k阶段的状态s到终点的最优效益值。 当k=1,且s1唯一时,R*=千1(S1 8
8 当k=1时，R*表示总目标效益函数的最优值。 R*=r1（s1，x1 *） ⊙ r2（s2，x2 *） ⊙ … ⊙ rn（sn，xn *） （ x1 * ， x2 * ，…， xn *）称为最优策略 fk（sk）=opt{rk（sk，xk *） ⊙ rk+1（sk+1，xk+1 *） ⊙ …⊙ rn（sn，xn *）} fk（sk）：由第k阶段的状态sk到终点的最优效益值。 当k=1，且s1唯一时，R*=f1（s1）
当⊙为“+”时, fk(sk) =opt(k(sk, Xk*)+ Ik+(sp k+1 Xx+1 +…+「n(Sn,Xn*)} 尔曼函数
9 当⊙为“+”时， fk（sk）=opt{rk（sk，xk *） + rk+1（sk+1，xk+1 *） + …+ rn（sn，xn *）} -----贝尔曼函数
最优化原理:若(X1*,…,xn*)是初始状态 s1S1的最优策略,则其一部分 (xk*,Xk+1*,…,xn*)1≤k≤n对于它的初始状 态sES而言也构成一个最优策略,或称: 最优策略的任何一部分子策略也是相应初始 状态的最优策略 证明(反证法) 10
10 最优化原理：若（ x1 * ， …， xn *）是初始状态 s1 є S1的最优策略，则其一部分 （xk * ，xk+1 * ，…，xn *）1≤k≤n对于它的初始状 态sk є Sk而言也构成一个最优策略，或称： 最优策略的任何一部分子策略也是相应初始 状态的最优策略。 证明（反证法）