经济旅游线路优化设计-数学建模.doc

2009-2010学年第一学期数学建模论文论文题目经济旅游线路优化设计姓 名学 号班 级论文分数(教师填写)1、论文的创新点综合运用了列举法结合C语言解决TSP简单问题；程序运行环境 visual C+6.0;2、各成员的分工丰田 搜索材料和编程 陈曦 撰写一部分论文 徐俊 撰写一部分论文 3、各成员的贡献丰田 35%；陈曦 35%；徐俊 30%；4、论文的原创性声明本人郑重声明：所呈交的论文，是在论文小组成员讨论下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。论文如有抄袭嫌疑，后果由本人承担。 各成员签字： 日 期： 2010年1月8日 经济旅游线路优化设计摘要：对给定的数据进行旅游线路优化，设计出更经济的旅游线路。 针对问题：如何用简洁的方法解决TSP商旅问题； 运用列举法通过C语言编程将所有可能的路线所需费用计算出来，通过比较求出最经济的旅行路线。关键词：经济，列举法，C语言。1、 问题的提出现在有8个城市，已知两个城市之间的路费如下表，现在有一个人从A城市出发旅行，应该选择怎样的路线才能刚好每个城市都到达一次又回到A城市，其总路费最少？A B C D E F G HABCDEFG0 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.1条件的假设: 把该问题的每个解看作是一次“巡回”。在下述意义下，引入一些0-1整数变量：其目标只是使为最小。这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。 。2.2符号约定： 循环路线（i=1，2，n j=1,2,3，n）从一个城市到另一个城市所需的费用。（i=1，2，n j=1，2，3，n）：额外变量旅行完8个城市所需总路费3、问题分析 从A市出发选择合适的路线旅游每一个城市一次，使路费最少，其本质是一个TSP商旅问题。我们可以对已有的TSP商旅模型进行修改，通过编程将所有路线所需费用列举出来，找出最经济的路线。关于TSP旅行商问题：旅行商问题（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery1已证明TSP问题是NP难题，因此，VRP也属于NP难题。 旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。 TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。TSP旅行商问题常见算法：枚举法，蚁群算法，模拟退火柴法。4、模型的建立与求解由2.1所给的条件与假设可以建立一个模型：最小费用=它是一个指派问题的整数规划模型。为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有把这k个式子相加，有，矛盾！故假设不正确，结论（1）得证。下面证明（2），采用构造法。对于任意的总巡回，可取访问城市i的顺序数，取值范围为。因此，。下面来证明总巡回满足该约束条件。()总巡回上的边（）非总巡回上的边从而结论（2）得证。这样我们把此问题转化成了一个混合整数线性规划问题。我们通过用C语言编程得到编译结果的截屏图像结论：最佳路线A-G-E-F-C-B-H-D-A。5、模型的评价与改进5.1、模型的优点： 该模型构造简洁，易于理解，思路清楚。通过列举法与C语言的结合使解决该问题更为快速。考虑到了各种情况。为消费者提供了一个好方法。5.2、模型的推广： 该模型适合在旅行城市个数较少的时候推广。当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。附录：程序中的变量所带表的含义money88二维数组（用来存放城市之间旅行的路费）all10000一维数组（用来存放每一条旅行线路的费用）sta2B城市sta3C城市sta4D城市sta5E城市sta6F城市sta7G城市sta8H城市L2最佳线路的第2个城市L3最佳线路的第3个城市L4最佳线路的第4个城市L5最佳线路的第5个城市L6最佳线路的第6个城市L7最佳线路的第7个城市L8最佳线路的第8个城市min最佳线路所需费用xuhaoall数组中最佳线路所需费用的序号解决该模型的C语言程序：#include stdio.hvoid main ()Long int money88=0,56,35,21,51,60,43,39,56,0,21,57,78,70,64,49,35,21,0,36,68,0,70,60,21,57,36,0,51,61,65,26,51,78,68,51,0,13,45,62,60,70,0,61,13,0,53,26,43,64,70,65,45,53,0,50,39,49,60,26,62,26,50,0;Long int sta2,sta3,sta4,sta5,sta6,sta7,sta8,i=0,x=0,y=0,min=0,xuhao=0;long int all10000,l2,l3,l4,l5,l6,l7,l8;printf(all case:n);for(sta2=1;sta2=7;sta2+)for(sta3=1;sta3=7;sta3+)for(sta4=1;sta4=7;sta4+)for(sta5=1;sta5=7;sta5+)for(sta6=1;sta6=7;sta6+)for(sta7=1;sta7=7;sta7+)for(sta8=1;sta8=7;sta8+) if(sta3!=sta2&sta4!=sta3&sta4!=sta2&sta5!=sta4&sta5!=sta3&sta5!=sta2&sta6!=sta5&sta6!=sta4&sta6!=sta3&sta6!=sta2&sta7!=sta6&sta7!=sta5&sta7!=sta4&sta7!=sta3&sta7!=sta2&sta8!=sta7&sta8!=sta6&sta8!=sta5&sta8!=sta4&sta8!=sta3&sta8!=sta2) alli=s0sta2+ssta2sta3+ssta3sta4+ssta4sta5+ssta5sta6+ssta6sta7+ssta7sta8+ssta80;i+;if(i=4039)/此处的i是通过首先运行程序得到xuhao值后确定的/l2=sta2;l3=sta3;l4=sta4;l5=sta5;l6=sta6;l7=sta7;l8=sta8; for(x=0;xi;x+) printf(%5d,allx); if(x!=0&x%10=0)printf(n);pri