数学建模竞赛获奖作品

1、新余学院2011年大学生数学建模竞赛承诺书我们仔细阅读了新余学院大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B中选择一项填写）：B我们的参赛报名号为（如果设置报名号的话）：24参

2、赛队员（打印并签名）：1.刘水根游凯王娟日期：2011年_月_日评阅编号：精选文库 新余学院第二届数学建模竞赛评阅专用页评阅编号阅卷人（签名）摘要20分假设的合理性10分算法的正确性20分创新性10分语言文字表述清晰、流畅20分论文的整体美观度10分论文的完整性10分总分总平均分组长签名：年月日最佳旅游路线设计摘要本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的条件下，实现小张的旅游愿望。基于对此的研究，建立数学模型，设计出最佳的旅游路线和途径。第一问没有时间的约束，要求设计合适的旅游路线。该问题是典型的货郎担（TSP）问题。我们建立了一个最优规划模型，在将八个旅游景点全部游完的前提下

3、花最少的钱为目的。从而推出交通费用、住宿餐饮费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：新余f福建武夷山f温州梅雨潭f河南嵩山少林寺f四川九寨沟f云南丽江古城f贵州黄果树f广西桂林大漓江f宜春明月山f新余。预计总费用为约2658.5元人名币。第二问放松费用的约束，要求游完所有景点。同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：新余f宜春明月山f福建武夷山f浙江温州梅雨潭f河南嵩山少林寺f四川九寨沟f云南丽江古城f贵州黄果树f新余。第三问在一、二问的基础上，增加了时间和费用的先限制，要求设计合适的旅游线路，使在约束条件下，所

4、游景点最多。再引入01变量表示是否游览某个景点，从而推出交通费用、住宿餐饮费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：新余f宜春明月山f福建武夷山f温州梅雨潭f河南嵩山少林寺f新余新余f宜春明月山f桂林大漓江f贵州黄果树f云南丽江古城f新余本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，word编辑，这样给处理数据带来了不少的方便。本文成功地对01变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。此外，本文建立的模型具有很强普适性，便于推广。关键词：最佳路线TC

5、P问题综合评判景点个数最小费用1问题重述随着人们生活水平的不断提高，假期旅行已受到越来越多人的青睐。假设小张也是一位旅游爱好者，想通过今年暑假到全国的一些著名景点旅游，具体旅游时间从7月3日上午八点开始，从新余出发，最后回到新余。考虑到跟团旅行受到的各种限制，他打算作为一名背包客出行，并列选了全国八个旅游景点作为游玩对象，具体的旅游景点名称、门票价格及最短逗留时间如下表：省市景点名称门票价格在景点最短逗留时间广西桂林大漓江2204小时江西宜春明月山1004小时云南丽江古城1003小时贵州黄果山1803小时福建武夷山1206小时河南嵩山少林寺1004小时四川九寨沟2205小时浙江温州梅雨潭120

6、3小时假设已知条件还有:1、两城市之间来往可乘火车（动车或高铁）、长途汽车或飞机（不允许包车或包机）；2、市内交通可乘坐公交车、地铁或出租车；3、旅游的门票价格以上标价格为准，不存在学生票半价，其他旅游费用包括交通费、住宿费、餐饮费等。又假如小张为晚上20：00至次日7：00之间在某地逗留时间超过6小时，则必须住宿，住宿费用不超过180元/天，餐饮费用为60元/天，出租车费用外算；4、各景点的开放时间为08：00-19：00.请根据以上已知条件，针对如下几种情况，结合实际问题，为小张设计详细的旅游行程表，入住宾馆的时间、地点、及宾馆名称，景点的停留时间等信息。1、如果时间不限，将所有八个旅游景

7、点全部游完，至少需要多少时间，请建立相应的数学模型并设计旅游行程表；2、如果旅游费用不限，将所有八个景点全部游玩，至少需要多少时间，请建立相应的数学模型并设计旅游行程表；3、如果游客只有四天时间，1500元旅游费用，想尽可能多的旅游景点，请建立相应的数学模型并设计旅行行程表。2问题分析问题背景的理解：根据对题目的理解我们可以知道，旅游的总费用包括交通费用、住宿餐饮费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。问题一、问题二和问三的分析。问题一要求我们为小张设计合适的旅游路线，使小张在时间充裕的条件下花最少的钱将所有景点

8、游完。在这里我们的做法是在满足相应的约束条件下，计算出在这种情况下的最小花费。问题二实质上是在问题一的基础上改变了约束条件，使得没有费用的限制下花最少的时间去将所有的景点游完。我们完全可以使用与问题一同样的方法进行求解。问题三要求我们在问题一的基础上充分考虑小张的实际情况来设计最佳旅游路线，在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。3模型假设1、所给前两条线路中的景点必须全部参观，最后一条线路中的景点可以去不参观，也可以参观其一；2、不考虑旅游天气对游览费用的影响；3、一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地而并不

