最小费用增益流

本文研究了具有分段线性费用的最小费用增益流问题。由于求满足边界条件的最短轨问题是NP完全问题[4,5],因此我们采用了线性规划的方法。本文提出了一系列与分段线性费用相对应的定理和概念,在此基础之上描述了一个初始对偶算法,它是Jewell算法[3]的自然推广,它完善了初始化的算法,是有效的, 计算复杂度为o((m n)~3n)。