第10章动态规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高 级 运 筹 学,第十章 动态规划,1,多阶段决策过程最优化问题举例,2,基本概念、基本方程与最优化原理,3,动态规划的应用,(1),4,动态规划的应用,(2),1,第十章 动态规划,动态规划：解决多阶段决策过程最优化问题,解决思路：多阶段 单阶段,解决的具体问题：最短路径、装载问题、库存、资源分配、生产过程最优化等问题、,决策过程,确定性决策过程,随机性决策过程,离散决策过程,连续决策过程,离散确定性决策过程,连续随机性决策过程,连续确定性决策过程,离散随机性决策过程,2,1,多阶段决策过程最优化问题举例,例,1,最短路径问题,下图表示从起点,A,到终点,E,之间各点的距离。求,A,到,E,的最,短路径。,B,A,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,3,1,多阶段决策过程最优化问题举例,讨论：,1,、以上求从,A,到,E,的最短路径问题，可以转化为四个性质完全相,同，但规模较小的子问题，即分别从,D,i,、,C,i,、,B,i,、,A,到,E,的最短路,径问题。,第四阶段：两个始点,D,1,和,D,2,，,终点只有一个；,表,10-1,分析得知：从,D,1,和,D,2,到,E,的最短路径唯一。,阶段,4,本阶段始点,（状态）,本阶段各终点（决策）,到,E,的最短距离,本阶段最优终点,（最优决策,),E,D,1,D,2,10*,6,10,6,E,E,B,A,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,4,第三阶段：有三个始点,C,1,，,C,2,，,C,3,，终点有,D,1,，,D,2,，对始点,和终点进行分析和讨论分别求,C,1,，,C,2,，,C,3,到,D,1,，,D,2,的最短路,径问题：,表,10-2,分析得知：如果经过,C,1,，,则最短路为,C,1,-D,2,-E,；,如果经过,C,2,，,则最短路为,C,2,-D,2,-E,；,如果经过,C,3,，则最短路为,C,3,-D,1,-E,。,1,多阶段决策过程最优化问题举例,阶段,3,本阶段始点,（状态）,本阶段各终点（决策）,到,E,的最短距离,本阶段最优终点,（最优决策,),D,1,D,2,C,1,C,2,C,3,8+10=18,7+10=17,1+10=11,6+6=12,5+6=11,6+6=12,12,11,11,D,2,D,2,D,1,B,A,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,5,第二阶段：有,4,个始点,B,1,B,2,B,3,B,4,，终点有,C,1,C,2,C,3,。对始点和终点进行分,析和讨论分别求,B,1,B,2,B,3,B,4,到,C,1,C,2,C,3,的最短路径问题：,表,10-3,分析得知：如果经过,B,1,，则走,B,1,-C,2,-D,2,-E,；,如果经过,B,2,，则走,B,2,-C,3,-D,1,-E,；,如果经过,B,3,，则走,B,3,-C,3,-D,1,-E,；,如果经过,B,4,，则走,B,4,-C,3,-D,1,-E,。,1,多阶段决策过程最优化问题举例,阶段,2,本阶段始点,（状态）,本阶段各终点（决策）,到,E,的最短距离,本阶段最优终点（最优决策,),C,1,C,2,C,3,B,1,B,2,B,3,B,4,2+12=14,4+12=16,4+12=16,7+12=19,1+11=12,7+11=18,8+11=19,5+11=16,6+11=17,2+11=13,3+11=14,1+11=12,12,13,14,12,C,2,C,3,C,3,C,3,6,第一阶段：只有,1,个始点,A,，终点有,B,1,B,2,B,3,B,4,。对始点和终,点进行分析和讨论分别求,A,到,B,1,B,2,B,3,B,4,的最短路径问题：,表,10-4,最后，可以得到：从,A,到,E,的最短路径为,A,B,4,C,3,D,1,E,1,多阶段决策过程最优化问题举例,阶段,1,本阶段始点,(,状态,),本阶段各终点（决策）,到,E,的最短距离,本阶段最优终点,(,最优决策,),B,1,B,2,B,3,B,4,A,4+12=16,3+13=16,3+14=17,2+12=14,12,C,2,7,以上计算过程及结果，可用图,2,表示，可以看到，以上方法不仅,得到了从,A,到,D,的最短路径，同时，也得到了从图中任一点到,E,的最,短路径。,以上过程，仅用了,22,次加法，计算效率远高于穷举法。,B,A,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,1,多阶段决策过程最优化问题举例,8,一、基本概念：,1,、,阶段,k,：,表示决策顺序的离散的量，阶段可以按时间或空间划分。,2,、,状态,s,k,：,能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。,3,、,决策,x,k,：,从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为,x,k,(s,k,),。,决策允许集合,D,k,(s,k,),：,在状态,s,k,下，允许采取决策的全体。,4,、,策略,P,k,n,(s,k,),：,从第,k,阶段开始到最后第,n,阶段的决策序列，称,k,子策略。,P,1,n,(s,1,),即为全过程策略。,5,、,状态转移方程,s,k+1,=,T,k,(s,k,x,k,),：,某一状态以及该状态下的决策，与下一状态之间的函数关系。,2,基本概念、基本方程与最优化原理,9,6,、,阶段指标函数,v,k,(s,k,x,k,),：,从状态,s,k,出发，选择决策,x,k,所产生的第,k,阶段指标。,过程指标函数,V,k,n,(s,k,x,k, x,k+1,x,n,),：,从状态,s,k,出发，选择决策,x,k,x,k+1, ,x,n,所产生的过程指标。动态规划要求过程指标具有可分离,性，即,V,k,n,(s,k,x,k, x,k+1, ,x,n,) =,v,k,(s,k, x,k,)+V,k+1,(s,k+1, x,k+1, ,x,n,),称指标具有可加性，或,V,k,n,(s,k,x,k, x,k+1, ,x,n,) =,v,k,(s,k, x,k,)V,k+1,(s,k+1,x,k+1, ,x,n,),称指标具有可乘性。,二、基本方程：,最优指标函数,f,k,(s,k,),：,从状态,s,k,出发，对所有的策略,P,k,n,，,过程指,标,V,k,n,的最优值，即,2,基本概念、基本方程与最优化原理,10,对于可加性指标函数，上式可以写为,上式中“,opt”,表示“,max”,或“,min”,。,对于可乘性指标函数，上式可以,写为,以上式子称为动态规划最优指标的递推方程，是动态规划的基本,方程。,终端条件：为了使以上的递推方程有递推的起点，必须要设定最,优指标的终端条件，一般最后一个状态,n+1,下最优指标,f,n+1,(s,n+1,) = 0,。,2,基本概念、基本方程与最优化原理,11,三、最优化原理,作为整个过程的最优策略具有如下性质：,不管在此最优策略上的某个状态以前的状,态和决策如何，对该状态来说，以后的所有决,策必定构成最优子策略。就是说，最优策略的,任意子策略都是最优的。,2,基本概念、基本方程与最优化原理,12,一、资源分配问题,例,2.,某公司拟将某种设备,5,台，分配给所属的甲、乙、丙三个工,厂。各工厂获得此设备后，预测可创造的利润如表,10-5,所示，问这,5,台设备应如何分配给这,3,个工厂，使得所创造的总利润为最大？,表,10-5,盈利 工厂,设备台数,甲 厂,乙 厂,丙 厂,0,0,0,0,1,3,5,4,2,7,10,6,3,9,11,11,4,12,11,12,5,13,11,12,3,动态规划的应用,(1),13,解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为,1,、,2,、,3,厂。设,s,k,=,分配给第,k,个厂至第,3,个厂的设备台数（,k=1,、,2,、,3,）。,x,k,=,分配给第,k,个设备台数。,已知,s,1,=5,并有,从与的定义，可知,以下,我们从第三阶段开始计算。,3,动态规划的应用,(1),14,第三阶段,:,显然将台设备都分配给第,3,工厂时，,也就是时，第,3,阶段的指标值（即第,3,厂的盈利）,为最大，即,由于第,3,阶段是最后的阶段，故有,其中可取值为,0,1,2,3,4,5,。其数值计算见表,10,6,。,3,动态规划的应用,(1),15,表,10,6,0,1,2,3,4,5,0,0,0,0,1,4,4,1,2,6,6,2,3,11,11,3,4,12,12,4,5,12,12,5,3,动态规划的应用,(1),16,其中表示取,3,子过程上最优指标值时的,决策，例如在表,10-6,中可知当,=4,时，有有,此时，即当时，此时取,（把,4,台设备分配给第,3,厂）是最优决策，此时阶段指标值,（盈利）为,12,，最优,3,子过程最优指标值也为,12,。,第二阶段：,当把台设备分配给第,2,工厂和第,3,工,厂时，则对每个值，有一种最优分配方案，使最大盈利,即最优,2,子过程最优指标函数值为,3,动态规划的应用,(1),17,因为上式也可写成,其数值计算如表,10,7,所示。,表,10,7,0,1,2,3,4,5,0,0,0,1,0,4, ,5,1,2,0,6,5,4, ,10,2,3,0,11,5,6,11,0, ,14,2,4,0,12,11,4,11,0,16,1,2,5,0,12,5,12,11,6,11,4,11,0,21,2,3,动态规划的应用,(1),18,其中在的这一行里，当时，,这里从表,10,5,中可知，把,1,台设备交给乙厂所得盈,利数即可，知，这里从表,10,6,查,即可知,=11,。同样可知当时，可知,;,当时，；当时，,；当时，,；由于，不可能分,2,厂,5,台设备，故时，栏空着不填。从,这些数值中取得最大即得，即有,=16,。在此行中,我们在取最大值的 上面加一横以示,区别，也可知这时的最优决策为,1,或,2,。,3,动态规划的应用,(1),19,第一阶段：,把台设备分配给第,1,，第,2,，第,3,厂时，最大,盈利为其中可取值,0,1,2,3,4,5.,数值计算见表,10,8,表,10-8,然后按计算表格的顺序推算，可知最优分配方案有两个：,1.,由于，根据，查表,10,7,可,知，再由 ，求得。即分配,给甲厂,0,台，乙厂,2,台，丙厂,3,台。,2.,由于，根据 ，查表,10,7,可,0,1,2,3,4,5,5,3,16 9+10 12+5 13+0,21 0,2,3,动态规划的应用,(1),20,知，再由,求得，,即分配给甲厂,2,台，乙厂,2,台，丙厂,1,台。,这两种分配方案都能得到最高的总盈利,21,万元。,3,动态规划的应用,(1),21,二、背包问题,设有,n,种物品，每一种物品数量无限。第,i,种物品每件,重量为,w,i,公斤，每件价值,c,i,元。现有一只可装载重量为,W,公斤的背包，求各种物品应各取多少件放入背包，使背,包中物品的价值最高。,这个问题可以用整数规划模型来描述。设,x,i,为第,i,种,物品装入背包的件数（,i,=1, 2, ,n,），,背包中物品的总,价值为,z,，,则,Max z = c,1,x,1,+c,2,x,2,+ +,c,n,x,n,s.t. w,1,x,1,+w,2,x,2,+,w,n,x,n,W,x,1, x,2, , x,n,0,且为整数。,3,动态规划的应用,(1),22,下面用动态规划逆序解法求解它。设,阶段变量,k,：第,k,次装载第,k,种物品（,k=1, 2, , n,）,状态变量,s,k,：第,k,次装载时背包还可以装载的重量；,决策变量,u,k,=,x,k,：第,k,次装载第,k,种物品的件数；,决策允许集合：,D,k,(s,k,) = ,x,k,| 0,x,k,s,k,/w,k,，,x,k,为整数,；,状态转移方程：,s,k+1,=,s,k,w,k,x,k,；,阶段指标：,v,k,=,c,k,x,k,；,最优过程指标函数,f,k,(s,k,),：第,k,到,n,阶段容许装入物品的最大使,用价值；,递推方程：,f,k,(s,k,) = max c,k,x,k,+,f,k+1,(s,k+1,),= max c,k,x,k,+,f,k+1,(s,k,w,k,x,k,),；,x,D,k,(s,k,),终端条件：,f,n+1,(s,n+1,) = 0,。,3,动态规划的应用,(1),23,例,3.,某咨询公司有,10,个工作日可以去处理四种类型的咨,询项目，每种类型的咨询项目中待处理的客户数量、处理每个,客户所需工作日数以及所获得的利润如表,10,9,所示。显然该公,司在,10,天内不能处理完所有的客户，它可以自己挑选一些客,户，其余的请其他咨询公司去做，应如何选择客户使得在这,10,个工作日中获利最大？,表,10,9,咨询项目类型,待处理客户数,处理每个客户所需工作日数,处理每个客户所获利润,1,2,3,4,4,3,2,2,1,3,4,7,2,8,11,20,3,动态规划的应用,(1),24,解：用动态规划来求解此题。,我们把此问题分成四个阶段，第一阶段我们决策将,处理多少个第一种咨询项目类型中的客户，第二阶段决,策将处理多少个第二种咨询项目类型中的客户，第三阶,段、第四阶段我们也将作出类似的决策。我们设,分配给第,k,种咨询项目到第四种咨询项目的所,有客户的总工作日（第,k,阶段的状态变量）。,=,在第,k,种咨询项目中处理客户的数量（第,k,阶段,的决策变量）。,已知,10,并有,3,动态规划的应用,(1),25,并从与的定义可知,从第四阶段开始计算：,显然将个工作日尽可能分配给第四,类咨询项目，即时，第四阶段的指标值为最大，,其中，表示取不大于的最大整数，符号为,取整符号，故有,由于第四阶段是最后的阶段，故有,3,动态规划的应用,(1),26,因为至多为,10,，其数值计算见表,10,10,。,表,10,10,0,1,0,0,0,1,0,0,2,0,0,3,0,0,4,0,0,5,0,0,6,0,0,7,0,20,1,8,0,20,1,9,0,20,1,10,0,1,1,3,动态规划的应用,(1),27,第三阶段：,当把个工作日分配给第四类和第,三类咨询项目时，则对每个值，都有一种最优分配方,案，使其最大盈利即最优,3,子过程最优指标函数值为,因为,因为至多为,10,，,所以的取值可为,0,1,2,。其数值计算,见表,10,11,。,3,动态规划的应用,(1),28,表,10,11,0 1 2,0,0,0,1,0,0,2,0,0,3,0,0,4,0,0,11,1,5,0,0,11,1,6,0,0,11,1,7,11+0,20,0,8,0,20,11+0,22,2,9,0,20,11+0,22,2,10,0,20,11+0,22,2,3,动态规划的应用,(1),29,第二阶段：,同样以每个值都有一种最优分配方案，使其最大盈利即,最优,2,子过程最优指标函数值为：,因为，故有,因为至多为,10,，所以的取值为,0,1,2,3,。其数值计算,见表,10,12,。,3,动态规划的应用,(1),30,3,动态规划的应用,(1),表,10-12,31,第一阶段：,我们已知，又因为 ，同样有,因为,故可取值为,0,1,2, ,10,。其数值计算,见表,10,13,。,表,10,13,3,动态规划的应用,(1),32,从,表,10,13,可知，从而得,10,0,10,，在表,10,12,的的这一行可知，由,，查表,10,11,的的这一行可知,，最后由，查表,10-10,的的这,一行得，综上所述得最优解为：,此时最大盈利为,28,。,现在我们不妨假设该咨询公司的工作计划有所改变，只有,8,个工作日来处理这四类咨询项目，那么该咨询公司如何选择,客户使得获利最大呢？我们不必从头开始重做这个问题，而只,要在第一阶段上把改成,8,，重新计算就可得到结果，如表,10,14,所示，这是动态规划的一个好处。,3,动态规划的应用,(1),33,表,10,14,如上一样可从表,10,14,10,12,10,11,10,10,得到两组最优解,如下：,它们的最优解（即最大盈利）都为,22,。,一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计,算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加,的工作日的新的信息，也可得到新的结果。,3,动态规划的应用,(1),34,实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为,W,公斤，这,N,种物品中第,i,种物品的重量为，价值为，第,i,种物品的总数量的，我们可以设表示携带第,i,种物品的数量，则其数学模型为：,S.T.,且为整数。,我们不妨用此模型去求解例,3,，也一定得出同样的结果。,3,动态规划的应用,(1),35,三、生产与存贮问题,例,4.,某公司为主要电力公司生产大型变压器，由于电力,采取预订方式购买，所以该公司可以预测未来几个月的需求,量。为确保需求，该公司为新的一年前四个月制定一项生产,计划，这四个月的需求如表,10,15,所示。,生产成本随着生产数量而变化。调试费为,4,，除了调度费,用外，每月生产的头两台各花费为,2,，后两台花费为,1,。最大,生产能力每月为,4,台，生产成本如表,10,16,所示。,表,10,15,3,动态规划的应用,(1),36,表,10,16,每台变压器在仓库中由这个月存到下个月的储存费为,1,，,仓库的最大储存能力为,3,台，另外，知道在,1,月,1,日时仓库里存,有一台变压器，要求在,4,月,30,日仓库的库存量为零。试问该公,司应如何制定生产计划，使得四个月的生产成本和储存总费,用最少？,解：我们按月份来划分阶段，第,i,个月为第,i,阶段,：（,i=1,2,3,4).,设 为第,k,阶段期初库存量；,k=1,2,3,4,3,动态规划的应用,(1),37,为第,k,阶段生产量；,k=1,2,3,4,为第,k,阶段需求量；,k=1,2,3,4,，,这已在表,10-15,中告诉我们。,因为下个月的库存量等于上个月的库存量加上上个月的,产量减去上个月的需求量，我们就得到了如下状态转移方,程：,因为，故有,因为，故有,3,动态规划的应用,(1),38,由于必须要满足需求，则有,通过移项得到,另一方面，第,k,阶段的生产量必不大于同期的生产能力,（,4,台），也不大于第,k,阶段至第四阶段的需求之和与第,k,阶段,期初库存量之差，否则第,k,阶段的生产量就要超过从第,k,阶段,至第四阶段的总需求，故有,以下我们从第四阶段开始计算：,从以上的状态转移方程可知,这样就有,3,动态规划的应用,(1),39,这里的阶段指标可以分成两部分，即生产成本与,储存费，即为,由于第四阶段末要求库存为零，即有，,这样可得,对于每个的可行值，的值列于表,10,17,。,表,10,17,3,动态规划的应用,(1),40,表中当时，可知第四阶段要生产,台，从表,10,16,可知总成本为,9,，同样可以算出当为,1,2,3,时,的情况，结果已列于表,10,17,中。,第三阶段：,此时有：,因为,以及,所以有,例如，当第三阶段初库存量时，生产量为,2,时，,则所以生产成本为,8,，第三阶段末库存,为,2,时，储存费为，而,3,动态规划的应用,(1),41,查,10,17,表可知，这样可知，,填入表,10,18,中的栏内，其他结果如表,10,18,所,示 ：,表,10,18,第二阶段：,因为所以有,3,动态规划的应用,(1),42,计算结果如表,10,19,所示。,表,10,19,3,动态规划的应用,(1),43,第一阶段：,因为故有,计算结果见表,10,20,。,表,10,20,3,动态规划的应用,(1),44,利用递推关系可以从表,10,20,，表,10,19,，表,10,18,和表,10,17,得到两组最优解：,这时有最低总成本,29,。,3,动态规划的应用,(1),45,3,动态规划的应用,(1),四、系统可靠性问题,例,5.,某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为,0.40,，,0.60,，,0.80,。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：,问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？,高级科学家,小组,1,2,3,0,0.40,0.60,0.80,1,0.20,0.40,0.50,2,0.15,0.20,0.30,46,3,动态规划的应用,(1),解：用逆序算法。设,阶段：每个研究小组为一个阶段，且,阶段,1,2,3,小组,1,2,3,47,3,动态规划的应用,(1),计算,当,n=3,时，,当,n=2,时，,s,3,f,3,*(s,3,),x,3,*,0,0,80,0,1,0,50,1,2,0,30,2,x,2,s,2,f,2,(s,2,x,2,)=P,2,(x,2,) f,3,*(s,2,-x,2,),f,2,*(s,2,),x,2,*,0,1,2,0,0,48,0,48,0,1,0,30,0,32,0,30,0,2,0,18,0,20,0,16,0,16,2,48,3,动态规划的应用,(1),当,n=1,时，,最优解为,x,1,*=1,，,x,2,*=0,，,x,3,*=1,；,科研项目最终失败的概率为,0.060,。,x,1,s,1,f,1,(s,1,x,1,)=P,1,(x,1,) f,2,*(s,1,-x,1,),f,2,*(s,2,),x,2,*,0,1,2,2,0,064,0,060,0,072,0,060,1,49,4,动态规划的应用,(2),*,一、,连续,确定性动态规划,对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。,50,4,动态规划的应用,(2),*,机器负荷分配问题,例,1,一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为,P,1,=8u,1,，,其中,u,1,为在高负荷状态下生产的机器数目，年完好率为,a=0.7,，,即到年底有,70,的机器保持完好。在低负荷下生产时，产量函数为,P,2,=5u,2,，,其中,u,2,为在低负荷状态下生产的机器数目，年完好率为,b=0.9,。,设开始生产时共有,1000,台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得,5,年内生产的产品总产量最高,。,51,4,动态规划的应用,(2),*,解 建立动态规划模型：,分为,5,个阶段，每个阶段为,1,年。设状态变量,s,k,表示在第,k,阶段初拥有的完好机器数目；,k=1,2,3,4,5,。,决策变量,x,k,表示第,k,阶段中分配给高负荷状态下生产的机器数目；,k=1,2,3,4,5,。,显然,s,k,-x,k,为分配给低负荷状态下生产的机器数目。,状态转移方程为,s,k,+1=0.7x,k,+0.9(s,k,-x,k,),阶段指标,r,k,(s,k,x,k,)=8x,k,+5(s,k,-x,k,),最优指标函数 ，其,中,k=1,2,3,4,5,。,f,6,(s,6,)=0,。,52,4,动态规划的应用,(2),*,第,5,阶段：,因为,f,5,(s,5,),是,x,5,的线性单调增函数，故有,x,5,*,=s,5,，,于是有,f,5,(s,5,)=8s,5,。,第,4,阶段：,53,4,动态规划的应用,(2),*,同样的,，,f,4,(s,4,),是,x,4,的线性单调增函数，有,x,4,*=s,4,，,f,4,(s,4,)=13.6s,4,。,对前几个阶段依次类推，可得,f,3,(s,3,)=17.5s,3,，,f,2,(s,2,)=20.75s,2,，,f,1,(s,1,)=23.72s,1,。,因为期初共有完好机器,1000,台，故,s,1,=1000,。有,f,1,(s,1,)=23.72s,1,23720,，即,5,年最大的产量为,23720,台。得最优解为 ，,， ， 。,这意味着前两年应把年初完好机器完全投入低负荷生产，,后三年应把年初完好机器完全投入高负荷生产。,54,4,动态规划的应用,(2),*,下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知,s,1,=1000,根据状态转移方程，有,:,55,4,动态规划的应用,(2),*,上面所讨论的最优策略过程，初始端状态,s,1,=1000,台是固定的，终点状态,s,6,没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。,如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第,5,年度结束时仍要保持,500,台机器完好（而不是,278,台），应如何安排生产才能使得总产量最大？,下面来分析：,根据终点条件有,可得,56,4,动态规划的应用,(2),*,显然，由于固定了终点的状态，,x,5,的取值受到了,约束。因此有,类似的，,容易解得 ，,f,4,(s,4,)=21.7s,4,-7500,。,57,4,动态规划的应用,(2),*,依次类推，得,f,3,(s,3,)=24.5s,3,-7500,f,2,(s,2,)=27.1s,2,-7500,f,1,(s,1,)=29.4s,1,-7500,再采用顺序方法递推计算各年的状态，有,s,1,=1000,，,58,4,动态规划的应用,(2),*,可见，为了使终点完好的机器数量增加到,500,台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第,5,年，也只能全部投入高负荷。,相应的最优指标为,f,1,(s,1,)=29.4s,1,-7500,21900,。,可以看到，因为增加了附加条件，总产量,f,1,(s,1,),要比终点自由情况下的产量要低。,59,二、离散随机性动态规划,随机型的动态规划是指状态的转移律是不确定的，即,对给定的状态和决策，下一阶段的到达状态是具有确定概率,分布的随机变量，这个概率分布由本阶段的状态和决策完全,确定。随机型动态规划的基本结构如下图：,4,动态规划的应用,(2),*,s,k,状态,x,k,决策,概率,k,阶段的收益,p,1,p,2,p,N,.,k+1,阶段的状态,s,k+1,c,1,c,2,c,N,1,2,N,60,4,动态规划的应用,(2),*,图中,N,表示第,k+1,阶段可能的状态数，,p,1,、,p,2,、,p,N,为给定状态,s,k,和决策,x,k,的前提下，可能达到下一个状态的概率。,c,i,为从,k,阶段状态,s,k,转移到,k+1,阶段状态为,i,时的指标函数值。,在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。,61,离散随机性动态规划,例,2,某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔,2000,元。根据有经验的技术人员估计，试制品合格的概率为,0.4,，每次试制一批的装配费为,200,元，每件产品的制造成本为,100,元。每次试制的周期为,1,个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？,62,离散随机性动态规划,解：,把三次试制当作三个阶段（,k=1,2,3,）,决策变量,x,k,表示第,k,次生产的产品的件数；状态变量,s,k,表示,第,k,次试制前是否已经生产出合格品，如果有合格品，则,s,k,=0,；,如果没有合格品，记,s,k,=1,。,最优函数,f,k,(s,k,),表示从状态,s,k,、,决策,x,k,出发的第,k,阶段以后的最小期望费用。故,有,f,k,(0),0,。,生产出一件合格品的概率为,0.4,，所以生产,x,k,件产品都不合格的概率为 ，至少有一件合格品的概率为,1-,，故有状态转移方程为,63,离散随机性动态规划,用,C(x,k,),表示,第,k,阶段的费用，第,k,阶段的费用包,括制造成本和装配费用，故有,根据状态转移方程以及,C(x,k,),，,可得到,64,离散随机性动态规划,如果,3,个月后没有试制出一件合格品，则要承担,2000,元的罚金，因此有,f,4,(1)=20,。,当,k=3,时，计算如下表：,x,3,s,3,C(x,3,)+20,f,3,(s,3,),x,3,*,0,1,2,3,4,5,6,0,0,0,0,1,20,15,11.2,9.32,8.59,8.56,8.93,8.56,5,65,离散随机性动态规划,当,k=2,时，计算如下表：,x,2,s,2,C(x,2,)+8.56,f,2,(s,2,),x,2,*,0,1,2,3,4,0,0,0,0,1,8.56,8.14,7.08,6.85,7.11,6.85,3,66,离散随机性动态规划,当,k=1,时，有,x,1,s,1,C(x,1,)+6.85,f,1,(s,1,),x,1,*,0,1,2,3,0,0,0,0,1,6.85,7.11,6.46,6.48,6.46,2,67,离散随机性动态规划,上面三个表中并没有列出,x,k,取更大数值的情况，因为可以证明以后的,C(x,k,)+ f,k+1,(1),的值是对,x,k,单调增加的。,因此得到的最优策略是，在第,1,个阶段试制,2,件产品；如果都不合格，在第,2,阶段试制,3,件产品；如果仍都不合格，则在第,3,个阶段试制,5,件产品。该策略得到的最小的期望费用,6.46,。,68,离散随机性动态规划,随机采购问题,例,3,某公司打算在,5,周内采购一批原料，未来,5,周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在,5,周内采购这批原料。如果第一周价格很高，可以等到第,2,周；同样的，第,2,周如果仍对价格不满意，可以等到第,3,周；类似地，未来几周都可能选择购买或者等待，但必须保证第,5,周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？,价格,概率,450,0.25,470,0.35,500,0.40,69,离散随机性动态规划,解,：建立动态规划。按照采购周期分为,5,个阶段，将每周的价格看作该阶段的状态。假设状态变量,s,k,表示第,k,周的实际价格，决策变量,x,k,表示第,k,周是否采购的,0-1,变量。如决定采购，则,x,k,=1,；,如选择等待，则,x,k,=0,。,用,s,k,E,表示第,k,周等待，而在以后采取最优决策时采购价格的期望值。,根据定义，,动态规划基本方程如下：,70,离散随机性动态规划,第五阶段：,因为如果前,4,周都没有买，那第,5,周必须购买，因,此有,f,5,(s,5,)=s,5,，即,f,5,(450)=450,；,f,5,(470)=470,；,f,5,(500)=500,。,第四阶段：,下面考虑第,4,周的情况。,如第,4,周购买，则需花费,s,4,；,如果不买，则必须,在第,5,周购买。在第,5,周采购的费用的期望值为,71,离散随机性动态规划,于是 ，有,故第,4,周的最优决策为,同理，考虑第,3,周的最优决策。,72,离散随机性动态规划,第三阶段：,如果第,3,周采购，则需花费,s,3,；,也要和第,3,周后再,采购的费用的期望值作比较。,于是 ，有,故第,3,周的最优决策为,73,离散随机性动态规划,第二阶段：,同理可得,故第,2,周的最优决策为,74,离散随机性动态规划,第一阶段：,同理可得,第,1,周的最优决策为,75,离散随机性动态规划,由上可知，最优的采购策略为：在第,1,、,2,、,3,周的市场价格为,450,时，应该立即采购，否则等待；在第,4,周时，若市场价格为,450,或,470,时，应该采购，否则等待。若等到第五周，只能采购。,76,