《动态规划》PPT课件.ppt

第五章动态规划,1多阶段决策过程及实例2动态规划的基本概念和基本方程3动态规划的最优性原理和最优性定理4动态规划与静态规划的关系,1多阶段决策过程及实例,在实际中，有一类问题可以看作是一活动的过程，由于它的特殊性，可将过程分为若干个相互联系阶段，在每个阶段都要依据该阶段所处的状态作出相应的决策，该决策又引起该阶段状态的转移，决定了下一阶段的状态，当每个阶段的决策确定后，由这些决策组成一个决策序列，即整个过程的一条活动路线。这类活动过程称为多阶段决策过程。这类问题称为多阶段决策问题。,1,2,n,状态,状态,状态,状态,状态,决策,决策,决策,例1最短路线问题如下图，是一线路网络，两点之间连线上的数字表示两点之间的距离（或费用）试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。,1,状态,状态,状态,状态,状态,决策,决策,决策,2,3,4,5,6,状态,状态,决策,决策,决策,B2,C3,D2,E3,F2,G,B2,C3,D2,E3,F2,G,A,V6,6=3,V1,6=24,V5,6=9,V4,6=11,V3,6=14,V2,6=21,V1,6=24,例2机器负荷分配问题某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数u的关系为,在低负荷下进行生产时，产品的年产量h和投入生产的机器数u的关系为,1,状态,状态,状态,状态,状态,决策,决策,决策,2,3,4,5,状态,决策,决策,u1,u2,u3,u4,u5,s2,s3,s4,s5,s6,s1,设：,2动态规划的基本概念和基本方程,2.1动态规划的基本概念1.阶段把过程依据一定的时间和空间特征恰当地划分为若干个相互联系的阶段，以便利用动态规划的方法求解。描述阶段的变量称为阶段变量，用k表示。k=1，2，n2.状态每个阶段开始所处的自然状况或客观条件，称为状态。状态是不可控的，是客观存在的。描述状态的变量称为状态变量，用sk表示。状态变量可以是一个数或一个向量。状态变量sk的取值范围称为可达状态集合，用Sk表示。例1中，S3=C1,C2,C3,C4。,状态变量的性质（无后效性）如果某阶段的状态给定后，则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展，当前的状态是以往历史的总结，以后发展的依据。这个性质称为无后效性（即马尔科夫性）。无后效性的特征：在每个阶段所作的决策只依据当前的状态，和以往的状态无关。在选取状态变量时，一定要保证状态变量具有无后效性，否则不能利用动态规划的方法求解。,3.决策在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态，又决定下一阶段的状态。描述决策的变量称为决策变量，用uk(sk)表示。他是状态变量sk的函数。决策变量的取值范围称为容许决策集合，用Dk(sk)表示。在例1中D1(A)=B1,B2D2(B1)=C1,C2,C3，D2(B2)=C2,C3,C4D4(D1)=E2,E3在例2中D1(s1)=u1(s1)|0u1(s1)s1D2(s2)=u2(s2)|0u2(s2)s2Dk(sk)=uk(sk)|0uk(sk)sk,4.策略按一定顺序排列的决策序列集合称为策略。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为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)策略的取值范围称为容许策略集合，用P表示。在P中,使指标函数达到最优的策略称为最优策略。例1中，每一条线路就是一个策略，容许策略集合中有48个策略。A到G的最短线路就是最优策略。,5.状态转移方程若给定第k个阶段状态变量sk的值，该阶段的决策变量uk的值一经确定，第k+1个阶段的状态变量sk+1的值也就完全确定了，即sk+1是sk和uk的函数，记为sk+1=Tk(sk,uk)该函数描述由第k个阶段到第k+1个阶段的状态转移规律,称为状态转移方程。,例1中，状态转移方程为,例2中，状态转移方程为,6.指标函数和最优值函数用来衡量过程和子过程（策略和子策略）优劣的一种数量指标，称为指标函数。它是定义在全过程和后部子过程上的数量函数，用Vk,n表示。即,指标函数的性质：动态规划中的指标函数应具有可分离性，并满足地推关系，,常见指标函数的形式（1）过程和子过程的指标函数可分解为它所包含的阶段的指标的和，即,（2）过程和子过程的指标函数可分解为它所包含的阶段的指标的积，即,指标函数的最优值称为最优值函数，记为,它表示最优的k子策略p*k,n(sk)对应的指标函数值。,2.1动态规划的基本思想和基本方程最短路线的特征：如果由起点A经过P和H到达G是一条由A到G的最短路线，则由P到G的最短路线是PHG即最短路线的子线路是最短路线。,根据最短路线的特征，求A到G的最短路线，可以采用由后向前逐步递推的方法，从最后一个阶段开始，求出每个点到G的最短路线，最后出A到G的最短路线。,P1H1G,P2H2G,A,12,15,8,3,18,4,3,7,5,9,0,4,3,7,5,9,7,6,8,0,4,3,7,5,9,7,6,8,13,10,9,12,0,4,3,7,5,9,7,6,8,13,10,9,12,13,16,0,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,AB1C2D1E2F2G,最短路线为：,最优策略为：,P*=,0,该题中，在求解过程中，利用了第k阶段与第k+1阶段之间的递推关系：,一般情况，第k阶段与第k+1阶段之间的递推关系式可表示为：,该递推关系式称为动态规划的基本方程。,边界条件,边界条件,即,一般情况，第k阶段与第k+1阶段之间的递推关系,动态规划模型的建立步骤：1.将过程恰当地划分为阶段；2.正确选择状态变量sk，既要描述过程的演变，又要满足无后效性；3.确定决策变量uk及uk的容许决策集合Dk(sk);4.写出状态转移方程sk+1=Tk(sk,uk);5.写出指标函数Vk,n(sk,uk,sk+1,sn),应满足：（1）是定义在全过程和后部子过程上数量函数；（2）具有可分离性，并满足递推关系；,（3）函数对于变量要严格单调；,6.写出基本方程。,1,状态,状态,状态,状态,状态,决策,决策,2,n-1,n,状态,决策,决策,u1,u2,un-1,un,s2,s3,sn-1,sn,sn+1,s1,D(s1),D(s2),D(sn-1),D(sn),转移方程,指标函数,基本方程,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,0,16,15,13,13,15,11,13,6,8,10,9,5,3,0,18,13,标号法,3动态规划的最优性原理和最优性定理,动态规划的最优性原理最优策略的子策略必是最优策略。它是最优策略的必要条件，而不是充要条件。,动态规划的最优性定理,4动态规划与静态规划的关系,动态规划、线性规划和非线性规划都是属于数学规划的范畴，本质都是求极值问题，都是利用迭代法逐步求解。线性规划迭代中的每一步是就问题的整体加以改善。动态规划递推中的每一步是问题局部最优解向整体最优解的靠近。对于某些静态规划问题可以引入某些因素，使之转化为动态规划问题。,静态规划问题,动态规划问题,解：将该静态规划转化为动态规划如下：,1,状态,状态,状态,状态,决策,决策,决策,2,3,0x1s1,0x2s2,x3=s3,s2=s1-x1,s3=s2-x2,s4=s3-x3=0,s1=c,1,状态,状态,状态,状态,决策,决策,决策,2,3,0x1s1,0x2s2,X3=s3,s2=s1-x1,s3=s2-x2,s4=s3-x3=0,s1=c,解：将该静态规划转化为动态规划如下：,1,状态,状态,状态,状态,决策,决策,决策,2,3,0x1c-s1,0x2c-s2,x3=c-s3,s2=s1+x1,s3=s2+x2,s4=s3+x3=c,s1=0,1,状态,状态,状态,状态,决策,决策,决策,2,3,0x1c-s1,0x2c-s2,X3=c-s3,s2=s1+x1,s3=s2+x2,s4=s3+x3=c,s1=0,解