首页 | 本学科首页   官方微博 | 高级检索  
     

点和边有容量约束的网络最小费用最大流算法*
引用本文:厍向阳.点和边有容量约束的网络最小费用最大流算法*[J].计算机应用研究,2010,27(8):3112-3154.
作者姓名:厍向阳
作者单位:西安科技大学,计算机科学与技术学院,西安,710054
基金项目:陕西省自然科学基金资助项目(2009JM7007);陕西省教育厅专项科研计划资助项目(08JK354)
摘    要:分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明:点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。

关 键 词:网络最小费用最大流    邻接矩阵    容量约束    残量网络

Min-cost and max-flow algorithm of network with both node and edge capacity confined
SHE Xiang-yang.Min-cost and max-flow algorithm of network with both node and edge capacity confined[J].Application Research of Computers,2010,27(8):3112-3154.
Authors:SHE Xiang-yang
Abstract:This paper analyzed the characteristic and type of the min-cost and max-flow algorithm in network, put forward the new min-cost and max-flow algorithm of network with both node and edge capacity confined. It generated the two-objective optimizing model of min-cost and max-flow in network,facing the characteristic of min-cost and max-flow of network with node and edge capacity confined, defined the orientation path and residual network, carried out the new min-cost and max-flow algorithm of network with both node and edge capacity confined, with adjacency matrix to deposit data, being based on feasible flow decompose theorem, by the way of the traversing in data structure. In the end, validated and compared the algorithm by examples. Algorithm testing shows that the new min-cost and max-flow algorithm of network with both node and edge capacity confined is completely feasible and availability.
Keywords:min-cost and max-flow of network  adjacency matrix  confined capacity  residual network
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机应用研究》浏览原始摘要信息
点击此处可从《计算机应用研究》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号