经济领域中网络最大流问题的求解开题报告

例如,交通网络中要对车辆的最大通过能力进行研究;供水网络中要对水流量进行研究; 信息网络中要对信息传输能力进行研究等等。

显然,这些网络都具有起点(发点)和终点(收点)、且每一弧都有明确的最大通过能力(容量)。

2. 研究内容和预期目标

研究内容：

在求解网络最大流的一个有效方法就是标号法。 其基本思想是从某个可行流出发,若网络图中没有给定可行流f,则可以设f为零流或按可行流的条件给定, 用给顶点标号的方法来构造v,在标号过程中,有标号的顶点表示是v中的点,没有标号的点表示不是v中的点,一 旦v有了标号,表明找到了一条增广链,对此增广链上的流f进行调整,对调整后的可行流重新进行标号,试图寻找新流的增广链。如此反复下去,如果标号过程进行不下去,即v得不到标号,则说明不存在增广链,也就说明已经得到了最大流,并且同时得到一个最小截集。

3. 国内外研究现状

国内学者给出了一种新的求解网络流问题的标号算法,对每个顶点进行标号,顶点有几个入弧,即有几个标号,每次在选择路径时先选取只有一个标号的路径,当所有单标号的路径走完时,再按照弧容量较大且最短的路径选择增广链。通过对Ford-Fulkerson标号算法进行改进,使得该算法容易理解,且又避免了Ford-Fulkerson标号算法在求解网络最大流问题时需经过多次的调整与标号,从而大大提高了求解最大流执行的效率。该算法通过实例给出了具体算法步骤并且表明了算法的实用性。

国外有学者提出求解最小费用流使用复合标号法, 将寻找增广链与求 .费用/最短路同时进行, 思路清晰、算法简捷。由于无须构造新的赋权图 , 避免了出现负权弧的麻烦, 减少了迭代次数和运算时间。当然, 最后应当指出的是：当原网络图中有负权弧出现时, 这种复合标号法也因Dijkstra标号法的失效而失效了

4. 计划与进度安排

2022年11月-12月选题，并确定指导老师；

2022年12月-2022年1月放假前，搜集基础资料，完成开题报告；

2022年1月-3月完成文献翻译，确定论文总体提纲；

5. 参考文献

[1]孙泽宇. 基于标号法求解网络最大流算法的研究[j]. 甘肃联合大学学报（自然科学版）

[2]w. h. moolman. the maximum flow and minimum cost–maximum flow problems: computing and applications[j]. asian journal of probability and statistics, 2020,: 28-57.

[3]张静,邱学绍.网络最大流模型算法及其实现[j].重庆大学学报(自然科学版)