《动态规划》PPT课件.ppt

《《动态规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《动态规划》PPT课件.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 动态规划动态规划1 1 多阶段决策过程及实例多阶段决策过程及实例2 2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程3 3 动态规划的最优性原理和最优性定理动态规划的最优性原理和最优性定理4 4 动态规划与静态规划的关系动态规划与静态规划的关系1 多阶段决策过程及实例多阶段决策过程及实例 在实际中，有一类问题可以看作是一活动的在实际中，有一类问题可以看作是一活动的过程，由于它的特殊性，可将过程分为若干个相过程，由于它的特殊性，可将过程分为若干个相互联系阶段，在每个阶段都要依据该阶段所处的互联系阶段，在每个阶段都要依据该阶段所处的状态作出相应的决策，该决策又引起该阶段状

2、态状态作出相应的决策，该决策又引起该阶段状态的转移，决定了下一阶段的状态，当每个阶段的的转移，决定了下一阶段的状态，当每个阶段的决策确定后，由这些决策组成一个决策序列，即决策确定后，由这些决策组成一个决策序列，即整个过程的一条活动路线。这类活动过程称为多整个过程的一条活动路线。这类活动过程称为多阶段决策过程。这类问题称为多阶段决策问题。阶段决策过程。这类问题称为多阶段决策问题。12n状态状态状态状态状态状态状态状态状态状态决策决策决策决策决策决策 例例1 最短路线问题最短路线问题 如如下下图图，是是一一线线路路网网络络，两两点点之之间间连连线线上上的的数数字字表表示示两两点点之之间间的的距距离

3、离（或或费费用用）试试求求一一条条由由A到到G的的铺铺管管线线路，使总距离为最短（或总费用最小）。路，使总距离为最短（或总费用最小）。1状态状态状态状态状态状态状态状态状态状态决策决策决策决策决策决策23456状态状态状态状态决策决策决策决策决策决策 B2 C3 D2 E3 F2 G B2 C3 D2 E3 F2 G AV6,6=3AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432V1,6=24V5,6=9V4,6=11V3,6=14V2,6=21V1,6=24 例例2 机器负荷分配问题机器负荷分配问题 某种机器可以在高低两

4、种不同负荷下进行生产。某种机器可以在高低两种不同负荷下进行生产。在在高高负负荷荷下下进进行行生生产产时时，产产品品的的年年产产量量g和和投投入入生生产的机器数产的机器数u的关系为的关系为 在低负荷下进行生产时，产品的年产量在低负荷下进行生产时，产品的年产量h和投入生产和投入生产的机器数的机器数u的关系为的关系为1状态状态状态状态状态状态状态状态状态状态决策决策决策决策决策决策2345状态状态决策决策决策决策 u1 u2 u3 u4 u5 s2 s3 s4 s5 s6 s1设：设：2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程 2.1 动态规划的基本概念动态规划的基本概念 1.阶段

5、阶段 把把过过程程依依据据一一定定的的时时间间和和空空间间特特征征恰恰当当地地划划分分为为若若干个相互联系的阶段，以便利用动态规划的方法求解。干个相互联系的阶段，以便利用动态规划的方法求解。描描述述阶阶段段的的变变量量称称为为阶阶段段变变量量，用用k表表示示。k=1，2，n 2.状态状态 每每个个阶阶段段开开始始所所处处的的自自然然状状况况或或客客观观条条件件，称称为为状状态。状态是不可控的，是客观存在的。态。状态是不可控的，是客观存在的。描描述述状状态态的的变变量量称称为为状状态态变变量量，用用sk表表示示。状状态态变变量量可可以以是是一一个个数数或或一一个个向向量量。状状态态变变量量sk的

6、的取取值值范范围围称称为可达状态集合，用为可达状态集合，用Sk表示。例表示。例1中，中，S3=C1,C2,C3,C4。状态变量的性质（无后效性）状态变量的性质（无后效性）如果某阶段的状态给定后，则该阶段以后的过程的如果某阶段的状态给定后，则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展，当前的状历史只能通过当前的状态去影响未来的发展，当前的状态是以往历史的总结，以后发展的依据。这个性质称为态是以往历史的总结，以后发展的依据。这个性质称为无后效性（即马尔科夫性）。无后效性（即马尔科夫性）。无