9、进行游览；4、在限定的时间内，代表们最终要返回成都，并且假设成都是代表们肯定要去的一个旅游景点；5、使用旅游大巴安排代表们往返于各个旅游景点，其交通费用参照当地客运公司的数据；在景点的花费、在景点的逗留时间参照题目中的附表中的数据；6、小张乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；4符号说明i,j第i个或者第j个景点，i，j=1，2，8；分别表示桂林大漓江、明月山、丽江古城、黄果山、武夷山、嵩山少林寺、九寨沟、温州梅雨潭；c小张的旅游总花费；t小张在第i个景点的逗留时间;ic小张在第i个景点的总消费；it从第i个景点到第j个景点路途中所需时间;ijc从第i个景点到第j个景

10、点所需的交通费用;ijn表示小张在旅途中的住宿总费用（具体见附表）。=ri代表直接从第i个景点到达第/个景点=|0其他5模型建立及求解5.1问题一：5.1.1目标函数的确立：经过对题目分析，我们可以知道本题所要实现的目标是，使小张在时间充裕的条件下花最少的钱游览全部的旅游景点。显然，花费最少是该问题的一个目标。因此，我们的做法是在满足相应的约束条件下，确定游览的8景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而小张可以根据自己的实际情况选择。游览的总费用由3部分组成，分别为交通总费用、住宿餐饮费用和在旅游景点的花费。我们定义：m小张的旅游总花费；m小张的交通总费用；1m

11、小张的旅游景点的花费；2m小张的餐饮总费用。3从而得到目标函数：Min1231）交通总花费因为c表示从第i个景点到第j个景点所需的交通费用，而r是判断代ijij表们是否从第i个景点直接到第j个景点的01变量，因此我们可以很容易的得到交通总费用为：88m=乙乙1i=1rxcijijj=12）旅游景点的花费因为c小张在i个景点的总消费,ir也可以表示出小张是否到达过第iij个和第j个景点，而整个旅游路线又是一个环形，因此工为rx（+c）实ijiji=1j=1际上将小张在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：iyy()m=xrxr+c722ijiji=ij=i3)餐饮费用工为(t+

12、1)根据题目意思餐饮费用为60元/天，所以餐饮总费用60 xII1j24我们可以的到小张的餐饮总费用为工另(t+1)iijm=60 xiTi-l3244)住宿费用由下表可知住宿总费用为n=223元人民币从而旅馆名字住宿费入住时间成都广胜旅社402110九寨沟雅来旅社502015贵阳永逢旅社45200柳州云来旅社39230桂林平顺旅社49130我们可以得到目标函数为：Minmmm+m+n123=工为rxc+ijiji-1j-1工另(t+1)iijxi-1i-i+n24xKrx(ji-1j-1:+c)+60ij5.1.2约束条件：旅游景点约束强j-8r-8根据旅游线路使环形，即最终小张要回到新余因

13、此i-1i-1ij即表示小张旅游的景点数。因此旅游景点数约束为佥8r-8iji-1i-1时间条件由题目可知，小张如果在20：00至次日7：00之间在某地逗留小时则必住宿，为了节省开资，某地逗留时间t要小于6小时。01变量约束根据假设，整个旅游路线是环形，即最终代表们要回到新余，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题，当然前提是我们已经知道了要旅游所有的景点。因此，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为：工r=1工r二1（i，j=1，2，11）ijijij同样，当i，j2时，根据题意不

14、可能出现r二r二1，即不可能出ijji现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：ijji(i，j=2，3，11)5.1.3模型建立：综上所述，我们可以得到总的模型为Minmmm+m+n123i=1j=1rxcijij1xrx2iji=1j=1+c)ij约束条件：n=8)iji=1j=1盒8(t+1)iij60 xi=1i=1+n24工r=1iji工r=1ijjrxr=0ijji5.1.4模型求解与结果分析各景点逗留时间（小时）tt?tqttg44336453各景点价格（元）c1c2c3c4c5c6c7c7220100100180120100220120行

15、程表起点站终点站乘车类型车次起始时间到达时间景点停留时间票价新余武夷山火车K1681/kl6840:297:076小时63武夷山上饶火车200218:1420:35、18上饶温州火车2208/220523:016553小时57温州合肥火车K8492/K849322:001059、126合肥郑州火车2192/219323:45801、41郑州登封汽车、11:3211504小时18登封郑州汽车、17:301748、18郑州成都火车K290/K29121:391956、170成都九寨沟汽车、7:2012205小时63九寨沟成都汽车、8:0015:00、65成都广通火车K14515:407:46、12

