C最佳旅游路线设计.丁一凡.doc

安徽工程大学数学建模课程设计论文题目: 最佳旅游路线设计姓名: 丁一凡班级: 数学 112 指导老师: 周金明成绩: 完成日期: 201 3年 7月 3日摘要本文主要研究的是如何选择最佳线路的问题。对于线路的选择,我们主要考虑旅行中的费用及旅行时间。我们首先通过网络查找得到各景点(包括景区)之间的距离,门票费用以及最佳逗留时间,据此将景点图简化成赋权无向图。然后利用 floyd 算法得到每 2个景点间的最短路径。据此,根据题目要求分别建立 0-1 线性规划模型。问题一给定了时间约束,要求花最少的钱游尽可能多的地方。据此,我们以花费最少为目标, 以时间限制及线路要求为约束,建立 0-1 规划模型,利用 ling o 软件对模型求解。对结果进行综合分析,最后我们向王先生夫妇推荐景点数为 16 的路线:乌鲁木齐- 达坂城- 哈密- 库尔勒- 楼兰- 阿克苏- 千佛洞- 天鹅湖- 伊犁-博乐-石河子-克拉玛依-阿勒泰-昌吉-天山天池-乌鲁木齐。平均每个景点花费为 73. 4 元,除了吃饭以外,这对夫妇总共花费估计为 4102 元。问题二要提出 2条路线游完所有景点,据此,我们首先将所有景点按南北疆分为 2组。这两条路线要求交通费用最少,即总路程最少,我们以总行驶路程为目标,以相应的条件为约束,建立 0-1 线性规划模型。利用 lingo 求解得到每组路线所需最短时间,并求得其均衡度。然后对其进行调整,找到均衡度最好的一种分组。我们为王先生夫妇推荐的第一个月的路线为:乌鲁木齐-昌吉-博乐-石河子- 克拉玛依- 阿勒泰- 额尔齐斯河- 喀纳斯湖- 天山天池- 哈密- 吐鲁番- 达坂城- 乌鲁木齐,交通费用为 740 元。第二个月的路线为乌鲁木齐--库尔勒--楼兰--尼雅遗址--和田--喀什--阿克苏--千佛寺--伊犁--天鹅湖--乌鲁木齐,交通费用为 820 元。问题三与问题二相似,我们根据各景点之间的最短路径画出以乌鲁木齐为树根的树形图,然后按分类原则分为三组。将模型二中的目标函数换为考察时间最小得到模型三,分别用 lingo 求解得到每组最佳路线及时间。求其均衡度,然后对其进行调整。最后,我们对该考察团设计了三条考察路线。路线一:乌鲁木齐- 博乐- 伊犁- 昌吉- 天山天池- 吐鲁番- 达坂城- 乌鲁木齐,考察时间为 47 天。路线二:乌鲁木齐-石河子-克拉玛依-天鹅湖-千佛洞-阿克苏-尼亚遗址-和田-喀什-乌鲁木齐,考察时间为 51 天。路线三:乌鲁木齐- 喀纳斯湖- 阿勒泰- 额尔齐斯河-库尔勒-楼兰-哈密-乌鲁木齐,考察时间为 48天。问题四中,由于参加每条路线的人数与该线路上服务能力成正比,我们认为每个景点只在一条线路上。据此,我们根据假期时间限制以及游遍所有景点所需时间最少,求得至少要提供 4条旅游路线才能满足题意。根据分析,我们发现无法找到这样 4条路线均满足要求,因此,我们将所有景点分为 5组,通过多次求解调整,最终我们为旅行社提供了 5种路线。具体结果在正文中给出。最后,本文对模型进行了分析与评价。关键词:最短距离均衡度 0-1 线性规划最佳路线一、问题的重述王先生夫妇是华东某高校的年轻教师,打算暑假中到新疆旅游。受文学作品的影响,天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方,新疆的其他地方对他们也有很大的吸引力。 1 .请你们为他们设计合适的旅游路线,使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方,并估算除吃饭之外的费用。 2 .如果他们打算今、明两年暑假完成对新疆的旅游,请你们为他们设计合适的旅游路线,使在新疆境内的交通费用尽量地节省。 3 .如果华东某高校的少数民族研究所组织对新疆文化考察,考察分三组进行,用于交通的时间和前两种情况相同,但考察时间是旅游观光时间的四倍,请你们为他们设计合适的考察路线,以便尽早完成考察任务。 “五一旅游黄金周”(考虑到远途旅游,自治区内游程延长为十二天)准备为自治区外的游客组织多条旅游路线以分散游客, 提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下,请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。下图是新疆主要景点分布图,各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆新疆旅游网对题。你也可以目做进一步的完善。二、问题的分析分析题意可知,本题的目标是寻找最佳旅游线路。便于分析,我们首先将景点进行编号,把实际地图简化为赋权无向图,即转化为图论问题。再考虑旅行中的花费,除吃饭和住宿外,主要考虑交通费用和景点的门票费。因此我们需收集各景点之间的路程、最佳逗留时间以及门票费用。问题一要找出一条最佳旅游路线,使得夫妇在一个月的时间内花最少的钱游尽可能多的地方, 这是一个最