动态规划的基本概念与方法课件

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一节 动态规划的基本概念与方法,一、多阶段决策问题,1.,时间阶段的例子（机器负荷问题）,某厂有,1000,台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。,1,2,3,4,5,S,1,=1000,x,1,x,2,x,5,x,4,x,3,s,5,v,1,v,2,v,3,v,4,v,5,s,2,s,3,s,4,2.,空间阶段的例子（最短路问题）,如图为一线路网络。现要从,A,点铺设一条管道到,E,点，,图中两点间连线上数字表示两点间距离。现需选一条由,A,到,E,的铺管线路，使总距离最短。,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,阶段,1,阶段,2,阶段,3,阶段,4,二、基本概念与方程,1.,基本概念,阶段,分步求解的过程，用阶段变量,k,表示，,k,=1,，,，,n,状态,每阶段初可能的情形或位置，用状态变量,S,k,表示。,按状态的取值是离散或连续，将动态规划问题分为,离散型和连续型。,决策,每阶段状态确定后的抉择，即从该状态演变到下阶,段某状态的选择，用决策变量,x,k,表示。,状态转移,由,S,k,转变为,S,k,+1,的,规律，记,S,k,+1,=,T,(,S,k,，,x,k,),。,策略,由各阶段决策组成的序列，记,P,1,n,=,x,1,，,，,x,n,，,称,P,kn,=,x,k,，,，,x,n,为阶段,k,至,n,的,后部子策略。,阶段指标,每阶段选定决策,x,k,后所产生的效益，记,v,k,=,v,k,(,S,k,，,x,k,),。,指标函数,各阶段的总效益，记相应于,P,kn,的指标函数,为,v,kn,=,v,kn,(,S,k,，,P,kn,),。,其中最优的称最优,指标函数，记,f,k,=,f,k,（,S,k,）,=opt,v,kn,。,问题：动态规划的最优解和最优值各是什么？,最优解：最优策略,P,1,n,，,最优值：最优指标,f,1,。,2.,基本原理与基本方程,（,1,）基本原理,以最短路为例说明,（,2,）基本方程 根据最优性原理，可建立从后向前逆推求解的递推公式,基本方程：,动态规划求解的一般步骤：,-,确定过程的分段，构造状态变量；,-,设置决策变量，写出状态转移；,-,列出阶段指标和指标函数；,-,写出基本方程，由此逐段递推求解。,三、求解方法,1.,离散型（用表格方式求解）,例,1,用动态规划方法求解前面的最短路问题。,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,解：设阶段,k,=1,，,2,，,3,，,4,依次表示,4,个阶段选路的过程；,状态,s,k,表示,k,阶段初可能处的位置；,决策,x,k,表示,k,阶段初可能选择的路；,阶段指标,v,k,表示,k,阶段与所选择的路段相应的路长；,指标函数,v,k,4,=,表示,k,至,4,阶段,的总路长；,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,4,k,S,k,x,k,v,k,v,kn,=v,k,+f,k+,1,f,k,3,C,1,C,2,C,3,8,7,12,C,1,D,1,E,C,2,D,2,E,C,3,D,2,E,k,S,k,x,k,v,k,v,kn,=v,k,+f,k+,1,f,k,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,2,B,1,B,2,B,3,20,B,1,C,1,D,1,E,14,B,2,C,1,D,1,E,19,B,3,C,2,D,2,E,k,S,k,x,k,v,k,v,kn,=v,k,+f,k+,1,f,k,A,E,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,2,9,5,3,12,2,5,1,5,6,4,6,8,10,13,12,11,14,10,1,A,19,AB,2,C,1,D,1,E,P*,14,=,AB,2,C,1,D,1,E,f,1,= 19,（最短路）,（最短距）,2.,连续型（用公式递推求解）,例,2,用动态规划方法求解前面的机器负荷问题。,某种机器可以在高、低两种负荷下进行生产。高负荷年产量,8,，年完好率,0.7,；低负荷年产量,5,，年完好率,0.9,。现有完好机器,1000,台，需制定一个,5,年计划，以决定每年安排多少台机器投入高、低负荷生产，使,5,年的总产量最大。,解：设阶段,k,=1,，,，,5,表示第,k,年安排机器的过程；,状态,s,k,表示第,k,年初的完好机器台数；,决策,x,k,表示第,k,年投入高负荷的机器台数；则投入低负荷的台数为,s,k,-,x,k,；,状态转移,s,k,+1,=0.7,x,k,+0.9(,s,k,-,x,k,),；,阶段指标,v,k,=8,x,k,+5(,s,k,-,x,k,),表示第,k,年的产量；,指标函数,v,kn,=,表示第,k,至,5,年的总产量；,5,年的最大总产量为,23 .721000=23720,。,