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

匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院经济管理学院物流专业重庆沙坪坝区摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1,其次要求所需总时间最少，并且给出了该类问题的求解方法。关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同：有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短,总费用最少，产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。指派问题的解法——匈牙利法早在1955年库恩(w.w.ku.hn)就提出了指派问题的解法，该方法是以匈牙利数学家康尼格(koning)提出的一个关于矩阵中0元素的定理为基础，因此得俎匈牙利法(TheHungonrianMethodofAssignment)匈牙利解法的基本原理和解题思路直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。而指派问题的最优解又有这样的性质：若从系数矩阵C(ij)的一行(列)各元素都减去该行(列)的最小元素，得到新矩阵CB(ij)，那么以CB(ij)为系数矩阵求得的最优解和原系数矩阵C(ij)求得的最优解相同。由于经过初等变换得到的新矩阵CB(ij)中每行(列)的最小元素均为"O"，因此求原指派问题C(ij)的最优方案就等于在新矩阵CB(ij)中找出n个分布于不同行不同列的"O"元素(简称为“独立O元素”)，这些独立O元素就是CB(ij)的最优解，同时与其对应的原系数矩阵的最优解。匈牙利法的具体步骤第一步：使指派问题的系数矩阵经过变换在各行各列中都出现O元素。先将系数矩阵的每行中的每个元素减去本行中的最小元素。再从系数矩阵的每列中的每个元素减去本列的最小元素。第二步：进行试指派，以寻求最优解。(l)从含有O元素个数最少的行(列)开始，给某个O元素加圈，记作◎,然后划去与◎所在同行(列)杂英他O元素，记作0。(注：从含元素少的开始标记◎的原则)(2)重复进行(1)的操作，直到所有O元素都记作◎或0,称作“礼让原则”。(3)按以上方法操作后，若◎元素数目m'等于矩阵阶数n,那么指派问题最优解已得到。若m<n,则转入下一步。第三步：做最少的直线覆盖所有的O元素，以确定该系数矩阵中能找到最多的独立O元素。(1)对没有◎的行打J号；(2)对已打J号的行中含有0元素所在的列打1号：（3）对已打J号的列中含有◎元素所在的行打J号：（4）重复（2）、（3）直到得不到新J号的行和列为止：（5）对没有V号的行画一横线，有J号的列画一竖线。如此便可以覆盖所有的O元素（注：这里的O元素是指◎或0）第四步：以上画线的目的是为了选取新的最小元素，以便增加O元素，最后达到©元素个数m二n。（1）为此在没有被直线覆盖的所有元素中找出最小元素，然后将没有被直线覆盖的每个元素都减去该最小元素，同时把打“1”的列中的每个元素加上该最小元素，以保证原O元素不变。（2）再按照第二步原则进行选取独立O元素。若得到n个◎元素，则已是该矩阵的最优解（同时也是原矩阵的最优解）；否则，回到第三步重复进行。第五步：在第四步得到的最优解情况下的系数矩阵变换为解矩阵。将系数矩阵中的所有◎都变成元素1，而其他元素均变成0元素，得到的新矩阵便为原指派问题的解矩阵,根据解矩阵中1元素所在的行、列数，去确左派哪个人员去做哪项任务。（注:在解矩阵（乂4）中，Xij=o元素表示不派第i个人去完成第j项任务，XijJ表示指派第i个人去完成第j项任务）需要对匈牙利法的第二步画0行的说明：当指派问题的系数矩阵经过变换得到了同行和同列中都有两个或两个以上。元素时，这时可以任选一行（列）中某个o元素，再划去同行（列）苴他O元素。这时会出现多重优化解，对应着多种最优的指派方案。如果出现此种情况，各位读者不必疑惑。极大化指派问题以上讨论的均限于极小化的指派问题，对于极大化的问题，即求MqyZ=工工（例如：如何安排n个工程队去完成n个项目才能使总收益最大）以下是解决该问题的原理部分：可令bl}=M-cjj（其中M是原系数矩阵（c»）中最大的元素）则原系数矩阵变换成新矩阵（女石），这时＞0，符合匈牙利法的条件，而且等式为为切内二为工（M—q坨恒成立，所以，当新的系数矩阵取到极小化指派问题的•• ••ij ij解矩阵时，就对应着原问题的最大化指派方案的最优指派方案。人员数不等于任务数的指派问题：以上我们讨论的问题均是标准型指派问题，但在实际生活中可能出现人手不够或者任务较少人员较多的情况，该类问题当然也可以利用匈牙利法求解。从以上讨论了匈牙利法的原理可知匈牙利法适用于系数矩阵为方阵的指派问题，从这个基本原则出发，给系数矩阵并非方阵的问题，添加虚拟人员或任务使英构成标准型指派问题，从而进一步利用匈牙利法求解最优解，而且构造的方阵的最优解同时也是原问题的最优解。3.1人数大于任务数的指派问题下而结合例子说明人数m大于任务数n的指派问题的解法。

