第14讲-确定型动态规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第八章 动态规划,*,运筹学,第八、九章 动态规划,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第14讲 确定型动态规划,第,14,讲 确定型性动态规划,(6.2),最短路问题,资源分配问题,生产与存储问题,动态规划和静态规划的关系,自学背包问题、排序问题、货郎担问题,资源分配问题：,把有限的资源,(,如资金、材料、设备、人力等,),分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。,资源可以有一种或若干种，,只有一种资源可供分配的问题称之为一维资源分配问题。,资源分配问题,(6.2.2),例,1,：,某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。,1,、一维资源分配问题,动态规划的数学模型,将三个分厂看作是三个阶段，即阶段变量,k=1,2,3,;,状态变量,s,k,表示第,k,阶段初可分配的设备台数,0s,k,5,;,决策变量,x,k,表示第,k,阶段分配给分厂,k,的设备台数，允许决策集合,X,k,(,s,k,)=,x,k,0,x,k,s,k,;,状态转移方程为,s,k+1,=,s,k,-,x,k,;,阶段指标,P,k,(,s,k,x,k,),表示第,k,阶段从,s,k,台设备中分配给,k,分厂,x,k,台设备的阶段效益,;,最优指数函数,f,k,(,s,k,),表示第,k,阶段从,s,k,开始到最后阶段采用最优分配策略取得的最大的效益值,;,递推方程函数式,第三阶段：,设将,S,3,台设备,（,S,3,0,1,2,3,4,5,）全部分配给丙厂时，最大盈利值为：,f,3,(S,3,),maxP,3,(X,3,),其中,X,3,S,3,0,1,2,3,4,5,X,3,*,表示使得,f,3,(S,3,),为最大值时的最优决策。,X,3,S,3,P,3,(X,3,),f,3,(S,3,),X,3,*,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,逆序求解,表,9,1,第二阶段：设将,S,2,台设备（,S,2,0,1,2,3,4,5,）分配给乙厂和丙厂时，对每一个,S,2,值，都有一种最优分配方案，使得最大盈利值为：,f,2,(S,2,),max P,2,(X,2,)+f,3,(S,2,X,2,),，,X,2,0,1,2,3,4,5,X,2,S,2,P,2,(X,2,),f,3,(S,2,X,2,),f,2,(S,2,),X,2,*,0,1,2,3,4,5,0,0,0,0,1,0,4,5,0,5,1,2,0,6,5,4,10,0,10,2,3,0,11,5,6,10,4,11,0,14,2,4,0,12,5,11,10,6,11,4,11,0,16,1,2,5,0,12,5,12,10,11,11,6,11,4,11,0,21,2,表,9,2,大家应该也有点累了，稍作休息,大家有疑问的，可以询问和交流,8,第一阶段：,设将,S,1,台设备（,S,1,5,）分配给甲厂、乙厂和丙厂时，则最大盈利值为：,f,1,(S,1,),max P,1,(X,1,)+f,2,(5,X,1,),其中，,X,1,0,1,2,3,4,5,X,1,S,1,P,1,(X,1,),f,2,(5,X,1,),f,1,(5),X,1,*,0,1,2,3,4,5,5,0,21,3,16,7,14,9,10,12,5,13,0,21,0,2,按计算表格的顺序反推，可知最优分配方案有两个：,1,）由,X,1,*,0,，,S,2,S,1,X,1,*,5,0,5,。再由,表,9,2,，可知,X,2,*,2,。,S,3,S,2,X,2,*,5,2,3,，故,X,3,*,S,3,3,。即得甲厂分得,0,台，乙厂分得,2,台，丙厂分得,3,台。,2,）由,X,1,*,2,，,S,2,S,1,X,1,*,5,2,3,。再由表,9,2,，可知,X,2,*,2,。,S,3,S,2,X,2,*,3,2,1,，故,X,3,*,S,3,1,。即得甲厂分得,2,台，乙厂分得,2,台，丙厂分得,1,台。,以上两种最优方案的总盈利均为,21,万元。,例,2,机器负荷问题,某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为,g=8u,1,，其中,u,1,为投入生产的机器数量，年完好率为,a,=0.7,；在低负荷下生产的产量函数为,h=5y,，其中,y,为投入生产的机器数量，年完好率为,b=0.9,。假定开始生产时完好的机器数量,S,1,1000,台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。,2,、资源连续分配问题,动态规划的数学模型,每年为一个阶段，即阶段变量,k=1,2,3,4,5;,状态变量,s,k,表示第,k,年初所拥有的完好机器台数，,s,1,=1000,;,决策变量,u,k,表示第,k,年投入高负荷生产的机器数，允许决策集合,U,k,(,s,k,)=,u,k,0,u,k,s,k,;,s,k,u,k,表示为第,k,年初分配在低负荷下生产的机器数量。,状态转移方程为,s,k+1,=,a,u,k,+,b,(,s,k,u,k,)=,0.7u,k,+,0.9,(,s,k,u,k,),=,0.9s,k,0.2,u,k,;,阶段指标,v,k,(,s,k,x,k,),表示第,k,年的产量：,v,k,(,s,k,u,k,)=,8u,k,+,5,(,s,k,u,k,)=,5s,k,+,3u,k,;,最优指数函数,f,k,(,s,k,),表示第,k,阶段从,s,k,开始到最后阶段采用最优分配策略实现的最大产量,;,解：,K=5,从第,5,阶段开始，向前逆推计算,f,5,(,s,5,),是关于,u,5,的单增函数，故,u,*,5,=,s,5,时，,f,5,(,s,5,),最大，,f,5,(,s,5,)=8,s,5,K=4,f,4,(,s,4,),是关于,u,4,的单增函数，故,u,*,4,=,s,4,时，,f,4,(,s,4,)=13.6,s,4,K=3,f,3,(,s,3,),是关于,u,3,的单增函数，故,u,*,3,=,s,3,时，,f,3,(,s,3,)=17.52,s,3,K=2,f,2,(,s,2,),是关于,u,2,的,单调减函数,，故,u,*,2,=,0,时，,f,2,(,s,2,)=20.8,s,2,依次类推，可求得：,u,1,*,0,，,f,1,(s,1,),23.7 s,1,最优生产策略,：,u,*,1,=,0,，,u,*,2,=,0,，,u,*,3,=,s,3,，,u,*,4,=,s,4,，,u,*,5,=,s,5,各阶段状态,：,s,1,=1000,，,u,*,1,=,0,，,s,2,=,0.9s,1,0.2,u,1,=,0.9s,1,=900,，,u,*,2,=,0,，,s,3,=,0.9s,2,0.2,u,2,=,0.9s,2,=810,，,u,*,3,=,s,3,，,s,4,=,0.9s,3,0.2,u,3,=,0.7s,3,=576,，,u,*,4,=,s,4,s,5,=,0.9s,4,0.2,u,4,=,0.7s,4,=397,，,u,*,5,=,s,5,s,6,=,0.9s,5,0.2,u,5,=,0.7s,5,=278,即前两年应把年初全部完好的机器投入低负荷下生产，后三年应把年初全部完好的机器投入高负荷下生产。这样最高产量为,23700,台。,企业一年中的产品生产往往是分期分批生产的。,组织每批产品的生产，都要花费一些生产准备费和存贮费用。,若某一时期增大生产批量则可减少生产批次，从而降低生产成本。,与此同时，批量大了，必然增加库存而使存贮费用增加。,在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。,生产存储问题,(6.2.3),1,、生产计划问题：,例,3,某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产品的固定成本为,3,千元，若不生产就为,0,，每单位产品成本为,1,千元，每个时期生产能力所允许的最大生产批量为不超过,6,个单位，每个时期末未售出的产品，每单位需付存货费,0.5,千元。还假定在第一个时期的初始库存量为,0,，第四个时期之末的库存量也为,0,。试问：该厂应如何安排各个时期的生产与库存，才能在满足市场需求的条件下，总成本最小。,动态规划的数学模型,该问题分成四个阶段，k表示年度，k1，2，3，4,;,状态变量,s,k-1,表示为第,k,年初的库存量，第,k,1,年末的库存量。,决策变量,u,k,表示,为第k年的生产量，d,k,表示为第k年的需求量。,允许决策集合,D,k,(,s,k,)=,u,k,0,u,k,6,状态转移方程为,s,k,=,s,k-1,+,u,k,d,k,;,s,0,0;,s,4,0,第k年的生产成本为：,解：,第,k,期末库存量为,s,k,的存贮费用为,:,h,k,(s,k,)=0.5 s,k,总成本为,:,c,k,(u,k,),h,k,(s,k,),f,k,(s,k,),表示由第,1,年的初始库存为,0,到第,k,年末的库存为,S,k,的最小总成本。,f,k,(s,k,),min c,k,(u,k,),h,k,(s,k,),f,k-1,(s,k-1,),min c,k,(u,k,),h,k,(s,k,),f,k-1,(s,k,d,k,u,k,),k=1,2,3,4,边界条件,f,0,(s,0,),0,写出顺序递推关系式：,由于库存量必须非负,s,k-1,s,k,d,k,u,k,u,k,s,k,d,k,u,k,6,所以,u,k,min s,k,d,k,，,6,s,k,即使以后各期不再生产，须满足最后的库存为,0,。在,0,和,min,，,6-d,k,之间取值,+,=,n,k,j,j,d,1,f,1,(s,1,),min c,1,(u,1,),h,1,(s,1,),f,0,(s,0,),s,1,s,0,+u,1,d,1,d,1,=2,s,1,0,，,u,1,2,，,f,1,(0),5,s,1,1,，,u,1,3,，,f,1,(1),6.5,s,1,2,，,u,1,4,，,f,1,(2),8,对,s,1,9,之间的值分别进行计算。,k,1,s,1,3,，,u,1,5,，,f,1,(3),9.5,s,1,4,，,u,1,6,，,f,1,(4),11,f,2,(s,2,),min c,2,(u,2,),h,2,(s,2,),f,1,(,s,2,d,2,u,2,),k,2,其中，,u,2,min s,2,3,，,6,s,2,1,，,f,2,(1),min c,2,(u,2,),h,2,(1),f,1,(4,u,2,),对,s,2,6,之间的值分别进行计算。,s,2,0,，,f,2,(0),min c,2,(u,2,),h,2,(0),f,1,(3,u,2,),u,2,=0,f,2,(0),9.5 u,2,=0,u,2,=0,f,2,(1),11.5,，,u,2,=0,s,2,2,，,f,2,(2),min c,2,(u,2,),h,2,(2),f,1,(5,u,2,),14,，,u,2,=5,s,2,3,，,f,2,(3),min c,2,(u,2,),h,2,(3),f,1,(6,u,2,),15.5,，,u,2,=6,s,2,4,，,f,2,(4),min c,2,(u,2,),h,2,(4),f,1,(7,u,2,),17.5,，,u,2,=6,s,2,5,，,f,2,(5),min c,2,(u,2,),h,2,(5),f,1,(8,u,2,),19.5,，,u,2,=6,s,2,6,，,f,2,(6),min c,2,(u,2,),h,2,(6),f,1,(9,u,2,),21.5,，,u,2,=6,f,3,(s,3,),min c,3,(u,3,),h,3,(s,3,),f,2,(s,3,d,3,u,3,),其中，,u,3,min s,3,2,，,6,s,3,在,0,至,d,4,4,之间,k,3,s,3,0,，,f,3,(0),minc,3,(u,3,),h,3,(0),f,2,(2,u,3,),u,3,=0,s,3,1,，,f,3,(1),min c,3,(u,3,),h,3,(1),f,2,(3,u,3,),16 u,3,=0,3,s,3,2,，,f,3,(2),min c,3,(u,3,),h,3,(2),f,2,(4,u,3,),17.5 u,3,=4,f,3,(0),14 u,3,=0,；,f,3,(1),16 u,3,=0,3,；,f,3,(2),17.5 u,3,=4,f,3,(3),19 u,3,=5,所以，,u,4,=0,，,u,3,=6,，,u,2,=0,，,u,1,=5,最小总成本为,20.5,千元,f,4,(s,4,),min c,4,(u,4,),h,4,(s,4,),f,3,(s,4,d,4,u,4,),其中，,u,4,min s,4,4,，,6 s,4,0,k,4,f,4,(0),min c,4,(u,4,),h,4,(0),f,3,(4,u,4,),u,4,=0,f,3,(4),20.5 u,3,=6,例,4,：某车间需要按月在月底供应一定数量的某种部件给总装车间，由于生产条件的变化，该车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时数如下表所示。,设仓库容量限制为,H=9,，开始库存量为,2,，期终库存量为,0,，要求制定一个半年的逐月生产计划，既使得满足需要和库容量的限制，又使得生产这种部件的总耗费工时数为最少。,动态规划的数学模型,该问题分成六个,阶段,，,k,表示月份，,k,1,2,3,4,5,6,设,s,k,表示为第,k,月初的库存量，第,k,1,月末的库存量。,u,k,表示为第,k,月的生产量，,d,k,表示为第,k,月的需求量。,状态转移方程：,s,k+1,s,k,u,k,d,k,;d,k,s,k,H,允许决策集合：,D,k,(s,k,),u,k,:u,k,0,d,k+1,s,k,u,k,d,k,H s,1,2 s,7,0,f,k,(S,k,),表示在第,k,月的库存为,s,k,时，从第,k,月到第,6,月所生产部件的最小累计工时数。,写出,递推关系式：,f,k,(S,k,),mina,k,(u,k,),f,k+1,(s,k,1,),min a,k,(u,k,),f,k+1,(s,k,u,k,d,k,)k=0,1,2,3,4,5,6,边界条件,:,f,7,(S,7,),0,解：,s,7,s,6,u,6,d,6,s,7,0,，,u,6,0 s,6,d,6,4 f,6,(s,6,),0,k,6,s,6,s,5,u,5,d,5,s,5,u,5,11,f,5,(s,5,),mina,5,(u,5,),f,6,(s,6,),10(11,s,5,),110,10s,5,u,5,*,11,s,5,k,5,f,4,(s,4,),mina,4,(u,4,),f,5,(s,5,),min20 u,4,+110,10(s,4,u,4,2)=min10 u,4,10 s,4,130,d,k+1,s,k,u,k,d,k,H,，,d,k+1,d,k,s,k,u,k,H,d,k,s,k,9,s,4,u,4,11,s,4,又,u,k,0 ;max0,9,S,4,u,4,11,s,4,f,4,(s,4,),10(9,s,4,),10 s,4,130,=220,20 s,4,;u,4,*,9,s,4,k,4,s,5,s,4,u,4,d,4,s,4,u,4,2,s,5,s,4,s,3,u,3,d,3,s,3,u,3,3,s,4,k,3,f,2,(s,2,),mina,2,(u,2,),f,3,(s,3,),min13 u,2,+244,17(s,2,u,2,5)=min,4u,2,17 s,2,329,8,s,2,u,2,14,s,2,又,u,k,0 max0,8,s,2,u,2,14,s,2,f,2,(s,2,),4(14,s,2,),17 s,2,329,=273,13 s,2,u,2,*,14,s,2,5,s,3,u,3,12,s3;,又,u,k,0 max0,5,s,3,u,3,12,s,3,f,3,(s,3,),3(12,s,3,),20 s,3,280=244,17 S,3,u,3,*,12,s,3,f,3,(s,3,),mina,3,(u,3,),f,4,(s,4,),min17 u,3,+220,20(s,3,u,3,3)=min,3u,3,20 s,3,280,k,2,s,3,s,2,u,2,d,2,s,2,u,2,5,s,3,f,1,(s,1,),mina,1,(u,1,),f,2,(s,2,),min18u,1,+273,13(s,1,u,1,8)=min5u,1,13 s,1,377,13,s,1,u,1,17,s,1,;,又,u,k,0 max0,13,s,1,u,1,17,s,1,f,1,(S,1,),5(13,s,1,),13s,1,377=442,18s,1,U,1,*,13,s,1,k,1,f,0,(s,0,),mina,0,(u,0,),f,1,(s,1,),min11u,0,+442,18u,0,18 s,0,=min,7u,0,18s,0,442,8,s,0,u,0,9,s,0,又,u,k,0 max0,8,s,0,u,0,9,S,0,f,0,(s,0,),7(9,s,0,),18s,0,442,s,0,=2,，,f,0,(s,0,),357 u,0,*,9,s,0,7,k,0,s,2,s,1,u,1,d,1,s,1,u,1,8,s,2,s,1,s,0,u,0,d,0,s,0,u,0,s,1,u,0,*,7,u,1,*,4,，,u,2,*,9,，,u,3,*,3,，,u,4,*,0,，,u,5,*,4,最小工时数为,357,。,3,动态规划和静态规划关系,对于某些静态规划问题,可以人为引入时间因素,适当引入阶段变量、状态、决策变量可把它看作是按阶段进行的动态规划问题。,线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划。,静态规划模型,其动态规划方程：,状态转移方程为,s,k,+1,=,s,k,x,k,s,1,=,a,（,1,）逆推解法：,设已知初始状态为,s,1,，并假定最优值函数,f,k,(s,k,),为表示第,k,阶段的初始状态为,s,k,，从,k,阶段到,n,阶段得到最大效益。,在第,n,阶段,在第,n-1,阶段,在第,1,阶段,在第,k,阶段,由于初始状态,s,1,已知，,按递推过程的相反顺序推算可得所要求结果,例,5,用动态规划逆推解法求解,按变量个数划分为,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,阶段所得的最大值。,解：,最优解为：,（,2,）顺推解法：,设已知终止状态为,s,n+1,，并假定最优值函数,f,k,(s),为表示第,k,阶段的结束状态为,s,，从,1,阶段到,k,阶段得到最大效益。,在第,1,阶段,在第,2,阶段,状态转移方程为：,1,2,k,s,1,u,1,s,2,u,2,s,3,s,k,u,k,s,k,+1,在第,k,阶段,由于终止状态,s,n+1,已知，,按计算过程的相反顺序推算可得所要求结果,例,6,按变量个数划分为,3,个阶段，设状态变量为,s,1,s,2,s,3,s,4,，,s,4,c,。取,x,1,x,2,x,3,为决策变量；指标函数按乘积方式结合。最优值函数,f,k,(s,k+1,),表示为第,k,阶段末的结束状态为,s,k+1,，从,1,阶段到,k,阶段所得的最大值。,用顺推解法求解,解：,最优解为：,例,7,用动态规划方法解下面问题,按变量个数划分为,3,个阶段，设状态变量为,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,阶段所得的最大值。,解：,该点不在允许决策集合内，因而最大值必在两端上选取,最优解为：,由于,s,3,未知，须对,s,3,求极值,当,s,3,9,时，,f,3,(s,3,),取最大。,f,3,(s,3,),2,9,2,+12,174,按计算过程的相反顺序推算可得所要求结果,判断题,1.,动态规划模型中,问题的阶段数目等于问题中子问题的数目,;,2.,动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性,;,3.,动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策,;,4.,对于一个动态规划问题,应用顺推或逆推解法可能会得到不同的结果；,5.,假如一个线性规划问题含有,5,个变量和,3,个约束条件，则用动态规划求解时将划分为,3,个阶段，每个阶段的状态将由一个五维的向量组成；,6.,动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。,作业：习题,6 1,，,2,，,4,有一个徒步旅行者，其可携带物品重量的限度为,a,公斤，设有,n,种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,物品,1 2,j,n,重量（公斤,/,件）,a,1,a,2,a,j,a,n,每件使用价值,c,1,c,2,c,j,c,n,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,背包问题,(,选学,),设,x,j,为第,j,种物品的装件数（非负整数）则问题的数学模型如下：,动态规划的数学模型,按照装入物品的种类划分阶段，k=1，2，,，n；,状态变量,s,k,表示装入第,k,种至第,n,种物品的总重量,决策变量,x,k,表示装入第,k,种物品的件数；。,状态转移方程为：,s,k+1,=s,k,a,k,x,k,允许决策集合为：,阶段指标函数,c,k,（,x,k,）,表示第,k,阶段装入第,k,种商品,x,k,件时的价值,f,k,(s,k,),表示第,k,阶段装入物品总重量为,s,k,时的最大价值,其中 表示不超过 的最大整数；,动态规划基本方程为：,当,k,=1,时，有：,例题：求下面背包问题的最优解,物品,1 2 3,重量（公斤）,3 2 5,使用价值,8 5 12,解：,a,5,，问题是求,f,3,(5),所以，最优解为,X,（,1.1.0,），最优值为,Z,=13,。,排序问题指,n,种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。,1,、,n,1,排序问题,即,n,种零件经过,1,种设备进行加工，如何安排？,14,6,8,20,23,交货日期（,d,）,4,5,1,7,3,加工时间（,t,）,零件代号,例、,排序问题,(,选学,),（,1,）平均通过设备的时间最小,按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,1,4,8,13,20,交货时间,8,23,14,6,20,平均通过时间,延迟时间,=13 6=7,（,2,）按时交货排列顺序,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,5,6,10,17,20,交货时间,8,23,14,6,20,平均通过时间,延迟时间,=0,（,3,）既满足交货时间，又使平均通过时间最小,零件加工顺序,工序时间,1,3,4,5,7,实际通过时间,1,6,9,13,20,交货时间,8,23,14,6,20,延迟时间,=0,平均通过时间,2,、,n,2,排序问题,即,n,种零件经过,2,种设备进行加工，如何安排？,例、,4,9,5,2,3,B,5,3,7,8,6,A,零件,设备,A,B,T,经变换为,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,3,、,n,3,排序问题,即,n,种零件经过,3,种设备进行加工，如何安排？,例、,3,4,6,8,5,6,4,6,8,3,5,7,9,3,10,C,B,A,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,排序,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,计算,T=6+10+8+7+6+4+3=44,计算依据：,一个著名的命题：一个串村走户的卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问：应如何选择行走路线，能使得总的行程最短。,设有,n,个城市，,1,2,n,。,D,ij,表示从,i,城到,j,城的距离。,规定推销员是从城市,1,开始的，设推销员走到,i,城，记,N,i,2,3,i-1,i+1,n,表示由,1,城到,i,城的中间城市集合。,S,表示到达,i,城中途所经过的城市的集合，则有,S N,i,1,）选取,（,i,S,）作为状态变量,，表示推销员从城市,1,开始走到,i,城，经过若干个城市，构成集合,S,。,2,）,最优值函数,f,k,(i,S),为从城市,1,开始经过,k,个中间城市的,S,集到达,i,城的最短路线的距离。,货郎担问题,(,选学,),（,TSP,问题,traveling salesperson problem,）,3,）,递推关系式：,f,k,(i,S)=min f,k-1,(j,Sj)+D,ji,(k=1,2,n-1.i=2,3,n.S N,i,),边界条件：,f,0,(i,)=D,1i,4,）,P,k,(i,S,),为最优决策函数,，表示从,1,城开始经,k,个中间城市到,i,城的最短路线上紧挨着,i,城前面的那个城市。,例：当推销员从,1,城出发，经过每个城市一次且仅一次，最后回到,1,城，问按怎样的路线走，使总的行程距离最短。（四个城市，其距离矩阵如下表）,5,）由边界条件可知：,f,0,(2,)=D,12,8,，,f,0,(3,)=D,13,5,，,f,0,(4,)=D,14,6,当,k=1,时,，即从,1,城开始，中间经过一个城市到达,i,城的最短距离是：,f,1,(2,3)=f,0,(3,)+D,32,5+9=14,f,1,(2,4)=f,0,(4,)+D,42,6+7=13,f,1,(3,2)=f,0,(2,)+D,23,8+8=16,f,1,(3,4)=f,0,(4,)+D,43,6+8=14,f,1,(4,2)=f,0,(2,)+D,24,8+5=13,f,1,(4,3)=f,0,(3,)+D,34,5+5=10,当,k=2,时，,即从,1,城开始，中间经过两个城市到达,i,城的最短距离是：,f,2,(2,3,4)=min f,1,(3,4)+D,32,f,1,(4,3)+D,42,=min14+9,10+7=17 P,2,(2,3,4)=4,1,i,1,i,1,i,