7、后效性的特征：在每个阶段所作的决策只依据当无后效性的特征：在每个阶段所作的决策只依据当前的状态，和以往的状态无关。前的状态，和以往的状态无关。在选取状态变量时，一定要保证状态变量具有无后在选取状态变量时，一定要保证状态变量具有无后效性，否则不能利用动态规划的方法求解。效性，否则不能利用动态规划的方法求解。3.决策决策 在在每每个个阶阶段段所所作作的的决决定定或或选选择择称称为为决决策策或或控控制制。决决策依据与当前状态，又决定下一阶段的状态。策依据与当前状态，又决定下一阶段的状态。描描述述决决策策的的变变量量称称为为决决策策变变量量，用用uk(sk)表表示示。他他是是状状态态变变量量sk的的函

8、函数数。决决策策变变量量的的取取值值范范围围称称为为容容许许决决策集合，用策集合，用Dk(sk)表示。表示。在例在例1中中 D1(A)=B1,B2 D2(B1)=C1,C2,C3，D2(B2)=C2,C3,C4 D4(D1)=E2,E3 在例在例2中中 D1(s1)=u1(s1)|0u1(s1)s1 D2(s2)=u2(s2)|0u2(s2)s2 Dk(sk)=uk(sk)|0uk(sk)sk 4.策略策略 按一定顺序排列的决策序列集合称为策略。按一定顺序排列的决策序列集合称为策略。由由过过程程的的第第k阶阶段段开开始始到到终终止止状状态态为为止止的的过过程程，称称为为问题的后部子过程（或称为

9、问题的后部子过程（或称为k子过程）。子过程）。由由k子子过过程程的的每每个个阶阶段段的的决决策策函函数数组组成成的的决决策策函函数数序序列列集集合合uk(sk),uk+1(sk+1),un(sn)称称为为k子子过过程程策策略略，简称为子策略，记为简称为子策略，记为pk,n(sk)，即，即 pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)当当k=1时时,此决策函数序列称为全过程的一个策略，此决策函数序列称为全过程的一个策略，简称为策略，记为简称为策略，记为p1,n(s1)。即。即 p1,n(sk)=u1(s1),u2(s2),un(sn)策略的取值范围称为容许策略集合，用策略的

10、取值范围称为容许策略集合，用P表示。表示。在在P中中,使指标函数达到最优的策略称为最优策略。使指标函数达到最优的策略称为最优策略。例例1中中，每每一一条条线线路路就就是是一一个个策策略略，容容许许策策略略集集合合中中有有48个策略。个策略。A到到G的最短线路就是最优策略。的最短线路就是最优策略。5.状态转移方程状态转移方程 若给定第若给定第k个阶段状态变量个阶段状态变量sk的值，该阶段的决策变的值，该阶段的决策变量量uk的值一经确定，第的值一经确定，第k+1个阶段的状态变量个阶段的状态变量sk+1的值也的值也就完全确定了，即就完全确定了，即sk+1是是sk和和 uk的函数，记为的函数，记为 s

11、k+1=Tk(sk,uk)该该函函数数描描述述由由第第k个个阶阶段段到到第第k+1个个阶阶段段的的状状态态转转移移规律规律,称为状态转移方程。称为状态转移方程。例例1中，状态转移方程为中，状态转移方程为 例例2 中，状态转移方程为中，状态转移方程为 6.指标函数和最优值函数指标函数和最优值函数 用用来来衡衡量量过过程程和和子子过过程程（策策略略和和子子策策略略）优优劣劣的的一一种种数数量量指指标标，称称为为指指标标函函数数。它它是是定定义义在在全全过过程程和和后后部部子过程上的数量函数，用子过程上的数量函数，用Vk,n表示。即表示。即 指标函数的性质：指标函数的性质：动动态态规规划划中中的的指

12、指标标函函数数应应具具有有可可分分离离性性，并并满满足足地地推关系，推关系，常见指标函数的形式常见指标函数的形式 （1）过过程程和和子子过过程程的的指指标标函函数数可可分分解解为为它它所所包包含含的的阶段的指标的和，即阶段的指标的和，即 （2）过过程程和和子子过过程程的的指指标标函函数数可可分分解解为为它它所所包包含含的的阶段的指标的积，即阶段的指标的积，即指标函数的最优值称为最优值函数，记为指标函数的最优值称为最优值函数，记为它表示最优的它表示最优的k子策略子策略p*k,n(sk)对应的指标函数值。对应的指标函数值。2.1 动态规划的基本思想和基本方程动态规划的基本思想和基本方程 最最短短路

13、路线线的的特特征征：如如果果由由起起点点A经经过过P和和H到到达达G是是一条由一条由A到到G的最短路线，则由的最短路线，则由P到到G的最短路线是的最短路线是 P H G即最短路线的子线路是最短路线。即最短路线的子线路是最短路线。根根据据最最短短路路线线的的特特征征，求求A到到G的的最最短短路路线线，可可以以采采用用由由后后向向前前逐逐步步递递推推的的方方法法，从从最最后后一一个个阶阶段段开开始始，求求出每个点到出每个点到G的最短路线，最后出的最短路线，最后出A到到G的最短路线。的最短路线。P1 H1 GP2 H2 GA12158318AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G

