动态规划的基本原理和基本应用教学教材.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,9,章,动态规划的,基本原理和基本应用,1,动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（,Bellman,）等人在,20,世纪,50,年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。,2,动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。,3,9.1,多阶段决策过程最优化问题举例,多阶段决策过程最优化,多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,4,例,1,多阶段资源分配问题,设有数量为,x,的某种资源，将它投入两种生产方式,A,和,B,中：以数量,y,投入生产方式,A,，剩下的量投入生产方式,B,，则可得到收入,g,(,y,),+h,(,x-y,),，其中,g,(,y,),和,h,(,y,),是已知函数，并且,g,(0),=h,(0),=,0,；同时假设以,y,与,x-y,分别投入两种生产方式,A,，,B,后可以回收再生产，回收率分别为,a,与,b,。试求进行,n,个阶段后的最大总收入。,5,若以,y,与,x-y,分别投入生产方式,A,与,B,，在第一,阶段生产后回收的总资源为,x,1,=,ay,+,b,(,x-y,),，再将,x,1,投入生产方式,A,和,B,，则可得到收入,g,(,y,1,)+,h,(,x,1,-,y,1,),，,继续回收资源,x,2,=,ay,1,+,b,(,x,1,-,y,1,),，,若上面的过程进行,n,个阶段，我们希望选择,n,个变量,y,y,1,y,2,y,n,-1,，使这,n,个阶段的总收入最大。,例,1,6,因此，我们的问题就变成：求,y,y,1,y,2,y,n,-1,，以使,g,(,y,)+,h,(,x-y,)+,g,(,y,1,)+,h,(,x,1,-,y,1,)+,g,(,y,n,-1,)+,h,(,x,n,-1,-,y,n,-1,),达到最大，且满足条件,x,1,=,ay+b,(,x-y,),x,2,=,ay,1,+b,(,x,1,-y,1,),x,n-1,=,ay,n-,2,+b,(,x,n-,2,-y,n-,2,),y,i,与,x,i,均非负,i=,1,2,n,-1,例,1,7,例,2,生产和存储控制问题,某工厂生产某种季节性商品，需要作下一,年度的生产计划，假定这种商品的生产周期需,要两个月，全年共有,6,个生产周期，需要作出,各个周期中的生产计划。,设已知各周期对该商品的需要量如下表所示,：,周期,1,2,3,4,5,6,需求量,5,5,10,30,50,8,8,例,2,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品,15,个单位，每生产一个单位商品的成本为,100,元。当开足夜班时，每一生产周期能生产的商品也是,15,个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为,120,元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储,费用的，假设每单位商品存储一周期需要,16,元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？,9,例,2,设第,i,个周期的生产量为,x,i,，周期末的存储量为,u,i,，那,么这个问题用式子写出来就是：求,x,1,x,2,x,6,，满足条件：,x,1,=5+,u,1,x,2,+,u,1,=5+,u,2,x,3,+,u,2,=10+,u,3,x,4,+,u,3,=30+,u,4,x,5,+,u,4,=50+,u,5,x,6,+,u,5,=8,0,x,i,30,0,u,j,i,=1,2,6;,j,=1,2,5,使,S,=,=,为最小，其中,10,例,3,运输网络问题：如图,1,所示的运输网络，点间连线上的数字表示两地距离,(,也可是运费、时间等,),，要求从,v,1,至,v,10,的最短路线。,这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为,4,个阶段，而作为多阶段决策问题来研究。,11,1,2,3,4,图,1,运输网络图示,12,动态规划方法导引,为了说明动态规划的基本思想方法和特点，下面以,图,1,所示为例讨论求最短路问题的方法。,第一种方法称做全枚举法或穷举法，,它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从,v,1,到,v,10,的路程可以分为,4,个阶段。第一二段的走法有三种，第三段的走法有两种，第四段的走法仅一种，因此共有,3321,18,条可能的路线，,54,次加法算出各条路线的距离，最后进行,17,次两两比较，可知最优路线是,v,1,v,2,v,5,v,8,v,10,最短距离是,27,13,显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算,第二种方法即所谓,“,局部最优路径,”,法,，是说某人从,k,出发，他并不顾及全线是否最短，只是选择当前最短途径，,“,逢近便走,”,，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是,v,1,v,2,v,5,v,9,v,10,，全程长度是,30,；显然，这种方法的结果常是错误的,14,第三种方法是动态规划方法，,动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为,4,个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。,为了找出所有可能状态的最优后继过程，动态规划方法是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。,15,具体说，此问题先从,v,10,开始，因为,v,10,是终点。再无后继过程，故可以接着考虑第,4,阶段上所有可能状态,v,8,v,9,的最优后续过程因为从,v,8,v,9,到,v,10,的路线是唯一的，所以,v,8,v,9,的最优决策和最优后继过程就是到,v,10,，它们的最短距离分别是,10,和,14,。,接着考虑阶段,3,上可能的状态,v,5,v,6,v,7,到,v,10,的最优决策和最优后继过程在状态,V,5,上，虽然到,v,8,是,6,，到,v,9,是,5,，但是,1,2,3,4,（,10,）,（,14,）,16,综合考虑后继过程整体最优，取最优决策是到,v,8,最优后继过程是,v,5,v,8,v,10,，最短距离是,16,同理，状态,v,6,的最优决策是至,v,8,；,v,7,的最优决策是到,v,9,。,同样，当阶段,3,上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段,2,上所有可能状态的最优决策和最优后继过程，如,v,2,的最优决策是到,v,5,最优路线是,1,2,3,4,（,10,）,（,14,）,（,16,）,（,15,）,（,17,）,17,v,2,v,5,v,8,v,10,，最短距离是,22,依此类推，最后可以得到从初始状态,v,1,的最优决策是到,v,2,最优路线是,v,1,v,2,v,5,v,8,v,10,，全程的最短距离是,27,。图,1,中红线表示最优路线，每点上圆括号内的数字表示该点到终点的最短路距离。,1,2,3,4,（,10,）,（,14,）,（,16,）,（,15,）,（,17,）,（,22,）,（,22,）,（,21,）,（,27,）,18,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。,19,拾火柴游戏,:,桌子上放,30,根火柴,每人一次可拾起,1,3,根,谁拾起最后一根火柴谁输,如果你先选择,如何保证你能赢得游戏？,29,25,21,17,13,9,5,1,动态规划与倒推求解,:,20,动态规划是解决,多阶段决策问题,的一种方法。所谓多阶段,决策问题是指这样的决策问题：其过程可分为若干个相互联,系的阶段，每一阶段都对应着一组可供选择的决策，每一决,策的选定即依赖于当前面临的状态，又影响以后总体的效果。,A,B,C,D,E,状态,A,状态,B,状态,C,状态,D,状态,E,状态,F,决策,A,决策,D,决策,E,当每一阶段的决策选定以后，就构成一个决策序列，称为一个,决策,B,决策,C,策略,，,它对应着一个确定的效果。,多阶段决策问题就是寻找使,此效果最好的策略。,21,动态规划问题实例,例 给定一个线路网络，,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,45,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,要从,A,向,F,铺设一条输油管道，,各点间连线上的数字表示距离，问应选择什么路线，可使总,距离最短？,22,9.2,动态规划的基本概念和基本原理,一、基本概念,阶段,：是指问题需要做出决策的步数。阶段总数常记为,n,，相,应的是,n,个阶段的决策问题。阶段的序号常记为,k,，称为,阶段,变量,，,k,=1,2,n,.,k,即可以是顺序编号也可以是逆序编号，,常用顺序编号。,全过程,；,后部子过程,。,状态,：各阶段开始时的客观条件，第,k,阶段的状态常用,状态,变量,表示，状态变量取值的集合称为,状态集合,，用,表示。,例如，例中，,23,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第,1,阶段,第,2,阶段,第,3,阶段,第,4,阶段,第,5,阶段,状态,1,状态,2,状态,3,状态,4,状态,5,状态,6,24,决策,：是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为,决策变量,，用 表示,例如：表示走到,3,阶段,当处于,C,2,路口时，下一,步奔,D,1,.,时的允许决策集合记为 ，例如：,策略,:,全过程策略,p,1,n,；子策略,p,kn,；,最优策略,。,状态转移方程,：是从上一阶段的某一状态值转变为下一阶段,某一状态值的转移规律，用,表示。,决策变量允许的取值范围称为,允许决策集合,，第,k,阶段状态为,25,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第,1,阶段,第,2,阶段,第,3,阶段,第,4,阶段,第,5,阶段,状态,1,状态,2,状态,3,状态,4,状态,5,状态,6,26,指标函数,：分,阶段指标函数,和,过程指标函数,。,阶段指标函数,是指第,k,阶段从状态 出发，采取决策 时的效益，用,表示。而,过程指标函数,指从第,k,阶段的某状态出发，,采取子策略,时所得到的阶段效益之和：,最优指标函数,：表示从第,k,阶段状态为 时采用最佳策略,到过程终止时的最佳效益。记为,27,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第,1,阶段,第,2,阶段,第,3,阶段,第,4,阶段,第,5,阶段,状态,1,状态,2,状态,3,状态,4,状态,5,状态,6,28,其中,opt,可根据具体情况取,max,或,min,。,基本方程,：此为逐段递推求和的依据，一般为：,式中,opt,可根据题意取,max,或,min.,例如，例的基本方程为：,29,即确定各个变量及方程函数,1,、阶段变量,2,、状态变量：选择时要满足两个条件：,能正确描述受控过程的演变特性,要满足无后效性,无后效性,：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。,3,、决策变量,4,、列出状态转移方程,5,、指标函数,二、模型的构成（因素）,30,三、,最优化原理,：最优策略的任一后部子策略都是最优的。,无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。,动态规划应用举例,例,1,最短路线问题,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,31,逆序递推方程：,（,1,）,k=5,时，状态,它们到,F,点的距离即为,最短路。,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,32,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（,2,）,k=4,时，状态,它们到,F,点需经过中途,点,E,，需一一分析从,E,到,F,的最短路：先说从,D,1,到,F,的最短路,有两种选择：经过,E,1,E,2,比较最短。,33,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由,D,1,到,F,的最短距离为,7,，其路径为,相应的决策为：,34,这说明由,D,2,到,F,的最短距离为,5,其路径为,相应的决策为：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,35,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即,D,3,到,F,的最短距离为,5,，其路径为,相应的决策为：,36,（,3,）,k=3,时，状态,这说明由,C,1,到,F,的最短距离为,12,，相应的决策为,A,B,1,B,2C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,37,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由,C,2,到,F,的最短距离为,10,，相应的决策为,38,即由,C,3,到,F,的最短距离为,8,，相应的决策为,即由,C,4,到,F,的最短距离为,9,，相应的决策为,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,39,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（,4,）,k=2,时，状态,这说明由,B,1,到,F,的最短距离为,13,，相应的决策为,40,即由,B,2,到,F,的最短距离为,15,，相应的决策为,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,23,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,41,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（,5,）,k=1,时，只有一个状态点,A,则,即由,A,到,F,的最短距离为,17,，相应的决策为,42,所以最优路线为：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3再按计算顺序反推可得最优决策序列：,43,顺序递推方程：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例,1,：,1,阶段,2,阶段,3,阶段,4,阶段,5,阶段,行走方向,第,k,阶段,44,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=1,时,注意到：,所以,45,K=2,时,A,B,1,B,2C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,46,K=3,时,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,47,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,类似地，可算出48,最优策略：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,49,最短路径：,最短路长：,注,：顺序解法与逆序解法无本质区别，一般来说，当初始状,态给定时用逆序解法，当终止状态给定时用顺序解法。若问,题给定了一个初始状态与一个终止状态，则两种方法均可使,用。,50,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（,4,，,F,）,（,3,，,F,）,（,5,，,E,1,）,（,5,，,E,2,）,（,7,，,E,1,）,（,12,，,D,1,）,（,10,，,D,2,）,（,8,，,D,2,）,（,9,，,D,3,）,（,13,，,C,2,）,（,15,，,C,3,）,（,17,，,B,1,）,作业：,P235 5.2,（双标号法，顺序逆序选一）,51,9.3,背 包 问 题,一般的提法为：一旅行者携带背包去登山。已知他所能承受,的背包重量的极限为,a,(,千克,),，现有,n,种物品可供他选择装入,背包。第,i,种物品的单位重量为,(,千克,),，其价值（可以是表,明本物品对登山者的重要性指标）是携带数量 的函数,（,i,=,1,，,2,，,n,）,.,问旅行者应如何选择携带物品的件,数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题。,其数学模型为：,52,设 为第,i,种物品装入的件数，则背包问题可归结为如下,形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例 有一辆最大货运量为,10 t,的卡车，用以装载,3,种,货物，每种货物的单位重量及相应单位价值如表,4,所示。,应如何装载可使总价值最大？,53,货物编号,i,1,2,3,单位重量（,t,）,3,4,5,单位价值,c,i,4,5,6,表,4,设第 种货物装载的件数为,则问题可表为：,阶段,k:,将可装入物品按,1,，,2,，,3,的顺序排序，每段装入一,种物品，共划分,3,个阶段，即,k=1,2,3.,54,状态变量,：,在第,k,段开始时，背包中允许装入前,k,种,物品的总重量。,决策变量,：,装入第,k,种物品的件数。,状态转移方程：,最优指标函数,：,在背包中允许装入物品的总重量不超,过,kg,，采取最优策略只装前,k,种物品时的最大使用价值,。,货物,1,货物,2,货物,3,55,由此可得动态规划的顺序递推方程为：,货物,1,货物,2,货物,3,K=1,时,56,货物,1,货物,2,货物,3,K=1,时,注意到：,例如：,时，,其它计算结果见表,5,：,57,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,40,40,40,40,41,40 41 42,40 41 42 43,0,0,0,4,4,8,12,12,0,0,0,1,1,2,3,3,表,5,58,货物,1,货物,2,货物,3,K=2,时,其中,例如：,时,，,59,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,40,40,40,40,41,40 41 42,40 41 42 43,0,0,0,4,8,12,0,0,0,1,2,3,表,5,60,其它计算结果见表,6,：,0 1 2,0,1,2,3,4,5,6,7,8,9,10,50,0,50,4,51,0,50,12 51,8 52,0,0,5,13,0,1,1,表,6,61,货物,1,货物,2,货物,3,K=3,时,62,0 1 2,0,1,2,3,4,5,6,7,8,9,10,50,0,50,4,51,0,50,12 51,8 52,0,0,5,13,0,1,1,表,6,63,从,再由状态转移方程,0 1 2,0,1,2,3,4,5,6,7,8,9,10,50,0,50,4,51,0,50,12 51,8 52,0,0,5,13,0,1,1,表,6,货物,1,货物,2,货物,3,64,再由状态转移方程,0 1 2 3,0,1,2,3,4,5,6,7,8,9,10,40,40,40,40,41,40 41 42,40 41 42 43,0,0,0,4,8,12,0,2,4,0,0,1,2,3,表,5,最大装载价值为,65,总结：今后解背包问题应先从,k=3,入手：,k=3,时,下面应有重点地从,k=2,中求解三个最优函数值：,66,K=2,时,67,所以从第一阶段应有重点地求以下四个数：,K=1,时,68,由此逐一逆推代回上式：,69,由此逐一逆推代回上式：,70,由此逐一逆推代回上式：,71,最后,最优策略：,再由状态转移方程,再由状态转移方程,最大装载价值为,72,例：用动态规划方法求解：,解：我们用背包问题顺序解的思路：,人为的划分三个阶段：,k=1,2,3,阶段指标函数及其他分配情况如下图：,1,2,3,73,1,2,3,动态规划的顺序递推方程为：,74,1,2,3,75,76,1,2,3,77,78,79,80,81,最优决策为,所对应的最优值为,82,作业：,P235 5.8,83,