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

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

作　　者：熊德国[1] 胡勇文[1] 

机构地区：[1]河南理工大学能源科学与工程学院,河南焦作454000

出　　处：《山东大学学报（理学版）》2012年第3期103-109,共7页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(51074066);河南理工大学博士基金项目(648407);河南理工大学教改重点项目(2009JG042)

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

关 键 词：指派问题 最小费用流问题 对偶原理 互补松驰条件 允许边算法 

分 类 号：O224[理学—运筹学与控制论]