动态规划.ppt

动态规划,郭菊娥教授 guojuemail.xjtu.edu.cn 西安交通大学 2019/6/2,第五章：动态规划,动态规划概念与模型,引言,多阶段决策过程,动态规划概念与模型,动态规划模型,动态规划建模,动态规划概念与模型引言,多阶段决策过程,具有无后效性的多段决策过程,K后部子过程,动态规划模型,Opt表示求优 Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合 Uk是一个集合，表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此决策允许集合一般写为Uk(xk),动态规划建模,阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示。,状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集,动态规划建模,与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Uk(xk),系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确xk+1=Tk(xk,uk)中的函数Tk（ ）,动态规划建模,阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须明确rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。 由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。,5,动态规划求解,解的概念,最优性原理,动态规划求解,贝尔曼函数,动态规划的基本方程,动态规划方法基本原理,动态规划问题求解的一般步骤,动态规划四大要素、一个方程,动态规划解的概念,多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标R达到最优 最优目标值：R* 最优策略 ：使目标最优的决策序列 最优路线 采取最优策略时，系统从x1开始所经过的状态序列 求解动态规划模型 找到最优策略、最优路线和最优目标值,动态规划最优性原理,多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态 阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。 阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策,动态规划最优性原理,最优性原理 最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略,动态规划最优性原理,最优性原理的含意 最优策略的任何一部分子策略，也是相应初始状态的最优策略 每个最优策略只能由最优子策略构成 显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所提示的性质。,贝尔曼函数,贝尔曼函数fk(xk) 在阶段k从初始状态xk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的目标函数取值，称为条件最优目标函数，亦称贝尔曼函数,贝尔曼函数,条件最优策略 多段决策过程的任一阶段状态xk的最优策略处于条件xk时的最优策略 条件最优决策 构成条件最优策略的决策 条件最优目标函数值 执行条件最优策略时的目标函数值,贝尔曼函数,条件最优路线 执行条件最优策略时的阶段状态序列 条件最优k-子策略 系统从xk出发，在k-后部子过程中的最优策略 k-子过程条件最优目标函数 fk(xk) 从xk出发系统在k-后部子过程中的最优目标值 多段决策问题所求解的最优目标函数值：R*=f1(x1*) 动态规划基本方程：fk(xk)与fk1(xk1)之间的递推关系 动态规划方法的依据是最优性原理,动态规划基本方程,设在阶段k的状态xk执行了任意选定决策uk后的状态是xk+1=Tk(xk,uk)。这时k-后部子过程就缩小为k+1后部子过程。根据最优性原理，对k+1后部子过程应采取最优策略，由于无后效性，k后部子过程的目标函数值为 根据条件最优目标函数的定义有 称为动态规划基本方程，亦称贝尔曼方程 ，一般表示为： 其中：,动态规划基本方程,动态规划基本方程也可以直接由条件最优目标函数的定义导出，即：,动态规划方法基本原理,动态规划方法基本原理 rk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函数 需要首先求关于xk的所有k+1段状态的fk+1(xk+1) 逆序地求出条件最优目标函数值集合和条件最优决策集合 状态xk+1是由前面阶段的状态决定的 用问题给定的初始条件，即可顺序地求出整个多段决策问题的最优目标函数值、最优策略和最优路线,动态规划问题求解的一般步骤,k=n 时 动态规划基本方程是 边界条件 k=n时的动态规划基本方程成为,动态规划问题求解的一般步骤,k=n-1 时 动态规划基本方程是 所有的fn(xn)都已求出，因此根据xn=Tn-1(xn-1,un-1)就阶段n-1每个可能状态xn-1Xn-1求条件最优决策及相应的条件最优目标函数值fn1(xn1),动态规划问题求解的一般步骤,k=1 时 动态规划基本方程是 所有的f2(x2)都已求出，因此根据x2=T1(x1,u1)就阶段1每个可能状态x1X1求条件最优决策及相应的条件最优目标函数值f1(x1),动态规划问题求解的一般步骤,整个过程可以表示为,动态规划问题求解的一般步骤,若x1唯一确定时（始端固定问题），则 阶段1的条件最优决策就是阶段1的关于整个过程的最优决策,动态规划问题求解的一般步骤,若x1不是唯一时，则,动态规划四大要素、一个方程,四大要素 状态变量及其可能集合 决策变量及其允许集合 状态转移方程 阶段效应 动态规划基本方程：,动态规划应用举例,工程路线问题,资源分配问题,动态规划应用举例,动态规划应用举例工程路线问题,某旅行者希望从s地起到t地，其间的道路系统如图41所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路,第一阶段 第二阶段 第三阶段 划分阶段 k=1,2,3 代表三个阶段,动态规划应用举例工程路线问题,状态变量xk取为k阶段所在地，则有：,动态规划应用举例工程路线问题,k阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点,动态规划应用举例工程路线问题,第3阶段末已到达t，因此f4(t)=0 对3阶段所有可能的状态X3=d, e, f计算f3( )如下,动态规划应用举例工程路线问题,对2阶段所有可能的状态X2=a, b, c计算f2( )如下,动态规划应用举例工程路线问题,对2阶段所有可能的状态X2=a, b, c计算f2( )如下,动态规划应用举例工程路线问题,对1阶段所有可能的状态X1=s计算f1( )如下,动态规划应用举例工程路线问题,动态规划应用举例工程路线问题,动态规划应用举例资源分配问题,某公司拟将50万元资金投放下属A、B、C三个部门，各部门在获得资金后的收益如下表所示，用动态规划方法求总收益最大的投资分配方案（投资数以10万元为单位）,动态规划应用举例资源分配问题,对A、B、C三个部门分配资金形成三个阶段 xk表示给部门k分配资金时拥有的资金数 uk表示给部门k分配的资金数 状态转移方程是 目标函数是,第3阶段末资源分配完毕，因此f4(x4)=0 K=3时,动态规划应用举例资源分配问题,g3()是单调递增的函数,K=3时,动态规划应用举例资源分配问题,K=2时 对x2的所有取值，有,动态规划应用举例资源分配问题,K=2时,动态规划应用举例资源分配问题,同理可得,K=1时,动态规划应用举例资源分配问题,最优的分配方案所能得到的最大利润为70万元 分配方案可由计算过程反向查出为： 即为部门B分配50万元，部门A和C不分配,动态规划应用举例资源分配问题,