用最小费用流的允许边算法求解运输问题

A new method for solving the transportation problem based on the permissible-edge algorithm of minimum cost flow problem

将最小费用流的允许边算法运用于运输问题,提出了求解运输问题的一种新解法。构造运输问题的最小费用最大流模型,并用允许边算法求得容量-费用网络的最小费用最大流,此最大流对应于运输问题的最优调运方案。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量;对于非标准运输问题,可以直接求解,而不需要先将其转化为标准形式。

A new method for the transportation problem is proposed by applying the permissible-edge algorithm to its minimum cost maximum flow model. First, it constructs the minimum cost maximum flow model for a transportation problem. Then uses the permissible-edge algorithm until the minimum cost maximum flow of the original capacity-cost network is obtained. This maximum flow corresponds to the optimal solution of the trans- portation problem. During the iterating process, successive iteration will fully use the information of previous ones ,which effectively reduces the computation. For non-standard transportation problems, this algorithm can be directly applied without converting a problem to its standard form.