动态规划讲座

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4 动态,规,规划,4.1,多,多阶段决策,问,问题与动态,规,规划,4.2,动,动态规划的,基,基本概念,4.3,动,动态规划的,步,步骤,4.4,动,动态规划的,应,应用,1 求解,静,静态规划问,题,题,2 资源,分,分配问题,3 不确,定,定性采购问,题,题,4 排序,问,问题,例2 机器,负,负荷分配问,题,题,某种机器可,以,以在高低两,种,种不同的负,荷,荷下进行生,产,产在高负,荷,荷下进行生,产,产时，产品,的,的年产量g,和,和投入生产,的,的机器数量u的关系为gg(u),这,时,时机器的年,完,完好率为a,（,（0a1)在低,负,负荷下生产,时,时，产品的,年,年产量h和,投,投入生产的,机,机器数量v,的,的关系为h,h(v),这时机,器,器的年完好,率,率为b（ab1）,假定开始,生,生产时完好,的,的机器数量,为,为s,1,，要求制,定,定一个五,年,年计划,在,在每年开,始,始时决定,机,机器在两,种,种不同负,荷,荷下生产,的,的数量,使,使五年内,产,产品的总,产,产量最高,。,。,4.1,多,多阶段决,策,策问题与,动,动态规划,多阶段决,策,策问题和,我,我们前面,遇,遇到的决,策,策问题不,同,同，它是,和,和时间有,关,关的。与,时,时间有关,的,的活动过,程,程称为动,态,态过程，,其,其优化方,法,法称为动,态,态规划。,而,而与时间,无,无关的活,动,动过程称,为,为静态过,程,程，相应,的,的的优化,方,方法称为,静,静态规划,。,。,(1)阶,段,段（,stage）把所,研,研究的决,策,策问题，,按,按先后顺,序,序划分为,若,若干相互,联,联系的决,策,策步骤，,以,以便按一,定,定的次序,进,进行求解,。,。描述阶,段,段的变量,称,称阶段变,量,量，常用k表示。,(2)状,态,态（,state）状态,表,表示每个,阶,阶段开始,时,时所处的,自,自然状况,或,或客观条,件,件，它描,述,述了影响,决,决策的因,素,素随决策,进,进程的变,化,化情况，,它,它既是前,面,面阶段所,作,作决策的,结,结果，又,是,是本阶段,作,作出决策,的,的出发点,和,和依据。,描,描述状态,的,的变量称,为,为状态变,量,量，第k,阶,阶段的状,态,态变量常,用,用s,k,表示。通,常,常，,在第一阶,段,段状态变,量,量,s,1,是确定的,，称初始,状,状态。,(3)决,策,策（,decision,）,）决策表,示,示在某一,阶,阶段处于,某,某种状态,时,时，决策,者,者在若干,种,种方案中,作,作出的选,择,择决定。,描,描述决策,的,的变量称,决,决策变量,，,，第k阶,段,段的决策,变,变量常用u,k,表示。决,策,策变量的,取,取值会受,到,到状态变,量,量的制约,，,，被限制,在,在某一范,围,围之内。,4.2,动,动态规,划,划的基本,概,概念（一,）,）,(4)策,略,略（,policy）把,从,从第一阶,段,段开始到,最,最后阶段,终,终止的整,个,个决策过,程,程，称为,问,问题的全,过,过程；而,把,把从第k,阶,阶段开始,到,到最后阶,段,段终止的,决,决策过程,，,，或称为k子过程,。,。在全过,程,程上，各,阶,阶段的决,策,策按顺序,排,排列组成,的,的决策序,列,列p,1,n,u,1,u,2,u,n,称为全,过,过程策略,，,，简称策,略,略；而在k子过程,上,上的决策,序,序列p,k,n,u,k,u,k+1,u,n,称为k,子,子过程策,略,略，也简,称,称子策略,。,。,(5)状,态,态转移方,程,程 若第,k阶段的,状,状态变量,值,值为s,k,，当决策,变,变量u,k,的取值决,定,定后，下,一,一阶段状,态,态变量,s,k+1,的值也就,完,完全确定,。,。即,s,k+1,的值对应,于,于,s,k,和,u,k,的值。这,种,种对应关,系,系记为,s,k+1,T,k,(s,k,u,k,)，称为,状,状态转移,方,方程。状,态,态转移方,程,程描述了,由,由一个阶,段,段的状态,到,到下一阶,段,段的状态,的,的演变规,律,律。,4.2,动,动态规,划,划的基本,概,概念（二,）,）,(6)指,标,标函数和,最,最优值函,数,数 指标,函,函数分为,阶,阶段指标,函,函数和过,程,程指标函,数,数。阶段,指,指标函数,是,是对某一,阶,阶段的状,态,态和决策,产,产生的效,益,益值的度,量,量，用,v,k,(s,k,u,k,)表示。,过,过程指标,函,函数是指,过,过程所包,含,含的各阶,段,段的状态,和,和决策所,产,产生的总,的,的效益值,，,，记为,V,k,n,V,k,n,(s,k,u,k,s,k+1,u,k+1,s,n,u,n,),动态规划,所,所要求的,过,过程指标,函,函数应具,有,有可分离,性,性，即可,表,表达为它,所,所包含的,各,各阶段指,标,标函数的,函,函数形式,。,。常见的,两,两种过程,指,指标函数,形,形式是：,各阶段,指,指标函数,的,的和V,k,n,v,j,(s,j,u,j,)；,各阶段,指,指标函数,的,的积V,k,n,v,j,(s,j,u,j,)。,把过程指,标,标函数V,k,n,对,k子过程,策,策略p,k,n,求最优，,得,得到一个,关,关于状态,s,k,的,函,函,数,数,，,，,称,称,为,为,最,最,优,优,值,值,函,函,数,数,，,，,记,记,为,为,f,k,(s,k,),。,。,即,即,f,k,(s,k,),optV,k,n,(s,k,u,k,s,n,u,n,),u,k,u,n,式,中,中,的,的,“,opt,”,”,（,（optimization,）,）,可,可,根,根,据,据,具,具,体,体,问,问,题,题,而,而,取,取min,或,或max,。,。,(7),基,基,本,本,方,方,程,程,通,通,常,常,动,动,态,态,规,规,划,划,问,问,题,题,的,的,最,优,优,值,值,函,函,数,数,满,足,足,递,递,推,推,关,关,系,系,式,式,。,。,设,设,过,过,程,程,指,指,标,标,函,函,数,数,为,为,各,各,阶,阶,段,段,指,指,标,标,函,函,数,数,的,的,和,和,的,的,形,形,式,式,，,，,即,即V,k,n,v,j,(s,j,u,j,),，,，,则,则,有,有,f,k,(s,k,),optv,k,(s,k,u,k,)+f,k+1,(s,k+1,),u,k,D,k,(s,k,),(k,n,n-1,1)递,推,推,方,方,程,程,f,n+1,(s,n+1,),0,边,边,界,界,条,条,件,件,递,推,推,方,方,程,程,和,和,边,边,界,界,条,条,件,件,一,一,起,起,称,称,为,为,动,动,态,态,规,规,划,划,的,的,基,基,本,本,方,方,程,程,。,。,可,根,根,据,据,边,边,界,界,条,条,件,件,，,，,从,从k=n,开,开,始,始,，,，,由,由,后,后,向,向,前,前,逆,逆,推,推,，,，,逐,逐,步,步,求,求,得,得,各,各,阶,阶,段,段,的,的,最,最,优,优,决,决,策,策,和,和,相,相,应,应,的,的,最,最,优,优,值,值,，,，,最,最,后,后,求,求,出,出f,1,(s,1,),时,时,，,，,就,就,得,得,到,到,整,整,个,个,问,问,题,题,的,的,最,最,优,优,解,解,。,。,此,问,问,题,题,的,的,基,基,本,本,方,方,程,程,为,为,f,k,(s,k,),Mind,k,(u,k,)+f,k+1,(s,k+1,),u,k,D,k,(s,k,),k,6,5,4,3,2,1,f,7,(s,7,),0,4.3,动,动,态,态,规,规,划,划,的,的,步,步,骤,骤,（,（,一,一,）,）,当k=6,时,时,按,基,基,本,本,方,方,程,程,由,由,后,后,向,向,前,前,继续递,推,推有:,当k=5时,当k=4时,当k=3时,当k=2时,当k=1时,由此可,以,以看出,，,，A到G的最,短,短路长,为,为18,，,，路径,为,为：AB,1,C,2,D,1,E,2,F,2,G,现在把,动,动态规,划,划法的,步,步骤归,纳,纳如下,：,：,(1),将,将所,研,研究问,题,题的过,程,程划分,为,为,n个恰,当,当的阶,段,段，,k1,2,n；,(2),正,正确,地,地选择,状,状态变,量,量S,k,，并确,定,定初始,状,状态S,1,的值；,(3),确,确定,决,决策变,量,量,u,k,以及各,阶,阶段的,允,允许决,策,策集,D,k,(S,k,)；,(4),给,给出,状,状态转,移,移方程,；,；,(5),给,给出,满,满足要,求,求的过,程,程指标,函,函数V,k,n,及相应,的,的最优,值函数,；,；,(6),写,写出,递,递推方,程,程和边,界,界条件,，,，建立,基,基本方,程,程；,(7),按,按照,基,基本方,程,程递推,求,求解。,以上步,骤,骤是动,态,态规划,法,法处理,问,问题的,基,基本步,骤,骤，其,中,中的前,六,六步是,建,建立动,态,态规划,模,模型的,步,步骤。,4.3,动,动态,规,规划的,步,步骤（,二,二）,例：机,器,器负荷,问,问题某种机,器,器可以,在,在高低,两,两种不,同,同的负,荷,荷下进,行,行生产,在高,负,负荷下,进,进行生,产,产时，,产,产品的,年,年产量g和投,入,入生产,的,的机器,数,数量u,的,的关系,为,为 g,8u,这,时,时机器,的,的年完,好,好率为a=0.7,在,在低负,荷,荷下生,产,产时，,产,产品的,年,年产量h和投,入,入生产,的,的机器,数,数量v,的,的关系,为,为h5v,这,这时,机,机器的,年,年完好,率,率为b=0.9假,定,定开始,生,生产时,完,完好的,机,机器数,量,量为s,1,，要求,制,制定一,个,个五年,计,计划,在,在每年,开,开始时,决,决定机,器,器在两,种,种不同,负,负荷下,生,生产的,数,数量,使,使五年,内,内产品,的,的总产,量,量最高,。,。,(1),按,按年数,划,划分为5个阶,段,段，k=1,2,3,4,5,(2),取,取第k,年,年初完,好,好的机,器,器数s,k,为状态,变,变量,s,1,=1000,(3),取,取第k,年,年投入,高,高负荷,的,的机器,数,数x,k,为决策,变,变量,0 x,k,s,k,(4)状,态,态转,移,移方,程,程为s,k+1,=0.7x,k,+0.9(s,k,-x,k,)=0.9s,k,-0.2x,k,(5)指,标,标函,数,数为V,k,5,=8x,j,+5(s,j,-x,j,)=(5s,j,+3x,j,),(6)基,本,本方,程,程为,f,k,(s,k,)max,5s,j,+3x,j,+f,k+1,(s,k+1,)k=5,4,3,2,1,0 x,k,s,k,f,6,(s,6,)0,解:,当k=5,时,时,f,5,(s,5,)max5s,5,+3x,5,+f,6,(s,6,)=max5s,5,+3x,5,=8s,5,(x,5,*=s,5,),0 x,5,s,5,0 x,5,s,5,当k=4,时,时,f,4,(s,4,)max5s,4,+3x,4,+8s,5,=max5s,4,+3x,4,+8(0.9s,4,-0.2x,4,),0 x,4,s,4,0 x,4,s,4,=max,12.2s,4,+1.4x,4,=13.6s,4,(x,4,*=s,4,),0 x,4,s,4,当k=3,时,时,f,3,(s,3,)max5s,3,+3x,3,+13.6s,4,=max5s,3,+3x,3,+13.6(0.9s,3,-0.2x,3,),0 x,3,s,3,0 x,3,s,3,=max,17.24s,3,+0.28x,3,=17.5s,3,