16、5广通丽江东火车K9610/K961112:4217:563小时67丽江东昆明火车K9612/K960921:306:03、88昆明安顺火车K1106:3515523小时79安顺贵阳火车K1561:21142、16贵阳柳州火车K850/K85117:05140、35柳州桂林火车251422:400544小时14桂林宜春火车15580:4312394小时81宜春新余火车123618:431924、4.5从而根据模型，使用Lingo编程，得出结果如下表:问题二5.2.1目标函数的确立：此问与第一问大同小异，不同的是小张要花最少的时间游完全部的景点，而目标函数是求最少的时间。由第一问结论可知，总时间

17、为：t二佥8（txt）ijii=1j=1因此，该问题的目标函数为：Mint=乙乙(txt)iiji=1j=1模型建立：综上所述，我们可以得到的模型为Mint=工(txt)iiji=1j=15.2.3模型求解与结果分析：根据模型，使用Lingo编程，得出结果：行程表起点站终点站乘车类型车次起始时间到达时间景点停留时间新余宜春火车D205/D2089:109:364小时宜春武夷山火车K1681/K168423:447:076小时武夷山温州飞机MF808816:4517:253小时温州郑州飞机CZ368012:2514:10/郑州登封客车14:3015:354小时登封郑州客车20:1021:15/郑

18、州九寨沟飞机3U88583U860821:357:405小时九寨沟丽江飞机MU585214:3521:253小时丽江贵阳飞机MU596023:308:10/贵阳安顺火车T8881/T88848:309:063小时安顺贵阳火车K937015:0816:28/贵阳桂林飞机CZ3667/CZ395116:4523:104小时桂林新余火车K96014:052:42/住宿表及住宿费用入住宾馆时间地点名称价钱23:55束河古镇龙泉行政村文明而社丽江九域乡村束河客栈1360:00市中心-漓江风景区贵客0773酒店1335.3问题三5.3.1目标函数的确立此问在第一问的基础上改变约束条件，使小张的t旅游时间限

19、定在4天内，旅游的总费用限定在1500元，我们的做法同样是在满足相应的约束条件下，计算出在一定条件下最多游览的景点个数，得出几种方案，在根据实际情况选出最佳方案，这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择得出最后方案。时间约束游览的总时间由2部分组成，分别为在景点的逗留时间和第i个景点到第j个景点路途中所需时间从而我们可以得到函数为t=y11y11rxtijij+丄xyyrx(+1)2ijiji=1j=1i=1j=1费用约束游览的总费用由3部分组成，分别为交通总费用，住宿餐饮总费用和在旅游景点的花费。从而我们可以得到函数为mm+m+m+n123i=1j=1rxcijij

20、yy()xrxr+c丿ijiji=1j=1+60yy8(t+1)iijxi=ii=i+n2401变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束方程为r=r1ijijr=r1ijij(i,j=2,8)当i=1时，因为新余是出发点，所以工r=1并且工r=1；ij所以r=1并且r=1ijijj=1j=1i=1当j=1时,因为代表们最终要回到新余综合以上可知,r=r1ijijir=jijir=1jiji=1r=1ijj=1r2时，根据题意不可能出现r=r=1和r”=

21、r”=1，ijjiijji即不可能出现游客在两地见往返旅游,因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：rxr=0ijjirxr=0（i，j=2，3，8）ijji5.3.2模型建立：综上所述，我们可以得到总的模型为约束条件XXrxt厂ijij+1xXXrx(+1)962ijiji-1j-1i-1j-1+crxcrx+1x盒8(t.+1)xi_ii-i+n1500TOC o 1-5 h zijij2ijij24i-1j-1i-1j-1工r-Xr1ijijr”-Xr1(i,j=2,8)ijijij模型求解与结果分析：根据模型，使用Lingo编程，得出结果：行程起点站终点站乘车类型车次

22、起始时间到达时间景点停留时间票价新余宜春火车D205/D2089:109364小时4.5宜春武夷山火车K1681/K168423:447076小时63武夷山温州火车200218:1420353小时18温州合肥火车K8492/K849322:001059、126合肥郑州火车2192/219323:458014小时41郑州新余火车14377:201220100行程二起点站终点站乘车类型车次起始时间到达时间景点停留时间票价新余宜春火车D205/D2089:109:364小时4.5宜春桂林火车K1681/K168422:007:076小时63桂林贵州火车K158815:1420:35、18贵州安顺火车K849222:0010:593小时126安顺丽江火车K2175/K215623:458:013小时41丽江新余火车K143715:304:20160模型的评价、改进及推广6.1模型的评价本文思路清晰，模型恰当，得出的方案合理；本文成功的使用了01变量，使模型的建立和编程得以顺利进行；在解决实际问题中采用了合理简便算法，简化了模型的求解难度；问题中由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进行进一步的改进。6.2模型的改进与推广：实际情况中，在景点之间游玩可能还会受天气，交通堵塞和意外等因素影响，增加这些考虑