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

《匈牙利法解决人数及任务数不等的指派问题》由会员分享，可在线阅读，更多相关《匈牙利法解决人数及任务数不等的指派问题（6页珍藏版）》请在装配图网上搜索。

1、匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院 经济管理学院 物流专业 重庆沙坪坝区摘要： 本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。关键词： 运筹学 指派问题 匈牙利算法 系数矩阵 解矩阵 引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担

2、来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。1. 指派问题的解法匈牙利法早在1955年库恩（w.w.ku.hn）就提出了指派问题的解法，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment）1.1 匈牙利解法的基本原理和解题思路 直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。 而指派问题的最优解又有这样的性

3、质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。 由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“”元素（简称为“独立元素”），这些独立元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。1.2 匈牙利法的具体步骤第一步：使指派问题的系数矩阵经过变换在各行各列中都出现元素。（1） 先将系数矩阵的每行中的每个元素减去本行中的最小元素。（2）

4、再从系数矩阵的每列中的每个元素减去本列的最小元素。 第二步：进行试指派，以寻求最优解。（1） 从含有元素个数最少的行（列）开始，给某个元素加圈，记作，然后划去与所在同行（列）杂其他元素，记作。（注：从含元素少的开始标记的原则）（2） 重复进行（1）的操作，直到所有元素都记作或，称作“礼让原则”。（3） 按以上方法操作后，若元素数目m等于矩阵阶数n，那么指派问题最优解已得到。若mn，则转入下一步。 第三步： 做最少的直线覆盖所有的元素，以确定该系数矩阵中能找到最多的独立元素。（1） 对没有的行打号；（2） 对已打号的行中含有元素所在的列打号；（3） 对已打号的列中含有元素所在的行打号；（4） 重

5、复（2）、（3）直到得不到新号的行和列为止；（5） 对没有号的行画一横线，有号的列画一竖线。如此便可以覆盖所有的元素（注：这里的元素是指或） 第四步：以上画线的目的是为了选取新的最小元素，以便增加元素，最后达到元素个数m=n。（1） 为此在没有被直线覆盖的所有元素中找出最小元素，然后将没有被直线覆盖的每个元素都减去该最小元素，同时把打“”的列中的每个元素加上该最小元素，以保证原元素不变。（2） 再按照第二步原则进行选取独立元素。若得到n个元素，则已是该矩阵的最优解（同时也是原矩阵的最优解）；否则，回到第三步重复进行。 第五步：在第四步得到的最优解情况下的系数矩阵变换为解矩阵。将系数矩阵中的所有

6、都变成元素1，而其他元素均变成0元素，得到的新矩阵便为原指派问题的解矩阵，根据解矩阵中1元素所在的行、列数，去确定派哪个人员去做哪项任务。（注：在解矩阵（）中，Xij=0元素表示不派第i个人去完成第j项任务，Xij=1表示指派第i个人去完成第j项任务） 需要对匈牙利法的第二步画行的说明：当指派问题的系数矩阵经过变换得到了同行和同列中都有两个或两个以上元素时，这时可以任选一行（列）中某个元素，再划去同行（列）其他元素。这时会出现多重优化解，对应着多种最优的指派方案。如果出现此种情况，各位读者不必疑惑。2. 极大化指派问题以上讨论的均限于极小化的指派问题，对于极大化的问题，即求(例如：如何安排n个

7、工程队去完成n个项目才能使总收益最大)以下是解决该问题的原理部分： 可令 （其中M是原系数矩阵（）中最大的元素）则原系数矩阵变换成新矩阵（），这时0，符合匈牙利法的条件，而且等式恒成立，所以，当新的系数矩阵取到极小化指派问题的解矩阵时，就对应着原问题的最大化指派方案的最优指派方案。3. 人员数不等于任务数的指派问题：以上我们讨论的问题均是标准型指派问题，但在实际生活中可能出现人手不够或者任务较少人员较多的情况，该类问题当然也可以利用匈牙利法求解。 从以上讨论了匈牙利法的原理可知匈牙利法适用于系数矩阵为方阵的指派问题，从这个基本原则出发，给系数矩阵并非方阵的问题，添加虚拟人员或任务使其构成标准型

