动态规划+例子.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,动态规划+例子,动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。,2,最短路径问题,：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。,1,2,3,4,5,6,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,E,3,F,1,F,2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,3,背包问题,有一个徒步旅行者，其可携带物品重量的限度为,a,公斤，设有,n,种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,物品,1 2 ,j,n,重量（,公斤/件,）,a,1,a,2,a,j,a,n,每件使用价值,c,1,c,2,c,j,c,n,类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,4,生产决策问题,：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地,根据库存和需求决定生产计划。,机器负荷分配问题,：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在,每年开始时，决定如何重新分配,完好的,机器在两种不同的负荷下生产的数量,，使在五年内产品的总产量达到最高。,航天飞机飞行控制问题,：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。,5,根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。,在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。,各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。,当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。,多阶段决策过程的特点：,6,针对多阶段决策过程的最优化问题，美国数学家,Bellman,等人在20世纪50年代初提出了著名的最优化原理，,把多阶段决策问题转化为一系列单阶段最优化问题,，从而逐个求解，,创立了解决这类过程优化问题的新方法：动态规划。,对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是Bellman提出的著名的最优化原理。,简言之，一,个最优策略的子策略必然也是最优的,。,Bellman在1957年出版的Dynamic Programming是动态规划领域的第一本著作。,7,例1,、,从,A,地到,E,地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,二.最短路径问题,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,8,解：,整个计算过程分四个,阶段,，从最后一个阶段开始。,第四阶段（,D,E,）：,D,有两条路线到终点,E,。,显然有,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,9,首先考虑经过 的两条路线,第三阶段（,C,D,）：,C,到,D,有 6 条路线。,(最短路线为 ),A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,10,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),考虑经过 的两条路线,11,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),考虑经过 的两条路线,12,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),第二阶段（,B,C,）：,B,到,C,有 9 条路线。,首先考虑经过 的3条路线,13,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),考虑经过 的3条路线,14,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),考虑经过 的3条路线,15,A,B,2,B,1,B,3,C,1,C,3,D,1,D,2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C,2,(最短路线为 ),第一阶段（,A,B,）：,A,到,B,有 3 条路线。,（最短距离为19）,16,动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，,它可以把一个,n,维决策问题变换为几个一维最优化问题,，从而一个一个地去解决。,需指出：,动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法,。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,即在系统发展的不同时刻（或阶段）根据系统所处的状态，,不断地做出决策,；,动态决策问题的特点：,系统所处的,状态和时刻,是进行决策的重要因素；,找到,不同时刻,的最优决策以及,整个过程的最优策略,。,17,动态规划方法的关键：在于正确地写出,基本的递推关系式,和,恰当的边界条件,（简称,基本方程,）。,要做到这一点，就必须将问题的过程分成几个相互联系的,阶段,，恰当的选取,状态变量,和,决策变量,及定义,最优值函数,，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。,即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,18,2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段,分开,，又把当前效益和未来效益,结合,起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.,最优化原理：,作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，,一个最优策略的子策略也是最优的,。,3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。,19,动态规划求解的多阶段问题的特点：,每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。,具有这种性质的状态称为无后效性（即马尔科夫性）状态。,动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。,20,现有数量为,a,（万元）的资金，计划分配给,n,个工厂,用于扩大再生产。,假设：,x,i,为分配给第,i,个工厂的资金数量（万元）；,g,i,(,x,i,),为第,i,个工厂得到资金后提供的利润值（万元）。,问题：如何确定各工厂的资金数，使得总的利润为最大。,据此，有下式：,三.投资分配问题,21,令：,f,k,(,x,)表示 以数量为,x,的资金分配给,前,k,个,工厂，所得到的最大利润值。,用动态规划求解，就是,求,f,n,(,a,)的问题,。,当,k,=1 时，,f,1,(,x,)=,g,1,(,x,)（因为只给一个工厂）,当1,k,n,时，其递推关系如下：,设：,y,为分给第,k,个工厂的资金（其中 0,y,x,），此时还剩,x,y,（万元）的资金需要分配给前,k,1 个工厂,如果采取最优策略，则得到的最大利润为,f,k,1,(,xy,),因此总的利润为：,g,k,(,y,),f,k,1,(,xy,),22,如果,a,是以万元为资金分配单位，则式中的,y,只取非负整数0，1，2，,x,。上式可变为：,所以，根据动态规划的最优化原理，有下式：,23,例2：,设国家拨给,60,万元投资，供,四,个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,投资,利润,0,10,20,30,40,50,60,g,1,(,x,),0,20,50,65,80,85,85,g,2,(,x,),0,20,40,50,55,60,65,g,3,(,x,),0,25,60,85,100,110,115,g,4,(,x,),0,25,40,50,60,65,70,解,：依据题意，是要求,f,4,(60)。,24,按顺序解法计算。,第一阶段：求,f,1,(,x,)。显然有,f,1,(,x,),g,1,(,x,)，得到下表,投资,利润,0,10,20,30,40,50,60,f,1,(,x,),g,1,(,x,),0,20,50,65,80,85,85,最优策略,0,10,20,30,40,50,60,第二阶段：求,f,2,(,x,)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。,25,最优策略为（40，20），此时最大利润为120万元。,同理可求得其它,f,2,(,x,)的值。,26,最优策略为（30，20），此时最大利润为105万元。,27,最优策略为（20，20），此时最大利润为90万元。,最优策略为（20，10），此时最大利润为70万元。,28,最优策略为（10，0）或（0，10），此时最大利润为20万元。,f,2,(0)0。,最优策略为（0，0），最大利润为0万元。,得到下表,最优策略为（20，0），此时最大利润为50万元。,29,投资,利润,0,10,20,30,40,50,60,f,2,(,x,),0,20,50,70,90,105,120,最优策略,(0,0),(10,0),(0,10),(20,0),(20,10),(20,20),(30,20),(40,20),第三阶段：求,f,3,(,x,)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。,30,最优策略为（20，10，30），最大利润为155万元。,同理可求得其它,f,3,(,x,)的值。得到下表,31,投资,利润,0,10,20,30,40,50,60,f,3,(,x,),0,25,60,85,110,135,155,最优,策略,(0,0,0),(0,0,10),(0,0,20),(0,0,30),(20,0,20),(20,0,30),(20,10,30),第四阶段：求,f,4,(60)。即问题的最优策略。,32,最优策略为（20，0，30，10），最大利润为160万元。,33,有一个徒步旅行者，其可携带物品重量的限度为,a,公斤，设有,n,种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,物品,1 2 ,j,n,重量（,公斤/件,）,a,1,a,2,a,j,a,n,每件使用价值,c,1,c,2,c,j,c,n,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,四、背包问题,34,设,x,j,为第,j,种物品的装件数（非负整数）则问题的数学模型如下：,用,动态规划方法求解,，令,f,k,(,y,)=总重量不超过,y,公斤，包中只装有前,k,种物品时的最大使用价值。,其中,y,0，,k,1,2,n。,所以问题就是求,f,n,(,a,),35,其递推关系式为：,当,k,=1 时，有：,36,例3,：求下面背包问题的最优解,物品(,x,i,),x,1,x,2,x,3,重量（,a,i,）,3 2 5,使用价值,8 5 12,解,：,a,5 ，问题是求,f,3,(5),37,物品(,x,i,),x,1,x,2,x,3,重量（,a,i,）,3 2 5,使用价值,8 5 12,38,物品(,x,i,),x,1,x,2,x,3,重量（,a,i,）,3 2 5,使用价值,8 5 12,39,物品(,x,i,),x,1,x,2,x,3,重量（,a,i,）,3 2 5,使用价值,8 5 12,40,41,所以，最优解为,X,（1.1.0），,最优值为,Z,=13。,总结：,解动态规划的一般方法:,从终点逐段向始点方向寻找,最小(大)的方法。,42,排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。,1、,n,1 排序问题,即,n,种零件经过1 种设备进行加工，如何安排？,14,6,8,20,23,交货日期（d）,4,5,1,7,3,加工时间（t）,零件代号,例5.1,五、排序问题,43,（1）平均通过设备的时间最小,按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,1,4,8,13,20,交货时间,8,23,14,6,20,平均通过时间,延迟时间=13 6=7,44,（2）按时交货排列顺序,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,5,6,10,17,20,交货时间,8,23,14,6,20,平均通过时间,延迟时间=0,45,（3）既满足交货时间，又使平均通过时间最小,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,1,6,9,13,20,交货时间,8,23,14,6,20,延迟时间=0,平均通过时间,46,2、,n,2 排序问题,即,n,种零件经过2 种设备进行加工，如何安排？,例5.2,4,9,5,2,3,B,5,3,7,8,6,A,零件,设备,A,B,T,47,经变换为,4,9,5,2,3,B,5,3,7,8,6,A,零件,设备,加工顺序图如下：,A,B,T,3,7,5,6,8,9,5,4,3,2,+2,+2,-5,加工周期 T=3+7+5+6+8+2=31,48,3、,n,3 排序问题,即n 种零件经过 3 种设备进行加工，如何安排？,例5.3,3,4,6,8,5,6,4,6,8,3,5,7,9,3,10,C,B,A,A,B,C,T,49,A,B,C,T,变换,4+3,6+4,5+8,6+5,6+4,8+6,5+3,7+5,3+9,10+3,B+C,A+B,50,排序,4+3,6+4,5+8,6+5,6+4,8+6,5+3,7+5,3+9,10+3,B+C,A+B,复原,3,4,6,8,5,6,4,6,8,3,5,7,9,3,10,C,B,A,51,计算,T=6+10+8+7+6+4+3=44,计算依据：,52,