数模公园内道路设计问题

1、B题 公园内道路设计问题目录1.问题重述-12.问题分析-33.模型假设-44.符号说明-45.模型建立与求解-5问题一 -5 问题二-9 问题三-156.模型分析-187.参考文献-188.附录-198.1 附录一 -198.2 附录二 -208.3 附录三 -21一.问题重述西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的

2、最短道路长不大于两点连线的1.4倍。主要设计对象可假设为如图所示的矩形公园，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25).示意图见图1，其中图2即是一种满足要求的设计，但不是最优的。现完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问

3、题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图 1 公园及入口示意图图 2 一种可能的道路设计图图3 有湖的示意图二.问题分析题目欲对公园内道路进行设计，通过预先设定公园四周的八个入口

4、，建立模型设计道路让任意两个路口相连，使总的道路总长最小，前提条件是任意两个路口之间道路最短长度不大于两点直线距离的1.4倍，同时道路总长中不包含公园四周的边。在第一问中，题目已经给出公园内部确定的四个道路交叉点，要求设计道路使道路总长最小。由于内部的交叉点已经给定，解决该问题的关键是：建立合理模型在两点最短路径小于两点直线距离的1.4倍的条件下，优先运用矩形周边的连线，使八个入口点能够两两连通，并且总长度最小。在第二问中，公园内部的道路岔口没有给出，这样需要建立合理模型确定内部点的数量以及坐标。确定内部点的数量和坐标后利用相同方法生成最短路径。在得出的最短路径中需要人为修改以满足路径距离小于

5、直线距离1.4倍的条件。而在局部修改过程中需要确定一点到局部三点最短的问题，因此可以通过寻找费马点进一步优化最终的最短路径。在第三问中，矩形内部存在一片区域，道路不能通过，但可以到区域的边缘。因此可在第二问结论的基础上合理简化模型，设计不同方案，通过比较验证，确立最终结论。三.模型假设1.不计道路宽度，将路径简化为直线处理。2.不直接相连的两点间距离为无穷大。3.相邻两点且满足限定条件的两点间距离设为零。4.假设矩形内三点均匀分布在整个区域，且不靠近边界。四.符号说明1.G: 表示连通图。2.P: 表示G的最小生成树中顶点的集合。3.Q：表示G的最小生成树中边的集合。4.X1，X2，X3：表示

6、大范围内搜索点的横坐标。5.Y1，Y2，Y3：表示大范围内搜索点的纵坐标。6.X1，X2，X3：表示小范围内搜索点的横坐标。7.Y1，Y2，Y3：表示小范围内搜索点的横坐标。8.L：任意两点最小直线距离的1.4倍矩阵。9.Z: 任意两点最小路线距离矩阵。10.Q：L与Z的差值矩阵。11.W: 任意两点间的路径距离矩阵。12.P：任意两点在周边上距离的矩阵。五模型建立与求解问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。此部分针

