数学建模旅游问题C1

《数学建模旅游问题C1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文档旅游路线系统的数学模型及最优设计摘要本文建立了关于新疆旅游路线一系列问题的简洁数学模型。假设条件考虑周密，正确反映了实际中人的睡觉问题，以及旅游线路当中旅游城市可以作为交通城市借道存在的问题。同时引入满意度、城市重要值等解决问题的辅助参数，使得对旅游路线的设计更为切实合理化。在问题一中，通过优化非劣解目标空间，将多目标决策问题的最优解确定为6组，并通过人工分析得到最佳路线。对于问题二的MTSP（多旅行商）问题，我们通过Dijsktra算法构造生成完全图，转化为最优Hamilton回路问题，使用贪婪构造、2-代换

2、修正方法，最后给出一组非常理想的可行方案。问题三的双重极值问题，我们通过构造辅助MTSP问题，先求解出理论所需时间下界，再给出合理方法，构造出一组三覆盖路，使得考察时间最长的路线所需的时间近似等于理论下界，整个过程均采用多项式时间算法，时间复杂度很低，因此模型具有较强的实用性。问题四采用贪婪算法构造出5条旅游时间不超过12天的最优Hamilton路，并巧妙使用图中找“直径点”的方法，使求解出的旅游路线在真实地图上尽量“分散”。最后我们分析了程序给出的最优解，发现给出结果非常符合实际需求，这也印证了我们的假设是成功的。所有题

3、目均采取编程求解，我们采用VC++6.0编译通过所有源程序，并依此给出解答，程序作为附件保存，正文当中将给出程序的过程描述。关键词：旅游线路设计，MTSP问题，最优Hamilton路，最优Hamilton回路，2-代换修正方法文案大全实用标准文档摘要1一、问题重述4二、通篇模型假设与说明4三、模型的建立及求解4（一）问题一41.1问题重述41.2模型的假设41.3.1题目的优化51.3.2理想模型的建立51.3.3模型的求解61.3.3.1算法分析61.3.3.2求解所有可行解的近似算法71.3.3.3求解最优解的算法91

4、.3.3.4最优解的检验9（二）问题二112.1问题重述112.2模型的假设112.3模型的建立与求解112.3.1理想模型的建立及等价模型分析112.3.2等价模型的求解13（三）问题三143.1问题重述143.2模型的假设143.3模型的建立与求解143.3.1理想模型的建立143.3.2模型的求解143.3.2.1算法分析143.3.2.2辅助问题的求解153.3.2.3基于辅助问题下的构造16（四）问题四174.1问题重述174.2模型的假设174.3模型的建立与求解174.3.1问题分析17文案大全实用标准文档4

5、.3.2理想模型的建立及求解17四、模型的评价19五、模型的改进方向和推广20图1顶点编号和景点之间的对应关系图21图2新疆主要景点分布图22参考文献23附录24附录一：景点重要值24附录二：花费矩阵：24附录三：时间矩阵26附录四：满意度矩阵27附录五：[程序1]30附录六：[程序2]39附录七：[程序3-1]45附录八：[程序3-2]52附录九：[程序4]58文案大全实用标准文档一、问题重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地

6、方，新疆的其他地方对他们也有很大的吸引力。1.请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。2.如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。3.如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。4.新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自

7、治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。二、通篇模型假设与说明1.由于该问题是旅游线路/考察路线安排问题，必须考虑到人的基本生理需要，我们假定游客每天固定需要8小时的睡觉时间，以及1小时的自行支配时间，这样我们将时间利用率固定为15/24，也即下面我们总认为每天只有15个小时可用来进行旅游支配。相一致的，每个顶点的最佳旅游时间也不考虑在

8、该景点的睡觉时间（例如：我们给乌鲁木齐赋予旅游时间权28小时，它表示在乌鲁木齐除去睡觉时间共需呆28小时）；并假设交通时段皆在白天（不考虑坐夜车情形）。2.旅游过程中，假设每天王先生夫妇两人的住宿费用为定值。3.忽略天气，意外事故等不可抗因素对旅游路线的影响。4.不考虑两点间除了二级公路、一级公路、高速