匈牙利法解决人数与任务数不等的指派问题1

匈牙利法解决人数与任务数不等的指派问题 于凯

重庆科技学院 经济管理学院 物流专业 重庆沙坪坝区

摘要： 本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。 关键词： 运筹学 指派问题 匈牙利算法 系数矩阵 解矩阵

引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。 1. 指派问题的解法——匈牙利法

早在1955年库恩（w.w.ku.hn）就提出了指派问题的解法，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment） 1.1 匈牙利解法的基本原理和解题思路 直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。

而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。

由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。 1.2 匈牙利法的具体步骤

第一步：使指派问题的系数矩阵经过变换在各行各列中都出现○元素。 （1） 先将系数矩阵的每行中的每个元素减去本行中的最小元素。 （2） 再从系数矩阵的每列中的每个元素减去本列的最小元素。

第二步：进行试指派，以寻求最优解。

（1） 从含有○元素个数最少的行（列）开始，给某个○元素加圈，记作◎，

然后划去与◎所在同行（列）杂其他○元素，记作。（注：从含元素少的开始标记◎的原则） （2） 重复进行（1）的操作，直到所有○元素都记作◎或，称作“礼让原

则”。

（3） 按以上方法操作后，若◎元素数目m’等于矩阵阶数n，那么指派问题最

优解已得到。若m﹤n，则转入下一步。

第三步： 做最少的直线覆盖所有的○元素，以确定该系数矩阵中能找到最多的独立○元素。

（1） 对没有◎的行打√号；

（2） 对已打√号的行中含有元素所在的列打√号； （3） 对已打√号的列中含有◎元素所在的行打√号；

（4） 重复（2）、（3）直到得不到新√号的行和列为止；

（5） 对没有√号的行画一横线，有√号的列画一竖线。如此便可以覆盖所有

的○元素（注：这里的○元素是指◎或）

第四步：以上画线的目的是为了选取新的最小元素，以便增加○元素，最后达到◎元素个数m=n。

（1） 为此在没有被直线覆盖的所有元素中找出最小元素，然后将没有被直

线覆盖的每个元素都减去该最小元素，同时把打“√”的列中的每个元素加上该最小元素，以保证原○元素不变。

（2） 再按照第二步原则进行选取独立○元素。若得到n个◎元素，则已是

该矩阵的最优解（同时也是原矩阵的最优解）；否则，回到第三步重复进行。

第五步：在第四步得到的最优解情况下的系数矩阵变换为解矩阵。将系数矩阵中的所有◎都变成元素1，而其他元素均变成0元素，得到的新矩阵便为原指派问题的解矩阵，根据解矩阵中1元素所在的行、列数，去确定派哪个人员去做哪项任务。（注：在解矩阵（Xij）中，Xij=0元素表示不派第i个人去完成第j项任务，Xij=1表示指派第i个人去完成第j项任务）

需要对匈牙利法的第二步画行的说明：当指派问题的系数矩阵经过变换得到了同行和同列中都有两个或两个以上○元素时，这时可以任选一行（列）中某个○元素，再划去同行（列）其他○元素。这时会出现多重优化解，对应着多种最优的指派方案。如果出现此种情况，各位读者不必疑惑。 2. 极大化指派问题

以上讨论的均限于极小化的指派问题，对于极大化的问题，即求MaxZ(例如：如何安排n个工程队去完成n个项目才能使总收益最大) 以下是解决该问题的原理部分：

可令 bijMcij（其中M是原系数矩阵（cij）中最大的元素）则原系数矩阵变换成新矩阵（bij），这时bij0，符合匈牙利法的条件，而且等式

C

ij

Xij

bx(Mc)x恒成立，所以，当新的系数矩阵取到极小化指派问题的

ijij

ij

ij

i

j

i

j

解矩阵时，就对应着原问题的最大化指派方案的最优指派方案。

3. 人员数不等于任务数的指派问题：以上我们讨论的问题均是标准型指派问题，但在实际

生活中可能出现人手不够或者任务较少人员较多的情况，该类问题当然也可以利用匈牙利法求解。

从以上讨论了匈牙利法的原理可知匈牙利法适用于系数矩阵为方阵的指派问题，从这个基本原则出发，给系数矩阵并非方阵的问题，添加虚拟人员或任务使其构成标准型指派问题，从而进一步利用匈牙利法求解最优解，而且构造的方阵的最优解同时也是原问题的最优解。

3.1 人数大于任务数的指派问题

下面结合例子说明人数m大于任务数n的指派问题的解法。

