[工学]公园内道路设计问题

《[工学]公园内道路设计问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：西安培华学院参赛队员(打印并签名)：1.胡斌斌2.罗丹3.白桂兴指导教师或指导教师组负责人(打印并签名)：李艳日期：2012年8月11日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公园内道路设计

3、问题摘要最短路问题是现实生活中常见的问题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本文讨论的是公园道路最优设计问题:在满足任意两入口之间最短道路长不大于两点连线的1.4倍的条件下，建立相应最短道路模型，使得修建总道路长度最短。又因公园边界已经存在修建好的道路，且不计入修建总总长度，所以应尽量利用边界道路。对于问题一，首先：利用1.4倍的约束条件排除可利用边界的入口点，选出需要通过交叉点设计路线的入口点。然后：依据Kruskal算法，构造最小生成树。最后：运用MATLAB软件编程，在满足要

4、求的情况下，得到最优道路设计方案。使得公园新修路的总路程最小为394.5596米。对于问题二，首先：取问题一中不可利用边界的入口点，分析出满足条件下的可行最短路线。然后：引入费马点，确定费马点个数，运用LINGO和MATLAB分别求解费马点坐标。最后：运用费马点优化可行最短路线，在满足要求的情况下，得到最优道路设计方案。使得公园新修路的总路程最小为358.4320米。对于问题三，首先：取问题二的最优道路设计方案，添加一矩形人工湖。针对人工湖对路线的破坏段进行局部优化。然后：给出2个可行局部优化方案，对局部

5、区域分别引入费马点，运用LINGO和MATLAB分别求解费马点坐标。最后：运用费马点优化可行方案，分别得到2个方案的最优道路设计方案。对比2个方案，得到最优的道路设计方案。使得公园新修路的总路程最小为360.5758米。关键词：Kruskal算法最小生成树费马点MATLABLINGO一、问题重述1.1、问题背景西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更好的生活条件。要求：公园计划有若干个入口，需建立一个模型去设计道路让任意两个入口相连（可以利用公园的边

6、，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，且任意两个入口之间的最短道路长不大于两点连线的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。（附录一.Fun1）。（图1）1.2、需要解决的问题问题一：假定公园内确定要使用4个道路交叉点为：a(50，70),b(

7、40，40),c(120，40),d(115，70)，见图2（附录一.Fun2）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法，画出道路设计，计算新修路的总工程。（图2）问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法，画出道路设计和道路交叉点的坐标，计算新修路的总工程。问题三：若公园内有一条矩形的湖，新修的路不能通过，但可以到达湖四周的边，已知矩形的湖为R1(140,70),R2(140，45),R3(165，45),R4(165，70)，见图3（附录

8、六.Fun1）。重复完成问题二的任务。（图3）注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连接到四周的其它点。二、问题分析2.1、问题一的分析先计算出“8个入口点两两之间的直线距离”，然后计算出“8个入口点两两之间的边界路径距离”。“8个入口点两两之间的边界路径距离÷8个入口点两两之间的直线距离≤1.4”---不需要通过交叉点设计路线。“8个入口点两两之间的边界路径距离÷8个入口点两两之间的直线距