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

匈牙利法解决人数与任务数不等的指派问题于凯重庆科技学院 经济管理学院 物流专业 重庆沙坪坝区摘要： 本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相 等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差 不能超过 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)中每行(列)的最小元素均为“O”，因此 求原指派问题C (ij)的最优方案就等于在新矩阵CB (ij)中找出n个分布于不同行不同 列的“O”元素(简称为“独立O元素”)，这些独立O元素就是CB (ij)的最优解，同 时与其对应的原系数矩阵的最优解1.2匈牙利法的具体步骤第一步：使指派问题的系数矩阵经过变换在各行各列中都出现O元素1) 先将系数矩阵的每行中的每个元素减去本行中的最小元素2) 再从系数矩阵的每列中的每个元素减去本列的最小元素第二步：进行试指派，以寻求最优解1) 从含有O元素个数最少的行(列)开始，给某个O元素加圈，记作◎, 然后划去与◎所在同行(列)杂其他O元素，记作0注：从含元素 少的开始标记◎的原则)(2) 重复进行(1)的操作，直到所有O元素都记作◎或0，称作“礼让原 则”3) 按以上方法操作后，若◎元素数目m'等于矩阵阶数n,那么指派问题最 优解已得到。

若m

元素时，这时可以任选一行（列）中某个O元素，再划去同 行（列）其他O元素这时会出现多重优化解，对应着多种最优的指派方案如果出现此种 情况，各位读者不必疑惑2. 极大化指派问题以上讨论的均限于极小化的指派问题，对于极大化的问题，即求MaxZ = W CXij ij（例如：如何安排n个工程队去完成n个项目才能使总收益最大） 以下是解决该问题的原理部分：可令b = M - c （其中M是原系数矩阵（c ）中最大的元素）则原系数矩阵变换成 j ij新矩阵（b ），这时b > 0，ij j工工b x -工工 （M - c ）x恒成立，ij ij ij iji j i j符合匈牙利法的条件，而且等式所以，当新的系数矩阵取到极小化指派问题的解矩阵时，就对应着原问题的最大化指派方案的最优指派方案3.人员数不等于任务数的指派问题：以上我们讨论的问题均是标准型指派问题，但在实际生活中可能出现人手不够或者任务较少人员较多的情况，该类问题当然也可以利用匈牙 利法求解从以上讨论了匈牙利法的原理可知匈牙利法适用于系数矩阵为方阵的指派问题，从 这个基本原则出发，给系数矩阵并非方阵的问题，添加虚拟人员或任务使其构成标准型 指派问题，从而进一步利用匈牙利法求解最优解，而且构造的方阵的最优解同时也是原 问题的最优解。

3.1 人数大于任务数的指派问题下面结合例子说明人数m大于任务数n的指派问题的解法例】：设有三项任务J T 2、T 3,可以安排的的人为M 2、M 3、M 4去完成，各人完成各项工作所花费的时间C如表3.1所示，问应如何指派所用的总时间ij厂21015413140、0(C )=ij9141601 78110丿第二步:运用匈牙利法求解〔215130 ](011201(C)=ij1041408030914160710501 78110丿15400丿(1000 )T _min=2 ＞已找出四个独立元素故例1的解矩阵为（X ）=ij所以最优指派方案为Mi完成「成T，M完成T，而M没有任务花费总时间最少为min z 2 4 3 3=2+4+11=17（小时）4. 任务数大于人数的指派问题下面结合例2说明任务数n大于人数m的指派问题的解法 C +C11+C22 43例2设有四项任务J T 2、T 3、T4，可以安排三个人M 2、M3去完成’各人完成各项工作所需的时间c如表4.1所示，问应该指派哪个人去完成哪项任务所用的总 ij时间最少？最少？任务时间T1T2T3M121513M210414M391416M47811解：第将问题转化为人数与任务相等的指派问题步：添加M-N个虚拟任务，并赋予各人完成这些虚拟任务的时间为0.此时 （注：本题 M=4, N=3）时间 任务 *、、、、-,T2T3T4M]215134M21041415M39141613解:第一步:添加N-M个虚拟的人员，并赋予各虚拟人员完成各项任务所用的时间为+ g。

此时问题转化成人员与任务数相等的指派问题‘ 100000 '‘ 001000 '010000000001000100或010000001000或100000000010000010.000001,.000100,构造系数矩阵（X i）=第二步：运用匈牙利法求解(C)=ij21513410414159141613gggg0119丿‘0 1360< 011 2'10 1170■-Z"(fe 13 11 2、7 4化

招投标得出工程队A （i=l、2、3）对新楼B （j=i、2、・・・5）的预算费用为C , i j ij见表 4-2，求总费用最小的分派方案项目施工队A——B和B ,3 2 4B2B3B4B5A13871511A279101412A369131217思考：该问题若是直接利用以上添加两位虚拟工程队方法求解，只能先求出3个工程队 各完成1项项目的最优费用，还有2项任务没有工程队承接接下来还要添加1项虚拟 任务，然后进行第二次指派，确定第一次指派剩下来的2项任务由哪两个工程队再次承 接考虑到以上做法较为繁琐，我们寻求一次性寻找出最优指派方案的解法由施工队数3与项目数5的关系考虑到，只有1个施工队承担单个任务，而其他两个施工队均承担2项项目因此我们可以添加一个虚拟项目，以便让每个工程队都可以承担2项项目但又考虑到要一次性指派完成求解，则不能有虚拟工程队，而且利用匈牙利法一定要是方阵才行于是构造如下新系数矩阵C二［c ］ij 6*6解：第一步：将工程队重排一次形成6支工程队，添加一项虚拟项目最终形成方阵构造的系数矩阵c =0或c =3j ij第二步：匈牙利法求解该矩阵的指派问题'38715110 '79。