动态规划基本方法.ppt

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

1、动态规划基本方法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 例例2 机器负荷分配问题机器负荷分配问题 某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产产品品的的年年产产量量g和和投投入入生生产产的的机机器器数数量量u的的关关系系为为 gg(u)，这这时时机机器器的的年年完完好好率率为为a（0a1)；在在低低负负荷荷下下生生产产时时，产产品品的的年年产产量量h和和投投入入生生产产

2、的的机机器器数数量量v的的关关系系为为hh(v)，这这时时机机器器的的年年完完好好率率为为b（ab1）。假假定定开开始始生生产产时时完完好好的的机机器器数数量量为为s，要要求求制制定定一一个个五五年年计计划划，在在每每年年开开始始时时决决定定机机器器在在两两种种不不同同负负荷荷下下生生产产的的数数量量，使使五五年内产品的总产量最高年内产品的总产量最高。第第1年年第第1阶段阶段第第2年年第第2阶段阶段第第3年年第第3阶段阶段第第4年年第第4阶段阶段第第5年年第第5阶段阶段 多阶段决策问题和前面遇到的决策问题不同，它多阶段决策问题和前面遇到的决策问题不同，它是和时间有关的，状态（所处自然状况和客观

3、条件）是和时间有关的，状态（所处自然状况和客观条件）是随着决策进程而变化的，故有是随着决策进程而变化的，故有“动态动态”的含义。的含义。与时间有关的活动过程称为动态过程，处理它的与时间有关的活动过程称为动态过程，处理它的方法称为动态规划。而与时间无关的活动过程称为静方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的处理方法称为静态规划。态过程，相应的处理方法称为静态规划。以以上上两两个个问问题题都都可可以以划划分分为为先先后后多多个个决决策策阶阶段段。这类问题就称为多阶段决策问题。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：多阶段决策问题的过程如下图所示：阶段阶段1

4、状态状态1决策决策1阶段阶段2状态状态2决策决策2阶段阶段n状态状态n决策决策n状态状态3状态状态n+1第第2 2节节 动态规划的基本概念和基本方程动态规划的基本概念和基本方程 （1）阶段（阶段（stage）（2 2）状态（状态（statestate）把所研究的决策问题，按先后顺序划分为若干相把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。互联系的决策步骤，以便按一定的次序进行求解。这这些些决策步骤就称为阶段。决策步骤就称为阶段。描述阶段的变量称阶段变量，常用描述阶段的变量称阶段变量，常用k表示。表示。状态表示每个阶段开始时所处的自然状况或客观状态表示每个

5、阶段开始时所处的自然状况或客观条件条件。它描述了影响决策的因素随决策进程的变化情它描述了影响决策的因素随决策进程的变化情况况。它既是前面阶段所作决策的结果，又是本阶段作它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。出决策的出发点和依据。描述状态的变量称状态变量，第描述状态的变量称状态变量，第k阶段的状态变量阶段的状态变量常用常用sk表示。通常，第一阶段的状态变量表示。通常，第一阶段的状态变量s1是确定的是确定的，称初始状态。称初始状态。2.1 2.1 动态规划的基本概念动态规划的基本概念动态规划的基本概念动态规划的基本概念 描述决策的变量称决策变量，第描述决策的变量称决策变量

6、，第k阶段的决策变阶段的决策变量常用量常用uk表示。决策变量的取值会受到状态变量表示。决策变量的取值会受到状态变量的的制制约，被限制在某一范围之内约，被限制在某一范围之内，称为允许决策集，记为称为允许决策集，记为Dk(sk)。决策表示在某一阶段处于某种状态时，决策者在决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。若干种方案中作出的选择决定。（3）决策（决策（decision）（4）策略（策略（policy）把从第一阶段开始到最后阶段终止的整个决策过把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第程，称为问题的全过程；而把从第k阶段开始到最后阶阶段

