资源描述
,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,动运筹学态规划理论部分,动运筹学态规划理论部分动运筹学态规划理论部分 动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(RichardBa11man)首先提出的。它可以把一个 n 维最优化问题转化为 n 个一维最优化问题来求解。一个决策问题,往往可以分解成若干个相互联系,又相对独立的阶段,对于每一个阶段,存在着很多方案可供选择,我们要对每个阶段作出一个决策。而各阶段之间又有密切的联系,某一个阶段的不同决策,将会对其它阶段的决策产生重大的影响,某个阶段局部的较优方案,未必是整个问题的最好方案,某个阶段局部的不好方案,也未必是整个问题的不好方案。我们要寻找的是整个问题,也就是所有阶段总体的一个最优方案,这就是动态规划所要讨论的问题。,动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德,.,贝尔曼,(Richard,Ba11man),首先提出的。它可以把一个,n,维最优化问题转化为,n,个一维最优化问题来求解。,一个决策问题,往往可以分解成若干个相互联系,又相对独立的阶段,对于每一个阶段,存在着很多方案可供选择,我们要对每个阶段作出一个决策。,而各阶段之间又有密切的联系,某一个阶段的不同决策,将会对其它阶段的决策产生重大的影响,某个阶段局部的较优方案,未必是整个问题的最好方案,某个阶段局部的不好方案,也未必是整个问题的不好方案。,我们要寻找的是整个问题,也就是所有阶段总体的一个最优方案,这就是动态规划所要讨论的问题,。,一、多阶段决策问题,所谓多阶段决策问题是有这样一类决策过程,它可以划分为若干个相互联系的阶段,在任一阶段都有若干种方案可供选择,选择哪一种方案需要作出决策,这样就形成一个决策序列,通常称为一种策略。不同的策略就产生不同的效果,在所有可能的策略当中,选择一个效果最好的最优策略,就是解决多阶段决策问题的主要目的。下面举几个例子来说明。,例,1,:(最短路程问题)设从,A,地到,E,地要铺设一条管道,其中要经过若干个中间点,(,如图,),。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线,使总长度最短。,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,在这个问题中,从,A,到,B,1,,,B,2,,,B,3,中的哪一个点要作出一项决策,从,B,1,,,B,2,,,B,3,某点到,C,1,,,C,2,,,C,3,中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此,我们可以把整个路程分为,A,,,B,(,包括,B,1,,,B,2,,,B,3,),,,C(,包括,C,1,,,C,2,,,C,3,,,),,,D,(,包括,D,1,和,D,2,),,,E,四个阶段。这就是一个多阶段的决策问题。,二、动态规划的基本思想,用动态规划求解多阶段决策问题,是把整个问题划分为若干阶段后,依次地为每一个阶段作出最优决策,而每个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策,也就是到本阶段为止,包含以前各阶段在内的最优总决策。因此,在确定了最后一个阶段的决策之后,整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。,以上面的例,1,来说明动态规划解决问题的思想。设:,S,k,-,第,k,阶段的起点(状态变量),d,k,(,x,y,)-,第,k,阶段的顶点,x,到顶点,y,的“距离”;,f,k,(,S,k,)-,第,k,阶段从顶点,S,k,到终点的最短“路”长。,最短路线的重要特性就是:如果最短路线在第,K,站通过点,P,k,。则由点,P,k,出发到达终点的这条路线,对于从点,P,k,出发到达终点的所有可能选择的不同路经来说,必定也是最短路线。,例如,在最短路线问题中,如果找到了,A,到,E,的最短路:,则 应该是由,C,2,出发到,E,点的所有可能不同线路中的最短路线,最短路线这一特性,启发我们找最短路线的方法:那就是从最后一段开始,用由后向前逐步递推的方法,求出各点到,E,点的最短路线,最后求得由,A,点到,E,点的最短路线。所以,动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线”。如图所示:,行进方向,起点,终点,动态规划寻优途径,下面按上述思想,将例,1,从最后一段开始计算,由后向前逐步推移至,A,点。,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,5,(E)=0,设想有,k,5,时,,f,5,(,E,),0,。,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,1,)=5,f,5,(E)=0,K=4,时:,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,4,(D,1,)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,1,)=8,f,4,(D,1,)=5,K=3,时:,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,2,)=7,f,4,(D,1,)=5,f,3,(C,1,)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,3,(C,1,)=8,f,3,(C,2,)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,1,)=20,f,3,(C,2,)=7,f,3,(C,1,)=8,K=2,时:,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,2,)=14,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21,f,2,(B,2,)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,K=1,时:,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A,B,2,C,1,D,1,E,(,A,,,B,2,),(,B,2,,,C,1,),(,C,1,D,1,),(,D,1,E,),2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A,(,A,,,B,2,),B,2,(,B,2,,,C,1,),C,1,(,C,1,,,D,1,),D,1,(,D,1,,,E,),E,从,A到E的最短路径为19,路线为AB,2,C,1,D,1,E,三、动态规划的基本概念,(1)阶段(,stage),把所研究的决策问题,按先后顺序划分为若,(2),状态(,state),状态表示每个阶段开始时所处的自然状况或,(3)决策(,decision),决策表示在某一阶段处于某种状态时,决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量,第,k,阶段的决策变量常用,u,k,表示。决策变量的取值会受到状态变量的制约,被限制在某一范围之内。,干相互联系的决策步骤,以便按一定的次序进行求解。描述阶段的变量称阶段变量,常用,k,表示。,客观条件,它描述了影响决策的因素随决策进程的变化情况,它既是前面阶段所作决策的结果又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量,第,k,阶段的状态变量常用s,k,表示。通常,在第一阶段状态变量,s,1,是确定的,,称初始状态。,T,1,S,1,S,2,V,1,u,1,T,2,S,3,V,2,u,2,T,k,S,k,S,k+1,V,k,u,k,T,n,S,n,S,n+1,V,n,u,n,多阶段决策过程如下:,n,个决策子问题,k,称为阶段变量,S,k,描述,k,阶段初的状态,即状态变量,一般把输入状态称为该阶段的阶段状态。,u,k,的取值代表,k,阶段对第,k,子问题所进行的决策,称为,k,阶段的决策变量,V,k,为,k,阶段从状况,S,k,出发,做出决策,u,k,之后的后果,,(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)状态转移方程,(6)指标函数,(,准则函数),目标函数和,最优值函数,指标函数分为阶段指标函数和过程指标函数。,阶段指标函数是对某一阶段的状态和决策产生的效益值的度量,用,V,k,(,s,k,u,k,),表示。,从第,k,阶段到最终阶段的过程称为,k-,后部子过程,简称为:,k-,子过程。,若第,k,阶段的状态变量值为,s,k,,,当决策变量,u,k,的取值决定后,下一阶段状态变量,S,k+1,的值也就完全确定。即,S,k+1,的值对应于,S,k,和,u,k,的值。这种对应关系记为:,s,k+1,T,k,(,s,k,u,k,),,称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。,过程指标函数是指,从,第,k,阶段至第,n,阶段,所包含的各阶段的状态和决策所产生的总的效益值,记为:,V,k,n,V,k,n,(,S,k,u,k,S,k+1,u,k+1,S,n,u,n,),T,k,S,k,S,k+!,V,k,(S,k,u,k,),u,k,(S,k,),T,n,S,n,S,n+1,V,n,(S,n,u,n,),u,n,(S,n,),K,子过程,定义在全过程上的准则函数相当于目标函数,一般记为,:,V,1,n,V,1,n,(,S,1,u,1,S,k,u,k,S,n,u,n,),或简记为,V,1,n,把过程指标函数,V,k,n,对,k,子过程策略,p,k,n,求最优,得到一个关于状态,S,k,的函数,称为最优值函数,或,贝尔曼函数,,记为:,。,即,各阶段指标函数的和:,各阶段指标函数的积:,动态规划所要求的过程指标函数应具有可分离性,即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是:,也就是说在阶段,k,从初始状态,S,k,出发,执行最优决策序列或策略,到达过程终点时,整个,k-,子过程中的最优目标函数取值。,式中的“,opt”(optimization),可根据具体问题的实际意而取,min,或,max。,或,由最优性定理可知:,四、动态规划基本方程,逆序法,由此逆序算法的递归方程如下:,其中:,f,k,(,s,k,),表示第,k,阶段初始状态为,s,k,时,,k,后部子过程的最优准则函数,。,逆序递归方程:,状态转移方程:,正序递归方程:,状态转移方程:,其中:,f,k,(,s,k,),表示第,k,阶段初始状态为,s,k,时,,k,前部子过程的最优准则函数,。,动态规划建模有以下过程:,确定阶段与阶段变量,明确状态变量和状态可能集合。,确定决策变量和决策允许集合。,确定状态转移方程。,明确阶段效应和目标。,五、动态规划的建模,k=n,时,动态规划基本方程是,边界条件:,即,:,逆序地求出条件最优目标函数值集合和条件最优决策集合,,仅就逆序法说明求解步骤:,六、动态规划问题求解的一般步骤,式中的“,opt”,可根据具体问题的实际意,义,,而取,min,或,max。,k=n,1,时,,动态规划的基本方程是,因所有的 都已经求出,因此可以根据 就阶段,n-1,每个可能状态,,,求出条件最优决策及相应的条件最优目标函数值。,因所有 都已求出,因此可以根据 就阶段,n-2,每个可能状态,,,求出条件最优决策及相应的条件最优目标函数值。,k=n,2,时,,,动态规划的基本方程是,k=1,时,动态规划的基本方程是,由于所有的,f,2,(,s,2,),都已经求出,因此可以根据,s,2,=,T,1,(,s,1,u,1,),就阶段,1,每个可能状态,s,1,求条件最优决策及相应的条件最优目标函数值,f,1,(,s,1,).,依次下去,.,最后,顺序地求出最优目标值、最优策略和最优路线,解 该问题可以作为三段决策过程。对,A,、,B,、,C,三个部门分配资金分别形成,1,,,2,,,3,三个阶段。,s,k,表示给部门,k,分配资金时拥有的资金数。,u,k,表示给部门,k,分配的资金数(万元为单位)。状态转移方程是,s,k+1,=,s,k,-,u,k,。目标函数是阶段效应求和。,例,2,:某公司拟将,5,百万元资金投放下属,A,、,B,、,C,三个部门,其中,A,与,C,的投资额不超过,4,百万元,,B,的投资额不超过,3,百万元,,C,投资额至少是,1,百万元。各部门在获得资金后的收益如表所示,用动态规划方法求总收益最大的投资分配方案(投资数以百万元为单位)。,15,11,8,4,C,12,10,5,0,B,12,10,6,3,0,A,收,益,(万元),4,3,2,1,投放资金,(,万元,),0,递归方程为:,(,1,),K=3,时(第,3,阶段)注意到,C,的投资额不超过,4,百万元,,至少是,1,百万元,.,允许状态集合,S,3,1,2,3,4,即用剩余额,S,3,1,,,2,,,3,,,4,投资部门,C,,得到的收益为:,(,2,),K=2,时(第,2,阶段)注意到,C,的投资额至少是,1,百万元,,允许状态集合,S,2,1,2,3,4,5,下面是各种可能方案的列表,s,2,1,s,2,2,s,2,3,s,2,4,s,2,5,B C,B C,B C,B C,B C,0 1,0 2,0 3,0 4,1 4,1 1,1 2,1 3,2 3,2 1,2 2,3 2,3 1,故,(,3,),K=1,时(第,1,阶段),S,1,=5,允许决策集合,D,1,(S,1,),0,1,2,3,4,应用顺序追踪可知:最优方案有两个:,方案,1,:,方案,2,:,最大收益都为,21,百万元。,例,3,:,逆推解法求解下面问题,:,解,:,按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设,状态变量为,s,1,,,s,2,,,s,3,,,s,4,。并记,s,1,c,;令变量,x,1,,,x,2,,,x,3,为决策变量;各阶段指标按乘积方式结合。即令,:,令最优值函数,f,k,(s,k,),表示为第,k,阶段的初始状态为,s,k,时,从第,k,阶段到第,3,阶段所得到的最大值。,设,:s,3,=,x,3,s,3,+,x,2,=s,2,s,2,+,x,1,=s,1,=c,则有:,x,3,=s,3,0,x,2,s,2,0,x,1,s,1,=c,即状态转移方程为:,s,3,=s,2,x,2,s,2,=s,1,x,1,由逆推解法,,即最优解,x,3,=s,3,由,得,和(舍去),又,而,故为极大值点。,所以,即最优解。,求导并令导数等于,0,可得:,故,由于,s,1,=c,,,,,由,s,2,=s,1,x,1,,,由,s,3,=s,2,x,2,,,,,因此最优解为:,,最大值为:,例,:,正推解法求解下面问题,:,解:设,s,4,c,,决策变量仍为,x,1,,,x,2,,,x,3,;最优值函数,f,k,(s,k+1,),表示为第,k,阶段末的结束状态为,s,k+1,,从第,1,阶段到第,k,阶段所得到的最大值。,设,:s,2,=,x,1,s,2,+,x,2,=s,3,s,3,+,x,3,=s,4,=c,则有:,x,1,=s,2,0,x,2,s,3,0,x,3,s,4,=c,即状态转移方程为:,s,2,=s,3,x,2,s,3,=s,4,x,3,由顺推解法,即最优解,x,1,=s,2,最优解。,最优解,由于,s,4,=c,,,,,由,s,3,=s,4,x,3,,,由,s,2,=s,3,x,2,,,,,因此最优解为:,,最大值为:,例,:用正推解法求解下面问题,:,解,:,按问题的变量个数划分阶段,把它看作一个三阶段决策问题。,设,状态变量为,s,0,,,s,1,,,s,2,,,s,3,。并记,s,3,9,;,令变量,x,1,,,x,2,,,x,3,为决策变量;,最优值函数,f,k,(s,k,),表示为第,k,阶段末的结束状态为,s,k,,从第,1,阶段到第,k,阶段所得到的最大值。,设,:3,x,1,=s,1,s,1,+2,x,2,=s,2,s,2,+,x,3,=s,3,9,则有:,x,1,=s,1,3,0,x,2,s,2,2,0,x,3,s,3,9,即状态转移方程为:,s,1,=s,2,2,x,2,s,2,=s,3,x,3,由顺推解法,,即最优解,x,1,=s,1,3,由,得,(,它不在决策集,内,),则最大值在端点上,,最大值点为,x,2,=0,。故得到,及最优解。,由,得,又,故该点为极小值点。,而,最大值点为,x,3,=s,3,。故得到,及最优解,由于,s,3,不知道,故须在对,s,3,求一次极值,即,反推回去即可得最优解为:,。最大值为:,作业用动态规划法求解:,谢谢大家!,
展开阅读全文