《动态规划》PPT课件(I)

《《动态规划》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划郭菊娥教授guojue@mail.xjtu.edu.cn西安交通大学2021/7/22第五章：动态规划动态规划求解2动态规划应用举例33动态规划概念与模型31动态规划概念与模型引言多阶段决策过程动态规划概念与模型动态规划模型动态规划建模动态规划概念与模型——引言决策x1x2Zu输入决策输出决策效应第一月x1x2r1u1第二月x3r2u2第三月x4r3u3静态决策一次性决策动态决策多阶段决策多阶段决策过程T1x1x2r1u1T2x3r2u2Tkxkxk+1rkukTnxnxn+1rnun……n个决策子问题；K称为阶段变量xk描述k阶段初的状态，称为状态变量。一般把输入状态称为该阶段的阶段

2、状态uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应具有无后效性的多段决策过程x2T1x1r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+1rk(xk,uk)uk(xk)……Tnxnxn+1rn(xn,un)un(xn)Xk+1=Tk(xk,uk)系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系统以前的决策无关，则称为具有无后效性的多段决策过程。K后部子过程Tkxkxk+1rk(xk,uk)uk(xk)…Tnxnxn+1rn(xn,un)un(xn)多段决策过程中

3、从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程动态规划模型Opt表示求优Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合Uk是一个集合，表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此决策允许集合一般写为Uk(xk)动态规划建模1确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示。明确状态变量和状态可能集合2状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后

4、效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集动态规划建模与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Uk(xk)系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确xk+1=Tk(xk,uk)中的函数Tk（）确定决策变量和决策允许集合3确定状态转移方程4动态规划建模阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须明确

5、rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。明确阶段效应和目标5动态规划求解解的概念最优性原理动态规划求解贝尔曼函数动态规划的基本方程动态规划方法基本原理动态规划问题求解的一般步骤动态规划四大要素、一个方程动态规划解的概念多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标R达到最优最优目标值：R*最优策略：使目标最优的决策序列最优路线采取最优策略时，系

6、统从x1开始所经过的状态序列求解动态规划模型找到最优策略、最优路线和最优目标值动态规划最优性原理多段决策过程的特点每个阶段都要进行决策相继进行的阶段决策构成的决策序列前一阶段的终止状态又是后一阶段的初始状态阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策动态规划最优性原理最优性原理最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略AMB动态规划最优性原理最优性原理的含意最优策略的任何一部分子策略，也

7、是相应初始状态的最优策略每个最优策略只能由最优子策略构成显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所提示的性质。贝尔曼函数贝尔曼函数fk(xk)在阶段k从初始状态xk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的目标函数取值，称为条件最优目标函数，亦称贝尔曼函数贝尔曼函数条件