7、开始到最后阶段终止的决策过程，或称为段终止的决策过程，或称为k子过程。子过程。在在全全过过程程上上，各各阶阶段段的的决决策策按按顺顺序序排排列列组组成成的的决决策策序序列列p1,n=u1,u2,un称称为为全全过过程程策策略略，简简称称策策略略；而而在在k-子子过过程程上上的的决决策策序序列列pk,n=uk,uk+1,un称称为为k-子过程策略，也简称子策略。子过程策略，也简称子策略。（5）状态转移方程）状态转移方程 若第若第k阶段的状态变量值为阶段的状态变量值为sk，当决策变量当决策变量uk的取的取值决定后，下一阶段状态变量值决定后，下一阶段状态变量sk+1的值也就完全确定了的值也就完全确定

8、了，即即sk+1的值对应于的值对应于sk和和uk的值。这种对应关系记为的值。这种对应关系记为sk+1=Tk(sk,uk)，称为状态转移方程。称为状态转移方程。状状态态转转移移方方程程描描述述了了由由一一个个阶阶段段的的状状态态到到下下一一阶阶段的状态的演变规律。段的状态的演变规律。（6）指标函数和最优值函数）指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段阶段指标函数是对某一阶段上（上（由由状态和决策产状态和决策产生的）目标损益值的度量，用生的）目标损益值的度量，用vk(sk,uk)表示。表示。过过程程指指标标函函数

9、数是是指指过过程程所所包包含含的的各各阶阶段段上上（由由状状态和决策所产生的）总的目标损益值，记为态和决策所产生的）总的目标损益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un)动态规划所要求的过程指标函数应具有可分离性，动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数。即可表达为它所包含的各阶段指标函数的函数。常见的两种过程指标函数形式是：常见的两种过程指标函数形式是：各阶段指标函数的和各阶段指标函数的和 Vk,n=vj(sj,uj)；各阶段指标函数的积各阶段指标函数的积 Vk,n=vj(sj,uj)。把过程指标函数把过程指标函数Vk

10、,n对对k-子过程策略子过程策略pk,n求最优，求最优，得到一个关于状态得到一个关于状态sk的函数，称为（的函数，称为（k-子过程）子过程）最优最优值函数，记为值函数，记为fk(sk)。即即 fk(sk)opt Vk,n(sk,uk,sn,un)uk,un 式中的式中的“opt”（optimization）可根据具体问题而可根据具体问题而取取min或或max。2.2 2.2 动态规划的基本方程动态规划的基本方程动态规划的基本方程动态规划的基本方程 动态动态规划的最优性原理（贝尔曼原理）：作为整规划的最优性原理（贝尔曼原理）：作为整个过程的最优策略具有这样的性质，即无论过去的状个过程的最优策略具

11、有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，最优策略的下的诸决策必须构成最优策略。简言之，最优策略的子策略也必是最优的。子策略也必是最优的。根据此原理，要求全过程最优策略，可从子过程根据此原理，要求全过程最优策略，可从子过程策略的最优化入手。对于过程指标函数是阶段指标函策略的最优化入手。对于过程指标函数是阶段指标函数和的形式，考虑数和的形式，考虑k-子过程最优值函数子过程最优值函数fk(sk):则有递推方程：则有递推方程：还需有边界条件，一般取：还需有边界条件，一般取：于是，得基本方

12、程于是，得基本方程（k=n,n-1,2,1）利用基本方程，由后向前逆序递推，就可实现对利用基本方程，由后向前逆序递推，就可实现对动态规划问题的求解。动态规划问题的求解。类似地，对于过程指标函数是阶段指标函数积的类似地，对于过程指标函数是阶段指标函数积的形式，其基本方程为：形式，其基本方程为：（k=n,n-1,2,1）例例 最短路问题最短路问题437597681310912131618于是得于是得A到到G的最短距离为的最短距离为18，最短路线为：，最短路线为：AB1C2D1E2F2Gk=6时：时：f6(F1)=4 f6(F2)=3k=5时：时：f5(E1)=7 f5(E2)=5 f5(E3)=9

