点和边有容量约束的网络最小费用最大流算法

摘要：

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法.概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念.依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法.该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流.最后,通过实例进行了算法测试和比较.算法测试表明:点和边有容量约束的网络最小费用最大流算法是完全可行和有效的.

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

所属期刊栏目：27

分类号：TP301.6(计算技术、计算机技术)

资助基金：陕西省自然科学基金资助项目2009JM7007;陕西省教育厅专项科研计划资助项目08JK354

在线出版日期：2010-09-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：3112-3114,3119