第二节_最优化原理与动态规划

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二节 最优化原理与动态规划的数学模型,理解动态规划的基本概念和基本原理,一、动态规划方法导引,1.,全枚举法或穷举法。共有,18,条可能路线，进行比较，求得最优路线,Q,A,3,B,1,C,1,T,。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,2,.,“,局部最优路径,”,法,：选择当前最短途径，,“,逢近便走,”,。,所取决策必是,Q,A,1,B,2,C,2,T,，全程长度是,13,。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,全枚举法,计算工作量将会十分庞大。,局部最优求出的解不一定是最优解。,3.,动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。,解题步骤,如下：,把问题划分为几个阶段。,按阶段顺序首先考虑最后阶段,如,第四阶段的最优决策，也就是走哪条路线最短。,按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各,初始点,的最优决策即可。,用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，每一阶段的计算都要,利用上一阶段的计算结果,，因而减少了很多计算量。阶段数愈多，这种效果愈明显。,二、动态规划解题 标号法：,最短路径：,Q,A,3,B,1,C,1,T,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,阶段,1,阶段,2,阶段,3,阶段,4,0,，,T,3,T,4,T,4,C,1,7,C,2,6,C,1,11,B,1,B,2,8,B,1,8,B,1,11,A,3,三、动态规划的基本概念。,1.,阶段,(stage),和阶段变量。 把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,用以描述阶段的变量叫作,阶段变量,，一般以,k,表示阶段量,阶段数,k,的编号法有两种：,(1),顺序编号；,(2),逆序编号法。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,2.,状态,(state),、状态变量和可能状态集,(1),状态与状态变量。表示每个阶段开始所处的自然状况或客观条件。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,(2),动态规划维数,。,(3),可能状态集：用,S,(,s,k,),表示。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,3.,决策,(decision),、,决策变量和允许决策集合,(1),决策。表示当过程处于某一阶段的某个状态，可以作出不同的决定（选择），从而确定下一阶段的状态。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,(2),决策变量,:,x,k,=,x,k,(,s,k,),决策变量,x,k,(,s,k,),的允许决策集用,D,k,(,s,k,),表示,x,k,(,s,k,),D,k,(,s,k,),允许决策集合实际是决策的约束条件。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,4.,策略和子,策略,(Policy),（,1,）全过程策略指具有,n,个阶段全部过程，简称策略。表示为,x,1,(,s,1,),x,2,(,s,1,),x,n,(,s,n,),。,k,后,部子过程策略,表示为,p,k,(,x,k,),Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,(2),允许策略集合记作,P,。,最优策略,:,从允许策略集中，找出的具有最优效果的策略。,Q,T,A,1,A,2,A,3,B,1,B,2,B,3,C,1,C,2,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,5.,状态转移方程,(,状态转移律,),：多阶段决策过程的发展就是用阶段状态的相继演变来描述的。,或,简写为,从上阶段的某一状态值到下阶段某一状态值的转移规律成为,状态转移律,6.,指标函数,(1),阶段指标函数,(,也称阶段收益,),（是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量。）,v,k,(,s,k,x,k,),简记为,v,k,。,(2),过程指标函数,(,指标函数,),。,(,它所包含的各阶段指标函数的函数。）,V,k,n,(,s,k,x,k,s,k,+1,x,k,+1,s,n,x,n,),。,简记为,V,k,n,。,动态规划求解的问题的过程指标函数,(,指标函数,),，必须具有关于阶段指标的,可分离形式,(,和、积或其他形式,),：,表示某种运算，可为加、减、乘、除、开方等。,常见有,:,和,相应的子策略称为,s,k,状态下的最优子策略，记为,p,k,*,(,s,k,),；,而构成该子策略的各段决策称为该过程上的最优决策，记为,7.,最优指标函数：,f,k,(,s,k,),有,简记为,8.,概念的关系。,状态,s,k,阶段,k,T,(,s,k,x,k,),决策,x,k,(,s,k,),v,k,(,s,k,x,k,),状态,s,k+,1,阶段,k,+1,T,(,s,k,+1,x,k,+1,),决策,x,k,+1,(,s,k,+1,),v,k,+1,(,s,k,+1,x,k,+1,),状态,s,k+,2,四、,最优化原理与动态规划的数学模型,1.,最优化原理,(,贝尔曼最优化原理,),若某一全过程最优策略为：,则,最优化原理,：作为整个过程的最优策略具有这样,的性质，无论过去的状态和决策如何，对先前决策,所形成的状态而言，余下的诸决策必构成最优决策。,2.,动态规划的数学模型,(,逆序法时,),(8.3a),(8.3b),(8.3c),(8.3d),或,(8.3b),和,(8.3d),称为边界条件。,五、,动态规划方法的基本步骤,1.,阶段的划分,2.,正确地定义状态变量,s,k,(1),要能够正确地描述受控过程的变化特征。,(2),包含到达这个状态前的足够信息，且满足无后效性。,(3),要满足可知性。,3.,正确地定义决策变量及各阶段的允许决策集合,D,k,(,s,k,),4.,能够正确地写出状态转移方程，至少要能正确反映状态转移规律。,5.,根据题意,正确地构造出指标函数，应满足下列性质：,(1),可分性，,(2),为了进行动态规划计算,满足递推性，,或,6.,确立边界条件写出动态规划函数基本方程。,阶段,1,阶段,2,阶段,k,阶段,k+1,阶段,n,状态,S,1,决,策,x,1,状态,S,2,v,1,决,策,x,2,状态,S,3,v,2,决,策,x,k,状态,S,k+1,v,k,决,策,x,k+1,v,k+1,决,策,x,n,v,n,寻求最优解的方向,六、动态规划的分类,离散,决策过程,连续,决策过程,根据多阶段决策过程的,时间参量,根据决策过程的,演变,确定性,决策过程,随机性,决策过程,离散确定性,决策过程,连续,确定性,决策过程,离散随机性,决策过程,连续随机性,决策过程,七,、学习方法建议,第一步 先看问题，充分理解问题的条件、情况及求解目标。,第二步 分析针对该动态规划问题的,“,四大要素、一个方程,”,。,第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。,第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。,第五步 对照自己的求解，分析成败。,动态规划的四大要素 状态变量及其可能集合,s,k,S,k,决策变量及其允许集合,x,k,D,k,状态转移方程,s,k,+1,=,T,k,(,s,k,x,k,),阶段收益,v,k,(,s,k,x,k,),