8、指派问题，从而进一步利用匈牙利法求解最优解，而且构造的方阵的最优解同时也是原问题的最优解。3.1 人数大于任务数的指派问题下面结合例子说明人数m大于任务数n的指派问题的解法。例1：设有三项任务、，可以安排的的人为、去完成，各人完成各项工作所花费的时间如表3.1所示，问应如何指派所用的总时间最少？任务时间2151310414914167811解：第一步：添加M-N个虚拟任务，并赋予各人完成这些虚拟任务的时间为0.此时将问题转化为人数与任务相等的指派问题（注：本题M=4，N=3）第二步：运用匈牙利法求解已找出四个独立元素。故例1的解矩阵为所以最优指派方案为完成，完成，完成，而没有任务。花费总时间最

9、少为min z=+=2+4+11=17(小时)4. 任务数大于人数的指派问题下面结合例2说明任务数n大于人数m的指派问题的解法。、例2 设有四项任务、，可以安排三个人、去完成，各人完成各项工作所需的时间如表4.1所示，问应该指派哪个人去完成哪项任务所用的总时间最少？时间 任务21513410414159141613解：第一步：添加N-M个虚拟的人员，并赋予各虚拟人员完成各项任务所用的时间为+。 此时问题转化成人员与任务数相等的指派问题。构造系数矩阵第二步：运用匈牙利法求解故解矩阵的解矩阵为对应的原指派问题的方案为：完成，完成，完成。而任务没有分配，为了使四项任务都完成，需要进行二次指派。原系数

10、矩阵为，显然列最小元素位于第一行，即任务让做。所以最终指派方案为完成、两项，完成，完成。所需要的总时间为min z=4+4+9+13=30 (小时)例3.（2006年北京大学考研题）某房地产公司计划在一住宅小区建5栋不同型号的楼房（j=1、2、···5），现有三个工程队（i=1、2、3），允许每个工程队承接12栋楼。招投标得出工程队 （i=1、2、3）对新楼（j=1、2、···5）的预算费用为，见表4-2，求总费用最小的分派方案。 项目施工队38715117910141269131217思考：该问题若是直接利用以上添加两位虚拟工程队方

11、法求解，只能先求出3个工程队各完成1项项目的最优费用，还有2项任务没有工程队承接。接下来还要添加1项虚拟任务，然后进行第二次指派，确定第一次指派剩下来的2项任务由哪两个工程队再次承接。考虑到以上做法较为繁琐，我们寻求一次性寻找出最优指派方案的解法。由施工队数3与项目数5的关系考虑到，只有1个施工队承担单个任务，而其他两个施工队均承担2项项目。因此我们可以添加一个虚拟项目，以便让每个工程队都可以承担2项项目。但又考虑到要一次性指派完成求解，则不能有虚拟工程队，而且利用匈牙利法一定要是方阵才行。于是构造如下新系数矩阵。解：第一步：将工程队重排一次形成6支工程队，添加一项虚拟项目。最终形成方阵。构造

12、的系数矩阵第二步：匈牙利法求解该矩阵的指派问题对应的两个解矩阵为则原指派问题最佳的指派方案为，。第二种方案：，。其总费用最小为min z=3+7+12+9+12=43 （货币单位）5. 结束语在整篇论文中主要是讨论如何用匈牙利算法来求解最优指派的问题。而且重点是人数与任务不等的问题的解决，更重要的方面是引进虚拟任务或人数构造方阵的思想。但各位学者应注意引入虚拟任务或人员后对应的的值得确定。(要根据题目的实际意义确定) 对于例3类型问题的做法是更优于两次指派的求解方法，但对于例2进行两次指派却要比例3的方法更快捷。读者们若要快速有效的寻求出人数与任务数不等的指派问题的最优指派方案，还要根据具体问题中的人员数与任务数的相差数来决定。因此建议各位读者多多思考练习，以便灵活运用匈牙利法解决各类指派问题。6 / 6文档可自由编辑打印