不可分流网络的最小费用流问题  

Minimum cost flow problem in indecomposable flow network

作　　者：曹卫锋 梅霞[2] 张兴永[3] 

机构地区：[1]扬州大学,江苏扬州225000 [2]江苏农林职业技术学院基础部,江苏镇江212400 [3]中国矿业大学理学院,江苏徐州221008

出　　处：《现代电子技术》2018年第1期97-100,共4页Modern Electronics Technique

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

关 键 词：节点 最小费用流 不可分流 弧上限 最小费用路径 流值排序 

分 类 号：O22[理学—运筹学与控制论]