数学建模 公园内道路设计问题模型.docx

数学建模 公园内道路设计问题模型公园内道路设计问题模型 摘要 随着社会前进步伐的逐渐加快，人们的生活节奏也被无形的越拉越紧。获得更多收益的同时，我们的身体也严重透支。这就使人们越来越开始关注自身的锻炼问题。毫无疑问，人们在城市、学校里选择放松、锻炼的最佳去处就是公园了。 本文主要讨论公园内的道路修建问题。在数据的处理方面，我们较多的使用了matlab软件，因为他在数值计算和调用函数方面有着强大的功能，尤其在编程解决具体问题时它操作简便，效率高，能节省大量时间。 给出的三个问题都是优化问题，要求修的路程尽量短。因此我们有两个基本思路：一是充分利用边界上的道路，能通过边界解决的问题尽量不再去另外修路。二是充分利用已经修过的道路，通过“少修多连”的方法尽量减少路程，我们也称其为“借路原理”。在问题的解决过程中，我们主要是计算出数据，然后考虑是否满足思路一，紧接着通过思路二来进一步优化、减少路程。我们不是直接求出最优路径，而是利用排除法思维，先找到一条优化道路，但紧跟其后又找到了更优化的路径，通过层层对比，最终确定出最优路线。 关键字：matlab软件 基本思路一 基本思路二 排除法 1 / 27 一问题的重述 广州某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更好的生活环境。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连，使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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。重复完成问题二 的任务。其中矩形湖的四个顶点坐标为R1(140,70),R2(140,45),R3(165,45),R4(165,70)。 注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。 2 / 27 图 1 公园及入口示意图 图 2 一种可能的道路设计图 二问题的分析和符号说明 题目中对道路的修建有一个“硬性要求”，也是大前提，即“前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍”，下面我们来考 3 / 27 虑P1和P7，P1与P7间的直线距离乘以1.4等于141.0，而P1和P7仅通过边界路线相连接的最短距离为130,由于130<141.0，满足题目所给的大前提，所以无需再专门修路连接P1和P7。同理，对于其他任意两点也可尝试上述计算方法，尽量排除无关紧要的点，从而可大大简化问题，减少了计算量。 下面我们需要对一些常用变量进行命名： 1,2,3,4,5,6,7,8.P1,P2,P3,P4,P5,P6,P7,P8 Smn.m,n仅通过边界线路相连的最短距离 m-n.m,n间的直线距离 mn(q)m,n间通过方法q相连的距离 然后，我们可以运用matlab来计算上面提出的问题，只需用一个循环结构，便可以省去很多繁琐的运算。然后我们可以得到下面一个概览表： 解题用图- 1 概览表 4 / 27 通过观察易知，仅15, 16, 18, 34, 35, 36, 37, 25, 26, 27之间不符合Smn>=1.4*(m-n)的条件，需要重新规划路线。从而问题变得很简明。 三模型假设 1.近似认为每个入口都是一个质点，不占用空间位置，从而m，n之间修的直线路线的长度即为|mn|。 2.认为道路的宽度为0，即所修的路都是线段，长分别是a和b的两条路线相交，则两条路的总长度是a+b。 3.认为公园的地面是完全平整无凹陷和突起的。 四模型建立 根据上面的陈述，我们大致可总结出修路要遵循的两个原理： A1：满足mn<=1.4*的两点m，n间不需再专门修路。 A2：应充分利用已经修过的路来完成需修而未修的两点间的路，简称为“借路”原理。 下面我们将尝试在这两个原理的基础上，根据三个问题的不同要求，运用排除比较的方法来尽量确定最优道路。 五模型求解 问题一： 1.求解前提条件 该问题有一个基本要求就是“确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）” 。首先要明白什么是道路交叉点。我们取任一个交叉点Q，则至少有两条不同的道路通过Q，下面列出的三种情况都是符合题意的： Q Q 解题用图- 2 解题用图- 3 情况一：一点通过三条不同道路 情况二：一点通过多条不同道路 5 / 27 Q 解题用图- 4 情况三：一点通过两条不同道路 这里需要特别注意解题用图-4中所给的情况，只有两条道路以折线方式相交仍视点Q为道路交叉点。 前面所提到的“至少有两条不同的道路通过Q”中的 “不同道路”具体指两条不能连成线段的道路，如图， 解题用图- 5 Q 此时认为只有一条路通过Q，即Q不是道路交叉点 这是一种不符合Q为交叉点的情况。 另一种不符合Q为交叉点的情况是没有任何道路通过Q。 2.开始求解 观察需要重新修建道路的各点组合，即15, 16, 18, 34, 35, 36, 37, 25, 26, 27，发现1,2,3均需要连到5,6，所以选择从5,6点开始着手。 先考虑6点。 一1,6之间需要满足原理A1，最简单的办法就是1- -6，连接后，若不再修建其他道路，26=131.1<1.4*S=141.6，满足原理A1=a<b,A1.所需数据可在解题用图-1中找到）， 27(2- -1- -6- -7)=156.1>150.8，不符A1。 专门再为27修路代价太大，因此改变16之间的连接方法。 6 / 27 解题用图- 6 二考虑16通过1- -B- -6的方法，并且连接2- -B，则 16=104.9<141.6，A1。 26=141.4<141.6，A1。 27=126.4<150.8，A1. 7 / 27 解题用图- 7 有人会提出疑问，当连接16(1- -6)但27不符A1时，为何不像连接2- -B一样，从2或7到直线上修一条路？其实这是为了能使1,2能与5相连。 8 / 27 解题用图- 8 继续我们二中的方法。检验可得36=211.4<224.1，A1。37=236.4<252.4，A1。 下面着重考虑1,2,3和5的连接。 35. 35较简单，为使路程尽量短且通过C，D点，35取3- -C- -D- -5，又 35=117.4<150.8，A1。 15 由于A点还没有通过任何道路，所以考虑15, 此时15=155.4<198，A1。 25取25，此时25=151.9<170，A1。 9 / 27 解题用图- 9 存在以下疑问： *为什么不取15，25，这样通过“借路”，使总路程减少了-=9.1？ 解*：如果这样，那么25=173.1>170.9，不符A1。 10 / 27 解题用图- 10 现在看15, 16, 35, 36, 37, 25, 26, 27，之间的路程修建似乎可以结束了，但通过观察现有图形，考虑将A- -6代替B- -6，因为前者明显比后者短些。下面我们进行一些替换后的检验： 16=110.2<140，A1。 26=106.7<140.7，A1。 27=131.7<151.8，A1。 36=216.7<224.1，A1。 37=241.7<252，A1。 1,2,3到5的路线和原来完全一样，不用再赘述。 所以数据完全符合要求，即可以用A- -6代替B- -6。 11 / 27 解题用图- 11 *又有以下问题：用A- -6代替B- -6后，A点成了交叉点，那么若取15，25，路程会不会更短？ 解*：即便换线路后新数据完全符合A1，但>，路程反而增加，舍弃不用。 12 / 27 解题用图- 12 *为什么不25。15？ 解*：同上个问题，即便换线路后新数据完全符合A1，但>，路程反而增加，舍弃不用。 13 / 27 解题用图- 13 接下来考虑18和34. 18： 最直接最简便的方法当然是直接连接1,8两点，但考虑，我们可以过8做1- -B的垂线，设垂足为P显然比直接连接减少了路长，下面检验， 18=42.9<44.8，A1。 34： 和18思路完全相同，过4做3C的垂线，垂足设为O，检验。 34(3- -O-4)=70.6<89.6，A1。 我们再对18和34的求解过程做些补充。因为上述方法可用有一个大前提，就是和都是锐角，我们将证明列在下面： 角43C： a=arctan=45度 b=arctan>45度 所以=180-a-b<90，是锐角。 的证明方法和上面基本相同，不再赘述。 14 / 27 解题用图- 14 综上所述，我们已经解决了问题一，这里附上最后决定的连接图 ， 解题用图- 15 并计算得到优化后的总路程s=436.1米。 15 / 27 问题二： 1. 求解前提条件： “现在公园内可以任意修建道路“就是问题二的条件，在求解过程中，仍需用到原理A1,A2。不像问题一，问题二没有了交叉点的牵绊，但连线的灵活度也更大了。 2.开始求解 我们仍需从15, 16, 18, 34, 35, 36, 37, 25, 26, 27找下手点。相似地，1,2,3均需要连到5,6，所以选择从5,6点开始着手。 由于“以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点”,我们有一下两种方案. FIRST: 连接1- -6,3- -5, 显然16符合A1. 15(1- -3-5)=247.1>198.0,不符A1。 26=131.1<141，A1. 27=156.1>150.8，不符A1。 25=217.1>170.9,不符A1。 3- -5，则35符合A1。 36=192.1<224.1，A1。 37=217.1<252.4,A1. 16 / 27 解题用图- 16 所以，这种方案目前不符合要求的点对是15,25,27. 先讨论27， 一方案，过7做1- -6垂线，垂足为M， 则27=151.9>150.8,不符A1。 二方案，过2做1- -6垂线，垂足为N， 则27=150.9>150.8,不符A1。 17 / 27 解题用图- 17 三方案，综合一二方案， 但是考虑到做了两条垂线，路程过长，应该寻求更节省路长的画法画法。因则27=146.6<150.8,A1。 为原来什么都没做时27超出规定的长度是156.1-150.8<6，所以考虑A2，从2向1- -6做线段，与1- -6交点去N1，并设1- -N1=x，2- -N1=a，通过matlab，运用余弦定理，即2+x2-2*x*(1- -2)=a2,联立+x-a=6，即可算出比方案三更优化的方案四： 此时x=5.7，a=29.7,27=149.9<150.8，A1。 对应地，过7做垂线垂足设为M1，同样可得方案五： 此时x=5.8，a=24.8,27=150.1<150.8; 比较方案三四五所修路程长度，即可得最佳方案为方案五，所修长度L=24.7. 18 / 27 解题用图- 18 解题用图- 19 19 / 27 再讨论15,25 若连接2- -5， 则25显然符合A1。 15=152.1<198.0,A1. 解题用图- 20 考虑到A2，我们可以过2做3- -5垂线垂足为C， 则25=159.2<170.9,A1. 15(1- -2- -C- -5)=189.2<198.0,A1. 所以此方案才是最佳方案 20 / 27 解题用图- 21 考虑18,34 同问题1，我们过8做1- -6垂线垂足为O，过4做3- -5垂线，垂足为P和是否为锐角的问题，方法和问题一相同，不再重复，经判断两角都是锐角）， 18=43.4<44.8,A1 43(4- -P- -3)=87.2<89.6,A1 21 / 27 解题用图- 22 方案FIRST已经将问题二解决，最后的路线图如下： 22 / 27 解题用图- 23 且总路程S=413.7。 SECOND：连接2- -6，3- -5, 16=131.1<141.0，A1 26显然符合 27=126.1<150.8,A1 36(3- -2- -6)=211.1<224.1,A1 37(3- -2- -6- -7)=236.1<252.4,A1 35(3- -5)显然符合 15(1- -3-5)=247.1>198.0,不符A1。 25=217.1>170.9,不符A1。 到此，再往下的问题和FIRST里的重复，不再赘述。 考虑18,34 3,4和FIRST完全一样 23 / 27 解题用图- 24 但1,8和上FIRST有差别， 如果做了垂线，则8- -O=45.7>45,那么81更大于45，不符A1，舍去。 所以1,8间的路线选择直接连接。 24 / 27 解题用图- 25 方案SECOND已经将问题二解决，最后的路程图如下图： 25 / 27 解题用图- 26 且总路程S=397.9 综合FIRST和SECOND,我们最终确定选SECOND方案。 并给出该方案路线交叉点坐标：P，C 总路程S=397.9 问题三： 1. 求解前提条件： “公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边“，即我们所修路线不能穿过湖。 2. 开始求解： 其实求解方法和问题二完全一样，只需要把穿过湖的部分重新处理一下，因此我们把问题二最终确定的结果图和湖的位置图画到一个坐标系内: 解题用图- 27 观察计算得，仅3- -5与湖有两个交点M，N，如图所示，只需把湖内部分换为湖的边界, 又35(3- -N- -M- -5)=109.4<150.8,A1. 即可得问题三的最优方案 26 / 27 总路程S=400.3 道路的交叉点比问题二多了三个，即M，N，R2，P，C五点： M，N，R2，P，C 六模型评价： 该模型优点：运用排除法，减少了要考虑的点对的数量。大大简化了计算，能够效率很高的得出比较优化的方案。 该模型缺点：比较适合解决具体问题，例如像问题1,2,3中给出具体要求的问题，不太适合解决那种一般化的问题，例如任给出四点，求要修的最优化路程。 27 / 27