数学建模《最廉价飞机线路的选择》

最廉价飞机线路的选择摘要：改革开发以来，我国的经济发展迅速，人民生活水平逐渐提高，2010年，我国GDP超越日本，排名世界第二。我国经济的发展，使人们对交通运输提出越来越多的需求，而民航作为航空运输工具，在交通工具中起到十分重要的作用，新型飞机(民用)快速、续航能力强、安全、便捷的特点受到越来越多的人青睐。如果从交错复杂的飞机线路中找到最廉价的线路，不仅减少了中途时间，而且大大节省了开支费用，为企业和个人带来可观的经济效益。本文从航班网络的实际特点出发，对航班线路网和票价进行分析，将最佳路径搜索问题转化为图论中的最短路径的问题，通过对最短路径算法的分析，实现了Floyd算法求航班网络中的最短路径，将之建立模型，并描述了用matlab程序进行求解的过程。关键词：最短路matlabFloyd算法21问题提出北京的一科技公司由于业务的需要，其总经理每周要往返于总公司与各个子公司之间，其出行所乘坐的交通工具是飞机，各个城市间的飞机线路，及票价如下表城市北京天津南京青岛上海广州深圳西安武汉杭州北京050INF4025101214INF15天津5001520INF2520INF1716南京INF1501020INFINF2628INF青岛4020100102532221821上海25INF201005516INF2124广州1025INF255501724INF25深圳1220INF3216170162718西安14INF2622INF241601819武汉INF17281821INF2718020杭州1516INF2124251819200(注：数字代表价格，INF表示城市之间没有线路。)问怎样才能算出一张任意城市间的最廉价路线表。2问题分析若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。（此两点为主要约束条件）我们确定本题为全局最短路问题，并采用Floyd算法，具体原理如下：（1）求距离矩阵的方法根据路线及票价表建立带权矩阵W，并把带权邻接矩阵我w作为距离矩阵的初始值，即(0)(0)()ijvvDdW1.1(1)()ijvvDd，其中1(0)(0)(0)11min,ijijijdddd，(1)ijd是从iv到jv的只允许以1v作为中间点的路径中最短路的长度。2.2(2)()ijvvDd，其中2(1)(1)(1)22min,ijijijdddd，(2)ijd是从iv到jv的只允许以1v，2v作为中间点的路径中最短路的长度。……()()(1)(1)(1)(min,vvvvvijijijvjvDdddd,()vijd是从iv到jv的只允许1v、2v、……、vv作为中间点的路径中最短路的长度。即是从iv到jv中间可插入如何顶点的路径中最短路的长度，因此()vD即是距离矩阵。（2）求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R，()ijvvRr，ijr的含义是从iv到jv3的最短路径要经过点号为ijr的点。(0)(0)(0)(),ijvvijRrrj每求得一个()kD时，按下列方式产生相应的新的()kR：(1)(1)()(1),,kkijikkjkijkijkddddrr若否则即当kv被插入任何两点间的最短路径时，被记录在()kR中，依次求得()kD时求得()kR，可由()vR来查找任何点对之间最短的路径。（3）查找最短路径的方法若()1vijrp，则点1p是点i到j的最短距离的中间点，然后用同样的方法再分头查找。若：1.向点i追溯得：12()()()23,,...,kvvvipipipkrprprp2.向点j追溯得：11()()()12,,...,mvvvpjqjqjrqrqrj则由点i到j的最短路的路径为：i，kp,…,2p，1p，1q，2q，…,mq，j。3模型假设a.各城市间的飞机线路固定不变b.各城市间飞机线路的票价不改变c.忽略乘客除票价以外的各项开销费用d.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。4模型建立4．1建立带权邻接矩阵根据飞机路线及票价表建立带权邻接矩阵，在带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵(1)D、(2)D、…、()vD，使最后得到的矩阵()vD为飞机的廉价矩阵。W=050402510121415500152025201716150102026284020100102532221821252010055162124102525550172425122032161701627181426222416018191728182127180201516212425181920044．2采用floyd算法步骤为:,ijD:i到j的最短距离,ijR：i到j之间的插入点输入带权邻接距阵w(1)赋初值：对所有,,,,,,,1.ijijijijwdjrk(2)更新,ijD,,ijR:对所有i,j若,,,ikkjijddd，则,,,ikkjijddd,,ijkr.(3)若kv,停止；否则1kk，转（2）.5模型求解运行程序得：D=0314035251012143215310152030252035171640150102035352628313520100102526221821253020100331632212410253525330172442251220352616170162718143526223224160181932172818214227180201516312124251819200R=11085567881010234467991082345428925234565891014345774910124476782101225567891019344678910823452789101224567891056结果分析根据模型求解，分析得出任意两个城市之间最廉价线路及票价为（横线可逆）：北京—天津：北京—杭州—天津；31北京—南京：北京—西安—南京；40北京—青岛：北京—上海—青岛；35北京—上海：北京—上海；25北京—广州：北京—广州；10北京—深圳：北京—深圳；12北京—西安：北京—西安；14北京—武汉：北京—西安—武汉；32北京—杭州：北京—杭州；15天津—南京：天津—南京；15天津—青岛：天津—青岛；20天津—上海：天津—青岛—上海；30天津—广州：天津—广州；25天津—深圳：天津—深圳；20天津—西安：天津—武汉—西安；35天津—武汉：天津—武汉；17天津—杭州：天津—杭州；16南京—青岛：南京—青岛；10南京—上海：南京—上海；20南京—广州：南京—青岛—广州；35南京—深圳：南京—天津—深圳；35南京—西安：南京—西安；26南京—武汉：南京—武汉；28；南京—杭州：南京—天津—杭州；31青岛—上海：青岛—上海；10青岛—广州：青岛—广州；25青岛—深圳：青岛—上海—深圳；26青岛—西安：青岛—西安；22青岛—武汉：青岛—武汉；18青岛—杭州：青岛—杭州；21上海—广州：上海—深圳—广州；33上海—深圳：上海—深圳；16上海—西安：上海—青岛—西安；32上海—武汉：上海—武汉；21上海—杭州：上海—杭州；24广州—深圳：广州—深圳；17广州—西安：广州—西安；24广州—武汉：广州—天津—武汉；42广州—杭州：广州——杭州；256深圳—西安：深圳—西安；16深圳—武汉：深圳—武汉；27深圳—杭州：深圳—杭州18西安—武汉：西安—武汉；18西安—杭州：西安—杭州；197方案评价（1）本文把所解决的问题归结为最短路问题，建立的数学模型清晰合理。（2）运用MATLAB软件处理数据和进行运算，降低运算量，简单易行，有很大的可操作性。且所得数据较为合理可靠。（3）在实际运用本方案中还应考虑自然因素对飞机航行的影响，还需根据实际情况进行灵活改变。参考文献[1]赵静数学建模与数学实验[M]高等教育出版社2000.11[2]张静李涛任意城市间最短路径的matlab语言实现[J]九江学院学报2007[3]百度百科Floy算法[4]百度百科最短路问题附件matlab主程序：Road.ma=[0,50,inf,40,25,10,12,14,inf,15;50,0,15,20,inf,25,20,inf,17,16;inf,15,0,10,20,inf,inf,26,28,inf;40,20,10,0,10,25,32,22,18,21;25,inf,20,10,0,55,16,inf,21,24;10,25,inf,25,55,0,17,24,inf,25;12,20,inf,32,16,17,0,16,27,18;14,inf,26,22,inf,24,16,0,18,19;inf,17,28,18,21,inf,27,18,0,20;15,16,inf,21,24,25,18,19,20,0];[D,R]=floyd(a)Floyd函数：Floyd.mfunction[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDREnd