2022年数学建模《最廉价飞机线路的选择》终稿 .pdf

《2022年数学建模《最廉价飞机线路的选择》终稿 .pdf》由会员分享，可在线阅读，更多相关《2022年数学建模《最廉价飞机线路的选择》终稿 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最廉价飞机线路的选择摘要：改革开发以来，我国的经济发展迅速，人民生活水平逐渐提高，2010 年，我国 GDP 超越日本，排名世界第二。我国经济的发展，使人们对交通运输提出越来越多的需求，而民航作为航空运输工具，在交通工具中起到十分重要的作用，新型飞机(民用)快速、续航能力强、安全、便捷的特点受到越来越多的人青睐。如果从交错复杂的飞机线路中找到最廉价的线路，不仅减少了中途时间，而且大大节省了开支费用，为企业和个人带来可观的经济效益。本文从航班网络的实际特点出发，对航班线路网和票价进行分析，将最佳路径搜索问题转化为图论中的最短路径的问题，通过对最短路径算法的分析，实现了 Floyd 算法求航班网络

2、中的最短路径，将之建立模型，并描述了用matlab 程序进行求解的过程。关键词：最短路 matlab Floyd算法名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -2 1问题提出北京的一科技公司由于业务的需要，其总经理每周要往返于总公司与各个子公司之间，其出行所乘坐的交通工具是飞机，各个城市间的飞机线路，及票价如下表城市北京天津南京青岛上海广州深圳西安武汉杭州北京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 2

3、0 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(注：数字代表价格，INF 表示城市之间没有线路。)问怎样才能算出一张任意城市间的最廉价路线表。2问题分析若网络中的每条边都有一个数值(长度、成本、时间等)，则

4、找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题求图中所有的最短路径。题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。（此两点为主要约束条件）我们确定本题为全局最短路问题，并采用Floyd 算法，具体原理如下：（1）求距离矩阵的方法根据路线及票价表建立带权矩阵W，并把带权邻接矩阵我w 作为距离矩阵的初始值，即(0)(0

5、)()ijv vDdW1.1(1)()ijv vDd，其中1(0)(0)(0)11min,ijijijdddd，(1)ijd是从iv 到jv 的只允许以1v 作为中间点的路径中最短路的长度。2.2(2)()ijv vDd，其中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 中间可插入如何顶点的路径中最短路的长度，因此(

6、)vD即是距离矩阵。（2）求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R，()ijv vRr，ijr 的含义是从iv 到jv名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -3 的最短路径要经过点号为ijr 的点。(0)(0)(0)(),ijv vijRrrj每求得一个()kD时，按下列方式产生相应的新的()kR：(1)(1)()(1),kkijikkjkijkijkddddrr若否则即当kv 被插入任何两点间的最短路径时，被记录在()kR中，依次求得()kD时求得()kR，可由()vR来查找任何点对之间最短的路径。（3）查找最短路径的方法若()1vijrp，则点1

7、p 是点i到j的最短距离的中间点，然后用同样的方法再分头查找。若：1.向点i追溯得：12()()()23,.,kvvvipipipkrp rprp2.向点j追溯得：11()()()12,.,mvvvp jq jqjrq rqrj则由点i到j的最短路的路径为：i，kp,2p，1p，1q，2q，,mq，j。3模型假设a.各城市间的飞机线路固定不变b.各城市间飞机线路的票价不改变c.忽略乘客除票价以外的各项开销费用d.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。4模型建立41 建立带权邻接矩阵根据飞机路线及票价表建立带权邻接矩阵，在带权邻接矩阵中用插入顶点的方法依次构造出v个矩阵

8、(1)D、(2)D、()vD，使最后得到的矩阵()vD为飞机的廉价矩阵。W=0 50 40 25 10 12 14 1550 0 15 20 25 20 17 16 15 0 10 20 26 28 40 20 10 0 10 25 32 22 18 2125 20 10 0 55 16 21 2410 25 25 55 0 17 24 2512 20 32 16 17 0 16 27 1814 26 22 24 16 0 18 19 17 28 18 21 27 18 0 2015 16 21 24 25 18 19 20 0名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7

