动态规划的最优化原理及其算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.1,动态规划的最优化原理及其算法,5.1.1 求解多阶段决策过程的方法,例5.1.1 最短路问题,1,决策树法,可以枚举出20条路径，其中最短的路径长度为16,2,例,5.1.1,最短路问题,表现为明显的阶段性,一条从,A,到,B,的,最短路径中的任何一段都是最短的,最优性原理,“最优策略的一部分也是最优的,”,每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关,因此我们可以从,B,向回搜索最短路,标记法,如何找出最短路径,3,5.1.2,动态规划的基本概念及递推公式,状态,(每阶段初始的出发点),最短路问题中，各个节点就是状态,生产库存问题中，库存量是状态,物资分配问题中，剩余的物资量是状态,控制变量,(决策变量),最短路问题中，走哪条路,生产库存问题中，各阶段的产品生产量,物资分配问题中，分配给每个地区的物资量,阶段的,编号,与递推的,方向,一般采用反向递推，所以阶段的编号也是逆向的,当然也可以正向递推,4,动态规划的步骤,1、确定问题的阶段和编号,2、确定状态变量,用,S,k,表示第,k,阶段的状态变量及其值,3、确定决策变量,用,x,k,表示第,k,阶段的决策变量，并以,x,k,*,表示该阶段的最优决策,4、状态转移方程,s,k,-1,=,g,(,s,k,x,k,),反向编号,s,k,+1,=,g,(,s,k,x,k,),正向编号,5、直接效果,直接一步转移的效果,d,k,(,s,k,x,k,),6、,总效果函数,指某阶段某状态下到终端状态的总效果，它是一个递推公式,5,动态规划的步骤,h,k,是一般表达形式，求当前阶段当前状态下的阶段最优总效果,(1)如最短路问题，是累加形式，此时有,终端的边际效果一般为,f,0,(,s,0,x,0,)=0,(2),如串联系统可靠性问题，是连乘形式，此时有,终端的边际效果一般为,f,0,(,s,0,x,0,)=1,从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段,6,