灾情巡视路线的最优解决方案.doc

44组 罗霄 伏龙 秦琪灾情巡视路线的最优解决方案摘要本文依据某县的公路网络图，求解不同条件下的灾情巡视路线：一为定组巡视，二为限时巡视，并总结出该问题属于分组旅行员推销(TSP)问题。文中首先将公路网络图转化为赋权连通图，经Kruskal算法画出最小生成树并将原权图分为若干子图，最后画出哈密尔顿圈，通过比较选出最优路径。对于问题一:首先利用Kruskal算法画出最小生成树，再以树干为基础分为三组，分组后依据分组情况画出哈密尔顿圈并在Lingo中编程求出每组最小权值，选出最优路径。最优路径见图6，均衡度a=12.3%，三组走的路程和为616.5km 对于问题二：经分析计算，巡视人员至少分为4组。然后按照分类准则把最小生成树分成4组，利用第一问的算法思想依次求出每组的最优哈密尔顿回路。根据均衡度的大小对所求得的结果进行调整，最后我们得到最优解为：时间均衡度a1=18.67%,路径均衡度a2=33.06%,最优巡视路线见表10。对于问题三:我们利用Dijkstra算法求出O点距离其它各点的距离，根据O点到最远点的距离确定时间上界，该点为H最短巡视时间为6.43。然后根据时间上界和到O点的距离由远及近确定最优巡视路线，见图14。 对于问题四：我们以第二问为基础分四组来考虑，运用控制变量法分三种情况进行讨论。讨论两个变量约束不变另外一个变量如何变化时，最佳巡视路线都不会改变。假定均衡度a10%,T,V和t变化不上上述范围时最佳巡视路线会发生改变,结果见图15 关键词：TSP问题 Kruskal算法 最小生成树 哈密尔顿圈291.问题重述1.1问题背景今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。图11.2本文需要解决的问题(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 (3)在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 (4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。2.问题假设与符号说明2.1问题的假设假设一：在巡视过程中不会出现汽车故障或道路堵塞等现象。假设二：各组路面状况一致，汽车行驶速度相等。假设三：村镇巡视一次后，再次经过不会停留。假设四：巡视过程中可以重复巡视某一条路。2.2符号说明符号符号说明w(Ck)分组后第k组的TSP回路路程a均衡度max(Ck)各组路径长度中最大值min(Ck)各组路径长度中最小值T巡视人员在各乡(镇)停留时间t巡视人员在各村停留时间V汽车行驶速度Gi第个加权网络图Vi第个顶点集cij城镇与城镇j之间的权值ai第组巡视人员巡视乡镇数目bi第组巡视人员巡视村数目Soi(n)从点到城镇的第n种路径的权值ki访问某镇或村一次所用的时间Ki从O点径直访问第点往返所用的时间Ki从O点径直访问第点附加访问其它城镇所用的时间maxKi从O点径直访问第点往返所用的最大时间3. 问题分析本文给出了某县的公路网络图，要求在不同条件下设计出最优的灾情巡视路线。将每个乡(镇)或村看作一个图的顶点，各乡镇、村之间的公路看作对应顶点的边，各条公路的长度(或行驶时间)看作对应边上的权，使得公路网络图转化为加权网络图，问题转化为图论中的分组旅行员推销问题(TSP)，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次后又回到点O，使得总权(路程或时间)最小。对于问题一：要求分三组巡视设计出总路程最短且尽可能均衡的巡视路线，我们首先利用Kruskal算法画出最小生成树。但因为图中节点数较多，有53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后,求出各部分类似最佳旅行员推销回路的权,再进一步调整，使得各部分满足给定的均衡性条件从O点出发到其它点并使得路程最短。故用Matlab求出O点到其它顶点的最短路程后再以树干为基础将图分为三组。由于分组有不同情况,我们先选择一种途径然后再优化处理从而确定分组情况,最后建立模型求得各组的最短路径。 对于问题二：从题中已知数据T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个，村镇有35个计算出在乡(镇)及村的总停留时间为172+35=69小时，要在24小时内完成巡回，若不考虑汽车行驶时间，由69/i24(i为分的组数)得到i最小为4，故至少要分4组。由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分4组时各组停停留时间大约为69/4=17.25小时，则每组分配在路途上的时间大约为24-17.25=6.75小时。而前面讨论过,分三组时有个总巡视路程602公里，分4组时的总路程不会比603公里大太多,不妨以603公里作为第二问的巡视总路程。路上约花603/35=17小时,若平均分配给4个组,每个组约需17/4=4.25小时2-5-6-L-19-J-13-J-18-I-16-17-K-21-20-25-M-O169.02O-2-5-6-7-E-9-F-10-F-12-H-14-13-G-11-E-8-4-D-3-C-B-1-O227.33 O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O206.7考虑到均衡性比较大,分析结果可知编号1较小，编号2偏大所以可以把编号2中的一些点划分到编号1中，则通过对最小生成树重新分三组后，得到以下最优路径：编号巡视路线长度1O-2-5-6-L-19-18J-13-14-15I-16-17-K-21-20-25-M-O191.62O-1-B-C-3-D-4-8-9-10-F-G-11-E-7-11-E-7O218.23 O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O206.7均衡度综合考虑以上两种情况我们发现这两种情况的总巡视路线长度比较接近但均衡度变化很大故我们选择第二种情况为最优巡视路线。巡视路线图如图6所示编号巡视路线长度1O-2-5-6-L-19-18J-13-14-15I-16-17-K-21-20-25-M-O191.62O-1-B-C-3-D-4-8-9-10-F-G-11-E-7-11-E-7O218.23 O-P-26-N-23-22-23-24-27-28-Q-29-Q-30-32-35-34-A-33-31-R-O206.7 图6图7 6.问题二的解答6.1模型的准备由第二问的分析得知，我们至少要分4组。现在对已经得到的最小生成树T进行分解，使4个子图Gi分解结果尽量均衡。由于最小生成树上，边权接近，可略认为均衡度即各子图包含的顶点数接近，各子图包含的顶点尽量接近(35+17)/4=13个。生成最小树划分为4组原则：1：使各图中点权和尽量接近13.2：分解后的各子图尽量为连通图。3：分解点为O或尽量接近O。4：生成的子图容易形成圈或接近圈。依据以上原则对最小生成树分解为4组如图8所示 图8组别顶点编号数量1A,B,C,R,Q,1,29,30,31,32,33,34,35132K,M,N,P,16,17,21,22,23,24,25,26,27,28143G,H,I,J,L,5,6,11,12,13,14,15,18,19,20154D,E,F,2,3,4,7,8,9,1010 图96.2模型建立6.2.1确定目标函数此文在第一问的基础上分成了4组，且多了访问时间的限制。为使总巡视路线尽可能短且每组巡视路线尽可能均匀且访问时间在24小时以内，我们确立了三个目标函数1:分成的四组回路中每组回路对应的权值w(Ck)最小令，则所以2：均衡度a最小:我们定义为该分组的实际均衡度，显然。越小说明分组的均匀性越好。因此所以我们建立了以下目标函数： 6.2.2确定约束条件在加权图G中，将顶点集V划分为V1 , V2, V3，V4,则G的三个子图为GV1, GV2, GV3, GV4需满足一下几个条件：1:顶点O包含在每个顶点集Vi 中，即O Vi，i=1,2,3,42：顶点集Vi为V（G）的子集，即3:在加权图G中，G的三个子图GV1, GV2, GV3 ,GV4,必须形成一条4:每个组在巡视的过程中，往返的时间不能超过24小时即： 6.2.3综上所述得到问题二的最优化模型为 6.3问题二的解答根据我们确定的分组原则把最小生成树大致分成四组，在Lingo中依次求出每组的最优哈密尔顿回路（详见附录2）。再依据均衡度的大小进行调整，最后得到的结果为近似最优解。 通过对最小生成树分三组后，得到以下最优路径如图10：编号巡视路线路程行走时间等待时间总时间1O-C-B-34-35-32-30-Q-29-R-31-33-A-1-O136.53.901821.902O-P-28-27-26-N-24-23-22-17-16-17-K-21-25-M-O154.34.411822.413O-M-25-21-K-18-I-15-14-H-12-G-11-G-13-J-19-L-20-25-M203.95.831823.834O-2-3-P-4-8-E-9-F-10-F-9-E-7-6-5-2-O153.44.381519.38 图10最佳巡视路线图为：图127.问题三的解答7.1模型的建立7.1.1确定目标函数在问题三中， T , t和V同二没有改变，在巡视人员足够多的情况下要求求出巡视的最短时间。分析的，在人员足够的情况下，我们给每个镇（乡）或村都分派一名巡视员 。每个巡视员所走的路线该点与O点之间的最短路径，巡视时间为往返时间加上访问点权时间。对他们巡视时间进行比较，当巡视时间最长的巡视员返回时，其他巡视员都已近返回。所以巡视时间最长的即为要求的最短时间，因此我们确定的目标函数为： 7.1.2确定约束条件巡视人员从O点出发径直走向i点，在这个过程中Soi为两点之间权值最小值： 若巡视员访问某点权的时间Ki与maxKi之差大于一小时，则可考虑访问一个村。若大于两小时以上则可考虑访问多个村或镇，但附加访问的村或镇所用的时间Ki仍小于maxKi则 综上所述得到问题三的最优化模型为 7.2模型的求解首先我们通过Dijkstra算法算出O点距离其它52各点的权值最小值，通过比较发现点H距离O点最小权值最大，H又恰好为一个镇，综上二者可知从O点径直访问H点所用的时间最长，最长时间为所以在人员足够多的情况下，完成巡视的最短时间为6.431234567891069.21434.917.527.234.549.749.565.91112131415161718192055.967.364.172.769.960.353.552.946.238.32122232425262728293039.6493944.331.820.628.422.220.835.7313233343536ABCD22.130.223.727.836016.311.911.522.2EFGHIJKLMN41.755.162.777.561.154.343.73919.831.1PQR10.12812.9图13：Dijkstra算法算出O点距离其它52各点的权值最小值通过Matlab编程求解（详见附录3,4 ）在上述条件下求得共需要29组巡视人员最优的巡视方案如下：编号巡视路径停留地点所需时间 1 O,2,5,6,7,E,9,F,10,F,9,E,7,6,5,2,O124.76571428620.2,5,6,L,19,J,13,14,13,J,19,L,6,5,2,O145c,0C2.6571428574O,2,5,6,7,E,9,F,9,E,7,6,5,2,OF5.1485714295O,2,5,6,7,E,11,G,11,E,7,6,5,2,OG5.5828571436O,2,5,6,7,E,9,F,12,H,12,F,9,E,7,6,5,2,OH6.4285714297O.M,25,21,K,18,I,18,K,21,25,M,OI5.4914285718O,2,5,6,L,19,J,19,L,6,5,2, OJ5.1028571439O,2,5,6,L,19,J,19,L,6,5,2,OK4.497142857100,2,3,2,02,32.811O,2,3,D,4,D,3,2,OD,44.99428571412O,2,5,6,5,2,O5,63.55428571413O,2,5,6,7,E,8,E,7,6,5,2,O7,84.8414O,2,5,6,7,E,9,E,7,6,5,2,OE,95.82857142915O,M,25,21,K,17,K,21,25,M,OM,176.05714285716O,M,25,21,K,18,K,21,25,M,O25,21,186.02285714317O,2,5,6,L,19,L,6,5,2, OL,195.6418O,P,26,N,23,22,23,N,26,P,OP,225.819O,P,26,N,23,N,26,P,O26,N,236.22857142920O,53,29,53, OR,294,53,29,Q,30,Q,29,53,OQ,305.0422O,53,31,32,31,53, O31,323.72571428623O,1,A,33,A,1,O1,A,335.35428571424O,1,A,34,35,34,A34,354.05714285725O,2,5,6,7,E,11J,19,20,25,M,O11,204.47142857126O,2,5,6,7,E,9,F,12,G,13,J,19L,6,5,2,O12,134.39142857127O,M,25,21,K,18,I,15,I,16,17,K,21,25,M O15,164.58571428628O,P,26,N,24,27,26,P,O24,273.80285714329O,1,B,1,O,P,28,P,OB.284.314285714图148.问题四的解答8.1模型的建立在第二问的基础上，我们讨论四个组的情况，运用控制变量法对所要讨论的变量进行讨论。并令时间复杂度为a=10%，若变量变化时而时间复杂度小于等于10%，则认为对巡视路线没有影响，以此来确定变量的变化范围。所以建立的目标函数为：令，所以假设时间均衡度a10%时，最佳巡视路线不会改变，假设第i组巡视时间最长，第j组巡视时间最短，分三种情况进行讨论：1：T，t不变，由a10%,可以得出2：T,V不变，由a10%,可以得出3：V,t不变，由a10%,可以得出8.1.1综上所述得到问题三的最优化模型为8.2模型的求解在问题四中分四组情况时求得时间均衡度为，我们假定时间10%，运用控制变量法，分三组进行讨论，每次控制两个变量不变，一个变量变动，最后求得求得结果如图15T和t不变时T和V不变时t和V不变时0.69t12T2.67图15由上表可知：当T和t不变时，V只能变小，可以减小到8.82公里/小时，此时的最佳巡视路径不变。 当T和V不变时，t只能减小，可以减小到0.69小时，此时的最佳巡视路线不变。 当t和V不变时,T只能增大，可以增大到2.67小时，此时的最佳巡视路线不变。9.模型的评价、改进及推广9.1模型的评价9.1.1模型的优点：(1) 把灾情巡视问题看作旅行员推销问题，便于快速解决问题。(2) 运用Kruskal算法画出最小生成树，再根据近似算法使得问题简化。9.1.2模型的缺点：(1)模型中的计算都只是近似计算，不能够保证所求的解为最优解。(2)缺乏严格的理论基础。(3)模型求解过程中存在经过一个点多次的情况。(4)在分组时凭借经验划分可能存在不合理现象。9.2模型的改进(1)先利用计算机仿真巡视过程后再进行求解可使结果更准确。(2)所建立的模型没有考虑到意外情况，我们可以先调查统计对意外情况发生的概率及所产生的影响进行综合考虑后再优化模型。9.3模型的推广 该图论模型可以广泛应用于物理学控制论、信息论、工程技术。交通运输、经济管理、电子计算机等各领域。对于科学研究、市场和社会中的许多问题，可以用该模型来解决。例如各种通信线路的架设、输油管道的铺设、铁路或者公路交通图的合理布局等问题都可应用该图论模型的方法，简便，快速地加以解决。10.参考文献1王朝瑞.图论M，北京：北京工业学院出版社.1987年。2李当志.数学建模竞赛教程M.南京：江苏教育出版社.1996年。3姜启源.数学模型M.北京：高等教育出版社.1987年。4卢开澄.图论及其应用.北京：清华大学出版社.1981年。11. 附录附录1：最小生成树源程序：b=1,1,1,1,2,2,2,3,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,9,9,10,11,11,11,12,12,12,13,13,13,13,14,14,14,15,15,16,16,17,17,17,18,18,18,19,19,19,20,20,20,20,21,21,21,21,22,22,22,23,23,23,23,24,24,24,25,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29,30,30,31,31,31,32,32,32,32,33,33,33,33,34,34,34,35,35,35,36,36,36,36,36,36,37,37,37,37,37,38,38,38,38,39,39,39,39,40,40,40,40,41,41,41,41,42,42,42,43,43,43,44,44,45,45,45,45,45,46,46,46,46,46,47,47,47,47,48,48,48,48,49,49,49,49,49,50,50,50,50,50,51,51,51,51,52,52,52,53,53,53,53;36,37,38,39,3,5,36,2,39,40,8,40,2,6,40,49,5,7,48,49,6,40,41,48,4,41,41,42,42,41,43,46,42,43,44,14,43,45,46,13,15,44,14,45,17,45,16,22,47,45,46,47,20,46,48,19,21,25,48,20,23,25,47,17,23,47,21,22,24,50,23,27,50,20,21,49,50,27,50,51,24,26,28,27,51,52,51,52,53,32,52,32,33,53,30,31,33,35,31,32,35,37,35,37,38,32,33,34,1,2,39,49,51,53,1,33,34,38,53,1,34,37,39,1,3,36,38,3,4,5,7,7,8,9,11,9,10,12,11,12,13,12,14,13,15,16,18,46,11,13,18,19,45,17,18,21,22,6,7,19,20,5,6,25,36,50,23,24,25,26,49,26,28,29,36,28,29,30,29,31,36,37;6,10.3,5.9,11.2,4.8,8.3,9.2,4.8,7.9,8.2,20.4,12.7,8.3,9.7,11.3,11.4,9.7,7.3,11.8,9.5,7.3,15.1,7.2,14.5,20.4,8,7.8,5.6,10.8,14.2,6.8,13.2,12.2,7.8,10.2,8.6,8.6,16.4,9.8,8.6,15,9.9,15,8.8,6.8,11.8,6.8,6.7,9.8,8.2,8.2,9.2,9.3,8.1,7.2,9.3,7.9,6.5,5.5,7.9,9.1,7.8,4.1,6.7,10,10.1,9.1,10,8.9,7.9,8.9,18.8,13.2,6.5,7.8,12,8.8,7.8,10.5,10.5,18.8,7.8,7.9,7.9,12.1,8.3,15.2,7.2,7.9,10.3,7.7,8.1,7.3,9.2,10.3,8.1,19,14.9,7.3,19,20.3,7.4,8.2,11.5,17.6,14.9,20.3,8.2,6,9.2,11.5,19.8,10.1,12.9,10.3,7.4,11.5,12.2,8.8,5.9,17.6,12.2,11,11.2,7.9,11.5,11,8.2,12.7,11.3,15.1,7.2,8,7.8,14.2,5.6,10.8,12.2,6.8,7.8,8.6,10.2,9.9,16.4,8.8,11.8,8.2,15.8,13.2,9.8,8.2,8.1,15.8,9.8,9.2,4.1,10.1,11.8,14.5,7.2,5.5,11.4,9.5,12,19.8,14.2,7.9,13.2,8.8,10.5,14.2,10.5,12.1,15.2,10.1,8.3,7.2,7.7,7.9,9.2,12.9,8.8;B,i=sortrows(b,3);B=B; m=size(b,2);n=53;t=1:n; k=0; T= ; c=0;for i=1:m if t(B(1,i)=t(B(2,i) k=k+1; T(k,1:2)=B(1:2,i), c=c+B(3,i) tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end endif k=n-1 break ; endendT,c 附录2：问题一及问题二的Lingo程序model: sets: city / 1. 19/: u; link( city, city): dist, ! 距离矩阵; x; endsets n = size( city); data: !距离矩阵，它并不需要是对称的; dist = 061434.934.549.749.565.955.967.364.172.711.911.522.241.755.162.777.56019.14040.555.755.571.961.973.370.178.75.911.227.347.761.168.783.51419.1020.923.338.538.354.744.756.159.768.318.97.98.230.543.951.566.334.94020.9027.820.436.252.642.6545866.639.828.812.728.441.849.464.234.540.523.327.8015.21531.421.432.836.845.442.231.215.17.220.628.24349.755.738.520.415.2015.832.222.233.637.646.257.446.430.3821.42943.849.555.538.336.21515.8016.42217.834.237.957.246.230.17.85.625.62865.971.954.752.631.432.216.4037.62339.443.173.662.646.524.210.830.833.255.961.944.742.621.422.22237.6014.615.42463.652.636.514.226.86.824.867.373.356.15432.833.617.82314.6016.420.1756447.925.612.27.810.264.170.159.75836.837.634.239.415.416.408.67667.651.929.628.68.618.572.778.768.366.645.446.237.943.12420.18.6084.676.260.538.232.317.29.911.95.918.939.842.257.457.273.663.6757684.601127.149.462.870.485.211.511.27.928.831.246.446.262.652.66467.676.211016.138.451.859.474.222.227.38.212.715.130.330.146.536.547.951.960.527.116.1022.335.743.358.141.747.730.528.47.287.824.214.225.629.638.249.438.422.3013.42135.855.161.143.941.820.621.45.610.826.812.228.632.362.851.835.713.402022.462.768.751.549.428.22925.630.86.87.88.617.270.459.443.3212001877.583.566.364.24343.82833.224.810.218.59.985.274.258.135.822.4180; !随机产生，这里可改为你要解决的问题的数据; enddata !目标函数; min = sum( link: dist * x); FOR( city( K): !进入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保证不出现子圈; for(city(I)|I #gt# 1: for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1); ); !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解; for(city(I) | I #gt# 1: u(I)36 t1=2; else t1=1; end% d,p=lujinf(36,i); tc=d*2/35+t1;c=1; for j=p(2:end-1) if j=p(1) continue; end if sum(re=j,2)=0 continue; end if j36 t2=2; else t2=1; end% tc=tc+t2; if tc36 t1=2; else t1=1; end if j36 t2=2;else t2=1;end d(j)=(df1+df2+df3)/35+t1+t2; end mi,c=min(d); if re(c)=0 o=1;continue; end if mimaxt zh(m,1:2)=re(i),re(c); re(i)=0;re(re=re(c)=0; tf(m)=mi; m=m+1; endendre(re=0)=;c=1;zj=re;zj(end+1:end+size(zd,2)=zd;for i=zj; d1,p1=lujinf(36,i); d2,p2=lujinf(i,36); p(c,1:size(p1,2)=p1; p(c,size(p1,2):size(p1,2)+size(p2,2)-1)=p2; dd(c,1)=d1+d2; c=c+1;endfor i=1:size(zh,1) d1,p1=lujinf(36,zh(i,1); d2,p2=lujinf(zh(i,1),zh(i,2); d3,p3=lujinf(zh(i,2),36); p(c,1:size(p1,2)=p1; p(c,size(p1,2):size(p1,2)+size(p2,2)-1)=p2; p(c,size(p1,2)+size(p2,2)-1:size(p1,2)+size(p2,2)+size(p3,2)-2)=p3; dd(c,1)=d1+d2; c=c+1;end附录四：问题三的fun函数a=0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 6 10.3 5.9 11.2 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf InfInf 0 4.8 Inf 8.3 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 9.2 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf InfInf 4.8 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 7.9 8.2 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf InfInf Inf Inf 0 Inf Inf Inf 20.4 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 12.7 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf InfInf 8.3 Inf Inf 0 9.7 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 11.3 Inf Inf Inf Inf Inf Inf Inf Inf 11.4 Inf