word摘要随着人们生活水平的不断提高，作为“无烟工业”旅游活动便成为人们生活水平的重要指标。本文围绕五一黄金周的旅游问题进行了定量的评估，对即有时间限制又有时间限制的旅游质量问题建立了数学模型，对求解结果进行了分析。问题要求在只有1000元的旅游费用且在7天之的条件下游览尽可能多的城市。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件不仅要求费用不大于1000而且旅游时间在7天之，因此，我们从长途汽车站和火车车次中选取费用最低且最节约时间的路线并记录了最优行程费用表。另外，由于时间的限制，因此，需引入0-1变量表示是否游览某个景点，根据求解最优Hamilton回路算法三边交换调整法，以费用和时间为参考量，我们建立了一个适用于本问题最优规划模型，得出最优旅游路线。关键词：三边交换调整法 最优旅游路线 Matlab程序 01模型 / 问题重述旅游路线安排计划黄金周又到了，希望安排出外旅游。你要考虑的因素很多。首先，你得考虑时间有限（天）；其次要考虑费用问题：根据有限的费用安排你的交通方式。当然，还要考虑出游的乐趣，希望多走几个景点。还要考虑劳逸结合，如较远的地方如坐火车需乘坐卧铺，晚上休息。如何安排你的假期。假设一个景点一天的平均费用为100元，你手中恰有刚刚发下来的奖学金1000元。要制定合理的旅行路线，需要考虑的因素很多，如交通方式，尽可能去多个景点，休息住宿等。假设一个景点一天的平均费用为100元。那么如何安排你的假期？预选的九个市旅游景点市景点名称在景点的最短停留时间卢芽山5小时吕梁北武当山7小时晋祠6小时藏山6小时晋中平遥古城5小时上党门7小时五老峰4小时九女仙湖4小时豫西大峡谷7小时模型假设与符号说明模型假设1、所有的车票均预订；2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑；3、平均每个城市的交通费用30元(如公交车、出租车等)；4、景点的开放，列车和汽车的运营不受天气的影响；5、每天的伙食费达到最高标准40元/天；6、景点停留时间超过六小时必须住宿，住宿费每晚60元；7、在时间的认识上，我们把当天的8点至次日8点作为一天；8、由于旅游者携带学生证，所有门票按半价计算。符号说明、i,j表示第i个城市(景点)或第j个城市(景点)，i、j=1,210；、Z表示计划行程中的总费用；、W表示各城市(景点)之间的交通费用的总和，表示各城市(景点)之间的交通费用；、A表示在景点所在城市的总花费，其中包括表示第i个城市(景点)的交通费用，表示第i个城市(景点)的食宿费用，表示第i个城市的景点的门票费用， 表示第i个城市(景点)总费用，故=+；、表示在第i个城市(景点)的逗留时间，表示从第i个景点到第j个景点路途中所需时间，T表示本次旅游的总时间；、问题分析问题背景分析根据对题目的理解，我们知道旅游时的总费用包含交通费用、住宿费用和在景点旅游时的费用，在研究确定旅游路线和选用的交通工具后，我们的目标是在所有的约束情况下，求出所求目标的最优解。对问题分析问题要在7天的时间、不大于1000元的旅游费用的情况下使游客游览尽可能多的景点数。模型的准备先给11个旅游城市分别进行编号，、吕梁、晋中、分别编号为、。则这10个城市和其交通路线构成了一个网络图。这些城市可看作该网络图的节点。各城市距离（单位：公里）吕梁晋中0347.1380262440241315.5148594192.1347.10269.981.3183.7108.4304.1500462519.9吕梁380269.90184.8275.3.7377.8376.06457.9436.326281.3184.80118.137.5223.8392.9322.3437.1440183.7275.3118.1097.9313.3412439527.6晋中241108.4.737.597.90.9398280.8444.8315.5304.1377.8223.8313.3.90360518384148500376.06392.9412398360017957.8594462457.9322.3439280.85181790240192.1519.9436.3437.1527.6444.838457.8240001模型目标函数的确立：旅游总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们已经定义：Z旅游总花费；W交通总费用；A旅游景点的花费；从而得到目标函数： Z=W+A(1)、交通总花费因为表示第i个景点到第j个景点所需的交通费用，而是判断游客们是否从第i个景点到第j个景点的01变量，因此我们可以很容易的得到交通总费用为：(2)、旅游景点的花费因为表示游客在i个景点的总消费，也可以表示出是否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此实际上将所到景点的花费计算了两遍，从而我们可以得到旅游景点的花费为：从而我们可以得到目标函数为：约束条件:时间约束：旅游时间应该不超过5天，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为表示从第i个景点到第j个景点路途中所需时间，所以路途中所需的总时间为；表示在第i个景点的逗留时间，故在旅游景点的总逗留时间为因此，总的时间约束为：旅游景点数约束： 根据假设，整个旅游路线是环形，即最终要回到，因此即表示旅游的景点数，这里我们假定要旅游的景点数为n（n=1，2，3，9）。因此旅游景点数约束为：01变量约束：我们可以把所有的景点连成一个圈，而把妹一个景点看做圈上一个点。对于每个景点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且有一条边进入就要有一条边出去。因此可得约束：当i=1时，因为是出发点，所以；j=1时，因为最终要回到，所以。综上所述，我们可以得到总的模型为：约束条件 各大景点门票信息4景点卢芽山北武当山晋祠藏山风平遥古城上党门五老峰九女仙湖豫西大峡谷门票15元25元35元40元60元65元30元32元30元 *所有票价按学生票均半价*模型的建立与求解建立既有时限又有费限的旅游质量Hamilton回路模型，由于规定了费用1000元和时间7天，所以这是一个完整的01模型，通过对综合模型和结合Hamilton回路模型的运算最优通行费用表最少旅费吕梁晋中03740254524.5352055233702618221934524653吕梁4026022.526.523383745.545251822.50181624413645455226.518018.5354345.553.5晋中24.519231618.5023.5412754353438243523.503652.5392052374143413602117554645.53645.52752.521024.52353454553.554391724.50编写基于Hamilton回路算法的C语言程序，输入上表数据，运行得出有时间限制又有费用限制的情况下，最优城市顺序为：。城市之间的交通费=24.5+18.5+18+22.5+37+17+23=160.5(元)市的交通费 M=(元)餐饮费S=(元)住宿费N=2=120(元)景点门票费 =60+40+35+25+30+30=220（元）所以总旅行费用 =160.5+180+120+280+220=960.5（元）模型结果分析针对该问题推荐最优旅游路线：。旅游景点数：6 旅游总费用：960.5元旅游总耗时：6天12小时（156小时）本文通过建立基于三边交换调整法的旅游路线模型和引入01模型进行规划，在一定的约束条件下为游客设计了近似最优旅行路线。由于用了01模型进行简化，建模和编程得以顺利完成；经后期检验，所得结果能满足题目的要求，最大程度减少了时间或资金的消耗，具有较好的实际意义。但由于数据量过于庞大，模型中为了方便研究又有一些假设，所以所得结果只是近似最优解。模型的评价本文根据游客的旅行路线进行了合理假设，简化了次要因素，把问题转化为图论上最佳旅行商回路问题解决，思路比较清晰，模型恰当，得出的方案相对合理,使问题得到了比较合理的解决；成功的使用了01变量，使模型的建立和求解得以顺利进行。但是，由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进一步的改进。实际情况中，两景点之间的交通方式比较复杂，如公路、铁路、航班之间可以转换，增加这些考虑后，结果会更加合理。且数据资料搜集的不完整，有一定的局限性，准确性也有待商榷，而且没有对最终方案进行更为细致的研究讨论，这些方面还有待改进。参考文献1卢开澄，卢华明编著，图论及其应用，：清华大学，1996。2来福，增文艺，数学模型与数学建模，师大学，1998。3刁在筠，汉鼎，运筹学，：高等教育，2006.7。4 列车时刻表，zhidao.baidu./,2011年5月1日。5 长途客运站信息，.piaojia./changtuzhan/,2010年5月1日。