《机场登机口分配 - 副本》由会员分享，可在线阅读，更多相关《机场登机口分配 - 副本（22页珍藏版）》请在金锄头文库上搜索。
1、四川理工学院毕业论文图论最大流理论在登机口分配中的应用学 生：彭叶 学 号： 专 业:数学与应用数学 班 级：应数2009 指导老师:熊廷见四川理工学院理学院二0 年 4 月四川 理工 学院毕业设计(论文）任务书设计（论文）题目：图论最大流理论在登机口分配中的应用学院: 四川理工学院 专业： 数学与应用数学 班级:20091 学号: 学生： 彭 叶 指导教师： 熊廷见 接受任务时间。03 教研室主任 （签名) 二级学院院长 (签名）1毕业设计（论文）的主要内容及基本要求分析机场登机口在日常运转中的分配不够优化的现状，利用图论中的最大流理论，探讨如何运用这个理论来优化机场登机口的分配状况.解决大
2、多数机场登机口在运输过程中所面临的问题。2指定查阅的主要参考文献及说明。 要求参考文献达到十五本及其以上3进度安排设计（论文）各阶段名称起 止 日期1确定论文题目，接受任务2查阅文献资料，完成文献综述和开题报告3完成论文初稿修改并完成论文直至定稿5论文答辩摘 要随着现代生活水平的提高,与物质精神文明的发展,远程旅游的人们越来越多，再加上中外来往交流的越发频繁，跟地区间的往来也很常见,出游人们对现代交通运输的要求越来越高，乘坐飞机出行的游客数量迅速增长。航空公司的运输压力也越发的大，机场航班一再的增加，飞机起降的次数日益频繁,对机场的布置与各机场登机口的设计要求也非常高。现在的登机口的分配面临着
3、很严峻的考验。大多数机场往往通过采用以往常接待游客的方法来接待游客，根本就没办法满足旅客出游效率。现在机场对登机口的分配以及人员调度、应急举措的不完善经常导致许多载客数量较大的飞机停靠在距离安检或者行李取放大厅比较远的登机口，有的还会因为远近机位登机口的航班密度的安排布置上面的不合理，使各个登机口的航班组合不能最大限度的利用起来而使登机口的可用效率降低。没有实现让游客出游达到最便捷的状态.登机口的分配利用并不充分合理。针对这些普遍存在的资源不太优化的现象本文通过图论最大流理论的优越性对机场登机口合理化分配中的应用做了一些探讨.以进出港旅客的总步行距离最短为主要优化目的，运用图论中的网络最大流理
4、论来解决登机口的分配与怎样优化来保证机场快速运输和处理一些紧急情况保证畅通安全快速的为旅客服务，提高登机口的利用效率,体现民航旅客运输的便捷性与舒适性。关键词：图论；最大流理论;登机口；网络流;最优化ABRACTith the delopment of life eelad aterilad sirtalcvilization, people who nt to have long istc tal aeiasin side，trales have iher nee on den trnporttide tothe frqnt concaton betwen coutris an regos
5、so th te puli f people taking plane goes up raidly。 As rel， the ssure in trnspot hat theschedu fig icreseconsant ecomes gerad igger。An ten， heetodoaon in airportn designobordin gates quite igh.I is a geat lleng to istrbute the bordigates Mot airports lays take the tratoalmeaureto gre vsitos， whic s
6、notsatifed withte eficincy o traveling. Acoig t heallocaonof boaig gat， pesonne aignment nd incomplete emergecy masur, no any big planestys fa from security chc orlgagepace hall Wats worse， theavailable eccyma o downbecase of nresnale allto oading gate and density f flight.Itisnotovnient or vsitors
7、to trave ith this locon。In termsof thcomo hennon，ti par use th vantage o gah heor oma-flw t scss the allocaion i bording gat.Thmain pros so otmize the hole waling distace for inwar and utwrd aveler by networ maximum lo theoy ue toeolehellocatoo bordin an how o optiize tanport an emeecy situations. I
8、nthat y, it animpre thewrkig effiency， whch cn sow cnenienceand cmortKey words：rph hey;network maximum flow teory; oardnggate； netwok flow；optimtio目 录摘 要3ASACT第一章图61。1 图的概念6. 图的连通性71.3 图论最短路问题71.3. 从一个顶点到一个终点vn的最短路问题1.2 Dijktra算法原理81。3. Dijtr算法步骤：9第二章 网络最大流1。 网络的流112 最大流的算法1221算法思想22.2.2 算法步骤12。2.3
9、总结3第三章 图论最大流理论在机场登机口分配中的运用43.1研究与方法15。1旅客步行距离最短模型的优化目标与约束条件5.2可步行距离最短模型的设置条件163。2 结果和分析132 优化分配网络模型的构建163.3 结语。18参 考 文 献19第一章 图图论是一门应用数学，它的概念和结果来源非常广泛,既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人，既有许多天才的数学家，也有不少业余爱好者。我们先来看一个著名的例子：Kogsberg七桥问题 在贯穿古普鲁士Koserg城的Prgel河上有七座桥连接两岸及河中的两个小岛.当时困扰当地居民的一个问题是：是否存在一种走法，使
10、走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因.问题被提到当时在Seesbrg的数学教授Euler(7071782)面前，他把每块地用一个顶点代替,把每座桥用连接对应顶点的一条边代替，把问题抽象为一幅平面图。为解决这个具体问题,他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明.这结果发表于176年，并被公认为第一篇图论文章,他本人也被尊崇为图论和拓扑学之父【】。在现实世界的许多情况下，经常会遇到在有限的某几个元素之间有没有存在某种联系或者他们之间又有怎样的联系。假如这些元素之间存在着某种联系而且这种联系还是对称的话,人们就能用“图”来模拟这种存在着的联
11、系，我们就把这种联系能准确直观的反应出。就可以用来解决实际情况中存在的问题，我们也就从图的概念出发，开始对本文在机场登机口会遇到的一些问题的探讨。1。1 图的概念 对于图的概念我这里先有一个例子来辅助我的定义：假设某航空公司要为国内几个重要城市提高航空服务，他们拥有一张航空路线示意图,假设两个城市之间又该航空公司的直达航班,那么航空线路图上就会有一条连接两个城市的线,那么我们把这些具体的城市名称取消掉,剩下的这个模型就是我们需要研究的图。代表城市位置的点就是图论中所说的顶点。那些连接各个顶点之间的线就叫做图的边，旅客乘坐该航空公司的航班能否从一个城市也就是顶点到达另一个城市或者另一个顶点之间的
12、转换,这就是图论中的图的连通问题。如果我们再在图的边上标上一个正实数来表示两个相应城市之间机票的票价,这样的图就被称为赋权图。我们要从一个城市乘该航空公司的班机到另外一个城市,怎样乘坐飞机使所花的票价最低。实际上这就是图论中求最短路的问题. 图 1。1 接下来这里就给出图的概念 图G=（V(G)，E(G）)是由元素被称为顶点的一个有限非空集连同被称为边的图的不同顶点有限无续对集(可能是空集)组成。 V(G)称为G的顶点集，而(G）称为G的边集.一个图G的顶点集的顶点个数称为G的阶（如上图,它是一个八阶的图）,用p（G）或简单地用来表示，而它的边集的基数通常称为G的大小,用q（)或q来表示。一个
13、(p，q）图就是阶为p,大小为q的图.。2 图的连通性 对于图的两个顶点和v，如果在G中存在一条路,记为(u，v)路,则称u和是连通的。如果一个图的每一对顶点都至少有一条路连接,则称该图是连通图；否则称为非连通图或分离图.G的每一个最大的连通子图称为一个连通分支。图。1 连通图图1.2. 非连通图定理1 如果G是具有n个顶点的连通图,则G中至少有-1条边(2)， 也就是说，在一个具有n个顶点1条边的连通图中，如果删去任意一边，图便不通了，我们称这样的图为最小连通图【2】.证明：对顶点个数n用归纳法。当n=时，若图连通,则两顶点至少有一条边相连，即结论成立。假设当n=k时结论成立。考察n=k+的情形。首先证明,如果边数m,则图中至少有一个顶点的度为1,这是因为，如果对于V中的任意顶点v都有（v）2,则2n，即m，这与mn矛盾。于是证明了,如果m，则必有顶点u，使d(u)=1。现在从中删去顶点u及其锁关联的边,得到一个具有k个顶点的连通图.由归纳假设知该图至少有k1条边,再将u及其关联的那条边添加回去，则恢复原图。于是它有k+1个顶点,至少有条边。如果边数，而nk1，则mk+，结论也成立。故命题对n=k+1时成立，由数学归纳法,定理1证完.
