中文摘要：

构造指派问题的最小费用最大流模型，并将基于对偶原理的允许边算法用于该模型，提出了求解指派问题的一种新算法。该算法按照互补松驰条件，通过修改已标号节点的势，在容量一费用网络中逐步扩大允许网络，并在其中增广流量，直至求得容量一费用网络的最小费用最大流，此最大流中的非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.