第八届苏北地区数学建模联赛B题一等奖论文.doc

2011年第八届苏北数学建模联赛 承 诺 书 我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛报名号为： 参赛组别（本科或专科）： 参赛队员 (签名) ： 队员1： 队员2： 队员3： 获奖证书邮寄地址： 2011年第八届苏北数学建模联赛 编 号 专 用 页 参赛队伍的参赛号码：（请各个参赛队提前填写好）： 竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）： 2011年第八届苏北数学建模联赛 题 目 摘要(((((((((((； 第四步，综合考虑安排，建立行程表；计算可得最少的总旅行费用为3101元。 问题二在不限制费用的条件下，要求用最短的时间游览完十个景点。其原理与问题一非常相似，故可用问题一的数学模型及方法，改用景点之间消耗的时间作为参考量，最终得到行程表且知最优旅游路线：(((((((((((；最短的旅行总时间8天22小时23分。 问题三要求我们在只有2000元旅游费用的条件下游览尽可能多的城市。因此我们引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件。这样寻找不同景点数时的最优旅游路线，并计算其总费用。则最优旅游路线的总花费为1795元，游览了7个景点，是不超过2000元的最大值，据此构建行程表。 问题四中我们要在5天的时间内游览最多的景点并回到徐州。其实质是把问题三中的费用约束条件变成了时间约束，故在此我们依然可用问题三中的模型进行求解，得到最多可游览6个景点，耗时4天13小时（106小时），据此建立行程表。 问题五可看做是问题三、四的合并，其中费用和时间都是约束条件。因此我们综合问题三、四中的算法，运用问题三中的模型对其进行全面分析，得到最多可游览6个景点，并建立行程表。 关键词：Hamilton回路算法 C语言 最优旅游路线 0—1模型1.问题重述 随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。 表1. 预选的十个省市旅游景点 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院洛阳龙门石窟 6小时 假设： (A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。 (B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 (C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。 (D) 假设景点的开放时间为8:00至18:00。 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。 (3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 2.模型的假设与符号说明 2.1模型的假设 五一黄金周正值旅游旺季，各地旅游景点吸引了大批游客前往观光。考虑到该游客的旅游路线跨越区域较大，交通情况尚存在一些不确定因素。为了研究方便，我们给出以下假设： （1）城际交通出行可以