14、531368766835338422133355266432437590AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437597680AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109120AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842213335526643243759768131091213160AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766

15、835338422133355266432437597681310912131618A B1 C2 D1 E2 F2 G最短路线为：最短路线为：最优策略为：最优策略为：P*=0 该该题题中中，在在求求解解过过程程中中，利利用用了了第第k阶阶段段与与第第k+1阶阶段之间的递推关系：段之间的递推关系：一一般般情情况况，第第k阶阶段段与与第第k+1阶阶段段之之间间的的递递推推关关系系式式可表示为：可表示为：该递推关系式称为动态规划的基本方程。该递推关系式称为动态规划的基本方程。边界条件边界条件 边界条件边界条件 即即一般情况，第一般情况，第k阶段与第阶段与第k+1阶段之间的递推关系阶段之间的递推关系

16、 动态规划模型的建立步骤：动态规划模型的建立步骤：1.将过程恰当地划分为阶段；将过程恰当地划分为阶段；2.正正确确选选择择状状态态变变量量sk，既既要要描描述述过过程程的的演演变变，又又要满足无后效性；要满足无后效性；3.确定决策变量确定决策变量uk及及uk的容许决策集合的容许决策集合Dk(sk);4.写出状态转移方程写出状态转移方程 sk+1=Tk(sk,uk);5.写出指标函数写出指标函数Vk,n(sk,uk,sk+1,sn),应满足：应满足：（1）是定义在全过程和后部子过程上数量函数；）是定义在全过程和后部子过程上数量函数；（2）具有可分离性，并满足递推关系；）具有可分离性，并满足递推关

17、系；（3）函数）函数 对于变量对于变量 要严格单调；要严格单调；6.写出基本方程。写出基本方程。1状态状态状态状态状态状态状态状态状态状态决策决策决策决策2n-1n状态状态决策决策决策决策 u1 u2 un-1 un s2 s3 sn-1 sn sn+1 s1 D(s1)D(s2)D(sn-1)D(sn)转移方程转移方程 指标函数指标函数基本方程基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109121316180AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668

18、3533842213335526643216151313151113681095301813标号法标号法3 动态规划的最优性原理和最动态规划的最优性原理和最优性定理优性定理 动态规划的最优性原理动态规划的最优性原理 最最优优策策略略的的子子策策略略必必是是最最优优策策略略。它它是是最最优优策策略略的必要条件，而不是充要条件。的必要条件，而不是充要条件。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109121316180动态规划的最优性定理动态规划的最优性定理4 动态规划与静态规划的关系动态规划与静态

19、规划的关系 动动态态规规划划、线线性性规规划划和和非非线线性性规规划划都都是是属属于于数数学学规规划划的的范范畴畴，本本质质都都是是求求极极值值问问题题，都都是是利利用用迭迭代代法法逐逐步步求求解解。线线性性规规划划迭迭代代中中的的每每一一步步是是就就问问题题的的整整体体加加以以改改善善。动动态态规规划划递递推推中中的的每每一一步步是是问问题题局局部部最最优优解解向向整整体体最最优优解解的的靠靠近近。对对于于某某些些静静态态规规划划问问题题可可以以引引入入某某些些因因素，使之转化为动态规划问题。素，使之转化为动态规划问题。静态规划问题静态规划问题动态规划问题动态规划问题解：将该静态规划转化为动

20、态规划如下：解：将该静态规划转化为动态规划如下：1状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1s10 x2s2 x3=s3s2=s1-x1 s3=s2-x2 s4=s3-x3=0 s1=c1状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1s10 x2s2 X3=s3s2=s1-x1 s3=s2-x2 s4=s3-x3=0 s1=c解：将该静态规划转化为动态规划如下：解：将该静态规划转化为动态规划如下：1状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1c-s10 x2c-s2 x3=c-s3s2=s1+x1 s3=s2+x2 s4=

21、s3+x3=c s1=01状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1c-s10 x2c-s2 X3=c-s3s2=s1+x1 s3=s2+x2 s4=s3+x3=c s1=0解：将该静态规划转化为动态规划如下：解：将该静态规划转化为动态规划如下：1状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1s1/30 x2s2/20 x3s3s2=s1-3x1 s3=s2-2x2 s4=s3-x30 s1=91状态状态状态状态状态状态状态状态决策决策决策决策决策决策230 x1s1/30 x2s2/20 x3s3 s4=s3-x30 s1=9s2=s1-3x1 s3=s2-2x2