用最小费用流的允许边算法求解指派问题

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

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。

A new algorithm of the assignment problem is proposed by constructing its minimum cost maximum flow model and applying the permissible-edge algorithm based on the principle of duality to the model. The new algorithm gradually expands the permissible network in the capacity-cost network by means of modifying the potential of labeled nodes subject to complementary slackness condition, and then augments flows on the permissible network, which pro- ceeds until the minimum cost maximum flow of the original capacity-cost network is obtained. The non-zero edge of this maximum flow corresponds to the optimal solution of the assignment problem. During the iterating process, succes- sive iteration will fully use the information of previous ones, which effectively reduces the computation. For non-stand- ard assignment problems, this algorithm can be directly applied without converting the problem to the standard form.