数学建模论文：最佳旅游路线.doc.doc

数学建模论文最佳旅游路线设计院系: 信息科学与技术学院 2 保证书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则,我们完全明白在竞赛开始后不能以任何方式与队外的任何人讨论有关竞赛试题的求解内容,抄袭别人的成果也是违反竞赛规则的,如被发现将会受到严肃处置。我们也知道如果引用别人的成果或其他公开的资料(包括网上查到的资料)必须按照规定的参考文献的表述方式在正文和参考文献中明确列出。为了确保竞赛的公正、公平性,我们保证严格遵守竞赛规则。参赛院系:信息科学与技术学院参赛队员: 2008 年 6月 28日 3 最佳旅游路线设计摘要为了提出合适的旅游线路,从实际情况出发考虑,本文建立了合适的线路选择模型,并给出了一些结果。问题一为既考虑旅游消费,又考虑旅游的景点数的旅游线路选择问题。本文对去各景点间的路费、景点门票、在景点内每天的平均消费加以考虑,建立了 0 1 ?规划模型。对于多目标模型,我们采用适当的拟合将多目标转化为单目标。并使用 lingo 软件编程得出最优旅游线路及合适的旅游时间为:二号线:成都→乐山→峨嵋,最合适的旅游时间均为 1天;三号线:成都→四姑娘山→丹巴,最合适的旅游时间均为 1天;四号线:成都→都江堰→青城山,最合适的旅游时间为都江堰 2天,青城山 1天;五号线:成都→康定,最合适的旅游时间为 1天。并对最优线路给出了详细的评价。问题二,在代表时间充裕的条件下仅考虑旅游的交通费用,我们把各景点看成是纯数学中的点,利用图论的知识求解。在建模中,我们把各景点间的路费作为巡回图边的邻接矩阵权,使原题巧妙的转化为了图论中旅行商问题(即最短路问题) ,建立了线性规划模型, 利用 lingo 软件求解得到最少的交通费用为 元,最佳的旅游路线为: 成都→青城山→都江堰→四姑娘山→丹巴→黄龙→九寨沟→海螺沟→康定→峨眉→乐山→成都。问题三在问题一的基础上增加了对代表旅游意向的考虑,建模思路与问题一大致相同。我们把代表的旅游意向刻画为代表对旅游路线的满意度,然后在问题一的基础上增加一个目标函数,即在整个旅游线路中满意度最高。建立了多目标优化模型,采用同样的方法把多目标规划问题转化为单目标问题利用 lingo 软件求解得到: 旅游的景点总数是 7 个,总的满意度是 ,各条路线的满意度分别为 , , , , 。下面是求得的最佳旅游路线以及最合适的旅游时间:二号线:成都→乐山→峨嵋,最合适的旅游时间为前者 2天,后者 1 天;三号线:成都→四姑娘山→丹巴,最合适的旅游时间为前者 1 天,后者 2 天;四号线:成都→都江堰,最合适的旅游时间为 2天; 五号线:成都→海螺沟→康定,最合适的旅游时间均为 1天。最后,我们对整个过程进行了科学性的评价。并提出了使用 Dijkstra 算法和遗传算法解题的思路。关键词: 0 1 ?规划线性规划多目标规划 lingo 遗传算法 Dijkstra 算法 4 1 问题重述随着生活水平的提高,旅游逐渐成为最热门的户外活动之一。在旅游的过程中,我们不仅可以感受大自然的美,而且可以领略不同地方的文化气息,乡土风情。在这里考虑到旅游者的以下需求:;;。设计合适的旅游线路方案来满足旅游者的各种需求,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足旅游者的各种不同需求。在这里只针对将要来参加西南交通大学数学系召开的“×× 学术会议”的来自国内外的许多著名学者,为其设计合适的旅游路线。需要解决如下问题: 1. 根据提供的五条线路,要求设计出合适的旅游路线,使得会议代表能在 10天内花最少的钱,游最多的地方。 ,当代表时间非常充裕(比如一个月) 时,可以游完所有的景点才离开,设计合适的旅游路线,使在四川境内的交通费用尽量地节省。 ,充分考虑这些代表的意愿,为设计代表们合适的旅游路线,使他们在会议结束后的 10 天时间内花最少的钱游尽可能多的地方。 2 条件假设 。 。 3 .假设在问题一中不考虑每一条路线的最优,而是考虑整个旅游过程的最优问题。 3天。 3 符号说明模型一中: ijy ——第i 条线路中第 j 个景点( 0 1 ?变量) ijp ——第i 条路线第 j 个景点的门票(单位:元) ija ——在第 i 条路线第 j 个景点平均每天的基本消费(单位:元) il ——第i 条路线的平均路费(单位:元) c —— 10天中旅游的景点总数 n —— 10天中的总消费(单