2012西工大数模竞赛B题公园道路设计论文答案.doc

PAGE 装 订 线 “工大出版社杯”第十三届西北工业大学数学 建模竞赛暨全国大学生数学建模竞赛选拔赛题目 B题 密封号 2012年5月2日 剪 切 线 密封号 2012年5月2日 理 学院 第 182 队 队员1 队员2 队员3 姓名 杜雅丽 贾天一 潘琦明 班级11021002装 订 线 公园内新修道路路径设计问题 摘 要 本题讨论的是公园内道路设计最优化问题，即在公园的任意两个入口之间的最短道路不大于两点连线的1.4倍的前提下，使得新修路的总路程最短，并绘出相应的道路设计图。 由于公园的四周默认存在已经修好的路，因此先利用公园四周的路找出不满足题意条件的路径，以这些路径为主要研究对象，根据题目的具体条件找出最优建设路径。 对于4个交叉点已经确定的问题， 先将包括入口在内的12个点构成完全图，根据完全图的邻接矩阵，用Kruskal算法，生成最小生成树。再在此基础上，利用Floyd算法，将不符合条件的路径进行删除或替换，并依据总路程最短的原则，找出最优解。根据逐步逼近的算法，可求得优化后所得的最后结果，即是新修路总长为394.5米。在最后的模型讨论中，通过进一步假设，可求得进一步最优解为351.9米。 针对可以任意修建道路的情形，本文从0开始逐步增加公园内部交叉点的数目，发现至少有2个交叉点才能满足题中所给前提条件。本文先找出2个交叉点（）情况下的最优解，修路总长为375.3米。通过添加交叉点来对它进行优化，得到3个交叉点时的最优解为361.6米。最后，通过交替迭代优化算法，控制一部分点，改变其他点的位置，找出最终最优解为327.5米。 对于有湖存在的问题，根据假设，湖边的道路距离不计入新修建道路的总长，因此在第二问的基础上，利用湖边的道路对道路修建方案进行进一步优化，再次利用交替迭代优化算法，逐步求解得到最终结果297.68米。 关键词：交替迭代优化法 Kruskal 局部优化 贪婪算法 Floyd算法 第十三届西北工业大学校数模参赛作品 PAGE \* MERGEFORMAT1 目录 TOC \o 1-3 \h \u HYPERLINK \l _Toc15116 一、问题重述 PAGEREF _Toc15116 1 HYPERLINK \l _Toc10088 二、问题分析 PAGEREF _Toc10088 1 HYPERLINK \l _Toc6796 三、符号说明与模型假设 PAGEREF _Toc6796 2 HYPERLINK \l _Toc5418 3.1 符号说明 PAGEREF _Toc5418 2 HYPERLINK \l _Toc29473 3.2 模型假设 PAGEREF _Toc29473 3 HYPERLINK \l _Toc20982 四、模型的建立与求解 PAGEREF _Toc20982 3 HYPERLINK \l _Toc25792 4.1问题一的模型与解答 PAGEREF _Toc25792 3 HYPERLINK \l _Toc4662 4.1.1 模型的建立 PAGEREF _Toc4662 3 HYPERLINK \l _Toc15686 4.1.2 模型的求解 PAGEREF _Toc15686 3 HYPERLINK \l _Toc13039 4.2问题二的模型与解答 PAGEREF _Toc13039 6 HYPERLINK \l _Toc31195 4.2.1 模型的建立 PAGEREF _Toc31195 6 HYPERLINK \l _Toc18451 4.2.2 模型的求解 PAGEREF _Toc18451 7 HYPERLINK \l _Toc25704 4.3 问题三的模型与解答 PAGEREF _Toc25704 12 HYPERLINK \l _Toc27292 4.3.1 模型的建立 PAGEREF _Toc27292 12 HYPERLINK \l _Toc13777 4.3.2 模型的求解 PAGEREF _Toc13777 12 HYPERLINK \l _Toc11377 五、模型的扩展和讨论 PAGEREF _Toc11377 14 HYPERLINK \l _Toc