武汉理工大学第十二届数学建模校内热身邀请赛武汉某动物园路线规划

1、武汉理工大学第十二届数学建模校内热身邀请赛 承  诺  书 我们仔细阅读了武汉理工大学第十二届数学建模校内热身邀请赛的竞赛细则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们的参赛报名号为：

2、A42        参赛队员  (签名) ： 队员1：         队员2：         队员3：         武汉理工大学第十二届数学建模校内热身邀请赛 编 号 专 用页   选择的题

3、号：    A       参赛的编号：   A42                                    

4、60;                                （以下内容参赛队伍不需要填写）              竞赛评阅编号：

5、0;        武汉某动物园路线规划摘要本文研究的是最短路线设计问题，通过道路程设计来探求如何使得新修路总路程最小，在数学归类上属于规划类问题。本题是一个道路设计的最优化的问题，即是如何设计路径使动物园内部新修路总长最小，但要满足以下两个控制条件：1.两个入口相连最短道路长不超过两点连线1.5倍；2.要求动物园内新修的道路与四周的连接只能与8个路口相通而不能连到四周的其他地方。在该问题中，因为题目中所言动物园边界路长度不计，所以我们的基本思路是多利用动物园边界路。由此，我们利用勾股定理，证明出了两邻边入口的边界

6、距离一定小于其直线距离的1.5倍，由此简化成为两对边入口连接问题。我们对题目所给条件进行分析，认为可以分为两种情况，一种为交叉点不全用的情况，这种情况下，问题一的最短路程为1230.80米；另一种为交叉点全用，这种情况下，问题一的最短路程为1446.87米。对于问题二，我们分析发现，海洋馆对于规划无影响，问题一的解答完全适用于问题二，所以问题二的解同问题一。关键字：路线规划 问题简化 模型优化 01. 问题的重述与分析1.1问题的重述 改革开放以来，作为中部最大城市的武汉，在经济发展上取得巨大成果。为了响应国家中部崛起战略，营造美好家园，武汉市政府近期决定建造一个矩形动物园。为方便游客游玩，动

7、物园设计规划决策者想在已经建好道路的矩形动物园的四边上设置8个入口；内部有四个交叉点，分别是：。现在请你建立一个模型，在两个入口最短道路长不超过两点连线1.5倍的情况下，如何使道路总长最短？（总长中不计入矩形四边的长度，新修的路与矩形四边的连接只能在入口处，不能在矩形的其他位置） 矩形动物园的基本参数及各个路口坐标为：长：1000米 ，宽：500米图1是动物园入口图，图2是一种可能的规划，但不是最优化的问题一：根据以上信息给出你的计算方法并算出最短总长问题二：如果在中间设一个矩形海洋馆，如图3，海洋馆的四个点坐标为：，要求道路不能穿过海洋馆，但可以到达四边，以此绕过海洋馆，那最短长度又是多少呢

8、？ 图1矩形动物园及其入口图 图2可能的一种情况（但不是最优）图3 有海洋馆的示意图1.2问题的分析总的来说，该动物园的路线规划主要是须服从“任意两个入口最短道路长不超过两点连线1.5倍”这个条件。我们首先要简化该问题。因为动物园边界路的长度不计入所修路程的总长度，所以我们优先考虑动物园边界路。因为题目中动物园的门较多，所以我们首先考虑了哪些门是在不修任何路的情况下，可以互相由动物园边界路到达。经过计算，得出以下几个是不满足从边界到达的：M1M5，M2M5，M2M6，M3M5，M3M6，M3M7。因题目中未提及交叉点是否必须使用，于是我们分两种大类情况进行建模。第一种为四个交叉点不都用，第二种

9、为四个交叉点必须全用。2. 假设与符号说明2.1模型假设1.假设所修道路沿线风景美丽程度相同，不影响游客的游览心情。2.假设动物园中除题二中所指部分区域内不能修路外，其他处均满足修路的客观条件。3.假设动物园里所修路宽度一致，且均可看做是直线。4.假设动物园四周的门均不占空间，视为一个点。5.假设道路交点处的道路径不会因交叉等因素而变长。2.2符号说明：C1:记动物园边界路最小距离不大于连线距离1.5倍的无序点对为C1类无序点对 ；C2: M1，M2M8构成的所有无序点对中除C1类之外的无序点对记为C2类无序点；B1:以动物园入口M1，M2，M3，M5，M6，M7为顶点的连通图的邻接矩阵；B2

10、:以动物园入口M4，M8为顶点的连通图的邻接矩阵；D1: 以M1，M2，M3，M5，M6，M7个点中任意两点沿矩形边框的最短距离构成的矩阵；D2: 以M4，M8两点沿矩形边框的最短距离构成的矩阵；3.模型的建立因为动物园四周边上已经建好的道路不计入道路总长，要想园内道路总路程最短，应尽可能利用动物园边界路。由于c1类无序点对满足边框最短距离不大于1.5倍连线距离，所以c1无序点对对应的入口可以通过动物园边上道路连通，在进行道路设计时不予考虑，对c2类无序点对，可以将相关点连成连通图，通过平面几何知识“三角形的两边之和大于第三边以及两点之间线段最短”得到这些无序点对的最短路径，最后检验验证方案设