例1：设有三项任务丁「T「T3，可以安排的的人为M2.M3.“4去完成，各人完成各项工作所花费的时间勺如表3.1所示，问应如何指派所用的总时间1120）10 14141610 141416105 0T—已找出四个独立元素。最少？务时T.T,Ts21513■10114M391116M47811解：第一步：添加M-N个虚拟任务，并赋予各人完成这些虚拟任务的时间为0•此时将问题转化为人数与任务相等的指派问题（注：本题N二3）r2 15 13010414、0(q) 914160<7 811第二步：运用匈牙利法求解11"100010故例010故例1的解矩阵为(Xy)=000<001所以最优指派方案为Mi完成T「Ng完

1°J成T.完成「而卜舄没有任务。花费总时间最少为minz=CH+C22+C43=2+4+11=17（小时）任务数大于人数的指派问题下面结合例2说明任务数n大于人数m的指派问题的解法。、例2设有四项任务T「T2>T3.T「可以安排三个人卜1「M2.M3去完成，各人完成各项工作所需的时间5如表4.1所示，问应该指派哪个人去完成哪项任务所用的总时间最少？

时间任务T,T,T；Mi215134M，■1041415M39141613构造系数矩阵(XH)二00<o第二步：运用匈牙利法求解0000000、00100100000100001>r构造系数矩阵(XH)二00<o第二步：运用匈牙利法求解0000000、00100100000100001>r000或10<000100010000000000100、0100001000,， 15 13 410 4 14 15(q)= 9 14 16 13OO.O0O0；131126010、11\o"CurrentDocument"05 7 4\o"CurrentDocument"<00 00>\o"CurrentDocument"1311 2◎10H119min・ 8◎10112〉 ◎ 3 5 2、0◎二故解矩阵(。’)的解矩阵为(Xry)=1<001r000>此时问题转化成人员与任务数相等的指派问题o对应的原指派问题的方案为：M「完成完成丁2，卜乂完成而任务T3没有‘215134、分配，为了使四项任务都完成，需要进行二次指派。原系数矩阵为1041415,9141613,显然T3列最小元素位于第一行，即口任务让M「做。所以最终指派方案为完成T“「两项，卜【2完成丁2，完成T"所需要的总时间为minz=CI4+C22+C31+C13=4+4+9+13=30(小时)

例3.（2006年北京大学考研题）某房地产公司计划在一住宅小区建5栋不同型号的楼房Bj（j=l.2、・・・5），现有三个工程队A「（i=L2、3），允许每个工程队承接1-2栋楼。招投标得出工程队A,（i=L2、3）对新楼BJ（j=L2、・・-5）的预算费用为q,见表4-2,求总费用最小的分派方案。施A3fB2八B4,B2B4A.3871511A279101412卷69131217思考：该问题若是直接利用以上添加两位虚拟工程队方法求解，只能先求出3个工程队各完成1项项目的最优费用，还有2项任务没有工程队承接。接下来还要添加1项虚拟任务，然后进行第二次指派，确定第一次指派剩下来的2项任务由哪两个工程队再次承接。考虑到以上做法较为繁琐，我们寻求一次性寻找出最优指派方案的解法。由施工队数3与项目数5的关系考虑到，只有1个施工队承担单个任务，而其他两个施工队均承担2项项目。因此我们可以添加一个虚拟项目，以便让每个工程队都可以承担2项项目。但又考虑到要一次性指派完成求解，则不能有虚拟工程队，而且利用匈牙利法一左要是方阵才行。于是构造如下新系数矩阵C=[c.]6.6。解：第一步：将工程队重排一次形成6支工程队，添加一项虚拟项目。最终形成方阵。构造的系数矩阵C疔0或c严第二步：匈牙利法求解该矩阵的指派问题(8779106913(87791069133877910、913151101412、012170151101412012173203¥\o"CurrentDocument"0 0 4 0◎ 2 2 00 5 ◎ 3203¥\o"CurrentDocument"0 0 4 0◎ 2 2 00 5 ◎ 50 ◎ 4 00 2 2 ◎0 5 0 5P(00 3<2\o"CurrentDocument"0 ◎ 4 0 10220、◎◎ 5 0 5 0\o"CurrentDocument"0 0 4 0 10 2 2 ◎ 00 5 ◎ 5 0)\o"CurrentDocument"0100 0对应的两个解矩阵为(&)二0 0 0 0 00 1 0 0 0 11 0 0 0 0 0 则原指派问题最佳的指派方案<00000b<00010 0为Aj—>B］和B3,A,—>8?和B5,A3—>B40第二种方案：Aj—>B］和B3,A2—>B5,A3TB2和B-苴总费用最小为minz=3+7+12+9+12=43（货币单位）5.结束语在整篇论文中主要是讨论如何用匈牙利算法来求解最优指派的问题。而且重点是人数与任务不等的问题的解决，更