- 1、本文档共28页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2012西工大数模竞赛B题公园道路设计论文答案
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
您可能关注的文档
最近下载
- 秋冬季常见传染病预防 ppt课件.pdf
- GB 55009-2021 燃气工程项目规范.pdf
- 液体石油产品烃类的测定-荧光指示剂吸附法(GB-T11132-2008).ppt
- 上海市病媒生物密度控制水平评估技术方案.doc VIP
- 高空作业车售后服务方案.docx
- 2024-2025学年河北省沧州市泊头市第一中学高二(上)月考物理试卷(9月)(含答案).docx
- 自-机械制造技术基础课程设计说明书 .doc VIP
- 53个经典病例分析及答案.doc VIP
- [职高 对口升学] 2021年重庆高职分类考试 文化素质测试 真题.pdf VIP
- 电子技术基础数字部分(第7版)康华光习题解析.pdf
文档评论(0)