您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(理学版)》

J4 ›› 2012, Vol. 47 ›› Issue (3): 103-109.

• 数学 • 上一篇    下一篇

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

熊德国,胡勇文   

  1. 河南理工大学能源科学与工程学院, 河南 焦作 454000
  • 收稿日期:2011-05-06 出版日期:2012-03-20 发布日期:2012-04-01
  • 作者简介:熊德国(1964- ),男,教授,博士,主要从事运筹学、系统工程的教学及研究. Email: xiongdg@hpu.edu.cn
  • 基金资助:

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

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

XIONG De-guo, HU Yong-wen   

  1. School of Energy Science and Engineering, Henan Polytechnic University, Jiaozuo 454000, Henan, China
  • Received:2011-05-06 Online:2012-03-20 Published:2012-04-01

摘要:

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

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

Abstract:

 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 proceeds 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, successive iteration will fully use the information of previous ones, which effectively reduces the computation. For non-standard assignment problems, this algorithm can be directly applied without converting the problem to the standard form.

Key words: assignment problem; minimum cost flow problem; principle of duality; complementary slackness conditions; permissible edge algorithm

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!