一种新的非线性最小费用网络流算法

New nonlinear minimum cost network flow algorithm

为求解非线性可分凸费用网络流问题，提出了一种原始对偶算法，并证明了算法的收敛性。该算法可从任意满足节点流量平衡条件但不一定可行的初始解处开始计算，且能方便地处理目标函数的一阶导数有第一类间断点凸规划问题。用７５０节点和５０１０条弧的网络对本算法作了测试，计算结果说明算法有较高的效率。本算法已被用于实际电网水火联合经济调度问题中，实践证明算法是正确和有效的。

This paper presented a new algorithm that is capable of solving network flow problem with convex separable costs. This algorithm could be begun with any circulation, feasible or not, provided node conservation conditions are satisfied. Also, it could deal with upper and lower bounds on the variables easily and has good convergence. Tests with networks of more than 700 nodes and 5000 arcs have been performed. The results have demonstrated the high efficiency of the code.