版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图论最大流理论
在机场登机口分配中的应用教师:张金山联系方式:zjscdut@163.com;主要参考书籍:1.数学建模与数学实验,赵静,但琦2.数学实验,萧树铁3.数学建模方法及其应用,韩中庚4.数学建模导论,陈理荣
数学建模简介
理想与现实什么是数学建模?
数学建模是利用数学方法解决实际问题的一种实践。即通过抽象、简化、假设、引进变量等处理过程后,将实际问题用数学方式表达,建立起数学模型。数学建模所涉及的问题都是现实生活中的实际问题,范围广、学科多,包括工业、农业、医学、生物学、政治、经济、军事、社会、管理、信息技术等方面。
1、问题的描述(背景)随着机场航班日起降架次的增多和乘飞机出行旅客数量的迅速增长,现有的登机口资源正面临着日益严峻的考验。目前,大多数机场通过借鉴其他机场的做法,或根据以往的经验来进行登机口分配和调度,往往导致很多载客数量较多的大中型飞机停靠在距安检或者行李提取大厅较远的登机口;或由于远、近机位登机口航班密度安排不合理,使得每个登机口的航班组合没有达到最优,从而降低了登机口的利用效率。
相关信息
根据某机场一天中部分时段的航班计划,将各航班信息汇总表1所示
航站楼布局登机口、安检区与行李提取大厅的位置
安检区与行李提取大厅不同层但位置相近安检区与行李提取大厅(不)同层但位置不同在保证机场安全、高效运行的前提下,尽可能提高登机口利用效率,体现民航旅客运输的便捷性与舒适性。2、问题分析旅客步行距离最短模型的优化目标与约束条件优化目标1)使进、出港旅客的总步行距离最短,满足旅客对航空运输“便捷性”的需求;2)使现有设施使用效率达到最高,优化资源配置。约束条件1)机型与机位类型相匹配;2)分配登机口时,一个航班必须被分配且仅能被分配至一个登机口;3)应满足最短过站时间和同机位安全间隔时问的要求;4)“航班对”的限制:由于在机场停靠的绝大部分航班既担负着进港航班任务,又担负着出港航班任务,因此,尽量将此类飞机尽可能安排在同一个登机口,降低航空公司运营成本。除此之外,根据各机场的性质和特点不同,还需考虑登机口分配的优先原则、航班过夜、飞机维修等约束条件。3、模型的建立与求解
3.1数据收集与整理利用表l中已知航班信息作为实例分析的数据来源,采用最广泛的航站楼布局形式即假定安检区和行李提取大厅分别位于航站楼的上、下两层,位置近似相同,以此来说明该模型的构建方法和应用过程。3.2优化分配网络模型的构建3.2.1进、出港旅客步行距离最短模型建立与实证分析对于国内大部分干线和支线机场而言,始发或终到旅客所占比例甚多,从长时间的数据统计来看,这两部分旅客所占比例相当,因此,可将其步行距离视为近似相等。以下就是进、出港旅客步行距离最短模型的实施步骤:步骤1按照登机口启用时间的先后顺序,由左至右把每个航班作为网络图上的一个节点,在考虑各种约束条件的基础上,将节点之间进行有向连线,方向为由离港时间早的航班指向晚的,由此形成一个由节点和箭头构成的网络图。不难理解,网络图中从起点到终点的每一条有向路径上的节点都是可以安排在一个登机口上的航班组合,如图3所示。步骤2在图3上,按照各节点的时间顺序对其进行二次编号G(A,B),G表示航班编号;A表示航班G的前一个航班的编号(若为起始航班,则其编号为本次航班的号码);B表示航班载客人数的累计,即前一个航班A的实际载客人数与本次航班G的实际载客人数之和。需要注意的是,若A前有两个或多个已编号航班,则择选B最大的那个航班作为G的前一个航班,如图4所示。步骤3将每架航班的人数看成是网络图中的流量,从登机口结束使用的这个网络图的最大流量就表示可以使用同一个登机口的人数最多的航班组合。从终点开始逆向寻找一条至起点航班人数最多的路径,并把这条路径上的航班安排在距安检出口最近的登机口。在图4中,01→04→07即为网络图中旅客流量最大的航班组合,可将这3个航班按照登机口启用先后顺序安排至离安检区最近的登机口。步骤4在调度网络图上去掉已安排过的航班节点及与其相关联的箭线,再从新的起点开始寻找一条至终点航班人数最多的路径,并把这条路径上的航班安排在距安检出口次近的登机口,如图5所示。在图5中,02→03→05→08为网络图中旅客流量最大组合,可将这4个航班按照登机口启用先后顺序安排至离安检区次近的登机口。步骤5重复步骤4,按照上述方法直到所有的航班安排完为止。本例中剩下06号航班,可将其安排至3号登机口。3.3.1算法的复杂度分析如前所述,该模型总运算次数不会超过n,而网络图中航班节点的总数也不会超过n,故总运算次数不会大于n2,即其计算复杂度为o(n2)。3.3算法复杂度分析和最优性证明2.3.2算法的最优性证明为了说明算法是最优算法,现在登机口调度网络图上增加一个虚拟起始节点s和一个虚拟终结节点t,并将虚拟起始节点s与所有起始航班节点用箭头相连,同样,将所有终结节点与虚终结节点t也用箭头相连,如图6所示。由于各航班节点是按时间顺序由左至右排列的,因此,图6所示的网络图是一个具有两端点s和t的无环路网络图。其中每一条从s到t的有向路径,都是可在同一个登机口安排航班组合的可行方案。如果把各节点的航班人数作为以该节点为终点的各箭线的权值,则该网络图就相
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年日用及医用橡胶制品项目经营分析报告
- 2024年营养强化剂项目营销方案
- 2024年水电站自动控制系统行业商业计划书
- 2024年氯氟氰菊酯市场分析及竞争策略报告
- 2024年度高校教师资格证资格考试(a卷)
- 2024医疗器械购销合同1208
- 2024单项项目保密协议书范本
- 防汛应急演练的点评材料
- 村级退役军人服务站
- 2024安全员(初级)考试题模拟考试题库(考试直接用)
- 小学三年级下册全套奥数讲义(共65页)
- 原电池化学电源(练习题)
- 劳动跟社会保障部《关于实施〈工伤保险条例〉若干问题的意见》
- 基于EDEM的带凝聚力的颗粒系统的输送仿真
- 石景山区街道办事处实施社区教育工作评价指标体系试行
- 病史采集、病例分析
- 世界各国插头型式一览表
- 汽车销售的存贮策略--数学与应用数学论文设计
- 建设工程质量竣工验收意见书版本
- 东南大学Mathematica数学实验报告
- C臂机技术参数
评论
0/150
提交评论