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