二最优化原理与动态规划.pptx

一、动态规划方法导引
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)