基于最小费用最大流问题的“排序”算法

摘要

Due to the limitations of existing solving the minimum cost and maximum flow method,in order to better solve practical problems, propose a algorithm to solve the problem of the minimum cost and maximum flow based on the existing shortest path algorithm and minimum cost algorithm. A simple algorithm to solve the problem of the shortest path between two points in a small-scale networks is discussed. Moreover,the algorithm can be finished in a graph,so can save a lot of drawing time,improve the algorithm's intuition and controllability. And design a network model of oil transportation,then combining with the minimum cost and maximum flow algorithm, give the best scheme of transportation from the origin to the market,at last validate the efficiency and practicability of the method through concrete models.%由于现有的求解最小费用最大流问题的方法都存在其局限性,为了更好地解决实际问题,在已有最短路算法以及最小费用算法的基础上作了改进,给出了一种求解基于最大流的最小费用问题的算法.文中针对小规模网络给出求两点之间最小费用的一种简单易行的方法,此外该算法可以在一个图上完成,这样可以节省许多画图时间,增强了算法的直观性和可控性.并且构建石油运输的网络模型,结合最小费用最大流算法,给出该模型从产地到销地的最优运输方案,最后通过具体的模型实例验证了该方法的效率和实用性.