【摘要】 通常情况下单位流量费用最小的那条路径发送各个流总费用是最小的,但是往往单位流量费用最小的那条路径并不一定能满足所有流均可通过。针对不可分流的网络流最小费用问题,提出按流值排序寻求最优解的算法,并给出相关的理论证明及算法,最后通过具体实验测试了该算法的有效性。此算法可以快速求解所提的问题,并能够算出最优值。实例结果表明,该算法有效地解决了不可分流的网络流最小费用问题,可以应用于实际的网络优化中。更多还原

【Abstract】 The total flow cost is minimum when each flow is sent through the path with minimum unit flow cost. But the path with minimum unit flow cost doesn′t necessarily meet that all flows can be passed. Aiming at the minimum cost flow problem of the indecomposable flow network,an algorithm for optimal solution seeking by means of flow value ranking is proposed,and its relative theoretical proof and algorithm are given. The validity of the algorithm was tested with the specific experiment.THe algorithm can solve the proposed problem quickly,and get the optimal value. The results of the practical example show that the algorithm can solve the minimum cost flow problem of the indecomposable flow network effectively,and is applied to the actual network optimization.更多还原