7、对公园内部有四个交叉口的情况进行模型建立，模型建立过程中有一定的约束条件。需要对已有的模型算法进行改进使之符合题目的要求，编写程序，读出结果，做出图形；1.建立模型:（1）.图论的最小生成树模型：最小生成树概念：在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个真子集。若(u，v）是G中一条“一个端点在U中（例如：uU），另一个端点不在U中的边（例如：vV-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包

8、括此边（u，v）。最小生成树算法prim算法的描述：设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。prim算法的思想是从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。prim算法如下：（i），；（ii）while end(2).模型的改进最小生成树模型与最短路模型的结合：由于本题对最小生成树模型加有一定的约束条件，就形成了带有约束条件的最小生成树问题。在最小生成树模型基础上结合最短路模型对两路口之

9、间最短路径小于两路口连线的1.4倍加以限制，即采用最短路模型中dijkstra算法相互结合求解。Dijkstra算法简介：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijksta算法步骤：1. 初使时令 S=V0,T=其余顶点，T中顶点对应的距离值 ，若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 ，若不存在<V0,Vi>，d(V0,Vi)为 。2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S 。3.对T中顶点的距

10、离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值，重复上述步骤2、3，直到S中包含所有顶点，即S=T为止2.求解模型:第一步：先采用最小生成树prim算法计算出在没有约束条件下的总路径最短的设计方法即没有两个路口之间最短路径小于两点之间直线距离的1.4倍及路径长度中不包含周边道路的条件。生成的最短路径图如图4：图4（程序见附录一）第二步：程序输出不满足限制条件的路径，进一步修改程序的输入邻接矩阵，即使不可能的路径权值为无穷大，这里权值设置成1000达到无穷大效果。得到路径解同时输出不满足约束条件的路径，合理局部修改得到最优解。最短路径图如图5：图5经计算

11、最短的总路径长度为：w(1,8)+w(2,10)+w(9,5)+w(9,10)+w(9,6)+w(12,5)+w(11,12)+w(11,3)+w(3,4)= 394.55973.方案验证：（1）任意两点间直线距离的1.4倍矩阵为L：（2）任意两点间的路径距离矩阵为W：（3）两矩阵的差值为Q： 经验证，差值矩阵Q中元素全部为正数，表示任意两点之间最短路径不超过两点直线距离的1.4倍，因此此方案合理。问题二 现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。此部分针对公园内可以任意修建道路，通过在公园内寻找合理数

12、目与位置的基点，在第一问的基础上建立模型，利用最小生成树的prim算法和每两点最短路径的Dijkstra算法求解模型，得出最短路径，在此基础上利用费马点结论进一步优化结果并验证得出最优路线。1.建立模型根据第一问得出的路线图四个交叉点存在冗余交点，因此假设矩形区域存在三个交叉点。假设三点均匀分布在矩形区域内且不靠近边界，合理计算三点坐标，以交叉点为中心确定适当大小的圆形区域。以此三点作为圆心，利用变化半径和变化角度，在各自区域内循环搜索最小生成树路线总长度最短的三个交叉点。在合理基点的基础上，缩小半径变化范围，减小步长，利用相同方法寻找更合理的交叉点以实现更短路径。得到基点以后建立同第一问中的

13、模型，利用最小生成树模型结合prim算法和Dijkstra算法求解模型，得出最短路径图。通过制定任意两点在周边上距离的表格，查找出距离大于两点直线距离1.4倍的所有点，在最短路径图的基础上合理优化，以满足所有1.4倍条件。利用费马点原理，由2,5,6三点和3,4,5三点分别构成三角形，通过几何方法找出其费马点，进一步优化最短路径图，并验证结果是否符合1.4倍条件。2.求解模型.大范围基点搜索将公园矩形区域划分成三等份，在每个区域中确定三个基点即A(50,30)，B(100,60)，C(150,30)，以此三点作为圆心，以R（0<=R<=25）为半径，在基点周围12个角度方向上取点即

14、：X1=50+R1*cos(a*/6) （R1=0,5,10,15,20,25） (a=0,1,2,3,4,5)Y1=30+R2*sin(a*/6) （R1=0,5,10,15,20,25） (a=0,1,2,3,4,5)X2=100+R1*cos(a*/6) （R2=0,5,10,15,20,25） (b=0,1,2,3,4,5)Y2=60+R2*sin(a*/6) （R2=0,5,10,15,20,25） (b=0,1,2,3,4,5)X3=150+R1*cos(a*/6) （R3=0,5,10,15,20,25） (c=0,1,2,3,4,5)Y3=30+R2*sin(a*/6) （R3

15、=0,5,10,15,20,25） (c=0,1,2,3,4,5)通过设计四重循环，以最短路径作为约束条件，逐点排查，寻找大体的合理基点，结果为：A（70,30），B（70,75），C（170,30）.小范围基点搜索一步基点确定为 ，以此四点为圆心，步长缩短为1m，以R（0<R<5）,在基点周围12个角度方向上即：X1=50+R1*cos(a*/6) （R1=0,1,2,3,4，5） (a=0,1,2,3,4,5)Y1=75+R2*sin(a*/6) （R1=0,1,2,3,4，5） (a=0,1,2,3,4,5)X2=40+R1*cos(a*/6) （R2=0,1,2,3,4，5

16、） (b=0,1,2,3,4,5)Y2=40+R2*sin(a*/6) （R2=0,1,2,3,4，5） (b=0,1,2,3,4,5)X3=120+R1*cos(a*/6) （R3=0,1,2,3,4，5） (c=0,1,2,3,4,5)Y3=40+R2*sin(a*/6) （R3=0,1,2,3,4，5） (c=0,1,2,3,4,5)利用相同方法可得出进一步细化的合理交叉点，结果为：A（70,30），B（74,75），C（174,30）.生成最短路径图以上一步所得的基点为基础，利用最小生成树的方法和Dijkstra算法求解模型，可得出最短路径图，算法及结果为：图5.合理优化最短路径图任意

17、两点在周边上距离的矩阵P为： 通过以上矩阵将最短路径图优化成为：图6(5).最终的最短路径图分析以上所得最短路径图，通过寻找某些三角形的费马点可以实现对最短路径图的进一步优化。费马点：定义：在一个三角形中，到3个顶点距离之和最小的点叫做这个三角形的费马点。 费马点作法： i.平面内一点P到ABC三顶点的之和为PA+PB+PC，当点P 为费马点时，距离之和最小。 ii.三内角皆小于120°的三角形，分别以 AB,BC,CA，为边，向三角形外侧做正三角形ABC1,ACB1,BCA1,然后连接AA1,BB1,CC1,则三线交于一点P,则点P就是所求的费马点. iii.若三角形有一内角大于或

18、等于120度,则此钝角的顶点就是所求的费马点. iv. 当ABC为等边三角形时,此时外心与费马点重合 通过分析上一步所得的最短路径图可得：分别以2,5,6和3,4,5为定点构成三角形，分别找出其费马点，费马点分别为（62.67,77.284）和（172.1,43.5），经演算发现1和6之间不满足条，因此以此费马点作为圆心，以1-5为步长寻找符合条件的交叉点，得出新的基地为（58.67,78.284），以此进一步优化最短路径图如图所示： 图73.方案验证：（1） 任意两点间直线距离的1.4倍矩阵L为：（2）任意两点间的路劲距离矩阵W为： （3）两矩阵的差值Q为： 经验证，差值矩阵中元素全部为正数

19、，表示任意两点之间最短路径不超过两点直线距离的1.4倍，因此此方案符合题目条件，依此所求的最短总路程的长度为:w(1,8)+w(2,9)+w(9,5)+w(9,6)+w(10,5)+w(10,3)+w(10,4)=358.6042m问题三若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图。重复完成问题二 的任务。图8此部分针对公园内存在一条矩形湖，可以利用第二问所得结论进行分析调整，制定不同的设计方案，通过分析对比选择最为合理的方案以实现满足条件的最短路径图。1.建立模型分析第二问所得结论，由于三角形两边之和大于第三边，显然绕湖边修路长度大于折线，排除所有绕

20、湖修建新路的方案。因此提出方案一为：以R2为交点，连接R2和3以及R2和5，并连接3和4，得出新的路径图，如图9。分析第二问所得结论，提出方案二为：以R4为交点，以R4，3和4构成三角形，通过寻找此三角形的费马点，并利用此费马点和R4作为交叉点，得出新的路径图，设为方案二，如图10。通过比较两种方案的路径长度和验证任意两点的距离是否小于直线距离1.4倍的条件，选择合理的方案。2.求解模型根据方案一，连接连接R2和3， R2和5， 3和4，得出新的路径图如图：图9其路径为: 5-R2-3-4 路径长度: 171.798m并且满足任意两点的最短路径距离小于直线距离的1.4倍。根据方案二，以R4为交

21、叉点，以R4，3和4构成三角形，通过寻找此三角形的费马点，并利用此费马点和R4作为新的交叉点，得出新的路径图如图10：图10其路径为：5-R4-10-(3、4) 路径长度为：152.7866 方案二中任意两点的最短路径距离小于直线距离的1.4倍。比较路径总长度，显然方案二更优，故选择方案二。3.方案验证：（1） 任意两点间直线距离的1.4倍矩阵L为：（2） 任意两点间的路劲距离矩阵W为：（3） 两矩阵的差值Q为：经验证，差值矩阵中元素全部为正数，表示任意两点之间最短路径不超过两点直线距离的1.4倍，因此此方案符合题目条件，依此所求得最短总路程的长度为:360.7485m六、模型的评价1. 本模

22、型第一问以最小生成树模型为基础，结合prim算法总路线和最短的特点和以最短路Dijkstra求每两点最短路径的优点。2. 结合人工解析法和计算机编程算法得出最优解。3. 巧妙应用费马点原理使路线得到很大的优化。4. 合理假设，对矩形内进行分区域逐层缩小范围，减小步长循环搜索，使结果趋近最优。5.模型求解采用人工与计算机结合方法，计算机编程较为复杂，并在人工分析中有一定的简化，数据计算精度有一定的误差，不一定能够达到最优解但也可趋近于最优解。 6.算法中加入了人为地优化及选择，不利于模型的推广应用。七、参考文献：1 梁国业，廖健平，数学建模，北京：冶金工业出版社，20042 朱道元，数学建模案例

23、，北京：科学出版社，20033 蒋珉，MATLAB程序设计及应用，北京：北京邮电大学出版社，20104 赵东方，数学模型与计算，北京：科学出版社，2007附录附录一clc;clear allM=1000;a=0 1 140 186.8154 141.4214 101.1187 100.4988 32.0156 58.3095 92.4175 156.89491 0 1 158.1139 122.0656 101.1187 107.7033 55.9017 36.0555 78.7464 127.5774140 1 0 64.0312 107.7033 160.0781 180.2776 161

24、.9413 94.8683 114.1096 33.1059186.8154 158.1139 64.0312 0 94.3398 172.4094 196.4688 201.5564 131.5295 128.4562 1000141.4214 122.0656 107.7033 94.3398 0 85 1000 141.5097 86.0233 52.3546 88.4081101.1187 101.1187 160.0781 172.4094 85 0 1 82.7647 78.2624 46.3249 155.631100.4988 107.7033 180.2776 196.468

25、8 1000 1 0 75.6637 92.1954 68.7095 178.314332.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0 70.1783 89.3085 174.071858.3095 36.0555 94.8683 131.5295 86.0233 78.2624 92.1954 70.1783 0 45.1774 10492.4175 78.7464 114.1096 128.4562 52.3546 46.3249 68.7095 89.3085 45.1774 0 109.6586156.8949 1

26、27.5774 33.1059 1000 88.4081 155.631 178.3143 174.0718 104 109.6586 0; result=;p=1;tb=2:length(a);s=0;while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=; b(j,k)=d; s=s+d;endresultsb=b+b'b(

27、find(b=0)=M;c=b;c(1,2)=30;c(2,1)=30;c(2,3)=110;c(3,2)=110;c(5,6)=85;c(6,5)=85;c(6,7)=25;c(7,6)=25;for i0=1:8 for j0=1:8 min,path=dijkstra(c,i0,j0); if (min >a(i0,j0)*1.4) path end endend 附录二三点搜索程序x3=150;y3=30;r3=0; for i3=1:5 for j3=1:12 x3=150+r3*cos(j3*pi/6);y3=30+r3*sin(j3*pi/6);x2=100;y2=60;r

28、2=0; for i2=1:5 for j2=1:12 x2=50+r2*cos(j2*pi/6);y2=75+r2*sin(j2*pi/6);x1=50;y1=30;r1=0; for i1=1:5 for j1=1:12 x1=r1*cos(j1*pi/6)+70;y1=r1*sin(j1*pi/6)+30; w=; for j=1:11 x=20,50,160,200,120,35, 10, 0, x1,x2,x3; y=0, 0, 0, 50, 100,100,100,25,y1,y2,y3; x0=x(j);y0=y(j); x=x-x0; y=y-y0; d0=sqrt(x.*x+

29、y.*y); w=w;d0; %w(1,2)=0;w(2,1)=0;w(5,6)=0;w(6,5)=0;w(6,7)=0;w(7,6)=0; end result=;p=1;tb=2:length(w);s=0; while ( length(result)=length(w)-1) temp=w(p,tb);temp=temp(:); d1=min(temp); jb,kb=find(w(p,tb)=d1); j0=p(jb(1);k=tb(kb(1); result=result,j0;k;d1;p=p,k;tb(find(tb=k)=; s=s+d1;s1=10000; end end

30、r1=r1+5; if (s<s1) s1=s; s1 x10=x1,y10=y1 x20=x2,y20=y2 x30=x3,y30=y3 end end endr2=r2+5; end end r3=r3+5; end 附录三验证程序z = 0 30 140 186.8154 141.4214 101.1187 100.4988 32.015630 0 110 158.1139 122.0656 101.1187 107.7033 55.9017140 110 0 64.0312 107.7033 160.0781 180.2776 161.9413186.8154 158.1139

31、64.0312 0 94.3398 172.4094 196.4688 201.5564141.4214 122.0656 107.7033 94.3398 0 85 110 141.5097101.1187 101.1187 160.0781 172.4094 85 0 25 82.7647100.4988 107.7033 180.2776 196.4688 110 25 0 75.663732.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0;%±ß×î¶Ìq =

32、 0 30 140 230 240 155 130 45 30 0 110 200 240 185 160 75 140 110 0 90 220 295 270 185 230 200 90 0 130 175 240 275 240 240 220 130 0 85 110 195 155 185 295 175 85 0 25 10 130 160 270 240 110 25 0 85 45 75 185 275 195 10 85 0 ;%1ͨ·¾ØÕót1=1000 30 1000 1000 100

33、0 1000 1000 32.016 1000 1000 1000 100030 1000 110 1000 1000 1000 1000 1000 1000 41.231 1000 10001000 110 1000 64.031 1000 1000 1000 1000 1000 1000 56.569 10001000 1000 64.031 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 1000 1000 1000 74.33 1000 1000 30.4141000 1000 1000 1000

34、 1000 1000 25 1000 29.155 1000 1000 10001000 1000 1000 1000 1000 25 1000 1000 1000 1000 1000 100032.016 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 74.33 29.155 1000 1000 1000 36.401 1000 10001000 41.231 1000 1000 1000 1000 1000 1000 36.401 1000 1000 10001000 1000 56.56

35、9 1000 1000 1000 1000 1000 1000 1000 1000 30.4141000 1000 1000 1000 30.414 1000 1000 1000 1000 1000 30.414 1000;%2ͨ·¾ØÕót2=1000 30 1000 1000 1000 1000 1000 32.0156 1000 100030 1000 110 1000 1000 1000 1000 1000 78.7626 10001000 110 1000 1000 1000 1000 1000 10

36、00 1000 45.30761000 1000 1000 1000 1000 1000 1000 1000 1000 28.09231000 1000 1000 1000 1000 1000 1000 1000 65.0612 77.24231000 1000 1000 1000 1000 1000 25 1000 32.1225 10001000 1000 1000 1000 1000 25 1000 1000 1000 100032.016 1000 1000 1000 1000 1000 1000 1000 1000 10001000 78.7626 1000 1000 65.0612 32.1225 1000 1000 1000 10001000 1000 45.3076 28.0923 77.2423 1000 1000 1000 1000 1000;%3ͨ·¾ØÕót3=1000 30 1000 1000 1000 1000 1000 32.0156 1000 1000 100030 1000 110 1000 1000 1000 1000 1000 1000 1000 78.76261