Ford–Fulkerson算法铁路运输系统中车辆流问题的研究.docVIP

Ford–Fulkerson算法铁路运输系统中车辆流问题的研究 摘要：最大流问题是图论理论的一个经典组合优化问题，在交通运输、通信工程、工业、商业、农业等许多领域有着广泛的应用，给我们的生活带来很大方便。而其在应用数学、管理科学和社会科学等众多领域中也起到了非常重要的作用。本文主要通过对求解最大流的经典算法mdash;mdash;Fordndash;Fulkerson算法的描述以及其原理思想的分析，给出了一种基于Fordndash;Fulkerson算法的求最大流的实现mdash;mdash;寻求最大流的标号法，并清晰完整地表现标号法求解最大流的过程。最后，结合实际情况，将最大流问题应用到地铁客流量问题和铁路运输系统中的车辆流问题中，通过简化及假设一些限制条件，建立网络模型，使用C++编程实现标号法，并用其求解客流量问题和车辆流问题。 关键字：最大流 Fordndash;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. 最大流问题的应用主要表现在下面几个方面： （1）在许多现实的网络中需要确定在两点之间最大可输送的流量； （2）许多问题表面上看起来和最大流问题无关，但其实它们可以通过图论和线性规划等方法把问题转化为最大流问题； （3）最大流问题常常作为一些其他的问题，主要是图论、组合优化和线性规划等问题的子问题出现。 最大流问题已经有多年的研究历史，而它的应用也一直是十分有意义的研究工作。网络流问题的研究者和具体问题的工程师从各个不同的角度充实着这方面的研究。无论是从线性规划还是组合优化的角度来看，最大流问题都是一个已经被研究得比较深入的问题，该领域已经存在许多优秀的算法和大量优秀的代码。因此，把许多问题转化为最大流问题或最小割问题后可以得到十分有效地解决。而发现具体的问题与最大流或最小割问题之间