《动态规划问题》PPT课件.ppt

第四章 动态规划问题 天马行空官方博客：/tmxk_docin ；QQ:1318241189；QQ群：175569632 动态规划的概念与模型 l静态决策 一次性决策 l动态决策 多阶段决策 决策 x1x2 Z u输入决策 输出 决策效应 第一月 x1x2 r1 u1 第二月 x3 r2 u2 第三月 x4 r3 u3 多段决策过程 T1 x1x2 r1 u1 T2 x3 r2 u2 Tk xkxk+! rk uk Tn xnxn+1 rn un n个决策子问题 K称为阶段变量 xk描述k阶段初的状态，称为状态变量 一般把输入状态称为该阶段的阶段状态。 uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量 rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。 具有无后效性的多段决策过程 Xk+1=Tk (xk, uk) 系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系 统以前的决策无关，则称为具有无后效性的多段决策过程。 T1 x1x2 r1 (x1, u1) u1(x1) T2 x3 r2 (x2 ,u2) u2 (x2) Tk xkxk+! rk (xk,uk) uk (xk) Tn xnxn+1 rn (xn,un) un (xn) K后部子过程 多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过 程，简称k-子过程。 Tk xkxk+! rk (xk,uk) uk (xk) Tn xnxn+1 rn (xn,un) un (xn) 动态规划模型 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的关系，才能构成目标函 数。目标函数是由阶段效应经过某种集结而得到的，如何 集结视具体问题而定，同时还应根据问题确定目标是求最 大还是最小。 由于在经济系统中的大多数情况下，目标的集结方法都是 求和，因此，在不作说明的情况下，往后的讨论都针对目 标为和的形式进行。 动态规划解的概念 多段决策过程中所要求解的是，从起始状态x1开始，进行 一系列的决策，使目标R达到最优 最优目标值 R* 最优策略 使得目标达到最优的决策序列。 最优路线 在采取最优策略时，系统从x1开始所经过的状态序列 求解动态规划模型 找到最优策略、最优路线和最优目标值。 动态规划最优性原理 多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态 阶段最优决策不能只从本阶段的效应出发，必须通盘考虑 ，整体规划。 阶段k的最优决策不应该只是本阶段效应的最优，而必须 是本阶段及其所有后续阶段的总体最优，即关于整个k后 部子过程的最优决策。 动态规划最优性原理 最优性原理 “最优策略具有的基本性质是：无论初始状态和初始决 策如何，对于前面决策所造成的某一状态而言，下余的决 策序列必构成最优策略”。 A M B 动态规划最优性原理 最优性原理的含意 最优策略的任何一部分子策略，也是相应初始状态的 最优策略。 每个最优策略只能由最优子策略构成。 显然，对于具有无后效性的多段决策过程而言，如果按照 k后部子过程最优的原则来求各阶段状态的最优决策，那 么这样构成的最优决策序列或策略一定具有最优性原理所 提示的性质。 贝尔曼函数 贝尔曼函数fk(xk)： 在阶段k从初始状态xk出发，执行最优决策序列或策 略，到达过程终点时，整个k-子过程中的目标函数取值， 称为条件最优目标函数，亦称贝尔曼函数。 条件最优策略 多段决策过程的任一阶段状态xk的最优策略 处于条件xk时的最优策略。 条件最优决策 构成条件最优策略的决策 贝尔曼函数 条件最优目标函数值fk(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)都是已知的函数 求fk(xk)需要首先求关于xk的所有k+1段状态xk+1的fk+1(xk+1) 逆序地求出条件最优目标函数值集合和条件最优决策集合 状态xk+1是由前面阶段的状态决定的 用问题给定的初始条件，即可顺序地求出整个多段决策问题 的最优目标函数值、最优策略和最优路线。 动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合 k=n时，动态规划基本方程是 边界条件 k=n时的动态规划基本方程成为 动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合 k=n1时，动态规划的基本方程是 所有的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的最短路。 ad b et cf s 9 7 5 7 8 4 5 6 4 6 54 7 图4-1 动态规划应用举例-最短路问题 ad b et cf s 9 7 5 7 8 4 5 6 4 6 54 7 第一阶段 第二阶段 第三阶段 划分阶段 k=1,2,3 代表三个阶段 动态规划应用举例-最短路问题 ad b et cf s 9 7 5 7 8 4 5 6 4 6 54 7 状态变量xk取为k阶段所在地，则有： 动态规划应用举例-最短路问题 ad b et cf s 9 7 5 7 8 4 5 6 4 6 54 7 k阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点。 动态规划应用举例-最短路问题 逆序求条件最优目标函数集和条件最优决策集 由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0 对3阶段所有可能的状态X3=d, e, f计算f3( )如下 动态规划应用举例-最短路问题 逆序求条件最优目标函数集和条件最优决策集 也可以用表格方法计算如下 t/tF3()U3() d e f 5+0 7+0 4+0 5 7 4 t t t r3(x3,u3)+f4(x4) f3(x3) u3(x3) 动态规划应用举例-最短路问题 逆序求条件最优目标函数集和条件最优决策集 对2阶段所有可能的状态X2=a, b, c计算f2( )如下 动态规划应用举例-最短路问题 逆序求条件最优目标函数集和条件最优决策集 对2阶段所有可能的状态X2=a, b, c计算f2( )如下 动态规划应用举例-最短路问题 逆序求条件最优目标函数集和条件最优决策集 也可以用表格方法计算如下 d/de/ef/fF2()U2() a b