楚雄师范学院2011年数学建模培训第二次测试论文题目玩转云南之旅游路线优化模型姓名李雯刘正权叶万颂系（院）数学系专业信息与计算科学2011年5月15日一、摘要云南风光旖旎，四季如春，是旅游的天堂。
本论文就是以到云南旅游的交通方式以及路线选择为背景，通过构建模型。
实现以经济的方式玩转云南的各大旅游景点。
旅游的交通方式一般有自驾游览和乘坐公共交通工具两种方式。
本论文通过比较用公共交通出行方式下所有旅游路线的费用，得出最佳的旅游路线。
为了方便进行进行比较，文中引入了带权图和最小生成树的模型，为比较提供了可以参考的标准，模型中既要考虑路线最短，又要在规定的时间范围完成旅程,且通过预订旅游近点数最多，费用较少。
该模型以云南各大旅游景点为带权图的点，以采用交通方式来进行旅游过程中在具体的两个旅游景点的途中花去的费用为权值，这样，在该种旅游方式下的花费就是各对应的权值之和。
当然，选择了公共交通的旅游方式，可能走的旅游路线也不尽相同。
这样就产生了同一个旅游方式下的多条路线费用的比较，通过比较大小，就得到了较为经济的相应旅游方式下的最佳路线了。
本文作者充分调查了云南省目前的各种交通方式的收费情况，并查找了相关的旅游路线，有利地确保了论文的真实性和可靠性。
关键字：最小生成树、最佳路线、时间、路程。
二、问题某旅客携带着家人想到云南旅游观光，并且想玩遍云南的各大旅游景点。
请为这一行旅客设计旅游路线，并为他们提供一个合理的旅游交通方式的建议。
三、符号说明把各景点用数据代替如下：昆明市⑴楚雄市⑵大理市⑶丽江市⑷香格里拉⑸怒江⑹保山⑺德宏⑻临沧⑼普洱市⑽西双版纳⑾玉溪市⑿红河⒀文山市⒁石林⒂曲靖⒃昭通⒄权值表示景点之间的车票价四、模型建立1. 当两点之间没有直线连接时，应改进为使其两点的距离最短（两点之间可以经过若干个点）.2. 遇到两点直间不直接连接，如果由这两点组成的最短路径与后面有重复，必须把后面的路径中重复的部分删除。
⒃⒄⑿⒁⑾⑵⑶⑷⑸⑼ ⑺⑹⑻27 44253832581972611090 ⒀70 20130⑽ 251602020⑴ ⒂30 252530五、模型求解5.1 约束条件（1）时间和消费约束：不考虑旅游者在景点处的逗留时间和消费；（2）旅游方式约束：当景点之间需分路时，先去了某个景点，如果原路返回去另一个景点比较合适，则可以原路返回；（3）交通方式约束：为了旅游方便，尽量选择客车。
5.2模型求解从昆明出发，可选路线如下：(1)→(5) →（4）→（3）→（2）→（1）: W(T)=197+58+38+32+44=369 (1)→(2) →(3) →(4) → (5) →(1): W(T)=44+32+38+58+197=369 (1)→(2) →(3) →(4) →(6) →(5) →(1): W(T)= 44+32+38+58+197=369(1)→(2) →(3) →(7) →(6) →(5) →(1): W(T)= 44+32+26+25+30+197=354（1）→ (12) → ( 11 ) → (10 ) → (9) → ( 7) →（6）→（5）+(1)：W(T)=25+110+25+160+20+25+30+197=592(1) → ( 12) → ( 11) →（10）→（9）→（7）→（3）→（4）→（5）→(1)：W(T)= 25+110+25+160+20+26+38+58+197=659(1)→(5) →(6) →(7) →(9) →(10) →(11) →(12) →(1):W(T)=197+30+25+20+160+25+110+25+197=789(1)→ (5) → (6) → (7) → (9) → (10) → (11) → (12) →(13) → (14) →(16) →(1): W(T)=197+30+25+20+160+25+110+70+20+130+27+197=1011……由昆明出发，进行云南省内旅游，根据游客的喜好，可以有很多种不同的路线供选择。
但是，从消费者的角度看：a、选择途经最多的旅游景点，尽量不重复，节约开销；b.每个景点都要旅游，尽管有路线的重复；C、通过寻找最小生成树的方法，找到一条最优线路。
对已问题a：（1）→（5）→（6）→（4）→（3）→（7）→（9）→（10）→（11）→（12）→（13）→（14）→（16）→（1），相应权值之和为W(T)=197+30+25+38+26+20+160+25+110+70+20+130+27=878 因此，满足问题a的旅游线路如图a所示。
图a对于问题b ：⒃⑿⒁⑾⑶⑷⑸⑼ ⑺⑹273819726 110 ⒀70 20130⑽ 2516020⑴⒂2530路线为:(1) → (5) → (6) → (4) → (3) → (7) → (8) → (7) → (9) → (10) → (11) → (12) → (13) → (14 ) → (16) → (17) →（16）→（1）→（15）→（1）→（2）→（1）W(T)=197+30+25+38+26+20+20+20+150+25+110+70+20+130+90+90 +27+30+44+44=1206该无向图的可达矩阵为：1100000000000000011010000000000001001000000000000010011100000000000000011100000000000000011100000000000000011100000000000000011100000000000000011010000000000000001100000000000000111000100000000000001110000000000000011000100000000000101100000000000010011000000000000000001101100000000010011C ：通过寻找最小生成树的方法，找到一条最优线路。
W(T)=30+25+25+20+26+20+32+44+25+110+25+27+30+70+20+90=619综上所述：⒃⒄⑿⒁⑾⑵⑶⑷⑸⑼⑺⑹⑻27 44253226 11090⒀7020⑽ 252020⑴ ⒂30 252530五、模型推广该模型可以推广到解决用最节省的经费建立通信网络的实际问题上。
如：假设要在n个城市之间建立通信联络网，则联通n个城市需要n-1条线路，那么怎样才能用最节省的经费建立通信网络？注释：图中的①②③④⑤⑥为城市代号；图中两个城市代号之间的数字代表修通信网的经费比例。
上图经过模型变换后得到以下的模型：六、参考文献1、数学模型引论， E．A。
Bender著，朱尧辰、徐伟宣译，科学普及出版社(1982).2、数学模型，[门]近藤次郎著，官荣章等译，机械工业出版社，(1985)．3、微分方程模型，(应用数学模型丛书第1卷)，[美]W．F．Lucas 主编，朱煜民等译，国防科技大学出版社，(1988)．4、政治及有关模型，(应用数学模型丛书第2卷)，[美W．F．Lucas 主编，王国秋等译，国防科技大学出版社，(1996)．5、离散与系统模型，(应用数学模型丛书第3卷)，[美w．F．Lucas主编，成礼智等译，国防科技大学出版社，(1996)．附录Ⅰ•昆明景点石林，民族村，九乡风景区，金殿，大观公园，世界园艺博览园，腾冲火山国家公园，西山森林公园，岩泉风景区•红河景点建水燕子洞，朱家花园，弥勒白龙洞，焕文公园，元阳，建水古城，弥勒湖泉生态园，元阳梯田，红河学院，元阳风光•大理景点崇圣寺三塔，南诏风情岛，新华民族村，天镜阁，洱海公园，漾濞石门关，剑川满贤林景区，弥度县东山森林公园，大理古城，苍山•丽江景点玉龙雪山，丽江古城，束河古镇，玉水寨，文笔山景区，文海，泸沽湖，四方街，白水河•迪庆景点梅里雪山，硕都湖，霞给藏族文化村旅游景，天生桥温泉，纳帕海，民族服饰旅游展演中心，中甸藏经阁景点，博物馆，中甸，香格里拉•曲靖景点陆良彩色沙林，罗平多依河，珠江源，罗平，沾益海峰湿地，罗平油菜花海，九龙瀑布，南盘江，曲靖师范学院，爨宝子碑•楚雄景点武定狮子山，元谋土林旅游景区，太阳历公园，永仁方山景区，牟定化佛山，彝人古镇，元谋人遗址，紫溪山森林公园，禄丰恐龙博物馆，盘龙寺••西双版纳景点原始森林公园，傣族园，热带花卉园，中科院热带植物园，野象谷，勐景来旅游景区，民族风情园，曼听公园，猴山景区，打洛独树成林•怒江景点六库，三江并流，怒江大峡谷，丙中洛，贡山，三江并流风景区，秋那桶，怒江，碧罗雪山，兰坪罗古箐•保山景点腾冲热海国家重点风景...，腾冲和顺景区，龙陵邦腊掌度假区，腾冲叠水河景区，北庙湖公园，太保公园，冲云峰山景区，和顺侨乡，北海湿地，腾冲景区•昭通景点大关黄连河，水富县西部大峡谷温泉...，大山包，盐津豆沙关，观斗山石雕，僰[bó]人悬棺，盐津火车站，昭通机场，孟孝琚碑，彝良火车站•玉溪景点汇龙生态园，映月潭修闲文化中心通海秀山历史文化公园，通海秀山公园，华宁象鼻温泉度假村，易门龙泉森林公园，抚仙湖，红塔山，李家山青铜器，聂耳故居•思茅景点梅子湖公园，小黑江森林公园，墨江北回归线标志园，澜沧江，哀劳山，梅子湖，思茅机场，白塔，迁糯佛寺•临沧景点沧源崖画，云县漫湾百里长湖景区，西门公园，五老山国家森林公园，凤庆凤山公园，茶文化风景园，沧源佤山，临沧机场，广允缅寺•德宏景点瑞丽市莫里热带雨林景...，潞西市勐巴娜西珍奇园，南甸宣抚司署，瑞丽旅游淘宝场，潞西市勐巴娜西大花园，盈江凯棒亚湖景区，瑞丽，三仙洞，瑞丽姐勒佛塔•文山景点邱北普者黑风景区，砚山浴仙湖，富宁驮娘江景区，西华公园，麻栗坡烈士陵园，普者黑，麻栗坡老山，官寨附录Ⅱ最小生成树的实现代码如下：void MiniSpanTree_PRIM(MGraph G,VertexType u){struct{VerType adjvex;VRType lowcost;}closedge[MAX_VERTEX_MUM];K=LocateVex(G,u);for(j=0;j<G.vexnum;j++)if(j!=k) closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);closedge[k].lowcost=MIN{closedge[v].lowcost|closedge[i v].loiwcost>0,v∈V-U}iprintf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge<[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj}}}19。