3动态规划.pptx

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