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

摘要

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