网络流问题及其应用开题报告

1. 研究目的与意义

网络流问题是运筹学的重要组成部分，它主要研究有关网络的一类最优化问题，主要包括最大流、最小费用最大流等方面。最大流问题是指在网络中弧的容量给定时，寻找一个可行流方案，使得在单位时间内从某个指定发点到收点的总流量最大。在实际生活中，涉及#8220;流#8221;的问题时，人们往往还会考虑费用的问题，使费用最低便是最小费用流问题。如果使得费用最低且总流量最大，这就是最小费用最大流问题。最大流问题在实际生产生活中应用广泛，如通信网络最大流、交通运输路线的制定、电力网的规划。

网络流问题在许多科学领域、工程领域等均有非常重要的作用，其具体应用主要表现在以下几方面：

1)解决现实网络中的流量问题及费用问题，寻找最优解决方案；

2. 研究内容和预期目标

研究内容及拟解决的关键问题：

网络流问题的算法在现实生活中应用十分广泛。本文主要研究网络最大流问题及网络最小费用流问题，介绍一些改进的算法及新算法，关键通过最小流算法分析物资运输问题，说明网络流问题与实际问题的联系性。

写作提纲：

3. 国内外研究现状

通过对网络流问题50多年的研究，随着信息技术的发展，人们已经逐渐建立起一个比较完善的理论体系。对于最大流问题，主要采用两种：一种是先寻找增广链，然后沿增广链对流进行增广的增广链算法，如ford-fulkerson标记法算法；另一种是将流沿允许弧进行推进，多余的部分返回的预留推进算法，具有代表性的是karzanov首先提出并由goldberg和tarjan改进的预流推进算法。本文主要介绍第一种。另外对于最小费用流问题的方法也可分为两种：一种是从图论角度出发的负回路算法或最小费用路算法；另一种是从最小费用流问题的线性规划模型出发，应用线性规划算法思想给出的对偶算法。本文主要介绍第一种。

国内外学者对网络流问题的研究从未松懈。由于现有算法总是存在这样或那样的局限性，众多学者在主流算法的基础上提出许多改进算法。例如基于容差的概念，针对ford-fulkerson 标记法对增广链选取的任意性，采用的在选取增广链的时候优先选择顶点容差为正的顶点的#8220;容差修正网络最大流2f#8221;算法；另外#8220;消链#8221;算法是基于ford-fulkerson标记法在求解网络最大流的时候需要经过多次的标号与调整的基础上受水流的启发，引入了极大一致链的概念，该算法主要是通过反复寻找并调整极大一致链，并最终求的最大流。除此之外还有其他算法

虽然对网络流问题的研究已经取得极大进展，但是由于现实问题的复杂性，这些理论研究还远远不够，主要是算法不够优化，最大流算法时间复杂性没有精确下界；实际应用方面，许多实际问题得不到解决，实际问题与网络流问题之间的联系与转化很难发现。对此仍需继续努力。

4. 计划与进度安排

2022-12-01-2022-04-20 完成基础材料收集，并确定写作提纲，完成论文初稿；

2022-04-21-2022-05-14 在导师指导下对初稿进行修改；

2022-05-15-2022-06-01 修改后定稿打印，并在导师指导下进行答辩前准备。

5. 参考文献

[1]王志强,孙小军. 网络最大流新算法[j].计算机工程与设计,2009,30(10):2357-2359.

[2]陈静,单锐.容差修正网络最大流2f算法[j].长春工业大学学报,2008,29(6):713-716.

[3]zhangxian-chao. research on the maximum network flow problem[j]. journal of computerresearch and development.2003,40(9):1281-1292.