11、计是否符合要求，若方案不合理，则需修改改优化模型，直到得到符合条件的最佳道路设计方案为止。（I）确定c1,c2类无序点对1.根据直角三角形的勾股定理知：a2+b2=c2， 又当a0，b0时有：a2+b22ab，所以 2abc21.25c2 2ab+a2+b21.25c2 + a2+b2=2.25 c2 （a+b）2（1.5c）2 所以a+b1.5c所以，矩形动物园的两临边上的入口都满足边界路最短距离不大于1.5倍连线距离，临边上的无序点对都属于c1类。2.由于临边上的入口都属于c1类无序点对，所以接下来只需考虑对边上的入口问题。根据图一坐标以动物园长边上的6入口M1，M2，M3，M5，M6，M

12、7为顶点的连通图的邻接矩阵B1以及这6点中任意两点沿动物园边界路的最短距离构成的矩阵D1，以动物园短边上的2入口M4，M8为顶点的连通图的邻接矩阵B2以及这2点沿动物园边界路的最短距离构成的矩阵D2，进行矩阵运算 Ni=1.5Di-Bi（i=1,2）对矩阵元素进行分析，当nij0时，1.5DijBij，即Mi，Mj两点的动物园边界路距离不大于两点连线的距离的1.5倍,构成的无序点对属于c1类无序点对在设计道路时不需考虑这两点对应入口的道路连接问题；当nij0时,即 Mi，Mj构成的无序点对属于c2类无序点对，需要设计合理的道路进行连接。（II）用平面几何知识对c2类无序点对进行处理一般情况下，

13、在一个平面上，有限个点中任意两点间线段最短，若中间要经过别的有限个点，线段数越少，总长度越短，根据这个对问题不断进行优化。综合考虑所有无序点对间的最短道路长和道路总长，在已经连接好的路线不做太大改变的前提下，将不合理的路线进行适当的修改优化，直到所有路线都满足要求且道路总长最小为止。4.模型的求解与优化问题一的解答4.1模型的简化根据图一得到动物园长边上的6个入口M1，M2，M3，M5，M6，M7为顶点的连通图的邻接矩阵B1和以动物园短边上的2入口M4，M8为顶点的连通图的邻接矩阵B2B1= B2 = M1，M2，M3，M5，M6，M7这6个点中任意两点沿动物园边界路的最短距离构成的矩阵D1和

14、M4，M8沿动物园边界路的最短距离构成的矩阵D2D1= D2 = 进行矩阵运算Ni=1.5Di-Bi（i=1,2）后，得到的矩阵N1= N2= 在N1和N2两个矩阵中，当nij0时，点（i，j）属于c1类无序点对；当nij0时，点（i，j）属于c2类无序点对。有矩阵N1和N果知，c22输出的结累类无序点有（3,7），（3,6），（3,5），（2,5），（2,6），（1,5）。其余均为c1类无序点。4.2模型求解用平面几何知识对c2类无序点对进行处理1. 若四个交叉点不都用用0个交叉点我们先考虑只修一条路的情况。可以轻易得出，没有可以满足条件的方案。然后我们考虑只修两条路的情况，发现也没有满足条

15、件的方案。于是我们考虑修三条道路，就有以下两种方案： 方案一 方案二经过计算，方案一修路总长为1687.35米，方案二的修路总长为1654.44米。我们发现方案二比方案一要好。用1个交叉点。从可知，所需修建道路至少为三条。而在此情形下，我们发现只铺三条路，则交叉点毫无作用，且无可以满足条件的方案。用大于1个交叉点因为一个交叉点会有至少两条线段相交，所以当交叉点个数大于1个时，线段条数也会至少是3条。我们容易发现，只有当两个交叉点相连时，才会有最少线段数，而此种情况显然不是最短修路长度。所以当交叉点大于1时，可以不予考虑。因此这种方法下最优解为方案二。总长为1654.44米。方法的优化：先不考虑

16、交叉点位置，利用线段的条数越少，总修路长度越小。我们把模型进行优化。首先考虑只修两条交叉道路连接四个门。只有如下三种情形满足条件 情形1 情形2 情形3再把它们的交叉点移动到离A，B，C，D四点中最近的一点上去，得出以下方案： 方案三 方案四 方案五经过计算，方案三修路长度为1230.80米，方案四修路长度为1506.17米，方案五的修路长度为1612.45米。因为此方案已经能满足题目条件。故无需再讨论三条交叉道路连接多个门情形。比较五个方案可知，方案三为最优方案，所修路程长度为1230.80米。2. 若四个交叉点都用根据一般情况下，在一个平面上，有限个点中任意两点间距离，线段最短，若中间要经

17、过别的有限个点，线段数越少，总长度越短。因为一定得用四个交叉点，为了使路程最短，必须有四条线段分别把交叉点与最近的入口相接。因为动物园长边上的入口相互通达，所以还需至少两条线段来连接。因此，我们从六条线段开始讨论，且只需讨论A，B，C，D四点的连接情况。当有六条线段时，四个交叉点必须有两对交叉点要相互通达。因此交叉点一共有3种连接方案，即AD,BC;AB,CD;AC,BD(此时AC，BD会相交，不予考虑)。因为我们考虑的是对边入口通达情况，发现AD，BC相连后，完全没有解决长边入口的通达问题，因此也不再考虑这种情况。只剩下AB，CD相连的情况。这种情况如图所示：经计算，发现这种情形不能解决M5到M1、M2的条件。因此要解决问题，至少需要七条线段，在六条线段的基础上，我们只需再加一条线段来满足题意,可加的线段有M5A,M5B,M5M2,DA,DB,DM2,CB,CM2。考虑到路程问题，我们选择加最短的一条。由图可知，AD最短，于是连线段AD。经计算发现，该方案满足题目要求。方案的检验：当有七条线段时，因四个交叉点