毕业设计---最大流问题及应用

《毕业设计---最大流问题及应用》由会员分享，可在线阅读，更多相关《毕业设计---最大流问题及应用（44页珍藏版）》请在毕设资料网上搜索。

1、 本科毕业设计（论文）本科毕业设计（论文） 题 目 最大流问题以及应用 学 院 名 称 数学与系统科学学院 专 业 班 级 学 生 姓 名 学 号 摘要摘要 网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一 个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、 商业、农业，运输业等领域可给我们的生活带来很大方便。 本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识； 阐述网络的基本概念； 介绍最大流问题的核心依据Ford-Fulkerson最大 流最小割定理；综述解决最大流问题的 几种算法 Ford-Fulkerson标号法、 Edmonds-Karp 修正

2、算法、Dinic 算法，并比较各算法在解决不同问题中的 优劣。 为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一 个实际生活中的问题铁路货运列车的最优调度来突出研究最大流问题 的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一 昼夜间能通过某段铁路的最多的货运列车数量并列出每 辆列车开出的时 刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为 最大流问题并应用图的性质和 Ford-Fulkerson标号法的算法依据，最终解 决了问题。 本文采用理论与 实例相结合，重在应用理论依据解决实际问题，具有 较强的实践性，突出的是应用。 Abstract The

3、network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and oth

4、er areas can bring us great convenience. The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem - Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct