资源描述：
《最优化原理与动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二节最优化原理与动态规划的数学模型◆理解动态规划的基本概念和基本原理一、动态规划方法导引1.全枚举法或穷举法。共有18条可能路线，进行比较，求得最优路线Q→A3→B1→C1→T。QTA1A2A3B1B2B3C1C2243746424425146333342.“局部最优路径”法：选择当前最短途径，“逢近便走”。所取决策必是Q→A1→B2→C2→T，全程长度是13。QTA1A2A3B1B2B3C1C224374642442514633334◆全枚举法计算工作量将会十分庞大。◆局部最优求出的解不一定是最优解。3.动态规划方法就是从终点逐段向始点方向寻找最短
2、路线的方法。解题步骤如下：●把问题划分为几个阶段。●按阶段顺序首先考虑最后阶段如第四阶段的最优决策，也就是走哪条路线最短。●按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各初始点的最优决策即可。◆用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，每一阶段的计算都要利用上一阶段的计算结果，因而减少了很多计算量。阶段数愈多，这种效果愈明显。二、动态规划解题标号法：最短路径：Q→A3→B1→C1→TQTA1A2A3B1B2B3C1C224374642442514633334阶段1阶段2阶段3阶段40，T3,T4,
3、T4,C17,C26,C111,B1,B28,B18,B111,A3三、动态规划的基本概念。1.阶段(stage)和阶段变量。把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。QTA1A2A3B1B2B3C1C224374642442514633334用以描述阶段的变量叫作阶段变量，一般以k表示阶段量．阶段数k的编号法有两种：(1)顺序编号；(2)逆序编号法。QTA1A2A3B1B2B3C1C2243746424425146333342.状态(state)、状态变量和可能状态集(1)状态与状态变量。表示每个阶段开始所处的自
4、然状况或客观条件。QTA1A2A3B1B2B3C1C224374642442514633334(2)动态规划维数。(3)可能状态集：用S(sk)表示。QTA1A2A3B1B2B3C1C2243746424425146333343.决策(decision)、决策变量和允许决策集合(1)决策。表示当过程处于某一阶段的某个状态，可以作出不同的决定（选择），从而确定下一阶段的状态。QTA1A2A3B1B2B3C1C224374642442514633334(2)决策变量:xk=xk(sk)决策变量xk(sk)的允许决策集用Dk(sk)表示,xk(sk)∈Dk(
5、sk)允许决策集合实际是决策的约束条件。QTA1A2A3B1B2B3C1C2243746424425146333344.策略和子策略(Policy)（1）全过程策略指具有n个阶段全部过程，简称策略。表示为{x1(s1),x2(s1),…,xn(sn)}。k后部子过程策略,表示为pk(xk)QTA1A2A3B1B2B3C1C224374642442514633334(2)允许策略集合记作P。最优策略:从允许策略集中，找出的具有最优效果的策略。QTA1A2A3B1B2B3C1C2243746424425146333345.状态转移方程(状态转移律)：多阶段
6、决策过程的发展就是用阶段状态的相继演变来描述的。或简写为从上阶段的某一状态值到下阶段某一状态值的转移规律成为状态转移律6.指标函数(1)阶段指标函数(也称阶段收益)（是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量。）vk(sk,xk)简记为vk。(2)过程指标函数(指标函数)。(它所包含的各阶段指标函数的函数。）Vk,n(sk,xk,sk+1,xk+1,…,sn,xn)。简记为Vk,n。◆动态规划求解的问题的过程指标函数(指标函数)，必须具有关于阶段指标的可分离形式(和、积或其他形式)：表示某种运算，可为加、减、乘、除、开方等。◆常见
7、有:和相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策略的各段决策称为该过程上的最优决策，记为7.最优指标函数：fk(sk)有简记为8.概念的关系。状态sk阶段kT(sk,xk)决策xk(sk)vk(sk,xk)状态sk+1阶段k+1T(sk+1,xk+1)决策xk+1(sk+1)vk+1(sk+1,xk+1)状态sk+2四、最优化原理与动态规划的数学模型1.最优化原理(贝尔曼最优化原理)若某一全过程最优策略为：则最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策
8、必构成最优决策。2.动态规划的数学模型(逆序法时)(8.3a)(8.3b)(8.3c)(8.3
