数学建模获奖论文设计.doc

《数学建模获奖论文设计.doc》由会员分享，可在线阅读，更多相关《数学建模获奖论文设计.doc（11页珍藏版）》请在三一办公上搜索。

1、word走遍全中国摘要：随着社会的开展，人们生活水平不断提高，人们对生活质量的要求也不断提升，不单只满足于温饱问题，还向更高层次生活方面追求，从而旅游观光成为一种潮流。许多高职干部，退休后的员工以与普通家庭等人员都喜欢在假期，闲暇时出行旅游，看遍祖国大好河山，享受自然风光。然而国家线路密集的开展给出行人带来便利的同时，怎样选择经济省时的出行路线的问题也随之产生。针对这一问题，本文给出了相应方案和算法。第一问，按照地理位置经纬度，利用蚁群算法，编译相应的程序给出理论最短路径。第二问，从实际出发，在最短路径的根底上，设计出最经济的旅游路线，以坐火车最省原如此设计，即为省钱路线。第三问，将省钱和省时

2、与方便问题转化为行走线路次序与交通工具的选择问题，在综合考虑省钱、省时和方便时，本文将在最短路径的根底上，给出不同的简化实用模型，用临界调整法求最优值，建立数学模型，设计出省钱、省时、方便方案。省钱方案中，主要选乘火车，可以考虑转车，最后得出实际总费用= 11481元，利用评价准如此公式，得出理论最少费用= 9117.36元，实际与理论的差值 =-= 2363.64元；省时方案中，主要选乘飞机，在飞机须转站时，如此选用火车，最后得出实际总时间= 53时，利用评价准如此公式，得出理论最少时间=51时12分，实际与理论的差值= 1小时48分；在方便方案中，坚持只选择一种交通方式和不转车的原如此，适

3、当调整以达到最优，两种方案中，交通方式的交换次数各为次，转车次数各为次。第四问，对算法的复杂性，可行性和误差进展分析。第五问，针对旅行商问题，根据自己的理解，对算法作了相关分析并且结合实际问题对算法进展了讨论和评价。关键字：蚁群算法 实际与理论的差值 省钱 省时 方便一问题的提出周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、某某、澳门、台北。需要为他设计出行方案，现有如下问题：1按地理位置经纬度,如何设计最短路旅行方案。22010.5.1周先生从某某市出发，每个城市停留3天，可选择航空、铁路快车卧铺或动车，要求设计最经济的旅行互联网上订票方案。3.要求综合考虑省钱、省时又方便，设

4、定评价准如此，建立数学模型，修订你的方案。4要求对算法作复杂性、可行性与误差分析。5关于旅行商问题的提出，要求写出所采用的算法的理解与评价。二问题的初步分析与假设问题的初步分析：此题是网络组合运筹问题，主要是运用图论的方法和理论解决。但对于最短路径问题，应找到一个可行的算法，利用该算法求出理论最短路线。本论文开始将给出该算法，以实现按地理位置经纬度，设计出最短路径，该步是通过蚂蚁算法运用matlab软件来实现，运行得出满意解从而实现问题1的求解。应用第1问的最短路径设计出第2问要求的最经济的订票方案，即省钱方案。在综合考虑省钱、省时和方便时，本文将在最短路径的根底上，给出一个简化实用模型，用临

5、界调整法求最优值。问题2和3在简化实用模型中给出讨论，问题4和5将通过讨论说明得以解决。 根本假设：1. 在第一问按经纬度求最短路径时，不考虑交通工具。2. 无论何时购票都能买到。3. 不考虑路上消费和路上因意外耽误的时间。4. 不考虑火车票和飞机票打折。5. 假如在上午到达目的地，如此该天算入停留天数。6. 特快列车算入快车之内。三符号说明1. ：每段路程的总费用2. ：i=1,2,3分别表示飞机飞行每千米的价格，快车运行每千米的价格，动车运行每千米的价格3. ：i=1,2,3 分别表示乘飞机的总路程，快车的总路车，动车的总路程4. ：乘交通工具的总时间5. ：i=1,2,3分别表示飞机的速

6、度，快车的速度，动车的速度6. ：省钱方案城交通工具的实际总费用7. ：省时方案乘交通工具的实际总时间8. ：费用理论与实际的差值9 ：时间理论与实际的差值 10. ： 方便方案中换车次数四模型的建立1.第一问要求按地理位置经纬度找出最短路径，运用蚂蚁算法等编出matlab程序，蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。蚂蚁优化算法是一种随即搜索算法，它基于对自然界真实蚂蚁的集体觅食行为的研究，模拟真实的蚂蚁协作过程。应用程序输入各省会的坐标，用计算机给出满意的效果，运行得出最短路径见如下图 2.1.最经济方案即省钱方案，主要原如此是尽可能省钱，以最短路径为根底，做适当调整，按地图逆