例1：设有三项任务1、2、3，可以安排的的人为1、2、3、4去完成，各人完成各项工作所花费的时间cij如表3.1所示，问应如何指派所用的总时间

解：第一步：添加M-N个虚拟任务，并赋予各人完成这些虚拟任务的时间为0.此时将问题转化为人数与任务相等的指派问题（注：本题M=4，N=3）

215130104140 (Cij)

91416078110

第二步：运用匈牙利法求解

215130011201041408030min2(Cij)已找出四个独立元素。914160710507811054001

0故例1的解矩阵为(Xij)00

000



100

所以最优指派方案为1完成1，2完

001



010

成2，4完成3，而3没有任务。花费总时间最少为min z=C11+C22+C43

=2+4+11=17(小时)

4. 任务数大于人数的指派问题

下面结合例2说明任务数n大于人数m的指派问题的解法。、

例2 设有四项任务1、2、3、4，可以安排三个人1、2、3去完成，各人完成各项工作所需的时间cij如表4.1所示，问应该指派哪个人去完成哪项任务所用的总时间最少？

解：第一步：添加N-M个虚拟的人员，并赋予各虚拟人员完成各项任务所用的时间为+。 此时问题转化成人员与任务数相等的指派问题。

100

构造系数矩阵（Xij）=

000000000



100000001000

或

010001000100

00001001000



0000110000



0000000010



00100

第二步：运用匈牙利法求解

215134

1041415(Cij)

9141613013112

601011

05740000

001



100

000

010

119◎08◎1011min2故解矩阵(C)的解矩阵为(X)0ijij◎35212◎0

对应的原指派问题的方案为：1完成4，2完成2，3完成1。而任务3没有

215134



分配，为了使四项任务都完成，需要进行二次指派。原系数矩阵为1041415，

9141613

显然3列最小元素位于第一行，即3任务让1做。所以最终指派方案为1完成3、

4两项，2完成2，3完成1。

所需要的总时间为min z=C14C22C31C134+4+9+13=30 (小时)

例3.（2006年北京大学考研题）某房地产公司计划在一住宅小区建5栋不同型号的楼房

···5），现有三个工程队i（i=1、2、3），允许每个工程队承接1—2栋j（j=1、2、

楼。招投标得出工程队i （i=1、2、3）对新楼j（j=1、2、···5）的预算费用为Cij，见表4-2，求总费用最小的分派方案。

思考：该问题若是直接利用以上添加两位虚拟工程队方法求解，只能先求出3个工程队

各完成1项项目的最优费用，还有2项任务没有工程队承接。接下来还要添加1项虚拟任务，然后进行第二次指派，确定第一次指派剩下来的2项任务由哪两个工程队再次承接。考虑到以上做法较为繁琐，我们寻求一次性寻找出最优指派方案的解法。

由施工队数3与项目数5的关系考虑到，只有1个施工队承担单个任务，而其他两个施工队均承担2项项目。因此我们可以添加一个虚拟项目，以便让每个工程队都可以承担2项项目。但又考虑到要一次性指派完成求解，则不能有虚拟工程队，而且利用匈牙利法一定要是方阵才行。于是构造如下新系数矩阵C[cij]6*6。

解：第一步：将工程队重排一次形成6支工程队，添加一项虚拟项目。最终形成方阵。构造的系数矩阵cij=0或cij=

第二步：匈牙利法求解该矩阵的指派问题

376[cij]

376

87

9109138

7910913

15110



1412012170



1511014120



12170

min1



◎3232

◎

2

424

55

5◎25

◎

2◎[***********]

100

（Xij）=

000

13

2或1◎

32◎000

000000

或001100

0101



22◎◎55

对应的两个解矩阵为

4122◎



5◎501000



0000110000

则原指派问题最佳的指派方案

0000000010



00100

◎4

22和5，34。11和3，25，为11和3，第二种方案：32和4。其总费用最小为min z=3+7+12+9+12=43 （货币单位）

5. 结束语

在整篇论文中主要是讨论如何用匈牙利算法来求解最优指派的问题。而且重点是人数与任务不等的问题的解决，更重要的方面是引进虚拟任务或人数构造方阵的思想。但各位

学者应注意引入虚拟任务或人员后对应的cij的值得确定。(cij=0或cij=要根据题目的实际意义确定) 对于例3类型问题的做法是更优于两次指派的求解方法，但对于例2进行两次指派却要比例3的方法更快捷。读者们若要快速有效的寻求出人数与任务数不等的指派问题的最优指派方案，还要根据具体问题中的人员数与任务数的相差数来决定。因此建议各位读者多多思考练习，以便灵活运用匈牙利法解决各类指派问题。