优化原理与动态规划.ppt

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