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

【Abstract】 This paper studies the problem of the Minimum Cost Flows in a Network with Gains,in which each edge’s cost is the piecewise-linear cost. Since the problem of finding the shortest path subject to side constraints is HP-complete, we suggest and describe a Primal-Dual Simplex Algorithm for Solving it.It is a natural generalization of Jewell’s Algorithm [3],and perfects iaitializatioa of the algorithm.It is effective.It’s computational complexity is O((m + n) 3n) .更多还原