运筹学第八章动态规划

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第八章 动态规划,引 言,动态规划是解决,多阶段决策过程,最优化的一种方法。,该方法是由美国数学家,贝尔曼,（,R.E.Bellman,）等人在,20,世,纪,50,年代初提出的。并成功地解决了生产管理、工程技术等方,面的许多问题，从而建立了运筹学的一个新的分支，即动态规,划。,Bellman,在,1957,年出版了,Dynamic Programming,一,书，是动态规划领域中的第一本著作。,动态规划与其他规划方法的不同之处在于：,动态规划是求解某类问题（,多阶段决策问题,）的一种方法，,是考察问题的一种途径，而不是一种特定算法。,因此，它不像线性规划那样有一个标准的数学表达式和明确,定义的一组（算法）规则，而必须对具体问题进行具体分析处,理。因此，学习动态规划时，除对基本概念和基本方法正确理解,外，还应在一定经验积累基础上，以丰富的想像力去建立模型，,用创造性的技巧去求解。,提 纲,1,动态规划实例,2,动态规划的基本概念,3,动态规划的基本思想与基本原理,4,逆序解法与顺序解法,学习目标：,1,明确什么是,多阶段的决策问题,，特别要注意没有明显,的时段背景的问题如何化归为多阶段的决策问题。,1,动态规划实例,P156,例,2,机器负荷分配问题（时间阶段问题）,设有某种机器设备，用于完成两类工作,A,和,B,。若,第,k,年初完好,机器的数量为,x,k,，若以数量,u,k,用于,A,，余下的（,x,k,u,k,）用于,工作,B,，则该年的预期收入为,g,(,u,k,)+,h,(,x,k,u,k,),。这里,g,(,u,k,),和,h,(,x,k,u,k,),是已知函数，且,g,(0)=,h,(0)=0,。,又机器设备在使用中会有损坏，设机器用于工作,A,时，一年后,能继续使用的完好机器数占年初投入量的,70%,；若用于工作,B,时，一年后能继续使用的完好机器数占年初投入量的,90%,。则在,下一年初,能继续用于,A,、,B,工作的设备数为,x,k,+1,=0.7,u,k,+0.9(,x,k,u,k,),。,设第,1,年初完好的机器总数为,1000,台，问在连续,5,年内每年应如,何分配用于,A,、,B,两项工作的机器数，使,5,年的总收益为最大。,1,动态规划实例,相应的问题称为,多阶段决策问题,。,这是一个,多阶段决策过程,。,该过程可以分为相互联系的若干阶段，每一阶段都需作出决,策，从而形成全过程的决策。,第,1,年,x,1,=1000,u,1,第,2,年,x,2,=0.7,u,1,+,0.9(,x,1,-,u,1,),u,2,第,3,年,x,3,=0.7,u,2,+,0.9(,x,2,-,u,2,),u,3,第,4,年,u,4,第,5,年,x,5,=0.7,u,4,+,0.9(,x,4,-,u,4,),u,5,x,4,=0.7,u,3,+,0.9(,x,3,-,u,3,),x,6,P156,例,1,最短路线问题（空间阶段的例子）,设有一个旅行者从下图中的,A,点出发，途中要经过,B,、,C,、,D,等,处，最后到达终点,E,。,从,A,到,E,有很多条路线可以选择,，各点之间的距,离如图所示，问该旅行者应选择哪一条路线，使从,A,到达,E,的总的路程,为最短。,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,1,2,3,4,状态,1,决策,1,状态,2,状态,3,状态,4,状态,5,决策,2,决策,3,决策,4,可看成,4,阶段,的决策,问题。,从以上两个例子，可以知道,所谓,多阶段,决策问题,是指这样的决策问题：其过程可分为若,干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，,每一决策的选定既依赖于当前面临的状态，又影响以后总体的效,果。,当每一阶段的决策选定以后，就构成一个决策序列，称为一,个,策略,，,它对应着一个确定的效果。,多阶段决策问题就是寻找使,此效果最好的策略。,多阶段决策过程的特点,1.,各阶段的决策相互关联,多阶段决策过程最优化的目的,，是要达到整个活动过程的总体,效果最优，而不是某个阶段“局部”的效果最优。因此，,各个阶段,决策的选取不是任意确定的,。,前一个决策的选取决定了当前状态，当前状态进行决策后又影,响到下一阶段的状态和决策，以至于影响总体效果。所以决策者,在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目,标的影响，从而做出对全局而言是最优的决策。,动态规划就是符合这一要求的一种最优化方法。,2.,各个阶段的决策一般与“时间”有关,动态规划方法与“时间”关系很密切，随着时间过程的发展而决,定各阶段的决策，从而产生一个决策序列，这就是,“动态”的意,思。,但是，一些与时间无关的静态问题，只要在问题中,人为引,入“时间”因素,，也可将其看成是多阶段的决策问题，用动态规划,方法去处理。,学习目标：,1,准确、熟练地掌握动态规划的基本概念、特别是状态,变量、决策变量、状态转移律、指标函数、基本方程,等。,2,动态规划的基本概念,为了便于求解和表示决策及过程的发展顺序，而把所给问题恰,当地划分为若干个相互联系又有区别的子问题，称之为多段决策,问题的,阶段,。,一个阶段，就是需要作出一个决策的子问题,。,通常，,阶段是按决策进行的,时间或空间,上先后顺序划分的,。,描述阶段的变量称为,阶段变量,，常记为,k,，,k,=1,2,n,。,如本例可按空间分为,4,个,阶段来求解，,k,=1,2,3,4,。,（,1,）阶段（,stage,）,状态,：,每阶段初,的客观条件。描述各阶段状态的变量称为,状态,变量,，常用,x,k,表示第,k,阶段的状态。,（,2,）状态（,state,）,例,1,中，,状态,就是某,阶段的出发位置。,x,1,x,2,x,3,x,4,x,5,按状态变量的取值是连续还是离散，可将动态规划问题分为,离,散型,和,连续型,。,动态规划中的,状态应满足,无后效性（马尔科夫性）,：,所谓,无后效性,指系统到达某个状态前的过程的决策将不影响,到该状态以后的决策。,指系统从某个阶段往后的发展，仅由本,阶段所处的状态及其往后的决策所决定，与系统以前经历的状态,和决策（历史）无关。,过程的过去历史只能通过当前的状态去影,响它未来的发展,例,1,中，当某阶段的状态已选定某个点时，从这个点以后的路,线只与该点有关，不受该点以前的路线的影响，所以满足状态的,无后效性。,状态集合,：状态变量,x,k,的取值集合称为,状态集合,，,状态集合,实际上是关于状态的约束条件。,通常用,S,k,表示状态集合,，,x,k,S,k,。,第,1,阶段,S,1,=A,；,第,2,阶段具有,3,个状,态,B1,、,B2,和,B3,，故,S,2,=B1,B2,B3,。,x,1,x,2,x,3,x,4,x,5,（,3,）决策（,decision,）,当过程处于某一阶段的某状态时，可以做出不同的决定，从而,确定下一阶段的状态,，这种决定称为,决策,。,描述决策的变量称为,决策变量,，常用,u,k,(,x,k,),表示第,k,阶段当状,态处于,x,k,时的,决策变量，它是状态变量的函数。,例,1,中，从第,2,阶段的,状态,B1,出发，可以选择,下一阶段的,C1,、,C2,、,C3,。,如我们决定选择,C1,，,则可表示为：,u,2,(B1)=,C1,。,B,1,C,1,C,2,C,3,x,2,决策集合,：,第,k,阶段当状态处于,x,k,时决策变量,u,k,(,x,k,),的取值范,称为,决策集合,，常用,D,k,(,x,k,),表示。,例,1,中，从第,2,阶段的,状态,B1,出发，可以选择,下一阶段的,C1,、,C2,、,C3,。,即,D,2,(,B,1,)=C1,、,C2,、,C3,；,B,1,C,1,C,2,C,3,决策集合实际上是决策的约束条件，,u,k,(,x,k,),D,k,(,x,k,),。,小结,阶段,k,、,状态,x,k,、,状态集合,S,k,、,决策,u,k,(,x,k,),、,决策集合,D,k,(,x,k,),。,x,1,x,2,x,3,x,4,x,5,（,4,）状态转移律（方程）,状态转移律,：从,x,k,的某一状态值出发，当决策变量,u,k,(,x,k,),的,取值决定后，下一阶段状态变量,x,k,+1,的取值也随之确定。描述,从,x,k,转变为,x,k,+1,的规律称为,状态转移规律（方程）,。,从第,2,阶段的状态,B1,出发，如我们决,定选择,C2,（也即确,定了下一阶段的状,态）。,B,1,C,2,B,1,C,2,上例中，,u,2,(B1)=C2,状态转移律为：,x,k,+1,=,u,k,(,x,k,),一般来说，下一阶段状态变量,x,k,+1,的取值是上阶段的某一状态,变量,x,k,和上阶段决策变量,u,k,(,x,k,),的函数，记为,x,k,+1,=,T,k,(,x,k,u,k,(,x,k,),1,2,n,x,1,u,1,x,2,u,2,x,3,x,n,u,n,x,n,+1,（,5,）策略（,policy,）和子策略（,subpolicy,）,策略,：,由依次进行的,n,个阶段决策构成的,决策序列,就构成一个,策略,，用,p,1,n,u,1,(,x,1,),u,2,(,x,2,),u,n,(,x,n,),表示。,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,本例中，如,p,14,u,1,(,A,)=,B,1,u,2,(,B,1,)=,C,2,u,3,(,C,2,)=,D,1,u,4,(,D,1,)=,E,表示其中一个,策略，其总距离为,2+5+6+3=16,。,策略集合：,在实际问题中，由于在各个阶段可供选择的决策有,许多个，因此，它们的不同组合就构成了许多可供选择的决策序,列（策略），由它们组成的集合，称为,策略集合,，记作,P,1,n,。,从策略集合中，找出具有最优效果的策略称为,最优策略,。,子策略：,从,k,阶段到第,n,阶段，依次进行的阶段决策构成的,决策序列称为,k,部子策略，表示为,p,kn,=,u,k,(,x,k,),u,k,+1,(,x,k,+1,),u,n,(,x,n,),如从第,3,阶段的,C2,状态开始的一个子策,略可表示：,p,34,=,u,3,(,C,2,)=,D,1,u,4,(,D,1,)=,E,C,2,（,6,）指标函数,用来衡量策略或子策略或决策的效果的某种,数量指标,，就称,为,指标函数,。,它是定义在全过程或各子过程或各阶段上的确定数量函数。,对不同问题，指标函数可以是诸如费用、成本、产值、利润、,产量、耗量、距离、时间、效用，等等。,阶段,指标函数,过程,指标函数,阶段指标函数,：是指第,k,阶段从状态,x,k,出发，采取决策,u,k,时产生的效益，用,v,k,(,x,k,u,k,),表示。,例,1,中，指标函数是,距离,。,如,v,2,(,B,1,C,2,),表示,由,B,1,出发，采用决策,到,C,2,点的两点间距,离，即,v,2,(,B,1,C,2,)=5,。,B,1,C,2,过程指标函数,：是指从第,k,阶段的某状态,x,k,出发，采取子策,略,p,kn,时所得到的,效益,，记作,V,kn,(,x,k,u,k,x,k,+1,u,k,+1,x,n,),例,1,中，如,V,34,(,C,2,u,3,(,C,2)=,D,1,D,1,u,4,(,D,1,)=,E,E,)=6+3=9,C,2,过程指标函数,V,kn,通常是描述所实现的全过程或,k,后部子过程效,果优劣的数量指标，它是,由各阶段的阶段指标函数,v,k,(,x,k,u,k,),累积形,成的,。,（,1,）,可分性：,适于用动态规划求解的问题的过程指标函数（即目,