7、时针行走，交通方式主要选择火车，查实际路线时，假如无火车、动车，如此可选择飞机，除乌鲁木齐某某，某某某某，某某某某，某某某某澳门某某，某某台北某某外，其他路径据可选择火车，具体路线见表2。设定线性函数作为评价准如此，在相互比拟中寻找一条省钱的方案。按最短路径向前行走，用函数评价 ，设该函数为=查资料得知：=5802km,=166181km,=2971,=0.8km/h, =0.23km/h, =0.22km/h, 带入理论值可得出理论最小值，即= 9117.36元，在实际方案中计算出实际总费用= 11481元 ，实际值与理论值坐差,即差值=-= 2363.64元。 在误差允许的X围内，理论值与

8、与实际值接接近，所以此方案可行。 表1 车次 发站-到站 全程时间 票价 T158/T155 某某某某2时25分107元T5302某某某某2时55分107元K266 转某某呼和浩特17时15分253元K598/K599 呼和浩特某某14时09分222元D2061 某某-某某1时18分70元K520/K521 某某某某9时43分170元K548/K545 某某-某某6时44分 137元K360/K361 某某-某某14时16分 197元K915 某某-某某8时40分 83元T197 某某-乌鲁木齐20时37分 390元T70中转T164/T165 乌鲁木齐-某某23时10分 248元K917 某

9、某-某某 1天10分 409元T24/T21(中转K113) 某某-某某2天13时53分471元K854 某某某某22时01分164元K652/K653 某某-某某4时25分 70元K9515/K9517 某某-某某10时14分 83元K139/K141/K144 某某-某某11时45分219元某某航空GS6522 某某-某某 45分 160元某某快运 UO196某某某某1时15分450元飞机某某澳门1时1000网上普遍价格南方航空 CZ634 澳门-某某2时30分1830元K648/K645 某某-某某7时50分116元G1022高速动车 某某-某某1时21分 175元立荣航空 B7178

10、某某-台北2时05分1170元某某航空 MF884 台北-某某1时20分2002元K666/K667 某某-某某9时58分 162元D96 某某-某某4时12分 199元D5654 某某-某某1时28分 54元D232 某某-某某2时19分 92元D5478/D5479 某某-某某 1时 48元K692/K693 某某-某某8时32分 162元K76/K77 某某-某某4时49分 106元K20 某某1时32分74元D25某某8时04分281元2. 省时方案的原如此是尽可能省时，以最短路径最为根底，因为按最短路径前进，同样可以保证总时间相对最短，具体时间只是因交通方式的选取不同而不同，此方案的

11、主要交通工具是飞机，在飞机需要转机等时间或没有航班时，可以选择动车或快车，具体乘坐方案可见表3。同时设定一个函数作为评价准如此，找出一条省时的方案。针对省时方案，在最短路径的根底上，按照总路径最短必然能相对保证总时间最省的思想，按最短路径向前行走，在每个点用函数评价，设该函数为 =查资料得知：=23357km,=859km,=1849，=600km/h,=180km/h,=251km/h,带入理论值得出理论最小值，即=51时12分,在实际方案中计算出实际用时= 53时，实际值与理论值坐差，即差值N= 1时48分。由此可见，在误差允许的X围内，理论值与实际值相差不大，说明此方案可行。表2车次 发

12、站到站运行时长票价某某航空FM9122某某1时35分343元东方航空MU5292某某1小时807元某某航空GS7419某某某某45分616元东方航空MU5580某某某某40分833元东方航空MU5468某某某某1小时441元某某航空FM2881某某-某某1小时222元东方航空MU2701某某某某1时18分896元东方航空MU2587某某某某40分821元某某航空 MF5506某某台北1时20分2314元南方航空 CZ3016台北某某2时30分1880元T275 特快列车某某-某某3时38分106元中国国航CA8231某某某某1时45分595元南方航空CZ3375某某某某55分206元南方航空

13、CZ3807某某澳门1时05分1288元飞机澳门某某1时142元某某快运 UO195某某某某1时05分790元南方航空CZ3342某某某某45分230元某某航空GS7519某某某某55分472元南方航空CZ3476某某某某50分405元D5101 详情 某某某某1时59分98元中国国航CA4411某某某某1时05分338元东方航空MU5837某某某某2时25分760元某某航空ZH9881某某某某2时50分2099元南方航空CZ6882某某乌鲁木齐2时25分805元祥鹏航空8L9924乌鲁木齐某某2时25分1256元K44B 某某某某8时7分131元南方航空CZ3710某某某某1时10分164元

14、G2004 某某某某2时25分暂无某某航空3U8880某某某某50分91元D2005某某某某1时13分70元祥鹏航空8L9945某某呼和浩特55分404元南方航空CZ6416呼和浩特某某1时25分811元D23某某某某2时01分93元D173某某某某1时46分76元3.方便方案：在最短路径的根底上，从只选取一种交通方式的角度来考虑，但有的省会之间达不到此要求，所以把换取交通方式的次数作为评价准如此。同时还要满足不能转车的条件，即坐车后直接到达目的地，所以中途转车与否，也成为一条重要的评价准如此。依据这两条评价准如此，在最短路径的根底上，模拟出路线，最终得到的两种方便的方案。方案三中，交通工具换