13、k=4时：时：f4(D1)=7 f4(D2)=6 f4(D3)=8k=3时：时：f3(C1)=13 f3(C2)=10 f3(C3)=9 f3(C4)=8k=2时：时：f2(B1)=13 f2(B2)=16;k=1时：时：f1(A)=18 现在把动态规划法的步骤归纳如下：现在把动态规划法的步骤归纳如下：（1）将将所所研研究究问问题题的的决决策策过过程程划划分分为为n个个恰恰当当的的阶阶段，段，k=1,2,n；（2）合理正确地合理正确地选择状态变量选择状态变量sk，并确定初始状态并确定初始状态s1的值；的值；（3）确定决策变量）确定决策变量uk及允许决策集及允许决策集Dk(sk)；（4）给出状态

14、转移方程给出状态转移方程 sk+1=Tk(sk,uk)；（5）给给出出满满足足要要求求的的过过程程指指标标函函数数Vk,n及及相相应应的的最最优值函数；优值函数；（6）写出递推方程和边界条件，建立基本方程；）写出递推方程和边界条件，建立基本方程；（7）按照基本方程递推求解。按照基本方程递推求解。以以上上步步骤骤是是动动态态规规划划法法处处理理问问题题的的基基本本步步骤骤，其其中的前六步是建立动态规划模型的步骤。中的前六步是建立动态规划模型的步骤。例：机器负荷问题例：机器负荷问题 某种机器可以在高低两种不同的负荷下进行生产。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的

15、年产量在高负荷下进行生产时，产品的年产量g和投入生产的和投入生产的机器数量机器数量u的关系为的关系为 g=8u,这时机器的年完好率为这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产的机器和投入生产的机器数量数量v的关系为的关系为h=5v,这时机器的年完好率为这时机器的年完好率为b=0.9。假。假定开始生产时完好的机器数量为定开始生产时完好的机器数量为1000，要求制定一个，要求制定一个五年计划，在每年开始时决定机器在两种不同负荷下五年计划，在每年开始时决定机器在两种不同负荷下生产的数量，使五年产品的总产量最高。生产的数量，使五年产品的总产

16、量最高。按年数划分为按年数划分为5个阶段，个阶段，k=1,2,3,4,5。取第取第k年初完好的机器数年初完好的机器数sk为状态变量，则为状态变量，则s1=1000。解：解：取第取第k年投入高负荷的机器数年投入高负荷的机器数xk为决策变量，为决策变量，0 xksk 状态转移方程状态转移方程sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk 指标函数为指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj)基本方程为基本方程为 fk(sk)max 5sk+3xk+fk+1(sk+1)k=5,4,3,2,1 0 xksk f6(s6)0当当k=5时：时：f5(s5)max5s

17、5+3x5+f6(s6)=max5s5+3x5 0 x5s5 0 x5s5=8s5 (x5*=s5)当当k=4时：时：f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4)0 x4s4 0 x4s4 =max12.2s4+1.4x4 0 x4s4=13.6s4 (x4*=s4)当当k=3时：时：f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3)0 x3s3 0 x3s3 =max17.24s3+0.28x3 0 x3s3当当k=2时：时：f2(s2)=max5s2+3x2+17.52s3=max5s2+

18、3x2+17.52(0.9s2-0.2x2)0 x2s2 0 x2s2 =max20.77s2-0.504x2 0 x2s2当当k=1时：时：f1(1000)=23.7 1000=23700s1=1000 x1*=0s1-x1*=1000=17.52s3 (x3*=s3)=20.77s2 (x2*=0)f1(s1)=max5s1+3x1+20.77s2 0 x1s1=23.7s1 (x1*=0)s2=900 x2*=0s2-x2*=900s3=810 x3*=810s3-x3*=0s4=567x4*=567s4-x4*=0s5=397x5*=397s5-x5*=0第第4 4节节 动态规划和静态

