2012暑假数学建模竞赛培训模拟题三

12012年南京理工大学数学建模竞赛承诺书我们仔细阅读了全国大学生数学建模的竞赛规则（）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛（报名）队号为：42（新编队号）题目：乘公交，看奥运参赛组别：本科组参赛队员(先打印,后签名,并留联系电话)：姓名（打印）签名(手写)联系电话队员1（队长）：队员2：队员3：22012年南京理工大学数学建模竞赛题目乘公交，看奥运摘要本文为解决赛题中的问题，通过C语言进行编程，建立了树状结构。对问题1，首先，我们建立了公交车和站台两个大的集合，公交车集合的因子是所停靠的站台，站台集合里面是在本站台停靠的公交车，经过对原始数据的处理，利用c语言实现建立这两个集合。在程序1中可以得到所有站台的停靠公交，根据初始站台，得到可以乘坐的第一班公交，再将其输入程序2，即可以得到所有直达的车站，并与终点站比较，若相同，则输出公交车编号，若不能直达，则输出所有直达站点，在返回程序1，得出可以乘坐的第二班车，再进入程序1，依次循环，直至到达终点站。对问题2，将换乘地铁站和公汽站视为对等的，与问题1相似，将地铁考虑进去，只要将最原始的公交和站台两个集合扩大，使其包含地铁路线和地铁站即可，思路相同，但是情况比问题1更复杂。此时，站点数、费用和时间的函数发生了变化。可将问题1的程序进行修改得到。对于问题3，由于标准是多重的，可以以时间、路程、换乘次数或总票价为主要考虑准则，因此模型更为复杂。关键词：树状结构C语言最优线路1一、问题的提出这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2二、问题分析在问题一中，仅考虑公共汽车的情况，要求在给出的任意两个车站之间选择最优的路径。公交线路是一个很庞大的系统，车站之间通过不同的线路连接。寻找最优线路的思路可以从始发站出发，寻找出通过该站点的若干条线路，再通过这些线路寻找到属于不同线路的下一站，然后不断重复车站——线路——车站——线路这样的寻找，直至寻至终点站。可以得到若干条可行路线，再根据不同的选择标准，作出最佳的路径。实施过程中，我们通过C语言编程，首先，我们建立了公交车和站台两个大的集合，公交车集合的因子是所停靠的站台，站台集合里面是在本站台停靠的公交车，经过对原始数据的处理，利用C语言实现建立这两个集合。在程序1中可以得到所有站台的停靠公交，根据初始站台，得到可以乘坐的第一班公交，再将其输入程序2，即可以得到所有直达的车站，并与终点站比较，若相同，则输出公交车编号，若不能直达，则输出所有直达站点，在返回程序1，得出可以乘坐的第二班车，再进入程序1，依次循环，直至到达终点站。本题所作程序，并不能实现数据的自动读入，必须通过人工把已知数据输入程序。在第二问中，要求在同时考虑公汽和地铁的情况下，解决始末站之间的路线选择问题。在可行路线的计算时，将换乘地铁站和公汽站视为对等的，与问题1相似，将地铁考虑进去，只要将最原始的公交和站台两个集合扩大，使其包含地铁路线和地铁站即可，思路相同，但是情况比问题1更复杂。此时，站点数、费用和时间的函数发生了变化。可将问题1的程序进行修改得到。但是在其后的最佳路线的选择中，因为地铁和公汽在票价、耗时等方面均有所不同，所以在规划最佳路线时，采用的参数也有所不同，只需要在第一问的程序基础上稍作修改即可。在第三问中，假设知道所有站点之间的步行时间，要求给出任意两个站点之间的路线选择结果。在可行路线的计算上，假设可以步行在任何两个站点之间移动，也可以通过公汽、地铁、步行三者的搭配到达目的地，因此计算非常复杂。我们认为这个模型应该给使用者提供多种标准下的路线选择方案：1、所需时间最短路线；2、花费最少路线；3、经过站点最少；4、换乘次数最少等。不同的标准只需在规划模型中设置不同的条件即可。3三、模型建立与模型求解（只考虑公汽的情形）1)基本假设:1、乘客到起始站可以直接选择公汽或地铁班次上车，即不记在起始站的等待时间。2、在实际过程中，对于公交（包括公汽与地铁）可能要换车2次以上，用户已无法容忍，视为无法到达。（因为如果他们之间换乘就使得费用增大了很多，这是人们不愿意看到的，且一般只坐地铁是无法到达终点站的，所以还要再换乘其他的工具，换乘次数太大我们也不再将其纳入考虑的范围）。3、相邻地铁站平均行驶时间(包括停站时间)：2.5分钟。4、相邻公汽站平均行驶时间(包括停站时间)：3分钟。5、公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)。6、地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)。7、地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)。8、公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)。9、公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价票价为：0～20站：1元；21～40站：2元；40站以上：3元。10、地铁票价：3元（无论地铁线路间是否换乘）。11、已知所有站点之间的步行时间。12、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。13、郊县和繁华地区公交车站的间隔大概一致。2)符号说明:1、Lxxx指公交线路，Sxxxx指公交站点，Tx指地铁线路，Dx指地铁站点。43）模型建立：流程图：建立公交车和站台两个大的集合输出起始站站台的停靠公交输入起始站输入到程序2得到所有直达的车站将直达车站与终点站比较相同输出公交车编号不相同5重要循环：1、循环检测各个Sxxx所对应的Lxxx，并输出：for(j=0;j6;j++)for(i=0;i4;i++)if(strstr(substr(total,pp[i],pp[i+1]),Station[j])!=0){strcpy(station[j],LOAD[i]);printf(S%04d:%s\n,j+1,station[j]);}2、检查线路中包含的站点与终点站是否匹配，是则输出yes：（以公交路线L231为例）for(i=0;i24;i++)printf(%s,L231[i]);printf(\n);for(i=0;i24;i++){if(strstr(L231[i],sq))printf(yes);}4）模型求解：1、由于本题的数据相当庞大，我们先试验了数据很少时代码1的效果：6这样可以得到每个站点对应的公交线路。2、在程序编译过程中我们遇到一个很大的问题，就是输入的线路信息过于庞大，无法读取。因而我们打算分开多次输入信息。以下是输入L231至L240的信息后起始站为S0001时的代码1输出结果：再将此结果输入到程序2中即可。7四、建模小结1、这道题目的数据量特别大，想要靠人力是无法完成的，必须借助软件来处理。由于先前没有处理过这类的问题，所以一开始就在这方面投入了大量的人力和时间，随着问题的一步步深入解决，我们学会了大批量的数据处理，这是本次最大的收获。2、在标准的选择上，我们选了换乘次数最少，当然也可以选其他，比如花钱最少等等，不同的标准得到的结果不一样。3、编程时采用树状发散的思想，由起点站出发找到终点站，但是程序实现并不简单，仍留下了一些问题有待解决。8参考文献：[1]2007高教社杯全国大学生数学建模竞赛题目[2]姜启源等，数学建模，第三版，2003年8月。[3]苏爱华，施法中，公交网络换乘问题的实现，工程图学学报，2005年第4期：55，59，2004.9附录附录1程序1#includestdio.h#includestdlib.h#includestring.h#includemalloc.hchar*substr(constchar*s,intn1,intn2)//从s中提取下标为n1~n2的字符组成一个新字符串，然后返回这个新串的首地址{char*sp=malloc(sizeof(char)*(n2-n1+2));inti,j=0;for(i=n1;i=n2;i++){sp[j++]=s[i];}sp[j]=0;returnsp;}main(){char*Station[6]={S0088,S0089,S0090,S0091,S0092,S0093};//包含Sxxx，应该要全部打进去的，这里只打了几个inti=0;//下面的这段是L231至L240的信息，因为要实现后面的循环，所以这里就烦了chartotal[10][1000]={S2867S0582S0577S1895S3648S0668S2978S0541S0153S1426S1427S0630S0854S0088S0609S0483S0604S2650S3693S1659S2962S0622S0456S0427,\S0871S0026S3546S3239S1315S3906S3680S2425S3416S2499S2459S2458S1470S1469S2843S0939S3920S2498,\S3406S2121S2122S3191S1064S1396S1381S1321S2019S2017S2159S2377S2482S1920S0641S2840S1402S2715S1454S2519S0301S0265S1140S1215S1218S2356S0725S2355S0647S2717S0643,\S0012S2636S0103S0104S0995S1318S0217S0737S0996S0994S1774S1808S3013S2651S0537S3060S0671S0074S0670S3705S2784S2276S2954S0531S0679S0125S0126S0216S0041S0040S0215,\S2390S0567S1258S1257S2200S1378S3043S3419S3678S0926S3641S3571S1158,\S2624S2008S1107S0012S2636S2113S2110S2153S3218S1573S1809S1173S0910S3517S0453S2424S1175S3728S1767S3729S0774S2346S2345S1252S0214S0458S1792S1783S1671S2948S2177S2157S0218S3623S3761S2952S1086S1857S1253S1176,\S0052S0051S0055S0029S2313S0268S3188S3657S2780S3700S3387S2944S1076S1559,\10S1828S1244S1671S2948S0218S3623S3761S2952S3229S1300S0533S3004S0786S3230S0791S1100S0373S037