15、取4次，即=4,转车次数为。方案四中，交通工具换取4次，即=4, 转车次数为。因换交通方式次数较少，所以，此方案可行。具体路径见表3和4 表3车次 发站到站运行时长票价某某航空FM9122某某1时35分343元东方航空MU5292某某1时807元某某航空GS7419某某某某45分616元东方航空MU5580某某某某40分833元东方航空MU5468某某某某1时441元某某航空FM2881某某-某某1时222元东方航空MU2701某某某某1时18分896元东方航空MU2587某某某某40分821元某某航空 MF5506某某台北1时20分2314元南方航空 CZ3016台北某某2时30分1880元

16、T275 特快列车某某-某某3时38分106元中国国航CA8231某某某某1时45分595元南方航空CZ3375某某某某55分206元南方航空 CZ3807某某澳门1时05分1288元飞机澳门某某1时142元某某快运 UO195某某某某1时05分790元南方航空CZ3342某某某某45分230元某某航空GS7519某某某某55分472元南方航空CZ3476某某某某50分405元D5101 详情 某某某某1时59分98元中国国航CA4411某某某某1时05分338元东方航空MU5837某某某某2时25分760元某某航空ZH9881某某某某2时50分2099元南方航空CZ6882某某乌鲁木齐2时2

17、5分805元祥鹏航空8L9924乌鲁木齐某某2时25分1256元K44B 某某某某8时7分131元K1087/K1086 某某某某14时32分197元G2004 高速动车某某某某2时25分暂无K472/K473 某某某某6时40分118元D2005某某某某1时13分70元祥鹏航空8L9945某某呼和浩特55分404元南方航空CZ6416呼和浩特某某1时25分811元D23某某某某2时01分93元D173某某某某1时46分76元表4 车次 发站-到站 全程时间 票价 T158/T155 某某2时25分107元K710/K711 -呼和浩特10时15分170元K598/K599 呼和浩特某某14时

18、09分222元D2061 某某-某某1时18分70元K520/K521 某某某某9时43分 170元K548/K545 某某-某某6时44分 137元K360/K361 某某-某某14时16分 197元K915 某某-某某8时40分 83元K594/K595 某某-乌鲁木齐1天11分 390元 南方航空CZ3630 乌鲁木齐-某某2时05分 531元K917 某某-某某1天10分 409元 东方航空MU5838 某某-某某3时05分 1271元K854 某某某某22时01分 164元K652/K653 某某-某某4时25分 70元K9515/K9517 某某-某某10时14分 83元 K139

19、/K141/K144 某某-某某11时45分 219元 某某航空GS6522 某某-某某45分 160元中国国航 某某-澳门 1时35分 1740元飞机 澳门-某某 暂无 1000元网上普遍价格 南方航空 CZ634 某某-某某40分钟510元K648/K645 某某-某某7时50分116元 G1022高速动车 某某南-某某1时21分175元立荣航空 B7178 某某-台北2时05分 1170元某某航空 MF884 台北-某某1时20分暂无K666/K667 某某-某某 9时48分 162元D96 某某-某某4时12分 199元D5654 某某-某某1时28分54元D232 某某-某某2时19

20、分92元 D5478/D5479 某某-某某1小时48元K692/K693 某某-某某8时32分 162元K76/K77 某某-某某4时49分 106元D177某某某某4时30分 213元D173 某某-某某2时19分 93元K339 某某-某某2时36分95元五、算法复杂性、可行性与误差分析 算法复杂度可以从时间复杂度和空间复杂度来考虑，算法程序的运行需要一定的时间，同时，程序占有一定量的内存空间；在算法的执行中，通过每次不同的小循环，得出不同的闭合路径，然而最后得出同一条路径，符合算法的迭加性，因此算法的可行性得以实现；在每次不同的循环中，因路径选取的不同，所以存在一定的误差。六 算法的理

21、解与评价针对旅行商问题，算法可以做以下解释：第一问通过蚂蚁算法得出最短路径，设计每种方案时都按最短路径行走，但在实际应用时，要考虑站点之间的实际情况，保证两地可以直接到达，假如不能直接到达，如此需调整路径，尽可能做到省钱或省时，譬如在方案一中，由于某某到乌鲁木齐，乌鲁木齐到某某，没有直达的车，可将原路线改为某某乌鲁木齐某某某某，这样可以少坐一趟飞机，且飞机不用转机，做到了省钱，方案二、三、四中也对路线做了适当调整，达到了方案设计的目的。旅行商或是游客可以根据自身需求选择不同的方案，在全部调整恰当后，进展行走，从而在实际允许的前提下，实现路径最短，从而旅行商问题得以真正实现！本文中给出的几个方案是可以推广到实际应用的。七参考文献1.数值分析第四版 李清扬 王能超 易大义 编 华中科技大学2.图论第二版 王树禾 编 科学3. 论文一种基于蚁群算法的TSP问题分段求解 吴斌 史忠植4数学建模竞赛 赫孝良 戴永红 周义仓 编 某某交通大学11 / 11