关于几种不平衡指派问题的修正匈牙利解法

关于几种不平衡指派问题的修正匈牙利解法

杜金玲①Du Jinling；周杰②Zhou Jie

【摘要】摘要：本文利用实例验证了在用匈牙利算法求解指派问题时，不平衡的指派问题转化为平衡指派问题的必要性；总结对于几种不平衡的指派问题转化为平衡指派问题的方法，从理论上作出解释，并给出了相应的例题，特别对于任务数多于人数的指派问题，本文提出了新的更有针对性的转化方法，如“一人化成p人法”、“加边补小法”、“加边补零（M）法”等。

【期刊名称】价值工程

【年(卷),期】2010(029)013

【总页数】3

【关键词】指派问题；匈牙利算法；一人化成p人法；加边补小法；加边补零（M）法

0 引言

在实际生活和生产安排中,经常遇到要指派不同的工作人员去完成不同的工作。由于每个人的专长不同,不同的人去完成各项任务的效率(或所花时间或成本等)一般地也不同。这样,就产生了指派何人去完成何任务,使总效率最高（或所花时间最少或成本最低等）的问题。这类问题称为指派问题（Assignment Problem），又称为分配问题。

1 平衡指派问题的数学模型

对于有n项任务且恰好有n个人去完成的指派问题（称为平衡指派问题），规定每人只完成一项任务，且每项任务只能由一个人去完成。已知aij表示第i个人完成第j项任务时的效率（所用时间或成本等），[aij]称为效率矩阵。设决策