关键词: 双费用权网络, 最小双费用流, 双层原始对偶算法, 复杂度

Abstract:

Multi-objective optimization is a critical part of network optimization. The paper derives a minimum doublecost flow problem in double-cost network model with limitations on capacity from a practical case. According to the thought of hierarchy and the feature of double-cost network, the corresponding minimum double-cost flow problem is introduced and a two-layer primaldual algorithm is proposed to solve it. The correctness of our algorithm is proved and its complexity is estimated as  O(n2v0). Besides, the algorithm is improved to solve the minimum kcost flow problem in k-cost network. Finally, a case is used to exhibit how the algorithm works.

Key words: double-cost network;minimum double-cost flow;two-layer primaldual algorithm;complexity