《机场登机口分配 - 副本.doc》由会员分享，可在线阅读，更多相关《机场登机口分配 - 副本.doc（22页珍藏版）》请在金锄头文库上搜索。
1、 四川理工学院毕业论文图论最大流理论在登机口分配中的应用学 生：彭叶 学 号：09071040115 专 业：数学与应用数学 班 级：应数2009.1 指导老师：熊廷见四川理工学院理学院二0 13 年 4 月四 川 理 工 学 院毕业设计（论文）任务书设计（论文）题目：图论最大流理论在登机口分配中的应用学院： 四川理工学院 专业： 数学与应用数学 班级：2009.1 学号： 09071040115 学生： 彭 叶 指导教师： 熊廷见 接受任务时间 2013.03 教研室主任 （签名）二级学院院长 （签名）1毕业设计（论文）的主要内容及基本要求分析机场登机口在日常运转中的分配不够优化的现状，利用
2、图论中的最大流理论，探讨如何运用这个理论来优化机场登机口的分配状况。解决大多数机场登机口在运输过程中所面临的问题。 2指定查阅的主要参考文献及说明。 要求参考文献达到十五本及其以上3进度安排设计（论文）各阶段名称起 止 日 期1确定论文题目，接受任务2查阅文献资料，完成文献综述和开题报告3完成论文初稿4修改并完成论文直至定稿5论文答辩 摘 要随着现代生活水平的提高，与物质精神文明的发展，远程旅游的人们越来越多，再加上中外来往交流的越发频繁，跟地区间的往来也很常见，出游人们对现代交通运输的要求越来越高，乘坐飞机出行的游客数量迅速增长。航空公司的运输压力也越发的大，机场航班一再的增加，飞机起降的次
3、数日益频繁，对机场的布置与各机场登机口的设计要求也非常高。现在的登机口的分配面临着很严峻的考验。大多数机场往往通过采用以往常接待游客的方法来接待游客，根本就没办法满足旅客出游效率。现在机场对登机口的分配以及人员调度、应急举措的不完善经常导致许多载客数量较大的飞机停靠在距离安检或者行李取放大厅比较远的登机口，有的还会因为远近机位登机口的航班密度的安排布置上面的不合理，使各个登机口的航班组合不能最大限度的利用起来而使登机口的可用效率降低。没有实现让游客出游达到最便捷的状态。登机口的分配利用并不充分合理。针对这些普遍存在的资源不太优化的现象本文通过图论最大流理论的优越性对机场登机口合理化分配中的应用
4、做了一些探讨。以进出港旅客的总步行距离最短为主要优化目的，运用图论中的网络最大流理论来解决登机口的分配与怎样优化来保证机场快速运输和处理一些紧急情况保证畅通安全快速的为旅客服务，提高登机口的利用效率，体现民航旅客运输的便捷性与舒适性。关键词：图论；最大流理论；登机口；网络流；最优化ABSTRACT With the development of life level and material and spiritual civilization, people who want to have long distance travel are increasing. Besides, trav
5、elers have higher needs on modern transportation due to the frequent communication between countries and regions so that the population of people taking plane goes up rapidly. As a result, the pressure in transport that the scheduled flight increases constantly becomes bigger and bigger. And then, t
6、he need to decoration in airport and design of boarding gate is quite high. It is a great challenge to distribute the boarding gates. Most airports always take the traditional measure to greet visitors, which is not satisfied with the efficiency of traveling. According to the allocation of boarding
7、gate, personnel assignment and incomplete emergency measures, now many big planes stays far from security check or luggage placed hall. Whats worse, the available efficiency may go down because of unreasonable allocation boarding gate and density of flight. It is not convenient for visitors to trave
8、l with this allocation. In terms of these common phenomenon, this paper use the advantages of graph theory of max-flow to discuss the allocation in boarding gate.The main purpose is to optimize the whole walking distance for inward and outward travelers by network maximum flow theory used to resolve
9、 the allocation of boarding and how to optimize transport and emergency situations. In that way, it can improve the working efficiency, which can show convenience and comfort.Key words: graph theory; network maximum flow theory; boarding gate; network flow; optimization目 录摘 要3ABSTRACT4第一章 图61.1 图的概念
10、61.2 图的连通性71.3 图论最短路问题71.3.1 从一个顶点v1到一个终点vn的最短路问题81.3.2 Dijkstra算法原理81.3.3 Dijkstra算法步骤：9第二章 网络最大流112.1 网络的流112.2 最大流的算法122.2.1算法思想122.2.2 算法步骤122.2.3 总结13第三章 图论最大流理论在机场登机口分配中的运用143.1研究与方法153.1.1旅客步行距离最短模型的优化目标与约束条件153.1.2可步行距离最短模型的设置条件163.2 结果和分析163.2.1 优化分配网络模型的构建163.3 结语.18参 考 文 献19第一章 图图论是一门应用数学
11、，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人，既有许多天才的数学家，也有不少业余爱好者。我们先来看一个著名的例子：Konigsberg七桥问题 在贯穿古普鲁士Konigsberg城的Pregel河上有七座桥连接两岸及河中的两个小岛。当时困扰当地居民的一个问题是：是否存在一种走法，使走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因。问题被提到当时在St.Peitersburg的数学教授Euler（1707-1782）面前，他把每块地用一个顶点代替，把每座桥用连接对应顶点的一条边代替，把问题抽象为一幅平面图。为解
12、决这个具体问题，他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明。这结果发表于1736年，并被公认为第一篇图论文章，他本人也被尊崇为图论和拓扑学之父【1】。在现实世界的许多情况下，经常会遇到在有限的某几个元素之间有没有存在某种联系或者他们之间又有怎样的联系。假如这些元素之间存在着某种联系而且这种联系还是对称的话，人们就能用“图”来模拟这种存在着的联系，我们就把这种联系能准确直观的反应出。就可以用来解决实际情况中存在的问题，我们也就从图的概念出发，开始对本文在机场登机口会遇到的一些问题的探讨。1.1 图的概念 对于图的概念我这里先有一个例子来辅助我的定义：假设某航空公司要为国内几个
13、重要城市提高航空服务，他们拥有一张航空路线示意图，假设两个城市之间又该航空公司的直达航班，那么航空线路图上就会有一条连接两个城市的线，那么我们把这些具体的城市名称取消掉，剩下的这个模型就是我们需要研究的图。代表城市位置的点就是图论中所说的顶点。那些连接各个顶点之间的线就叫做图的边，旅客乘坐该航空公司的航班能否从一个城市也就是顶点到达另一个城市或者另一个顶点之间的转换，这就是图论中的图的连通问题。如果我们再在图的边上标上一个正实数来表示两个相应城市之间机票的票价，这样的图就被称为赋权图。我们要从一个城市乘该航空公司的班机到另外一个城市，怎样乘坐飞机使所花的票价最低。实际上这就是图论中求最短路的问
14、题。 图 1.1 接下来这里就给出图的概念 图G=(V(G),E(G)是由元素被称为顶点的一个有限非空集连同被称为边的图的不同顶点有限无续对集（可能是空集）组成。 V(G) 称为G的顶点集，而E(G)称为G的边集。一个图G的顶点集的顶点个数称为G的阶（如上图，它是一个八阶的图），用p(G)或简单地用p来表示，而它的边集的基数通常称为G的大小，用q(G)或q来表示。一个(p,q)图就是阶为p，大小为q的图。1.2 图的连通性 对于图G的两个顶点u和v，如果在G中存在一条路，记为(u,v)路，则称u和v是连通的。如果一个图的每一对顶点都至少有一条路连接，则称该图是连通图；否则称为非连通图或分离图。
15、G的每一个最大的连通子图称为一个连通分支。 图1.2.1 连通图图1.2.2 非连通图 定理1.1 如果G是具有n个顶点的连通图，则G中至少有n-1条边(n2)， 也就是说，在一个具有n个顶点n-1条边的连通图中，如果删去任意一边，图便不通了，我们称这样的图为最小连通图【2】。证明：对顶点个数n用归纳法。当n=2时，若图连通，则两顶点至少有一条边相连，即结论成立。假设当n=k时结论成立.考察n=k+1的情形。首先证明，如果边数mn，则图G中至少有一个顶点的度为1，这是因为，如果对于V中的任意顶点v都有d(v)2,则2m2n，即mn，这与mn矛盾。于是证明了，如果mn，则必有顶点u，使d(u)=1。现在从G中删去顶点u及其锁关联的边，得到一个具有