9、页 -4 42 采用 floyd算法步骤为:,ijD:i到j的最短距离,ijR：i到j之间的插入点输入带权邻接距阵w(1)赋初值：对所有,1.i ji ji ji j wdjrk(2)更新,i jD,i jR:对所有i,j若,i kk ji jddd，则,i kk ji jddd,i jkr.(3)若kv,停止；否则1kk，转（2）.5模型求解运行程序得：D=0 31 40 35 25 10 12 14 32 15 31 0 15 20 30 25 20 35 17 16 40 15 0 10 20 35 35 26 28 31 35 20 10 0 10 25 26 22 18 21 25

10、30 20 10 0 33 16 32 21 24 10 25 35 25 33 0 17 24 42 25 12 20 35 26 16 17 0 16 27 18 14 35 26 22 32 24 16 0 18 19 32 17 28 18 21 42 27 18 0 20 15 16 31 21 24 25 18 19 20 0 R=1 10 8 5 5 6 7 8 8 10 10 2 3 4 4 6 7 9 9 10 8 2 3 4 5 4 2 8 9 2 5 2 3 4 5 6 5 8 9 10 1 4 3 4 5 7 7 4 9 10 1 2 4 4 7 6 7 8 2 10

11、1 2 2 5 5 6 7 8 9 10 1 9 3 4 4 6 7 8 9 10 8 2 3 4 5 2 7 8 9 10 1 2 2 4 5 6 7 8 9 10 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -5 6结果分析根据模型求解，分析得出任意两个城市之间最廉价线路及票价为（横线可逆）：北京天津：北京杭州天津；31 北京南京：北京西安南京；40 北京青岛：北京上海青岛；35 北京上海：北京上海；25 北京广州：北京广州；10 北京深圳：北京深圳；12 北京西安：北京西安；14 北京武汉：北京西安武汉；32 北京杭州：北京杭州；15 天津南京：天津南京；15

12、天津青岛：天津青岛；20 天津上海：天津青岛上海；30 天津广州：天津广州；25 天津深圳：天津深圳；20 天津西安：天津武汉西安；35 天津武汉：天津武汉；17 天津杭州：天津杭州；16 南京青岛：南京青岛；10 南京上海：南京上海；20 南京广州：南京青岛广州；35 南京深圳：南京天津深圳；35 南京西安：南京西安；26 南京武汉：南京武汉；28；南京杭州：南京天津杭州；31 青岛上海：青岛上海；10 青岛广州：青岛广州；25 青岛深圳：青岛上海深圳；26 青岛西安：青岛西安；22 青岛武汉：青岛武汉；18 青岛杭州：青岛杭州；21 上海广州：上海深圳广州；33 上海深圳：上海深圳；16

13、上海西安：上海青岛西安；32 上海武汉：上海武汉；21 上海杭州：上海杭州；24 广州深圳：广州深圳；17 广州西安：广州西安；24 广州武汉：广州天津武汉；42 广州杭州：广州杭州；25 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -6 深圳西安：深圳西安；16 深圳武汉：深圳武汉；27 深圳杭州：深圳杭州18 西安武汉：西安武汉；18 西安杭州：西安杭州；19 7方案评价（1）本文把所解决的问题归结为最短路问题，建立的数学模型清晰合理。（2）运用 MATLAB 软件处理数据和进行运算，降低运算量，简单易行，有很大的可操作性。且所得数据较为合理可靠。（3）在实际运用

14、本方案中还应考虑自然因素对飞机航行的影响，还需根据实际情况进行灵活改变。参考文献1 赵静 数学建模与数学实验 M 高等教育出版社 2000.11 2 张静 李涛 任意城市间最短路径的matlab 语言实现 J 九江学院学报 2007 3 百度百科 Floy 算法 http:/ 2011.6.14 4 百度百科最短路问题http:/ 6 页，共 7 页 -7 附件matlab 主程序：Road.m a=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,

15、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.m functionD,R=floyd(a)n=size(a,1);D=a for i=1:n for j=1:n R(i,j)=j;end end R for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);end end end k D R End 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -