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

摘要

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