最小费用最大双流算法的研究与应用

发布时间：2018-03-20 08:16

本文选题：最小费用最大双流　切入点：余网络　出处：《南京邮电大学》2017年硕士论文　论文类型：学位论文

【摘要】：最小费用最大双流问题具有很大的研究意义,许多网络优化问题都可归为它的特例,如最短路问题、最大流问题、最小费用最大流问题等。随着物流运输的发展,对于以上问题的研究已经满足不了运输行业不断发展的需要,需要迫切的对双费用流问题进行深入研究,研究最小费用最大双流不仅具有理论价值,而且也具有很大的实用价值。本文对于传统的最小费用最大双流算法进行改进,主要成果如下:1.通过对比剩余网络和余网络的区别,提出了一种基于剩余网络的最小费用最大双流算法,该算法避免了在构建剩余网络时,增广路径中有逆流存在引起的混淆。对改进的算法进行推理证明得出算法的正确性,仿真实验的结果证明算法能得到网络的最大双流。2.提出了一种定流值比例的最小双费用流的新算法,在求得的最大双流和最小费用的基础上,调整双流值,在求得定流值比例的同时使其总费用最小。逻辑推理和仿真实验结果均表明,所提出的算法可行、有效,能较好地解决稀疏网络以及复杂网络中定流值比例的最小双费用流问题。3.发现了一种最小费用流的新算法,新算法首先利用改进的Dijkstra算法搜索出从源点至汇点的所有费用路径,并且在余网络中增广流值,由于余网络比剩余网络构造简单,所以最终提高了算法的时间效率。仿真实验结果表明新算法较复杂网络更适用于稀疏网络。4.一种最小费用流的新算法应用于容量-费用双流网络中,从而得到一种求解最小双费用流的新算法,并通过实例验证算法是有效的。
[Abstract]:The minimum cost maximum double flow problem is of great significance, and many network optimization problems can be classified as its special cases, such as the shortest path problem, the maximum flow problem, the minimum cost maximum flow problem and so on. The research on the above problems can not meet the needs of the continuous development of the transportation industry. It is urgent to study the double cost flow problem. The research on the minimum cost maximum double flow is not only of theoretical value. It is also of great practical value. This paper improves the traditional two-stream algorithm with minimum cost and maximum cost. The main results are as follows: 1. By comparing the difference between residual network and residual network, In this paper, a two-flow algorithm with minimum cost and maximum cost based on residual network is proposed. The algorithm avoids the confusion caused by the countercurrent in the augmented path when the residual network is constructed. The reasoning of the improved algorithm proves the correctness of the algorithm. The simulation results show that the algorithm can get the maximum double flow of the network. 2. A new algorithm of minimum double cost flow with constant flow value ratio is proposed, which adjusts the double flow value on the basis of the obtained maximum double flow and minimum cost. At the same time, the proportion of constant flow value is obtained and the total cost is minimized. The results of logical reasoning and simulation experiments show that the proposed algorithm is feasible and effective. A new algorithm of minimum cost flow is found. The improved Dijkstra algorithm is used to search all the cost paths from the source point to the meeting point. And the value of current is increased in the redundant network, because the redundant network is easier to construct than the residual network. The simulation results show that the new algorithm is more suitable for sparse networks than complex networks. A new algorithm with minimum cost flows is applied to capacity-cost two-stream networks. A new algorithm for solving the minimum double cost flow is obtained, and an example is given to verify the effectiveness of the algorithm.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】