第2节最优化原理与动态规划.pptVIP

第二节 最优化原理与动态规划的数学模型;一、动态规划方法导引 1.全枚举法或穷举法。共有18条可能路线，进行比较，求得最优路线Q→ A3→ B1→ C1→T。;2.“局部最优路径”法：选择当前最短途径，“逢近便走”。 所取决策必是Q→ A1→ B2→ C2→T，全程长度是13。;◆全枚举法计算工作量将会十分庞大。 ◆局部最优求出的解不一定是最优解。;3.动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下： ●把问题划分为几个阶段。 ●按阶段顺序首先考虑最后阶段如第四阶段的最优决策，也就是走哪条路线最短。 ●按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各初始点的最优决策即可。;◆用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，每一阶段的计算都要利用上一阶段的计算结果，因而减少了很多计算量。阶段数愈多，这种效果愈明显。 ;二、动态规划解题 标号法：;三、动态规划的基本概念。;用以描述阶段的变量叫作阶段变量，一般以k表示阶段量． 阶段数k的编号法有两种： (1)顺序编号；(2)逆序编号法。;2.状态(state)、状态变量和可能状态集 (1)状态与状态变量。表示每个阶段开始所处的自然状况或客观条件。;(2)动态规划维数。;3.决策(decision)、决策变量和允许决策集合 (1)决策。表示当过程处于某一阶段的某个状态，可以作出不同的决定（选择），从而确定下一阶段的状态。;(2)决策变量:xk=xk(sk) 决策变量xk(sk)的允许决策集用Dk(sk)表示, xk(sk)∈Dk(sk)允许决策集合实际是决策的约束条件。;4.策略和子策略(Policy) （1）全过程策略指具有n个阶段全部过程，简称策略。表示为 {x1(s1),x2(s1),…,xn(sn)}。 k后部子过程策略,表示为pk(xk);(2)允许策略集合记作P。 最优策略:从允许策略集中，找出的具有最优效果的策略。 ;5.状态转移方程(状态转移律) ：多阶段决策过程的发展就是用阶段状态的相继演变来描述的。;6.指标函数;◆动态规划求解的问题的过程指标函数(指标函数)，必须具有关于阶段指标的可分离形式(和、积或其他形式) ： ;◆常见有: ;相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策略的各段决策称为该过程上的最优决策，记为;8. 概念的关系。;四、最优化原理与动态规划的数学模型 1.最优化原理 (贝尔曼最优化原理) 若某一全过程最优策略为：;2.动态规划的数学模型(逆序法时) ;(8.3c);五、动态规划方法的基本步骤;(1)要能够正确地描述受控过程的变化特征。 (2)包含到达这个状态前的足够信息，且满足无后效性。 (3)要满足可知性。;3.正确地定义决策变量及各阶段的允许决策集合Dk(sk) 4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。;5.根据题意,正确地构造出指标函数，应满足下列性质： (1)可分性， (2)为了进行动态规划计算满足递推性，;阶段1;六、动态规划的分类;七、学习方法建议 第一步 先看问题，充分理解问题的条件、情况及求解目标。 第二步 分析针对该动态规划问题的“四大要素、一个方程”。 第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。;第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。 第五?? 对照自己的求解，分析成败。 ◆动态规划的四大要素 ① 状态变量及其可能集合 sk ? Sk ② 决策变量及其允许集合 xk ? Dk ③ 状态转移方程 sk+1= Tk (sk ,xk ) ④ 阶段收益 vk ( sk , xk )