数学建模答辩

ﻪﻪ乘公交，看奥运问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的探索　　为了迎接08年奥运会北京的公交线路已达800条以上,为满足公众查询公交线路的选择问题,因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性,我们没有采用常规的Ｄiｊkstrａ算法,而采用了高效的广度优先算法　针对问题一(只考虑公汽系统),我们建立了模型一并通过ＶC+＋编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值模型二是根据问题二（同时考虑公汽和地铁系统）建立的,同样用VC++编程得到所求站点间的最优路线　　对问题三(将步行考虑在内）我们建立了模型三的优化模型，然后在模型改进里又建立了图论模型。摘要主要内容一、模型假设二、问题的理解与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 三、模型的建立与求解四、模型的评价与改进一、模型假设1、相邻公汽站平均行驶时间(包括停站时间):3分钟2、相邻地铁站平均行驶时间（包括停站时间):2．5分钟3、公汽换乘公汽平均耗时：5分钟(其中步行2分钟)4、地铁换乘地铁平均耗时:4分钟(其中步行分钟)5、地铁换乘公汽平均耗时:７分钟(其中步行4分钟)６、公汽换乘地铁平均耗时:6分钟(其中步行分钟）７、公汽票价:0～２0站：1元；21～4０站:2元40站以上：3元;8、地铁票价:3元9、查询者转乘公交的次数不超过两次；10、所有环行公交、地铁线Ｔ2线路都是双向的；1１、公交、列车均到站停车且都运行正常,不会发生堵车现象;对于路线的评价，我们可以分别以总时间，总转乘次数，总费用为指标,也可以将三种指标 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化后赋以不同权值形成一个综合指标。二、问题的理解与分析本问题可归结为一个求最短路径的问题,但是传统的Dｉjkstｒa最短路径算法并不适用于本问题，为此我们采用了效率较高广度优先算法，其基本思路是每次搜索指定点,并将其所有未访问过的近邻点加入搜索队列，循环搜索过程直到队列为空三、模型的建立与求解问题一：　　考虑到实际情况,转乘次数以不超过２次为佳,因此找出了任意两个公汽站点间的可行路线,就可以对这些路线按不同需求进行选择,找出最优路线了模型一建立:１）以时间最短作为最优路线的模型：行程时间等于乘车时间与转车时间之和。　　　　　　　　　　　　　　　　　　　　　　　　　　　其中，第k路线是以上转乘路线中的一种或几种。3）以费用最少作为最优路线的模型:其中2)以转乘次数最少作为最优路线的模型:此模型等效为以上转乘路线按直达、转乘一次、两次的优先次序来考虑(１）首先输入需要查询的两个站点(起始站，为终点站）；我们采用广度优先算法找出任意两个站点间的可行路线，然后搜索出最优路线。现将此算法运用到该问题中，如下图:其中(ａ）、（ｂ)、（c)图分别表示了从点到点直达、转乘一次、转乘两次的情况)图6.2　公交直达、转乘图模型一的求解:(2）搜索出经过起始站的公交线路和经过终点站的公交　　　线路存入数据文件；判断是与是否存在相同路线，若有则该路线是换乘次数最少（的路线,若有多条直达路线,则可以在此基础上找出时间最省的路线；这样可以找出所有直达路线（３）找出经过的起始站公交线路中的另一站点和经过终点站的公交线路中的另一站点。判断其中是否存在相同的点（４）再搜索出经过起始站线路上除了站点的另一站点的公汽线路找出公汽线路上的其他站点;判断，如果与经过的公汽线路中的其他站点存在相同的点则与间有二次换乘的路线（5）对上述存储的经过两个站点与的不同路线,根据不同模型进行最优路线进行搜索，得出查询者满意的最优路线。起始站耗时最少(miｎ)最优路线(条）S3359→Ｓ１82８６428S１557→S０４811062S０９7１→　S０4851062S0008→　S0０736７2S0148→　Ｓ０48106３S00８７→S３6７4612最后根据以上算法和前面建立的模型一,用ＶＣ＋＋进行编程就可以得出不同目标下的最优路线模型一的结果１)以耗时最少的最优路线表起始站公汽线路中转站公汽线路终到站耗时所需费用S3359L0９５６S1784Ｌ0６87Ｓ182810１3S33５9Ｌ0９56Ｓ1７84L0737S１8281０１3Ｓ0９71Ｌ０533Ｓ21８4L09３7S048５1２8３S0０08L0６7９S0291Ｌ0578S0073832S０008L0６7９S0４91L05７8Ｓ0０73８32Ｓ00０8L0679Ｓ25５９L05７8Ｓ007383２S0008Ｌ06７９S2６83L０578Ｓ00７3８32Ｓ0００8L0６７9S3614L0５78Ｓ0073832S00０8Ｌ0８7５S２263L03４５S007３832Ｓ0008L087５S２３０３L034５S0073８３2Ｓ0008L０875Ｓ391７L034５S0073８32S00０8Ｌ０９83S2083Ｌ０0５7Ｓ0０73832２）转乘次数最少的最优路线表3)以费用最少为目标的最优路线起始站费用（元)路线(条)备注S3359→S1828３3０2８条路线需64　miｎ,转乘２次，另两条路线需1０１ｍin，转乘１次Ｓ1557→S0481３2所需时间为１06ｍｉn,转乘2次；Ｓ0971→　S048533两条路线需106min，转乘2次，另一条需128miｎ,转乘1次S00０8→　Ｓ0０7329所需时间为８３　miｎ,转乘1次S0148　→S048３3所需时间为１06min,转乘２次Ｓ0087　→S367312所需时间为46　ｍｉn,转乘2次　将公汽与地铁同时考虑，找出最优路线。对于地铁路，也可以将其作为公交线路，本质上没有什么区别,只是参数不一样。因此地铁站可等效为公交站，地铁和公交的转乘站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相同模型二建立:1)以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公交（公汽和地铁)时间与公汽与地铁换乘、公汽间、地铁间换乘时间之和其中,第k路线为同时考虑公汽与地铁的转乘路线中的一种或几种问题二２）以转乘次数最少的路线作为最优路线的模型:此模型等效为以上转乘路线按直达、转乘一次、两次(包括公交与地铁间的转乘)的优先次序来考虑。3)以费用最少的路线作为最优路线的模型:可行路线的费用为乘公交和地铁费用的总和。其中仍满足模型一的约束条件　　由题可知,问题一是问题二解的一部分在问题二中,新产生的最优解主要源于在通过换乘地铁、换乘附近相近站点的路线上，如图：模型二的求解从点A到Ｂ,图(ａ)表示的是通过两公交线路上相邻公汽站S１,S2进行一次转乘;图(b）表示利用地铁站进行二次转乘;图(c)表示利用另一条公汽路线为中介进行二次转乘。图6.3T1与Ｔ2铁路位置关系图铁路线路引入给题目的求解增加了难度,为了形象了解为数不多的两条铁路间的交叉关系，我们通过matlab编程作出了两条铁路的位置关系图,如图所示，图中的直线表示T1铁路线,圆表示T2铁路线,数值表示站点同样将地铁线路等效为公交线路得出任意两个站点间的可行线路再将目标函数分别用模型二建立的模型表达式表达，用VC++进行编程求得出考虑地铁情况的最优路线1)以转乘次数最少为目标的最优路线模型二的 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 起始站转乘次数路线（条）S3３59→S1８2811S１５57→S0481０1Ｓ097１→S048521０S0０0８→Ｓ0０７３２２0S01４8→S0４８217Ｓ０0８７→S3６72２2)以耗时最少为目标的最优路线起始站耗时(mｉn)）路线(条）Ｓ３359→S1８2８642８S15５７　→　S０48１1０９17S0971→S0485９６３Ｓ0０08→　Ｓ0０７3５53S０148→S0４８87.５1０Ｓ0087→S36733１3）最少费用的最优路线起始站费用（元）路线（条)S33５9→S182832S15５7→S04８1３17S0９7１→Ｓ0485５1S０00８　→S0０73210S0148→S０48５1S０08７→S3６7210将步行方式考虑在了出行方式当中,更符合实际。因为当出发点与换乘点、终点站或转乘站与转乘站之间只相隔几个站时，当然该段选择步行方式更优。因此作出如下假设:一、如果存在某段路线，其两端点站之间相隔站点数小等于２（即至多经过4个站点）,则该段线路选择步行方式到达目的地。其他的情况用模型二来处理。二、相邻公交站点(包括地铁站)间平均步行时间为5分钟。三、如果在公汽线路上选择步行,则公汽间换乘次数减少1;如果在地铁线路上选择步行，则地铁间换乘次数减少１,直达线路除外。直达和转乘一次、两次的路线需要步行的路段示意图如图6.5所示。问题三图中（a)表示出发点A与终点站B间能直达;图中(b)表示出发点A与终点站B间通过一次换乘能到达,其中路段AＣ的站点数等于2所以选择步行,同样CB路段的站点数小等于２,则也采取步行的方式;是否选择步行方式的函数:　图6.5　步行示意图对于直达路线，如果出发点与终点站之间相隔站点数小等于4则步行,否则乘车。对于需要转乘的路线的最优路线模型讨论如下：1)以时间最短的路线作为最优路线的模型:路线总时间等于乘车时间加上步行时间,再加上转乘时间模型三建立:3）以费用最少的路线作为最优路线的模型:其中　　　　仍满足模型一的约束条件，2）以转乘次数最少的路线作为最优路线的模型:每步行一次就少换乘一次车　模型三的求解与一二相同,在此就不再细说三、模型的评价与改进（一）模型的优点：1、模型是由简单到复杂一步步建立的，使得更贴近实际。2、本文的模型简单,其算法直观,容易编程实现。３、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。4、本文模型注重效率的提高,通过大量的特征信息的提取,并结合有效的算法,使其完全可以满足实时系统的要求。(二)模型的缺点:在建模与编程过程中，使用的数据只是现实数据的一种近似,因而得出的结果可能与现实情况有一定的差距。（三)模型改进　　以上模型主要是从公交线路出发,寻找公交线路的交叉站作为换站点。我们也可以从公交站点的角度出发,用图论的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 建立有向赋权图如图所示1）当以时间最短为目标时，给每条边赋上时间的权值。当某段线路的两段点间间隔站点数小等于3时,选择步行，该线路的权值等于步行时间。不同公汽和地铁间进行换乘时需要赋给不同的权值,以表示换乘时间找出任意两点间可行路线的路径长度后,再搜索出其中的最短路径的的可行路线作为时间的最优路线２)当以费用最省为目标时,则给每条边赋上费用的权值。公汽站点间的边权赋值。同样可以找出任意两点间可行路线的路径长度，然后再搜索出最短路径作为费用的最优路线　　从公交站点出发，将公交站点作为网络图中顶点，得出公交的拓扑结构,进而寻求不同目标下的最短路径，为我们提供了另外一种思路。但是从以上图形的结构，我们已经看得出其复杂程度是不可预知的，尤其随着数据的增多,图的复杂度随之上升。如果不寻求一个好的算法,而用常规的Dijｋstra算法，将有可能在可以忍受的时间范围内得不出有效结果。　经过参考相关资料，我们发现用蚂蚁算法可能比较有效。该算法利用了蚂蚁寻食出行路径选择的行为特点,通过线路激素强度的更新机制