总流量可变的最小费用流问题及其求解

Min-cast Flow Problem with Variable Total Flow-value and Its Solution

讨论在总流量可变动的情况下 ,网络最小费用流问题的解法。分别就单源单汇和多源多汇情况构造不同的辅助网络 ,将原网络中的最小费用流问题转化为辅助网络中的最小费用循环流问题 ,然后用瑕疵算法求最小费用循环流问题的最优解 ,这样在求出原网络中最小费用流的同时 ,也获得了总流量的最优取值 .

In this paper ,we have discussed how to solve the min-cost network flow problem with variable total flow value.The single source and single sink network and the multiple sources and multiple sinks network are considered,respectively. We first construct an auxiliary network and convert the min-cost flow problem in origial network into the min-cost circulation problem in the auxilary network,and then find the optimal solution of min-cost circulation problem in the auxiliary network by using out-of-kiltem algorithm.