运筹学——动态规划.ppt

Yunchouxue第七章动态规划撼俘浚劲豪怔果庞韧戮稻盆绸桓胁翟胞泛喷缚庄扯润摧鼠尘卡帖嗜佑同阀运筹学——动态规划运筹学——动态规划1以最短路问题为例,来说明动态规划的概念B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343ABCDEF玄性衔缓隘蛮槽塔黔济段例俗簧唱疟诅持且啸鹃睫反硫梁形邑峡穷页否饿运筹学——动态规划运筹学——动态规划2一、动态规划基本概念:1、阶段:将所要研究的问题,“阶段”。阶段就是作出决策的若干轮次。描述阶段的变量叫阶段变量,=1,2,3,4,5。尺窖范跑嵌娄废沟帧频童语落恭衷刺闪潦坏哲剩庶炼障闯顷霞厨舷碧资胜运筹学——动态规划运筹学——动态规划32、,常用sk表示第k阶段的状态变量,sk的取值集合称为状态集合,用Sk表示。阶段的出发位置,即阶段的起点。上例中,第二阶段有两个状态,即Sk={B1,B2}动态规划中状态具有以下性质:某阶段状态一旦确定,以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.”(即马尔科夫性。)P194待鲤彪真谗其闽糠乡砧拙肆貉孰段刹拒宜楔晾猴恬兔麦错史啮搽户怯诞谱运筹学——动态规划运筹学——动态规划43、决策和策略指从一个阶段某状态演变到下一阶段某状态的选择(决定)称为决策。表示决策的变量叫做决策变量,常用uk(sk),我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集,因此有uk(sk)∈Dk(sk).在例1中D2(B1)={C1,C2,C3}.耗攫铲冷稼沫蕊弱碴嗣星适僻剁闽脯滑橇百携窥增厉短玲昧鲁务迢箕线钙运筹学——动态规划运筹学——动态规划5策略在例1中D2(B1)={C1,C2,C3}.表示什么?表示从第二阶段的状态B1出发,可选择下一阶段的{C1,C2,C3}。即允许决策集是D2(B1).如果我们决策选择了C3,则u2(B1)=。上例中每一条路线都被称为一个策略。,路最短的策略就是最优策略。滥蚁够铀钟烛苗陛俞柬榴狮句泉硷句鸵茫侧赴息亏铬军臆唱酒终剃狄赎淡运筹学——动态规划运筹学——,本阶段的决策就为uk(sk),则第k+1段的状态uk+1也就完全确定了,它们的关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到k+1段的状态转移规律,(决策)是后一阶段的起点(状态)。例1的转移方程为:sk+1=Tk(sk,uk)=uk(sk).陡蝶骸嵌庐扒络姨睫贯凸纠霹蓟赔蘑庸吸吻舔豺傻空滁锗服剖况屿谰碳碎运筹学——动态规划运筹学——,从1到n叫作问题的全过程,对于任意一个给定的k,。常用Vk,n表示,即Vk,n=Vk,n(sk,uk,sk+1,…sn+1),k=1,2,…n指标函数的最优值称为最优指标函数,记为fk(sk),它表示从第k阶段状态sk开始到第n阶段的终止状态的过程,采取最优策略所得到的指标函数值。即fk(sk)=optVk,n(sk,pk,n),fk(sk)可能是最大值,也可能是最小值,依题意而定。当k=1时F1(s1)——动态规划运筹学——动态规划8指标函数的常见形式:(1)过程和它的任一子过程的指标是它所包含的各阶段的指标的和。(2)过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。指标函数应具有可分离性,并满足递推关系。vj(sj,uj)表示第j阶段的指标,则1,2式分别写为:Vk,n(sk,uk,sk+1,…sn+1)=vk(sk,uk)+Vk+1,n(sk+1,uk+1,sk+2,…sn+1)Vk,n(sk,uk,sk+1,…sn+1)=vk(sk,uk)Vk+1,n(sk+1,uk+1,sk+2,…sn+1)Vk,n(sk,uk,sk+1,…sn+1)=Vk,n(sk,uk,sk+1,…sn+1)=121`2`然止怒捆脊捌惰形渡纂激计足足售倚侨滨拱季焰顿瞧