最佳灾情巡视路线的数学模型 375 表中符号说明:黑体表示前面经过并停留过,此次只经过不需停留;上加横线的表示此 点只经过不停留该分组实际均衡度 22.7-21.69 =4.62% 可以看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求 问题三在T,t,V的假定下,巡视人员足够多,完成巡视的最短时间为多少,并给出 此条件下的最佳路线 我们发现从O点巡视H点的最短时间是所有最短时间中最长的,其距离为77.5公里 算出时间为 77.5 35 ×2+2=6.43小时 因此,T=2小时,t=1小时,V=35公里/小时时,若巡视人员足够多,完成巡视的 最短时间为6.43小时 在最短时间的限定下,完成巡视的最优路线应满足如下条件: (1)每个组巡视的总时间不能超过最短时间t=6,43小时; (2)所有的点都必须访问到,不能漏点 (3)所需巡视组数要尽量少 在寻求最优路线时,从距离O点较远的一些点(如12,10,15,22等点)开始搜索比较容 易,因为到这些点的路线比较少 具体方法如下: 第一步依据图1算出从O点到每一个点的最短距离; 第二步找出其中最大的一个,算出从O点沿最短路巡视所需的时间t,并求△t=tH 第三步若△1<1,则这一组只能访问这一点 若△t<1,则在余下的点中找到距离O点最远的点,根据条件看这一组能否巡视这一 点 第四步若能巡视则算出△t,转到第三步; 第五步若不能,则依次判断次远点第三远点…,满足总巡视时间不超过tH,就让这 组巡视这一点,直到Mt<1,然后再从第二步开始 通过以上的方法,最后我们找到的最优解是22个组,如表4 问题四巡视组数已定,要求尽快完成巡视讨论T,t和V的改变对最佳巡视路线的 要尽快完成巡视,就得要求每组完成巡视时间尽量均衡,因为总的完成巡视时间按最长 的完成巡视时间计算现在讨论在在均衡允许的范围内已分成n组后,改变T,,V对最佳 巡视路线的影响,显然在分组不变的情况下,无论T,t,V如何改变,对每组内的最佳巡视 路线是没有影响的,但可能会影响各组间的均衡性因此该问题实际上是讨论T,t,V对分 组的影响,即在不破坏原来分组均衡的条件下,T,t,V允许的最大变化范围 在分n组的情况下,设 S;:表示第i组的最佳推销员回路路线总长度;
376 全国大学生数学建模竞赛优秀论文汇编 表4(时间单位:小时 编号 巡视路径 停留地点所需时间时间差 3,14 6.1 I-15-|-16-17 15,16 0.12 0-2-5-6-7-E-9-F-12-G-1 5 5-6-7-E-8-E-9-F-10-F-9 220.21 60 5.58 o-2-5-6-7-E-9-F-9=E-7-6=5-20|9,F 14 0-2-5-6-1-19-J-18-K-21-25M-oJ,18 0·9 90=M-=25-21-K18-1-18-K-21-25+M=O1 100-M-25-21-K-17-22-23N-26-P-O17,2,236.120.31 110=2-5-6-1-19 L,19 12o-M-25-20-21-23-24-N-26-P=O 130=M-25=21-K-21-25=M=0 20.2246.100.33 14o-2-5-6-7-E-7-6-5-2-0 . K 67,E 0.05 150-R=31-32=35-34-A-1-0 31,32.35346.320 160-R-29-Q-30=0-28=P-O Q.30,286.10.32 P-26-27-26-N-26-P-O 27N 20 1so-=2=32D.4,D下2=R= 3,D,45.990.44 200-2-5-MO A,3295.970.46 210-1-B-C-O 1,B,C 220-P-O-R=O P.r 1.1 X:表示第i组所要停留的乡镇的数目;,出 Y:表示第i组所要停留的村的数目; i=1,2,3,……,n 显然,当x=x,Y1=y,S1=S;i,j=1,2,3,…,n时,即每组的乡(镇)数、村数 最佳巡回的长度均相等,因而分组绝对均衡时,即a0=0,无论T,t,V如何改变都不会改变 原来分组的均衡 (一)不影响分组的均衡时,T,t,V的最大允许变化范围的讨论: 年对任意一个组,其完成巡视的时间 S Ti=XT+ Yt V·=1, 设均衡分组的最大允许时间均衡度为a,即 每中, Dax
最佳灾情巡视路线的数学模型 377 则有 1T-T≤a·maxT 记E=a·maxT,则c表示均衡分组所允许的最大时间误差,称为最大允许时间误 差.则 (X-X)·T+(Y-1)·t+S-S≤c的 同≤(X1-x)·7+(y,-y),+5少组 由式(1)我们得到 E 代(2) 式(2)可推出以下结果 1.当X-X>0时,要保持原均衡分组不变,T必须满足的条件为 S-S ≤T≤ (3) X-X 2.当Y=Y>0时,要保持原均衡分组不变,t必须满足的条件为 (X-X)·T 学x∈-(X;x)·T-5S (4) 3.当S1-S>0时,由(2)式得 (X-X)·T+(Y1):≤y系E(Xx)T-(Y1=Y) ①当0≤(X-X)·T+(Y1-Y)·t≤c时,有 (x-x5=5(x.-Y),; ②当(X-X)·T+(Y1-￥)·t>c时,有 ne(XX)·T(Ya-Y) ≤V(x,-x),+( (6) 由(3)-(6)式,当T,t,V三个变量中任意两个变量无论如何变化,都可计算出为保持均衡 分组不变,三个变量所允许的最大变化范围.的助,国彩 (二)分三组的实例讨论 现对分三组的情况进行讨论对问题一中所得的三个分组,若考虑停留时间和行驶 间,且取T=T0=2小时,=t0=1小时,V=V=35公里/小时时,结果如表5
378 全国大学生数学建模竞赛优秀论文汇编 表5(路程单位:公里;时间单位:小时) 编号 X S行驶时间总时间 13 546 92.3 549 28.49 4 216 实际均衡度为a0= 29,18-28.46 9.18 =2.5% 实际时间误差为0=2.5%×29.18=0.72小时 现分别规定均衡分组的最大允许均衡度a=2.5%和a=5%,即最大容许的时间误差 分别为E=0.72小时和E=1.44小时,计算出T,t,V三个参量中固定任意两个时,要不破 坏原均衡分组,另一个参量所容许的变化范围结果如下表: 表6 t,V不变 T,t不变 a=2.5%,=0.72小时1.25≤T≤2 1≤t≤1.38 V≥35 a=5%,=14小时051≤T≤2740.63≤t≤1:75 V≥17.3 表上表可以看出: (1)当实际均衡度-2.5%刚好等于最大容许均衡度a=2.5%时,要保持原均衡分 组,当 1,V不变时,T只能减小且下界为1,25小时;T的上界为T0=2小时; T,V不变时,只能增大,且上界为1.38小时;t的下界为to=1 T,t不变时,V只能增大,且无上界V的下界为Vo=35 (2)当实际均衡度a=2.5%小于最大容许均衡度a=2.5时,即e0<c时要保持原 均衡分组,当 t,V不变时,T变化的下界为0.51小时,上界为2.74小时; T,V不变时,变化的下界为0.63小时,上界为1.75小时; T,t不变时,V可以增大但无上界,也可减小,且下界为173公里/小时,0 (三)对实例结果的分析 上述实例的均衡分组有一个特点:各组的停留时间相等,即取T=Tn=2小时,=o 1小时,V=V0=35公里/小时时,在表5的分组中 (X2-X)·T+(Y-Y)·t0=0,i,j=1,2,3 (7) 定义4各组的停留时间相等的均衡分组称为停留时间相等的均衡分组,由(7)式得 T 考’,X-X≠0,i,=1,2,3 (8) 现讨论对停留时间相等的均衡分组,T,t,V的变化规律,岂 对停留时间相等的均衡分组,分组的实际时间误差:量量 =max(x-X,). To+(Y-Y)to+ S-S
最佳灾情巡视路线的数学模型 其中,为使S最大的组的标号;j为使S最小的组的标号 当T,不变时,即T=T,54时因(X=X),To+(Y1-Y1)·t0=0<c,由 式(6)知,要保持平衡分组,V的下界应为 m5-(X=X):70-(Xy1) ax S5,产的含义同(*)了出文 ①取∈=c0时,由(9)式得 肌 ②e>eo时,由(9)式得 年弘,直深 根景文本、厘0,B,算总 V0一下 故有以下定理 定理当取V=V,TT,t10时,对图进行停留时间相等的均衡分组后,设该 分组的实际时间误差为e0 (1)若取最大允许时间误差e=co,当T,t不变时,要使该均衡分组保持不变,V的下 界为V0,即V只能增加不能减少 (2)若取最大允许时间误差e>e0,当T,t不变时,要使该均衡分组保持不变,V的变 化范围的下界小于Va 四、模型的推广(略) 五、优缺点分析 原簧为一宗世量很脚 优点 :一厘人好,关的理点平 1.本文提出的分组准则简便易行,可操作性强,且可逐步调整使分组达到均衡 2.用均衡度的概念定量的刻画了分组的均衡性 3.在用近似算法求近似最佳推销员回路时,采取了三种不同的方法产生初始圈,使得 算法比较完善,得到了误差很小的近似最优解 4.从理论上定量地讨论了V,T,t的变化对均衡分组灵敏度的影响得到了得好的结果 缺点(略) 由,别 只5阶,量界总来是,BH m考立人只,海回到线国 持,量 舒贤林,余志才编著,图论基础及应用 5的量另回的, [2]龚劬编,图论与网络最优算法 3)费培之编著,图和网络及其应用.时同 小一,其神一出口 一的 语的一一厘进,去