19、规划的关系动态规划和静态规划的关系 静态规划所研究的问题是与时间无关的，而动态静态规划所研究的问题是与时间无关的，而动态规划所研究的问题是和时间有关的。对于某些静态规规划所研究的问题是和时间有关的。对于某些静态规划问题，也可人为地引入时间因素，把它看做一个按划问题，也可人为地引入时间因素，把它看做一个按阶段进行的动态规划问题，用动态规划的方法求解。阶段进行的动态规划问题，用动态规划的方法求解。例例 用动态规划法求解用动态规划法求解 max F=4x12-x22+2x32+12 3x1+2x2+x39 xi0 i=1,2,3解：解：按变量划分为按变量划分为3个阶段，个阶段，k=1,2,3 取取k

20、阶段初常数项的剩余量阶段初常数项的剩余量sk为状态变量，为状态变量，s1=9 取取xk为决策变量，为决策变量，0 xksk ak（a1=3,a2=2,a3=1）状态转移方程为状态转移方程为 sk+1=sk-akxk 指标函数为指标函数为 Vk,n=vj(xj)（v1(x1)=4x12,v2(x2)=-x22,v3(x3)=2x32+12）基本方程为基本方程为 fk(sk)=max vk(xk)+fk+1(sk+1)k=3,2,1 0 xksk ak f4(s4)=0当当k=3时：时：f3(s3)=max 2x32+12+0=2s32+12 (x3*=s3)0 x3s3当当k=2时：时：f2(s

21、2)=max-x22+2s32+12=max-x22+2(s2-2x2)2+12 0 x2s2 2 0 x2s2 2 =max7x22-8s2x2+2s22+12 0 x2s2 2=2s22+12 (x2*=0)当当k=1时：时：f1(s1)=max4x12+2s22+12=max4x12+2(s1-3x1)2+12 0 x1s1 3 0 x1s1 3 =max22x12-12s1x1+2s12+12 0 x1s1 3=2s12+12 (x1*=0)F*=f1(9)=2 92+12=174s1=9x1*=0s2=9x2*=0s3=9x3*=9 例例 用动态规划法求解用动态规划法求解 max z

22、=x1.x22.x3 x1+x2+x3=c xi0 i=1,2,3解：解：按变量划分为按变量划分为3个阶段，个阶段，k=1,2,3 取取k阶段初常数项的剩余量阶段初常数项的剩余量sk为状态变量，为状态变量，s1=c 取取xk为决策变量，为决策变量，0 xksk（k=1,2）,x3=s3 状态转移方程为状态转移方程为 sk+1=sk-xk 指标函数为指标函数为 Vk,n=vj(xj)（v1(x1)=x1,v2(x2)=x22,v3(x3)=x3）基本方程为基本方程为 fk(sk)=max vk(xk)*fk+1(sk+1)k=2,1 0 xksk f3(s3)=s3 （x3*=s3）当当k=2时

23、时:f2(s2)=maxv2(x2)s3=maxx22(s2-x2)0 x2s2 0 x2s2 当当k=1时时:z*=f1(c)=1/64c4 s1=cx1*=1/4cs2=3/4cx2*=1/2cs3=1/4cx3*=1/4c设设h2(s2,x2)=x22(s2-x2),且令且令dh2(s2,x2)/dx2=0解得解得:x2=0(舍去舍去),x2=2/3 s2于是于是 f2(s2)=4/27 s23 (x2*=2/3s2)f1(s1)=maxv1(x1)4/27 s23=maxx1 4/27(s1-x1)3 0 x2s2 0 x2s2 设设h1(s1,x1)=x1 4/27(s1-x1)3,且令且令dh1(s1,x1)/dx1=0解得解得:x1=s1(舍去舍去),x1=1/4 s1于是于是 f1(s1)=1/64 s14 (x1*=1/4 s1)