最小费用最大流在线性规划上的推广

最小费用最大流问题是运筹学中的一类典型问题,亦是许多实际问题的本质抽象。此外,最小费用最大流本身可以视为线性规划的一种特殊情况。由于其模型的特殊性和解决方法的特殊性,能够接受的数据规模远比一般线性规划大。对于某些线性规划问题,如果将其转化为最小费用流可以解决的模型,则可大大提高效率。文中针对一现有案例,探讨了用矩阵变化的方法,将一个本不能用最小费用最大流解决的问题巧妙转化为最小费用最大流问题,并从约束矩阵结构和实际问题两个方面给出了该算法的适用范围。

An Generalization of Minimum Cost Flows on Linear Programming

Minimum cost maximum flow is not only a typical problem in operation research, it is also the nature of many practical problem. Besides, minimum cost can be recognized as a special condition for linear programming. Thanks to its particularity both in models and solutions, minimum cost flow can deal with much larger data than linear programming. Thus, if some linear programming problems can be transformed into a minimum cost flow model, the efficiency would grew rapidly. The authors made observations on an instance and worked out a way to use minimum cost flows on liner programming, and gives the conclusion from both two fields.