网络流算法的若干的分析研究及分析.pdf

南京邮电大学硕士研究生学位论文中文摘要 I 中文摘要网络流问题作为运筹学的一部分,它主要研究的是网络最优化问题,在工程及科学等领域均有重要作用。其主要内容包括最短路、最大流及最小费用流等问题,随着信息技术的发展人们建立了较为完善的理论,提出了一系列相应的算法,取得了令人瞩目的成绩。本文的研究重点是基于石油运输网络模型,对最大流算法和最小费用流相关问题进行分析、比较与改进。本文首先介绍了FordFulkerson标记法、最短增广链算法及预流推进算法等求解网络最大流的三种主流算法,通过具体实例验证了上述算法的局限性。在分析以上算法自身特点的基础上,吸收最大流算法的最新研究成果,提出两种求最大流的新算法,并通过实例得以验证。其次,介绍了求最小费用流的负回路算法、最小费用路算法,以及预算固定最大流算法和最小费用最大流算法。其中在介绍最小费用流算法之前给出了一种求小规模网络两点之间最短路的简单易行的方法。最后,给出了本文所提出的石油运输网络的最佳运输方案。本文所有的算法均给出了相应的算例,虽然例子不能衡量一种算法的优劣,但以几种算法之间的比较为目的,使用若干代表性的算例不失为一种可取的方法。关键词: 运输网络;增广链;最大流;最短路;最小费用流;最小费用最大流南京邮电大学硕士研究生学位论文 ABSTRACT II work flowissue,as a part of operatinal research,mainly workoptimization plays an important role in engineering and science. Itsprimary coverageincludes shortest path,maximum flowand minimum cost flow problems,With the development of information technology,researchers have establisheda plete theory, proposeda set of relevant algorithms, and achievedremarkable results. This study focuses on oil work model,paresand improves maximum flow , minimumcost flow algorithm and related issues. Firstly,in order tosolve maximum flow works, thisthesisintroduces three main algorithms: the FordFulkerson marking method, the shortest path algorithm and the augmented preflow push specific examples,the author hasdemonstratedthe limitations of the on the analysis of the above algorithms’characteristics and through the latest research resultsoftheabsorption maximum flow algorithm,thisthesisproposestwo new algorithms for Maximum flowwhich can betestified by ,the author introducesthe Minimum Cost Flow including negative circuit algorithm, minimum cost path algorithm, and the maximum flow with a given budget algorithm and the minimum cost maximum flow algorithm. Before the introduction of the minimum cost flow algorithm,this thesisgives an easy method solving the shortest path between two points in small-works. Finally,the thesis proposes the bestsolutions for oil work. All of th