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

武汉理工大学第十二届数学建模校内热身邀请赛承诺书我们仔细阅读了武汉理工大学第十二届数学建模校内热身邀请赛的竞赛细则。我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规则的行为,我们将受到严肃处理。我们的参赛报名号为: A42 参赛队员(签名): 队员 1: 队员 2: 队员 3: 武汉理工大学第十二届数学建模校内热身邀请赛编号专用页选择的题号: A参赛的编号: A42 (以下内容参赛队伍不需要填写) 竞赛评阅编号: 0 武汉某动物园路线规划摘要本文研究的是最短路线设计问题, 通过道路程设计来探求如何使得新修路总路程最小, 在数学归类上属于规划类问题。本题是一个道路设计的最优化的问题,即是如何设计路径使动物园内部新修路总长最小,但要满足以下两个控制条件: 倍; 2. 要求动物园内新修的道路与四周的连接只能与 8 个路口相通而不能连到四周的其他地方。在该问题中,因为题目中所言动物园边界路长度不计,所以我们的基本思路是多利用动物园边界路。由此,我们利用勾股定理,证明出了两邻边入口的边界距离一定小于其直线距离的 倍,由此简化成为两对边入口连接问题。我们对题目所给条件进行分析,认为可以分为两种情况,一种为交叉点不全用的情况,这种情况下,问题一的最短路程为 米;另一种为交叉点全用, 这种情况下,问题一的最短路程为 米。对于问题二,我们分析发现,海洋馆对于规划无影响,问题一的解答完全适用于问题二,所以问题二的解同问题一。关键字:路线规划问题简化模型优化 1 1. 问题的重述与分析 问题的重述改革开放以来,作为中部最大城市的武汉,在经济发展上取得巨大成果。为了响应国家中部崛起战略,营造美好家园,武汉市政府近期决定建造一个矩形动物园。为方便游客游玩,动物园设计规划决策者想在已经建好道路的矩形动物园的四边上设置 8 个入口; 内部有四个交叉点, 分别是: 。现在请你建立一个模型,在两个入口最短道路长不超过两点连线 倍的情况下,如何使道路总长最短?(总长中不计入矩形四边的长度,新修的路与矩形四边的连接只能在入口处,不能在矩形的其他位置) 矩形动物园的基本参数及各个路口坐标为: 长: 1000 米,宽: 500 米图1是动物园入口图,图 2是一种可能的规划,但不是最优化的问题一:根据以上信息给出你的计算方法并算出最短总长问题二:如果在中间设一个矩形海洋馆,如图 3,海洋馆的四个点坐标为: ,要求道路不能穿过海洋馆, 但可以到达四边,以此绕过海洋馆,那最短长度又是多少呢? 图1 矩形动物园及其入口图图2 可能的一种情况(但不是最优) 2 图3 有海洋馆的示意图 问题的分析总的来说,该动物园的路线规划主要是须服从“任意两个入口最短道路长不超过两点连线 倍”这个条件。我们首先要简化该问题。因为动物园边界路的长度不计入所修路程的总长度,所以我们优先考虑动物园边界路。因为题目中动物园的门较多,所以我们首先考虑了哪些门是在不修任何路的情况下,可以互相由动物园边界路到达。经过计算,得出以下几个是不满足从边界到达的:M 1→M 5, M 2→M 5,M 2→M 6,M 3→M 5,M 3→M 6,M 3→M 7。因题目中未提及交叉点是否必须使用,于是我们分两种大类情况进行建模。第一种为四个交叉点不都用,第二种为四个交叉点必须全用。 2. 假设与符号说明 模型假设 ,不影响游客的游览心情。 ,其他处均满足修路的客观条件。 ,且均可看做是直线。 ,视为一个点。 。 符号说明: C1: 记动物园边界路最小距离不大于连线距离 倍的无序点对为 C1 类无序点对; C2: M 1,M 2 …… M 8 构成的所有无序点对中除 C1 类之外的无序点对记为 C2 类无序点; B 1:以动物园入口 M 1,M 2,M 3,M 5,M 6,M 7为顶点的连通图的邻接矩阵; B 2:以动物园入口 M 4,M 8为顶点的连通图的邻接矩阵; D 1:以M 1,M 2,M 3,M 5,M 6,M 7个点中任意两点沿矩形边框的最短距离构成的