路线设计课程设计.doc

课程数学建模课程设计题目路线设计序号7主要内容现在有8个城市，已知两个城市之间的路费如下表，现在有一个人从A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市，其总路费最少？A B C D E F G HABCDEFG 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 - 70 60 51 61 65 26 13 45 62 53 26 50要求1利用已学数学方法和计算机知识进行数学建模 2必须熟悉设计的各项内容和要求，明确课程设计的目的方法和步骤。3设计中必须努力认真，独立地按质按量地完成每一阶段的设计任务。4设计中绝对禁止抄袭他人的设计成果。5每人在设计中必须遵守各组规定的统一设计时间及有关纪律。6所设计的程序必须满足实际使用要求，编译出可执行的程序。7要求程序结构简单，功能齐全，使用方便。工作计划及进度提前一周：分组、选题；明确需求分析、组内分工；第一天：与指导老师讨论，确定需求、分工，并开始设计； 第二四天：建立模型并求解；第五天：完成设计说明书，答辩；第六天：针对答辩意见修改设计说明书，打印、上交。指导教师签字 张逵 刘巍 2011年5月6日教研室审定意见同意实施签字 栾悉道 2011年 5 月 6 日目录第一章 课程设计的名称、目的、任务及要求11.1课程设计的名称11.2课程设计的目的11.3课程设计的任务11.4课程设计的要求1第二章 问题分析22.1 问题重述22.2 问题背景22.3 问题分析2第三章 基本假设与符号约定33.1条件假设33.2 符号约定3第四章 模型的建立与求解44.1旅行商问题的基本理论44.2 模型建立44.3 模型求解5第五章 模型的结果与检验115.1 模型结果115.2 模型检验115.3模型的评价11结论12参考文献13结束语14第一章 课程设计的名称、目的、任务及要求1.1课程设计的名称 路线设计1.2课程设计的目的1、巩固数学建模课程基本知识，培养运用数学建模理论知识和技能分析实际应用问题的能力；2、初步掌握数学建模的基本流程，培养科学务实的作风和团体协作精神；3、培养调查研究、查阅技术文献、资料、手册以及撰写科技论文的能力。1.3课程设计的任务1、针对具体问题进行问题分析。2、基本假设与符号约定。3、模型建立：根据具体问题建立数学模型(可以是数学式子、图、表、算法步骤等)。4、模型求解：运用linggo软件求解模型。5、模型结果与检验：根据求解出的结果进行模型检验。6、模型评价。7、参考文献1.4课程设计的要求1利用已学数学方法和计算机知识进行数学建模 2必须熟悉设计的各项内容和要求，明确课程设计的目的方法和步骤。3设计中必须努力认真，独立地按质按量地完成每一阶段的设计任务。4设计中绝对禁止抄袭他人的设计成果。5每人在设计中必须遵守各组规定的统一设计时间及有关纪律。6所设计的程序必须满足实际使用要求，编译出可执行的程序。7要求程序结构简单，功能齐全，使用方便。第二章 问题分析2.1 问题重述 现在有8个城市，已知两个城市之间的路费如下表，现在有一个人从A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市，其总路费最少？A B C D E F G HABCDEFG 56 35 21 51 60 43 39 21 57 78 70 64 49 36 68 - 70 60 51 61 65 26 13 45 62 53 26 502.2 问题背景根据对题目的理解我们可以知道，旅游的费用只考虑路费的情况下，而在确定了要游览的景点的个数并且已只出发的城市，所以我们的目标就是在满足从某城市出发，恰好游览每一个城市最后回到出发城市的情况下，求出路费的最小值。2.3 问题分析题目中给出了8个城市间的所需路费，要求我们为周游设计一条最优的旅行路线，即从驻地出发，经过每个城市恰好一次。由此可知，此问题是属于旅行商问题，我们可以考虑运用改良圈算法求解此问题。按所给各城市的顺序编号1，2，38，我们可以考虑以任意两城市之间的最路费为权重，以1城市为出发点，利用改良圈算法得到的最优圈未必是最优解，所以我们将利用linggo软件编程重复进行改良圈算法，将会得到最优圈，从而保证最优解，即最优的旅行路线。用终点返回起点构成的闭合回路为最优路线。这样就设计出一条最优的旅游线路。第三章 基本假设与符号约定3.1条件假设（1）假设在旅途中不考虑突发事件干扰行程；（2）假设不考虑路费打折情况。3.2 符号约定i,j，k: 表示A，B，C，D，E，F，G，H八个城市；1=i=8, 1=j=8，1=k= U(k) + x (k, j) - (n - 2) * (1 - x( k, j) + (n - 3) * x(j,k););for(link: bin(x);for(stops(k)|k #GT# 1: U(k) = 1 + (n - 2) * x(k, 1);End执行，运行结果如下： Global optimal solution found. Objective value: 251.0000 Extended solver steps: 0 Total solver iterations: 63 Variable Value Reduced Cost N 8.000000 0.000000 U( 1) 0.000000 0.000000 U( 2) 6.000000 0.000000 U( 3) 7.000000 0.000000 U( 4) 1.000000 0.000000 U( 5) 4.000000 0.000000 U( 6) 3.000000 0.000000 U( 7) 5.000000 0.000000 U( 8) 2.000000 0.000000 D( 1, 1) 0.000000 0.000000 D( 1, 2) 56.00000 0.000000 D( 1, 3) 35.00000 0.000000 D( 1, 4) 21.00000 0.000000 D( 1, 5) 51.00000 0.000000 D( 1, 6) 60.00000 0.000000 D( 1, 7) 43.00000 0.000000 D( 1, 8) 39.00000 0.000000 D( 2, 1) 56.00000 0.000000 D( 2, 2) 0.000000 0.000000 D( 2, 3) 21.00000 0.000000 D( 2, 4) 57.00000 0.000000 D( 2, 5) 78.00000 0.000000 D( 2, 6) 70.00000 0.000000 D( 2, 7) 64.00000 0.000000 D( 2, 8) 49.00000 0.000000 D( 3, 1) 35.00000 0.000000 D( 3, 2) 21.00000 0.000000 D( 3, 3) 0.000000 0.000000 D( 3, 4) 36.00000 0.000000 D( 3, 5) 68.00000 0.000000 D( 3, 6) 99.00000 0.000000 D( 3, 7) 70.00000 0.000000 D( 3, 8) 60.00000 0.000000 D( 4, 1) 21.00000 0.000000 D( 4, 2) 57.00000 0.000000 D( 4, 3) 36.00000 0.000000 D( 4, 4) 0.000000 0.000000 D( 4, 5) 51.00000 0.000000 D( 4, 6) 61.00000 0.000000 D( 4, 7) 65.00000 0.000000 D( 4, 8) 26.00000 0.000000 D( 5, 1) 51.00000 0.000000 D( 5, 2) 78.00000 0.000000 D( 5, 3) 68.00000 0.000000 D( 5, 4) 51.00000 0.000000 D( 5, 5) 0.000000 0.000000 D( 5, 6) 13.00000 0.000000 D( 5, 7) 45.00000 0.000000 D( 5, 8) 62.00000 0.000000 D( 6, 1) 60.00000 0.000000 D( 6, 2) 70.00000 0.000000 D( 6, 3) 99.00000 0.000000 D( 6, 4) 61.00000 0.000000 D( 6, 5) 13.00000 0.000000 D( 6, 6) 0.000000 0.000000 D( 6, 7) 53.00000 0.000000 D( 6, 8) 26.00000 0.000000 D( 7, 1) 43.00000 0.000000 D( 7, 2) 64.00000 0.000000 D( 7, 3) 70.00000 0.000000 D( 7, 4) 65.00000 0.000000 D( 7, 5) 45.00000 0.000000 D( 7, 6) 53.00000 0.000000 D( 7, 7) 0.000000 0.000000 D( 7, 8) 50.00000 0.000000 D( 8, 1) 39.00000 0.000000 D( 8, 2) 49.00000 0.000000 D( 8, 3) 60.00000 0.000000 D( 8, 4) 26.00000 0.000000 D( 8, 5) 62.00000 0.000000 D( 8, 6) 26.00000 0.000000 D( 8, 7) 50.00000 0.000000 D( 8, 8) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 56.00000 X( 1, 3) 0.000000 35.00000 X( 1, 4) 1.000000 21.00000 X( 1, 5) 0.000000 51.00000 X( 1, 6) 0.000000 60.00000 X( 1, 7) 0.000000 43.00000 X( 1, 8) 0.000000 39.00000 X( 2, 1) 0.000000 56.00000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 1.000000 21.00000 X( 2, 4) 0.000000 57.00000 X( 2, 5) 0.000000 78.00000 X( 2, 6) 0.000000 70.00000 X( 2, 7) 0.000000 64.00000 X( 2, 8) 0.000000 49.00000 X( 3, 1) 1.000000 35.00000 X( 3, 2) 0.000000 21.00000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 36.00000 X( 3, 5) 0.000000 68.00000 X( 3, 6) 0.000000 99.00000 X( 3, 7) 0.000000 70.00000 X( 3, 8) 0.000000 60.00000 X( 4, 1) 0.000000 21.00000 X( 4, 2) 0.000000 57.00000 X( 4, 3) 0.000000 36.00000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 51.00000 X( 4, 6) 0.000000 61.00000 X( 4, 7) 0.000000 65.00000 X( 4, 8) 1.000000 26.00000 X( 5, 1) 0.000000 51.00000 X( 5, 2) 0.000000 78.00000 X( 5, 3) 0.000000 68.00000 X( 5, 4) 0.000000 51.00000 X( 5, 5) 0.000000 0.000000 X( 5, 6) 0.000000 13.00000 X( 5, 7) 1.000000 45.00000 X( 5, 8) 0.000000 62.00000 X( 6, 1) 0.000000 60.00000 X( 6, 2) 0.000000 70.00000 X( 6, 3) 0.000000 99.00000 X( 6, 4) 0.000000 61.00000 X( 6, 5) 1.000000 13.00000 X( 6, 6) 0.000000 0.000000 X( 6, 7) 0.000000 53.00000 X( 6, 8) 0.000000 26.00000 X( 7, 1) 0.000000 43.00000 X( 7, 2) 1.000000 64.00000 X( 7, 3) 0.000000 70.00000 X( 7, 4) 0.000000 65.00000 X( 7, 5) 0.000000 45.00000 X( 7, 6) 0.000000 53.00000 X( 7, 7) 0.000000 0.000000 X( 7, 8) 0.000000 50.00000 X( 8, 1) 0.000000 39.00000 X( 8, 2) 0.000000 49.00000 X( 8, 3) 0.000000 60.00000 X( 8, 4) 0.000000 26.00000 X( 8, 5) 0.000000 62.00000 X( 8, 6) 1.000000 26.00000 X( 8, 7) 0.000000 50.00000 X( 8, 8) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 251.0000 -1.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 12.00000 0.000000 6 8.000000 0.000000 7 0.000000 0.000000 8 10.00000 0.000000 9 9.000000 0.000000 10 11.00000 0.000000 11 8.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 1.000000 0.000000 16 4.000000 0.000000 17 3.000000 0.000000 18 0.000000 0.000000 19 2.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 3.000000 0.000000 25 2.000000 0.000000 26 4.000000 0.000000 27 1.000000 0.000000 28 0.000000 0.000000 29 0.000000 0.000000根据lingo的运行结果，我们可以得知最优旅行方案为：A-D-H-F-E-G-B-C-A最少总花费为：Min=251。如图所示： 第五章 模型的结果与检验5.1 模型结果由模型求解我们最终可知：在满足从A城市出发旅行，恰好每个城市都到达一次又回到A城市，其总路费最少的前提下，最优旅行路线为：A-D-H-F-E-G-B-C-A最少路费为：Min=2515.2 模型检验在问题的求解过程中，为了使问题简捷易求解，我们进行了适当的假设，建立了模型。通过求解使得由A城市出发每个城市都恰好经过一次并不重复，最后又回到A城市，并且总路费最少。我们利用手工建立模型，找出了最合理的一种方案为：由城市A出发依次经过城市D、城市H、城市F、城市E、城市G、城市B、城市C最后回到城市A。这个方案不仅满足题目要求，并且使得总花费最少为Min=21+26+26+13+45+64+21+35=251。因为模型结果符合检验结果，所以这个模型的建立于求解是成功的。5.3模型的评价1.本文思路清晰，模型恰当，得出的方案合理； 2.本文成功的使用了01变量，使模型的建立和编程得以顺利进行；3.采用了最短路径算法，简化了模型的求解难度；结论在这个题目模型的建立过程中，由于本人和搭档在知识和经验方面都存在着不足，另外，在整个建模的过程中，时间也比较仓促。因此，该模型必然会存在一些缺陷和不足。因为具体的旅行要考虑问题多之又多，旅行的整个流程我们也不熟悉，在问题分析时很难做到完全满足旅行者实际的需求。尽管该模型存在诸多的不足，但我与我的搭档依然认真查找最短回路以及Hamilton 圈的相关资料和学习建模需要的软件lingo的使用语法以及格式，认真、仔细的完成了此次题