Ford–Fulkerson算法铁路运输系统中车辆流问题的研究
时间:2016-12-28 17:33 来源:毕业论文 作者:毕业论文 点击:次
| 摘要：最大流问题是图论理论的一个经典组合优化问题，在交通运输、通信工程、工业、商业、农业等许多领域有着广泛的应用，给我们的生活带来很大方便。而其在应用数学、管理科学和社会科学等众多领域中也起到了非常重要的作用。本文主要通过对求解最大流的经典算法——Ford–Fulkerson算法的描述以及其原理思想的分析，给出了一种基于Ford–Fulkerson算法的求最大流的实现——寻求最大流的标号法，并清晰完整地表现标号法求解最大流的过程。最后，结合实际情况，将最大流问题应用到地铁客流量问题和铁路运输系统中的车辆流问题中，通过简化及假设一些限制条件，建立网络模型，使用C++编程实现标号法，并用其求解客流量问题和车辆流问题。 关键字：最大流 Ford–Fulkerson算法 标号法 车辆流 客流4841 The research of vehicle flow in the railway transport system Abstract: The maximum flow problem of graph theory is a classical combinatorial optimization problem, and it has been used widely, in transportation, communications engineering, industrial, commercial, agricultural, and many other fields, to bring great convenience for our daily life. And its application also play a very important role in many fields, such as the mathematics, management science, and social sciences. In this paper, through the description and analysis of the classic algorithm of the maximum flow problem, called the Ford - Fulkerson algorithm, we give an algorithm based of the Ford - Fulkerson algorithm, called the labeling algorithm. And we clearly and completely describe how the labeling algorithm solve the maximum flow problem. And then, combined with the actual situation, the maximum flow problem and its algorithm are applied to solve the passenger flow problem and the vehicle flow problem in the transport system.Via some simplified assumptions and limiting conditions, we build a network model. And we use the c++ programming to implement the label algorithm, and use it to solve the passenger flow problem and vehicle flow problem. Keywords: maximum flow, Ford–Fulkerson algorithm, labeling algorithm, vehicle flow, passenger flow 目录 一 绪论 1 1.1 课题的目的和意义 1 1.2 国内外研究现状与发展趋势 1 1.3 网络流基本概念及其数学模型 3 1.3.1 基本概念 3 1.3.2 数学模型 5 二 Ford–Fulkerson算法 6 2.1 Ford–Fulkerson算法的思想及原理 6 2.2 Ford–Fulkerson算法的具体步骤 7 2.3 Ford–Fulkerson算法的实现——标号法 8 2.4 寻求最大流的标号法举例 9 2.5 小结 11 三 最大流在交通运输系统中的应用 12 3.1 寻求最大流的标号法的C++实现 12 3.2 地铁运输系统中客流量问题 14 3.3 铁路运输系统中车辆流问题 17 3.3.1 车辆流问题模型建立 18 3.3.2 车辆流问题求解 19 四 全文总结 21 致谢 22 参考文献 23 附录 24 一 绪论 1.1 课题的目的和意义 图论是应用数学的一个重要分支，它涉及的内容非常广泛，并且在许多领域有十分广泛的应用。而最大流问题和它的对偶问题最小割问题则是图论中一个经典的组合优化问题，也是特殊的线性规划问题。它们的应用涉及交通运输、通信工程、VLSI、计算机科学与技术等许多工程领域和物理、化学、生物等许多科学领域。在应用数学、管理科学和社会科学等众多领域中最大流和最小割问题也起到了非常重要的作用。例如：在工程领域的电网络、网络可靠性测试等问题中的应用，在计算机科学和通信系统的一致并行计算机的调度问题、最大流路由问题、纹理分析问题和CAD中的最小割划分等问题中的应用，以及在交通运输中的各种路线调度问题的应用。 (责任编辑：qin) |