第19讲 欧拉回路及哈密顿回路

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模与数学实验,欧拉回路及哈密顿回路问 题,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例,（一） 欧 拉 图,（二） 中 国 邮 递 员 问 题,（一） 哈 密 尔 顿 图,（二） 推 销 员 问 题,7,3,1,2,3,4,1,2,4,5,5,6,6,7,8,9,割边,G,的边 是割边的充要条件是 不含在,G,的圈中,割边的定义,：设,G,连通，,E,(,G,),若从,G,中删除边 后，图,G,- ,不连通，则称边 为图,G,的割边,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧 拉 图,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,5,v,1,欧拉道路：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,欧拉巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,6,v,1,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧拉图,非欧拉图,返回,中国邮递员问题,-,定义,中国邮递员问题,-,算法,Fleury,算法基本思想,：从任一点出发，每当访问,一条边时，先要进行检查如果可供访问的边不只,一条，则应选一条不是未访问的边集的导出子图的,割边,作为访问边，直到没有边可选择为止,.,v,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,v,5,e,6,e,6,e,7,e,8,e,9,e,10,若,G,不是欧拉图，则,G,的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是：在一些点对之间,引入重复边（重复边与它平行的边具有相同的权），,使原图成为欧拉图，但希望所有添加的重复边的,权的总和为最小,v,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,v,5,v,6,e,6,e,7,e,8,e,9,（）求出,G,1,的,最小权理想匹配,M,，得到奇次顶点的最佳配对,返回,哈 密 尔 顿 图,返回,推销员问题,-,定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是,推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,定义,在加权图,G,=(,V,E,),中，,（）权最小的哈密尔顿圈称为,最佳,H,圈,（）经过每个顶点至少一次的权最小的闭通路称为,最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H,回路，长,22,最佳推销员回路，长,4,推销员问题近似算法：,二边逐次修正法,：,例,对以下完备图，用二边逐次修正法求较优,H,圈,返回,1,、引例（最短路问题）,假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从,A,地运往,E,地，中间通过,B,、,C,、,D,三个区域，在区域内有多条路径可走，现求一条由,A,到,E,的线路，使总距离最短（或总费用最小）。,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,E,2,4,3,7,4,6,3,2,4,2,6,5,3,4,6,3,3,3,3,4,将该问题划分为,4,个阶段的决策问题，即第一阶段为从,A,到,B,j,（,j=1,，,2,，,3,），有三种决策方案可供选择；第二阶段为从,B,j,到,C,j,（,j=1,2,3,），也有三种方案可供选择；第三阶段为从,C,j,到,D,j,(j=1,2),，有两种方案可供选择；第四阶段为从,D,j,到,E,，只有一种方案选择。如果用完全枚举法，则可供选择的路线有,3321=18,（条），将其一一比较才可找出最短路线：,AB,1,C,2,D,3,E,其长度为,12,。,显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。,由于我们考虑的是从全局上解决求,A,到,E,的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至,A,点：,第四阶段，由,D,1,到,E,只有一条路线，其长度,f,4,（,D,1,）,=3,，,同理,f,4,（,D,2,）,=4,。,第三阶段，由,C,j,到,D,i,分别均有两种选择，即,，,决策点为,D,1,决策点为,D,1,，,决策点为,D,2,第二阶段，由,B,j,到,C,j,分别均有三种选择，即：,决策点为,C,2,决策点为,C,1,或,C,2,决策点为,C,2,第一阶段，由,A,到,B,，有三种选择，即：,决策点为,B,3,f,1,（,A,）,=15,说明从,A,到,E,的最短距离为,12,，最短路线的确定可按计算顺序反推而得。即,AB,3,C,2,D,2,E,上述最短路线问题的计算过程，也可借助于图形直观的表示出来：,图中各点上方框的数，表示该点到,E,的最短距离。图中红箭线表示从,A,到,E,的最短路线。,从引例的求解过程可以得到以下启示：,对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,E,2,4,3,7,4,6,3,2,4,2,6,5,3,4,6,3,3,3,3,4,3,4,6,7,6,9,9,11,12,所谓多阶段决策问题是：,把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：,在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。,各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。,决策过程是与阶段发展过程逆向而行。,2,、多阶段决策问题的典型例子：,企业在生产过程中，由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划。,某种机器，可以在高、低两种负荷下生产。高负荷下生产的产量多，但每生产一个阶段后机器的完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产，问应该如何决定各阶段中机器的使用，使整个计划期内的总产量最大。,某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。,动态规划的基本概念,(,一,),、动态规划的基本要素,1,、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常用自然数,k,表示。如引例可划分为,4,个阶段求解，,k=1,，,2,，,3,，,4,。,2,、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。,（,1,）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用,S,k,表示第,k,阶段的状态变量。通常一个阶段有若干个状态。第,k,阶段的状态就是该阶段所有始点的集合。如引例中,（,2,）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。,3,、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决策。描述的变量称为决策变量。常用,d,k,(S,k,),表示第,k,阶段处于状态,S,k,时的决策变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合，常用,D,k,(S,k,),表示。显然,d,k,（,S,k,）,D,k,(S,k,),。,如在引例的第二阶段中，若从,B,1,出发，,D,2,（,B,1,）,=B,1,C,1, B,1,C,2, B,1,C,3,如果决定选取,B,1,C,2,，则,d,2,（,B,1,）,= B,1,C,2,。,称可供选择策略的范围，为允许策略集，用,P,表示。,动态规划方法就是要从允许策略集,P,中找出最优策略,P,1n,*,。,4,、策略与子策略。策略是一个决策序列的集合。当,k=1,时，,P,1n,（,S,1,）,=d,1,(s,1,),d,2,(s,2,),d,n,(s,n,),就称为全过程的一个策略，简称策略，简记为,P,1n,(S,1,).,称,P,k,n,(S,k,)= d,k,(s,k,),d,k+1,(s,k+1,),d,n,(s,n,),为由第,k,阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为,P,k,n,(S,k,),5,、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用,S,k+1,=T,k,(S,k,d,k,),表示。该方程描述了由第,k,阶段到第,k+1,阶段的状态转移规律。因此又称其为状态转移函数。,6,、阶段指标、指标函数和最优指标函数,（,1,）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用,v,k,(S,k,d,k,),表示第,k,阶段的阶段指标。,在不同的问题中，其含义不同。它可以是距离、利润、成本等。,在引例中，用,d,k,=v,k,(S,k,d,k,),表示在第,k,阶段由点,S,k,到点,S,k+1,=d,k,(S,k,),距离。如,d,2,(B,3,C,1,)=6,。,（,2,）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在全过程和所有后部子过程上确定的数量函数。记为,V,k,n,(S,k,P,k,n,). V,k,n,(S,k,P,k,n,)=V,k,n,(S,k,d,k,S,k+1,S,n+1,) k=1,2,n,。,构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。,常见的指标函数的形式有：,（,3,）最优指标函数,f,k,(S,k,),表示从第,k,阶段的状态,S,k,开始采用最优子策略,P*,k,n,，到第,n,阶段终止时所得到的指标函数值。,即,f,k,(S,k,)=Opt V,k,n,(S,k,d,k,S,n+1,),其中,Opt,是最优化的缩写,可根据题意取,max,或,min,。,在引例中,指标函数,V,k,n,表示在第,k,阶段由点,S,k,至终点,E,的距离。,f,k,(s,k,),表示第,k,阶段点,S,k,到终点,E,的最短距离。,f,2,(B,1,)=11,表示从第,2,阶段中的点,B,1,到点,E,的最短距离。,7,、基本方程（递推关系式）,从引例求,A,到,E,的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了,k,阶段与,k+1,阶段之间的递推关系,一般地，若 则有,若,(,二,),、动态规划的基本思想与最优化原理,1,、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。,在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。,动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化性。,2,、最优化原理,动态规划方法基于,RBellman,等人提出的最优化原理：“,作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策略的子策略总是最优的,”。,但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性的充要条件。由此可见，基本方程是动态规划理论与方法的基础。,动态规划模型的建立与求解,(,一,),、构成动态规划模型的条件,建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此，必须满足以下条件：,1,、,将问题的过程划分成恰当的阶段；,2,、,正确选择状态变量,S,k,，使它既能描述过程的演变，又要满足无后效性；,3,、,确定决策变量,d,k,及每阶段的允许决策集合,D,k,(S,k,),；,4,、,正确写出状态转移方程；,5,、,正确写出指标函数,V,k,n,的关系式，它应具有以下三个性质；,（,1,）是定义全过程和所有后部子过程上的数量函数；,（,2,）具有可分离性，并满足递推关系，即,V,k,n,(S,k,d,k,S,n+1,)=,f,(S,k,d,k,V,k+1,n,),（,3,）函数,f,（,S,k,d,k,V,k+1,n,）对于,V,k+1,n,要求严格单调。,以上五点是正确写出动态规划基本方程的要素。,(,二,),、求解动态规划模型的方法,1,、在已知初始状态,S,1,下，采用逆序解法：（反向递归）,按上图示意的求解方法称为逆序法。例如引例的求解，就是把,A,看作始端，,E,为终端，规定从,A,到,E,为过程的行进方向，而寻优则是从,E,到,A,逆过程进行，所以是采用了逆序法。,阶段,1,s,1,d,1,(s,1,),v,1,(s,1,d,1,),阶段,2,s,2,d,2,(s,2,),v,2,(s,2,d,2,),阶段,k,s,k,d,k,(s,k,),v,k,(s,k,d,k,),阶段,k+1,s,k+1,d,k+1,(s,k+1,),v,k+1,(s,k+1,d,k+1,),阶段,n,s,n,d,n,(s,n,),v,n,(s,n,d,n,),v,k,n,f,k,(s,k,)=optV,k,n,寻优方向,2,、在已知终止状态,S,n,下，采用顺序解法（正向递归）,如果我们把引例中,E,看作始端，,A,为终端，规定从,E,到,A,过程为行进方向，而寻优则是从,A,到,E,过程进行求解的方法称为顺序法。其示意图如下：,逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。,阶段,1,s,0,d,1,(s,1,),v,1,(s,1,d,1,),阶段,2,s,1,d,2,(s,2,),v,2,(s,2,d,2,),阶段,k,d,k,(s,k,),v,k,(s,k,d,k,),阶段,k+1,s,k+1,d,k+1,(s,k+1,),v,k+1,(s,k+1,d,k+1,),阶段,n,d,n,(s,n,),v,n,(s,n,d,n,),v,k,n,f,k,(s,k,)=optV,1,k,寻优方向,s,k,s,n,3,、两种解法在建模时的区别如下表所示,应用动态规划解决问题时必须首先建立动态规划模型，再用逆序或顺序算法求解。写一个问题的动态规划模型一般包含以下,6,个步骤：,（,1,）阶段划分,k=1,2,n,（,2,）确定状态变量,s,k,（,3,）确定决策变量,d,k,（,4,）确定状态转移方程,s,k+1,=f(s,k,d,k,),或,s,k-1,=f(s,k,d,k,),（,5,）确定阶段指标,V(s,k,d,k,),（,6,）确定基本递推方程,或,案例,1,某商店在未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为,1000,件，每月中旬订购商品，并于下月初取到订货。据估计，今后四个月这种商品的购价和售价如下表所示。假定商店在,1,月初开始经销时仓库已存有该种商品,500,件，每月市场需求不限，问应如何计划每个月的订购与销售量，使这四个月的总利润最大（不考虑仓库的存储费用）？,月份,k,购价,p,k,售价,q,k,1,10,12,2,9,9,3,11,13,4,15,17,解：首先建立动态规划模型。,（,1,）问题划分为四个阶段,K=1,，,2,，,3,，,4,；,（,2,）状态变量,s,k,表示第,k,阶段初的库存量，且,s,1,=500,（,3,）决策变量,x,k,表示第,k,月的订货量，,y,k,表示第,k,月的销售量；,（,4,）状态转移方程,s,k+1,=s,k,+x,k,-y,k,（,5,）指标函数表示第,k,月的利润,V(s,k,x,k,y,k,)=q,k,y,k,-p,k,x,k,（,6,）基本方程为,案例,2,某工厂有,100,台机器，拟分四期使用，在每一期都有两种生产任务。据经验，若把,x,1,台机器投入第一种生产任务，则在本期结束时将有,1/3 x,1,台机器损坏报废，剩下的机器全部投入第二种生产任务，则有,1/10,的机器在期未损坏报废。如果干第一种生产任务时每台机器可获得利润,10,，干第二种生产任务时每台机器可获利润,7,，问应怎样分配使用机器以使四期的总利润最大（期未剩下的完好机器数量不限）？,解：,1,、首先建立动态规划模型。,（,1,）问题划分为四个阶段,K=1,，,2,，,3,，,4,；,（,2,）状态变量,s,k,表示第,k,阶段初可用于分配的机器数，且,s,1,=100,（,3,）决策变量,x,k,表示第,k,阶段分配于干第一种任务的机器数，则干第二种任务的机器数为,s,k,- x,k,（,4,）状态转移方程,s,k+1,= 2/3x,k,+9/10,（,s,k,-x,k,）,= 9/10s,k,-7/30x,k,（,5,）阶段指标表示第,k,期的利润,V(s,k,x,k,)=10x,k,+7,（,s,k,-x,k,）,= 3x,k,+7s,k,（,6,）基本方程为：,思考：某厂在未来,3,个月连续生产某种产品。每月初开始生产，月产量为,x,，生产成本为,x,2,，库存费为每月每单位,1,元。假如,3,个月的需求量预测为：,b,1,=100,b,2,=110,b,3,=120,，且初始存货,s,0,=0,，第三个月的期未存货,s,3,=0,，问应如何安排生产使总成本最小 ？,案例,3,（生产存贮问题）某工厂与购货单位签订的供货合同如下表。该厂每月最大产量为,4,百件，仓库的存货能力为,3,百件。已知每一百件货物的生产费为一万元。在生产的月份，每批产品的生产准备费为,4,千元，仓库保管费为每一百件货物每月一千元。假定,1,月初开始时及,6,月底交货后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？,月份,1,2,3,4,5,6,交货量（百件）,1,2,5,3,2,1,解：,1,、建立动态规划模型,（,1,）阶段划分：,k=1,，,2,，,3,，,4,，,5,，,6,（,2,）状态变量,s,k,表示第,k,月初的库存量，,s,1,=0,（,3,）决策变量,d,k,表示第,k,月的计划生产量,表示第月的合同交货量,（,4,）状态转移方程：,（,5,）第,k,月的总费用包括生产费和库存费,（,6,）基本递推方程,2,、用逆序算法求解,当,k=6,时，,s,6,+d,6,-1=s,7,=0,所以,s,6,+d,6,=1,f,6,(s,6,)=minv,6,(s,6,d,6,),当,s,6,=0,d,6,=1, f,6,(s,6,)=14,当,s,6,=1,d,6,=0, f,6,(s,6,)=1,当,k=5,时，,s,5,+d,5,-2=s,6,所以,当,k=4,时，,s,4,+d,4,-3=s,5,所以,所求最优决策结果如下表：,月初存货量,s,k,最优生产量,d,k,月底存货量,s,k+1,0,4,1,3,0,2,1,4,5,0,3,3,0,3,2,1,0,1,案例,4,（背包问题）某工厂生产三种产品，各种产品重量与利润的关系下表所示。现将此三种产品运往市场出售，运输能力总重量不超过,6,吨，问如何安排使运输总利润最大？,种类,重量（吨,/,件）,利润（元,/,件）,1,2,80,2,4,180,3,3,130,解：其实本例是一个整数规划问题，其整数规划模型如下,但是由于整数规划的求解需用分枝定界法求解，计算量非常大，因而在此我们选用动态规划方法来解。,1,、建立动态规划模型（在此用的是逆序算法求解，与课本不同）,（,1,）阶段划分：,k=1,2,3,，把装载一种产品看成一个阶段（,2,）状态变量,s,k,表示第,k,阶段初可用于装载产品的总容量量，,s,1,=6,（,3,）决策变量,d,k,表示第,k,阶段装载第,k,种货物的件数。,（,4,）状态转移方程： 其中,a,k,表示第,k,种货物的单件重量,（,6,）基本递推方程,（,5,）指标函数：,v,k,(s,k,d,k,),表示装载第,k,种货物,d,k,件所得的利润，即,v,1,(s,1,d,1,)=80d,1,v,2,(s,2,d,2,)=180d,2,v,3,(s,3,d,3,)=130d,3,2,、用逆序法求解。,其结果如下表,s,3,d,3,f,3,(s,3,),d,3,*,0,0,0*,0,1,0,0,0,2,0,0,0,3,0,1,0,130,1,4,0,1,0,130,1,5,0,1,0,130,1,6,0,1,2,0,130,260*,2,其计算结果如下表,s,2,d,2,s,3,f,3,(s,3,),f,2,(s,2,),d,2,*,0,0,0,0,0,0,1,0,1,0,0,0,2,0,2,0,0,0,3,0,3,130,130,1,4,0,1,4,0,130,0,0+130,180+0*,1,5,0,1,5,1,130,180,0+130,180+0,1,6,0,1,6,2,260,180,0+260*,180+0,0,其计算结果如下表,s,1,d,1,s,2,f,2,(s,2,),f,1,(s,1,),d,1,*,6,0,1,2,3,6,4,2,0,260,180,0,0,0+260*,80+180*,160+0,240+0,0,1,按计算次序反推，得到最优解有两个：,（,1,）,x,1,=0,x,2,=0,x,3,=2,；（,2,）,x,1,=1,x,2,=1,x,3,=0,；,案例,5,（一维资源分配问题）某公司拟将,3,千万元资金用于改造扩建所属的,3,个工厂，每个工厂的利润增长额与所分配到的投资额有关。各工厂在获得不同的投资额时所能增加的利润如下表。问应如何分配这些资金，使公司总的利润增长额最大？,投资,工厂,0,10,20,30,1,0,2.5,4,10,2,0,3,5,8.5,3,0,2,6,9,解：这是一个静态问题，通过将对三个工厂的投资看成三个阶段化为一个多阶段的动态问题。,1,、建立动态规划模型,（,1,）阶段划分：,k=1,2,3,，把对每个工厂的投资看成一个阶段,（,2,）状态变量,s,k,表示第,k,阶段初可用于投资的投资总额，,s,1,=3,（,3,）决策变量,d,k,表示第,k,阶段对第,k,个工厂的投资额。,（,4,）状态转移方程：,（,5,）阶段指标,v,k,(s,k,d,k,),表示对,k,第个工厂投资,d,k,后所增加的利润，其值为表中数据。,（,6,）基本递推方程,2,、用逆序算法求解。,其计算结果见下表：,s,3,0,1,2,3,f,3,(s,3,),0,2,6,9,d*,3,0,1,2,3,s,2,d,2,s,3,f,3,(s,3,),f,2,(s,2,),d,2,*,0,0,0,0,0+0,0,1,0,1,1,0,2,0,0+2=2,3+0=3,1,2,0,1,2,2,1,0,6,2,0,0+6=6,3+2=5,5+0=5,0,3,0,1,2,3,3,2,1,0,9,6,2,0,0+9=9,3+6=9,5+2=7,8.5+0=8.5,0,1,其计算结果见下表：,其计算结果见下表：,s,1,d,1,s,2,f,2,(s,2,),f,1,(s,1,),d,1,*,3,0,1,2,3,3,2,1,0,9,6,3,0,0+9=9,2.5+6=8.5,4+3=7,10+0=10,3,所求最优解为,d,1,=3,，,d,2,=0,，,d,3,=0,，,公司总的最大利润增长额为期,10,千万元。,案例,6,、设备更新问题,在已知一台设备的效益函数,r(i),，维修费用函数,u(i),及更新费用函数,C(i),条件下，在,n,年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使,n,年总效益最大的这类问题称为设备更新问题。,设,r,k,(i),表示在第,k,年设备已使用,i,年（或称役令为,i,年的设备），再使用,1,年产生的效益：,u,k,(i),表示在第,k,年设备役令为,i,年，再使用,1,年的维修费用；,C,k,(i),表示在第,k,年卖掉一台役令为,i,的设备，买进一台新设备的更新净费用,(,即新设备的购买费,-,旧设备折旧费）。,设某企业在今后,4,年内需用一辆卡车，现有一辆已使用了,2,年的旧车，根据统计资料分析，预计卡车的年收入、年维修费（包括油料费）、一次性更新重置费及,4,年后的残值如下表：,（,1,）阶段划分：卡车使用的每一年作为一个阶段，,k=1,2,3,4,（,2,）状态变量,s,k,：表示设备的役龄。即在第,k,年初，设备已使用的年限数。,s,1,=2, s,2,=1,3, s,3,=1,2,4, s,4,=1,2,3,5, s,5,=1,2,3,4,6,（,3,）决策变量,d,k,：表示在第,k,年初对役龄为,s,k,的设备的决策，是更新，还是继续使用，即,i,0,1,2,3,4,5,6,r,k,(i),16,14,11,8,5,2,-,v,k,(i),1,2,2,3,4,4,-,c,k,(i),-,18,21,25,29,34,-,t,5,(i),-,15,12,8,3,0,0,试确定,4,年中的最优更新计划，以使总利润最大？,1,、建立动态规划模型,(6),指标函数：指标函数,f,k,(s,k,),表示第,k,年初，使用一台役令为,s,k,年的卡车，到第,4,年末的最大收益。,(5),阶段指标：,(4),状态转移方程：,（,7,）基本方程为：,f,5,(s,5,)=t,5,(s,5,),2,、用逆序算法求解结果如下表：,s,4,1,2,3,5,f,4,(s,4,),14-2+12=24*,16-1-18+15=12,11-2+8=17*,16-1-21+15=9,8-3+3=8*,16-1-25+15=4,2-4+0=-2*,16-1-34+15=-5,d,4,*,k,k,k,k,s,3,1,2,4,f,3,(s,3,),14-2+17=29,16-1-18+24=21,11-2+8=17,16-1-21+24=18,5-4-2=-1,16-1-29+24=10,D,3,*,k,R,R,s,1,2,f,1,(s,1,),11-2+19=28*,16-1-21+30=24,d,1,*,k,s,2,1,3,f,2,(s,2,),14-2+18=30*,16-1-18+29=26,8-3+10=15,16-1-25+29=19*,d,2,*,k,R,由此可得最优更新方案为：,d,1,(2)=k,d,2,(3)=R,d,3,(1)=k,d,4,(2)=k,其含义是第一年役龄为,2,年的卡车不更新，第二年役龄为,3,年的卡车更新，第三年役龄为,1,年的卡车不更新，第四年役龄为,2,年的卡车不更新。,