西工大数模竞赛b题公园道路设计论文答案

《西工大数模竞赛b题公园道路设计论文答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、装订线“工大出版社杯”第十三届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目B题密封号2012年5月2日剪切线密封号2012年5月2日理学院第182队队员1队员2队员3姓名杜雅丽贾天一潘琦明班级110210021102100211021002装订线公园内新修道路路径设计问题摘要本题讨论的是公园内道路设计最优化问题，即在公园的任意两个入口之间的最短道路不大于两点连线的1.4倍的前提下，使得新修路的总路程最短，并绘出相应的道路设计图。由于公园的四周默认存在已经修好的路，因此先利用公园四周的路找出不满足题意条件的路径，以这些路径为主要研究对象，根据题目的具体条件找出最

2、优建设路径。对于4个交叉点已经确定的问题，先将包括入口在内的12个点构成完全图，根据完全图的邻接矩阵，用Kruskal算法，生成最小生成树。再在此基础上，利用Floyd算法，将不符合条件的路径进行删除或替换，并依据总路程最短的原则，找出最优解。根据逐步逼近的算法，可求得优化后所得的最后结果，即是新修路总长为394.5米。在最后的模型讨论中，通过进一步假设，可求得进一步最优解为351.9米。针对可以任意修建道路的情形，本文从0开始逐步增加公园内部交叉点的数目，发现至少有2个交叉点才能满足题中所给前提条件。本文先找出2个交叉点（）情况下的最优解，修路总长为375.3米。通过添加

3、交叉点来对它进行优化，得到3个交叉点时的最优解为361.6米。最后，通过交替迭代优化算法，控制一部分点，改变其他点的位置，找出最终最优解为327.5米。对于有湖存在的问题，根据假设，湖边的道路距离不计入新修建道路的总长，因此在第二问的基础上，利用湖边的道路对道路修建方案进行进一步优化，再次利用交替迭代优化算法，逐步求解得到最终结果297.68米。关键词：交替迭代优化法Kruskal局部优化贪婪算法Floyd算法第十三届西北工业大学校数模参赛作品目录一、问题重述1二、问题分析1三、符号说明与模型假设23.1符号说明23.2模型假设3四、模型的建立与求解34.1问题一的模型与解

4、答34.1.1模型的建立34.1.2模型的求解34.2问题二的模型与解答64.2.1模型的建立64.2.2模型的求解74.3问题三的模型与解答124.3.1模型的建立124.3.2模型的求解12五、模型的扩展和讨论14六、模型评价15七、参考文献16八、程序附录168.1附录1求最小生成树的克鲁斯卡尔算法168.2附录2求解问题二两个交叉点的源程序188.3附录3问题二交替迭代求最优解的源程序218.4附录4求解问题三的源程序2324第十三届西北工业大学校数模参赛作品一、问题重述现在要修建一个有8个入口的公园，即确定公园入口与园内交叉点的适当连线，使得公园的任意两个入口相连

5、，但需满足道路总长度和最小，而且任意的两个入口之间的最短道路长不大于两点连线的1.4倍。同时公园四周的边上存在已经建好的道路，且不计入道路总长。我们将主要设计对象假设为一个长200米，宽100米的矩形公园。我们要做的有以下三项工作：1、假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。2、现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路

6、程。3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，以此为前提，重复完成上一问题中的任务。二、问题分析本题是一个道路设计的最优化的问题，即是如何设计路径使公园内部新修路总长最小，但要满足以下两个控制条件：1.任两个入口连通；2.任两个入口的最短路径不超过其直线距离的1.4倍。由于题设中说明公园四周存在修好的道路且允许通行，我们先利用四周道路，找出经过这些道路不能满足条件的路径，通过计算我们得出，，，，，，，，，这10条边不满足题意条件，在后续的问题中我们可将其作为主要条件，主要考虑这些路径，不考虑其他路径，这样就可以使问题简化，然后根据各个问题的具体要

7、求，进行求解。24第十三届西北工业大学校数模参赛作品三、符号说明与模型假设3.1符号说明1、，公园的8个入口；，公园8个入口及内部所设的m=n-8个交叉点依次编号。2、m，公园内交叉点数目；，公园内部修建道路总长。3、条件，控制条件，即任两入口之间的最短路径不大于其直线距离的1.4倍；条件，控制条件，即公园中新修路的总路程最短。4、D=，图中第i个和第j个点之间的直线距离。5、为控制矩阵，即为了保证设计路线中两入口间最短路径长度小于其直线距离1.4倍。6、S=，S为最短路径矩阵，元素表示在设计路径中第i和第j个点间