匈牙利算法在企业员工指派问题的应用

《匈牙利算法在企业员工指派问题的应用》由会员分享，可在线阅读，更多相关《匈牙利算法在企业员工指派问题的应用（29页珍藏版）》请在装配图网上搜索。

1、闽江学院本科毕业论文题 目 匈牙利算法在企业员工指派问题的应用 学生姓名 张雯 学 号 120080901139 系 别 数学系 年 级 2008级 专 业 数学及应用数学 指导教师 林耿 职 称 讲师 完成日期 2012年4月10日 闽江学院毕业论文诚信声明书本人郑重声明：兹提交的毕业论文(设计) 匈牙利算法在企业员工指派问题的应用,是本人在指导老师 林耿 的指导下独立研究、撰写的成果；论文(设计)未剽窃、抄袭他人的学术观点、思想和成果,未篡改研究数据,论文(设计)中所引用的文字、研究成果均已在论文(设计)中以明确的方式标明；在毕业论文(设计)工作过程中,本人恪守学术规范,遵守学校有关规定,

2、依法享有和承担由此论文(设计)产生的权利和责任.声明人(签名)：2012年4月10日摘要在当今社会，竞争无处不在，企业的竞争也是如此.而员工指派问题又是企业不得不面对的问题.因此，企业员工指派问题就显得非常重要了，谁能够在这方面做的好，谁就能在竞争中多一分胜算.企业员工指派问题是指企业安排若干人员去完成若干项任务（任务和人数不一定相等），并且要求完成的效率最高.对于这一问题，匈牙利算法就是一个很好的解法.本文首先给出企业员工指派问题的数学模型，它分为两大类，一类是标准指派问题（即企业指派员工数及任务数相等），另一类是非标准指派问题（即企业指派员工数及任务数不相等），其次，在对匈牙利算法及其原理

3、深入理解的基础上，利用匈牙利算法对企业员工指派问题的数学模型进行求解.其中，用标准的匈牙利算法求解标准的指派问题，对于非标准的指派问题，先把它进行适当的变换，然后用标准的匈牙利算法求解.再次，讲述了匈牙利算法的一些缺点及其改进，把匈牙利算法用C语言表示出来，并把它运用到实际的企业员工指派问题当中.最后，讲述了匈牙利算法的应用推广.关键词：匈牙利算法;员工指派问题;运筹学;效益矩阵Abstract In modern society, competition exists everywhere, so does the competition among enterprises. Staff a

4、ssignment is of great importance to enterprises. Those who do well in it will get more chances to win in the competition. Enterprise staff assignment is that enterprises assign a number of employees to accomplish some tasks in high efficiency ( The number of tasks is not necessarily equivalent to th

5、at of assigned staff ).To solve this problem, the hungary algorithm is the best choice. In this thesis, the author firstly illustrates the enterprise staff assignment, which includes normal assignment problem and abnormal assignment problem. Secondly, the author solves the enterprise staff assignmen

6、t with the hungary algorithm in two ways: one is normal hungary algorithm used to solve the normal assignment problem, the other is abnormal hungary algorithm used to solve the abnormal assignment problem. Thirdly, the author points out some defects and offers some improvements of the hungary algori

7、thm, and write it in C language. At last, the author gives some examples of the application of the hungary algorithm.Key words：hungary algorithm ;staff assignment problem; Operations Research; profit matrix目 录1. 引言12.指派问题的数学模型12.1 指派问题12.2指派问题的数学模型23.匈牙利算法的基本原理及解题步骤23.1 匈牙利算法的基本原理23.2匈牙利算法的解题步骤34.匈牙

8、利算法求解员工指派问题的模型假设及符号说明34.1 匈牙利算法解员工指派问题的模型假设44.2 符号说明45.企业员工指派问题的模型建立及求解45.1标准指派问题（当m=n时，即为每个人都被指派一项任务）45.2非标准指派问题66.匈牙利算法的缺点、改进以及C语言实现126.1 匈牙利算法的缺点126.2 匈牙利算法的改进146.3 匈牙利算法的C语言实现（附录）157.匈牙利算法的应用推广158.结束语17参考文献18附录19致谢2223 / 29匈牙利算法在企业员工指派问题的应用张雯（闽江学院 数学系；福建 福州 350108）1. 引言当今社会，人力资源规划在企业人力资源管理活动中具有重

9、要的地位和作用.人力资源规划是指为实施企业的发展战略，完成企业的生产经营目标，根据企业内外环境和条件的变化，运用科学的方法，使企业的人力资源和需求达到平衡，实现人力资源的合理配置，有效激励员工的过程.而企业员工指派问题在人力资源规划中又是必不可少的，为了使人力资源管理的“大才大用，小才小用，人尽其才，岗得其人，能位匹配”的基本原则得以实现.因此，企业员工指派问题就显得很重要了，而匈牙利算法就是求解人员及工作任务配置合理化、科学化的一个好方法.“匈牙利算法”最早是由匈牙利数学家考尼格（D.Koning）用来求矩阵中0元素的个数的一种方法，由此他证明了“矩阵中独立0元素的最多个数等于能覆盖所有0元

10、素的最少直线数”.1955年由库恩（W.W.Kuhn）在求解著名的指派问题时引用了这一结论，并对具体算法做了改进，仍然称为“匈牙利算法”.解指派问题的匈牙利算法是从这样一个明显的事实出发的：如果效率矩阵的所有元素，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的，其余的，则就是问题的最优解.2.指派问题的数学模型2.1 指派问题从运筹学中，我们知道工作中常遇到这样的问题：有项任务需要个人来承担，每个人都能完成其中的每项任务，只是由于每个人的特点及专长不同，每个人完成各项任务所需的时间、费用或所产生的效益各不相同，又因为任务性质的要求和管理上的需要等原因，每项任务只能由一个

11、人来完成，每个人也只能承担其中的一项任务.问应指派哪个人去完成哪项任务才能使完成各项任务花费的总时间最短或总费用最少，或所产生的总效益最佳.我们把这类最优匹配问题称为指派问题.2.2指派问题的数学模型 设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题可转化为0-1线性规划问题： 3.匈牙利算法的基本原理及解题步骤3.1 匈牙利算法的基本原理简要地讲，求指派问题的最优解就是要在阶系数方阵中找到个这样的元素：它们分布在方阵的不同行、不同列上，并且这些元素之和为最小.而要使这些元素之和为最小，就要使其中的每一个元素尽可能的小最好这些元素都是其所在行和列上的最小元素.而指派问题的最

12、优解又有这样的性质（定理1）：如果从分配问题效率矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵为效率矩阵求得的最优解和用原效率矩阵求得的最优解相同.由于新矩阵中每行、每列的最小元素均为“0”，因此，求原指派问题的最优解就转化为在新矩阵中找出n个分布在不同行、不同列上的“0”元素（简称为独立0元素），这些独立0元素就是新矩阵的最优解，找到新矩阵的最优解也就找到原矩阵的最优解了.要在矩阵中找到几个分布在不同行、不同列上的“0”元素，前提首先是在矩阵中确定存在几个这样的“0”元素.那么，如何判断在矩阵中是否存在n个这样的独立0元素呢？考尼格（Koning）证明了这样一个定理（定理

13、2）：“覆盖所有0元素的最少直线数等于矩阵中独立0元素的最多个数.”利用这一定理，就可以通过寻找“能覆盖所有0元素的最少直线”来确定矩阵中独立0元素的具体数量。倘若矩阵中独立0元素的数量小于矩阵的阶数n，就得继续对矩阵进行化简，直到有了n个独立的0元素为止，找到这n个独立0元素也就找到了原指派问题的最优解.这就是匈牙利算法的基本思路.3.2匈牙利算法的解题步骤第一步，对耗费矩阵C进行行（或列）约减，即每一行（或列）数据减去本行（或列）数据中的最小数，得矩阵；第二步，检查矩阵，若矩阵各行各列均有“0”，则跳过此步，否则进行列（或行）约减，即每一列（或行）数据减去本列（或行）数据中的最小数，得矩阵

14、;第三步，画盖“0”线.即画最少的线将矩阵中的0全部覆盖住，得矩阵；第四步，数据转换.若“盖0”线的数目等于矩阵的维数则直接跳到第六步，若“盖0”线的数目小于矩阵的维数则进行数据转换，进行数据转换的操作步骤如下：（1）找出未被“盖0”线覆盖的数中的最小值 （2）将未被“盖0”线覆盖住得数减去 （3）将“盖0”线交叉的数加上第五步，重复第三步和第四步，直到“盖0”线的数目等于矩阵的维数.第六步，求最优解.对n维矩阵，找出不同行，不同列的n个“0”，每个“0”的位置代表一对配置关系，具体步骤如下：（1）先找只含有一个“0”的行（或列），将该行（或列）中的“0”打“”（2）将带“”的“0”所在列（或

15、行）中的“0”打“”（3）重复（1）步和（2）步至结束.若所有行列均含有多个“0”，则从“0”（4）的数目最少得行或列中任选一个“0”打“”第七步，打“”即为员工所对应的指派任务.4.匈牙利算法求解员工指派问题的模型假设及符号说明4.1 匈牙利算法解员工指派问题的模型假设（1）员工数目及任务数目相等（2）求解的是最小化问题，如工作时间最小化、费用最小化等.4.2 符号说明 表格4-2 字母符号说明符号符号说明表示企业指派的员工数表示需要完成的任务数表示指派第i人去完成第j项任务是所用的时间表示决策变量5.企业员工指派问题的模型建立及求解5.1标准指派问题（当m=n时，即为每个人都被指派一项任务

16、）问题的提出假定某企业有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如5-1所示. 表5-1 某企业员工完成任务时间汇总表 单位：(小时)员工任务甲乙丙丁戊A10591811B131961214C32445D189121715E116141910请求出：员工及任务之间应当如何进行配置，才能保证完成工作任务的时间最短？最短时间为多少？模型的建立设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题的数学模型为： 模型的求解由题意及匈牙利算法得效益矩阵由此可知当员工甲负责任务A，员工乙负责任务D

17、，员工丙负责任务B，员工丁负责任务C，员工戊负责任务E时，才能保证完成工作任务的时间最短，且最短的时间t=10+9+6+4+10=39小时.5.2非标准指派问题（1）当时，即企业指派的员工数小于要求完成的任务数问题的提出某企业安排2个员工，完成3项任务，每个员工完成每项工作的时间如表5-2所示.表5-2 某企业员工完成任务时间汇总表一 单位：(小时)任务员工甲乙A105B1319C32求：应如何分配任务才能保证工作时间最短？模型的建立模型1 根据题意设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题的数学模型为： 因为该模型不能直接运用匈牙利算法求解，故我们进行如下分析：两员

18、工负责三项任务，则必有一个员工需承担两项任务，因此增加甲和乙,分别表示他们完成第二项工作的情况，则上表变形为表5-3.表5-3 某企业员工完成任务时间汇总表二 单位：(小时)员工任务甲甲乙乙A101055B13131919C3322表5-3中，员工数目多于任务数目，添加虚任务D，得表5-4 表5-4 某企业员工完成任务时间汇总表三 单位：(小时)员工任务甲甲乙乙A101055B13131919C3322D0000此时模型1变形为模型2设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题的数学模型为：模型的求解利用匈牙利算法求解，得效率矩阵 .即当乙完成A、C任务，甲完成B任务时

19、，完成工作时间最短，最短时间t=5+2+13=20小时.（2）当时，即企业指派员工数大于要求完成的任务数 问题的提出 某企业目前有5名员工，需要完成4项任务，每个员工完成每项任务的工作时间如表5-5所示.表5-5 某企业员工完成任务时间汇总表一 单位：(小时)员工任务甲乙丙丁戊A10591811B131961214C32445D116141910求：应如何分配任务才能保证工作时间最短？模型的建立模型1根据题意设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题可转化为0-1线性规划问题： 因为该模型不能直接运用匈牙利算法求解，故我们进行如下分析：五个员工负责四项任务则必有一个员

20、工没有任务，此时可增添一项虚任务E，则各员工完成任务E的时间均为0，上表变形为5-6表5-6 某企业员工完成任务时间汇总表二 单位：(小时)员工任务甲乙丙丁戊A10591811B131961214C32445D116141910E00000此时模型1变形为模型2：设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题可转化为0-1线性规划问题：4模型的求解此时可用匈牙利算法计算，得效率矩阵 即当甲分配C任务， 乙分配A任务，丙分配B任务，戊分配D任务时，工作时间最短，最短时间t=3+5+6+10=24小时.（3）当所求问题为求最大化值时问题的提出 某企业目前有5名员工完成5项任务

21、，每个员工完成各项任务所获得的利润如表5-7所示. 表5-7 某企业员工完成任务收益汇总表一 单位：(万元)员工任务甲乙丙丁戊A10591811B131961214C32445D189121715E116141910求：如何给甲、乙、丙、丁、戊分配任务，使他们完成任务总收益最大？问题分析因为匈牙利算法求得是最小化问题，故我们需把最大化问题转化为最小化问题，我们取，令，这样我们就可以将最大化问题转化为最小化问题了，即由题意知表5-7中最大的数据为19，用19分别减去其中的各个数据，则数据表转化为表5-8.表5-8 某企业员工完成任务收益汇总表二 单位：(万元)员工任务甲乙丙丁戊A9141018B

22、601375C1617151514D110724E813509模型的建立设用表示指派第人去完成第项任务时所用的时间，定义决策变量，则指派问题可转化为0-1线性规划问题： 模型的求解此时可以用匈牙利算法求解，得效率矩阵即当甲分配D任务，乙分配B任务，丙分配E任务，丁分配A任务，戊分配C任务时，他们完成的任务收益最大，最大值为18+19+14+18+5=74万元.6.匈牙利算法的缺点、改进以及C语言实现6.1 匈牙利算法的缺点1.“匈牙利算法”在各种已发表的教材、专著和研究成果中，通常求解中、小型分配问题，效能矩阵的阶数通常不超过20，故很难发现“匈牙利算法”存在的问题.事实上，匈牙利算法在处理一

23、些特殊数据时并不有效，算法不收敛，无法找出最优解.2.在匈牙利算法的求解步骤中，效率矩阵既可以先进行“行约减”也可先进行“列约减”，并没有说是先进行“行约减”还是先进行“列约减”，但是，有时先进行“行约减”要比先“列约减”复杂，增加了许多步，有时却相反，我们来看下面例题.例题：效率矩阵 1.先进行“行约减”：2.先进行“列约减”：由此可见，先进行“行约减”比先进行“列约减”更简单.6.2 匈牙利算法的改进综合上面两道例题，我们知道匈牙利算法还是有一些不足的，经过我反复的实验、观察效率矩阵的特殊性，现对效率矩阵进行改进，改进之后，就能少了许多麻烦的步骤，知道是先进行“行约减”还是先进行“列约减”

24、.匈牙利算法的改进如下：第一步，简化效率矩阵.（1）统计效率矩阵每行的最小元素的个数总和和每列的最小元素的个数总和 .（2）若和均大于，且当时，则先对效率矩阵的每列减去该列的最小元素，再对所得的效率矩阵的每行减去该行的最小元素.反之，当时，则先对效率矩阵的每行减去该行的最小元素，再对所得效率矩阵的每列元素减去该列的最小元素.（3）若和不满足均大于，且当时，则先对效率矩阵的每列减去该列的最小元素，再对所得的效率矩阵的每行减去该行的最小元素.反之，时，则先对效率矩阵的每行减去该行的最小元素，再对所得的效率矩阵的每列减去该列的最小元素.第二步，检查矩阵，若矩阵各行各列均有“0”，则跳过此步，否则进行

25、列（或行）约减，即每一列（或行）数据减去本列（或行）数据中的最小数，得矩阵第三步，画盖“0”线.即画最少的线将矩阵中的0全部覆盖住，得矩阵；第四步，数据转换.若“盖0”线的数目等于矩阵的维数则直接跳到第六步，若“盖0”线的数目小于矩阵的维数则进行数据转换，进行数据转换的操作步骤如下：（1）找出未被“盖0”线覆盖的数中的最小值 （2）将未被“盖0”线覆盖住得数减去 （3）将“盖0”线交叉的数加上第五步，重复第三步和第四步，直到“盖0”线的数目等于矩阵的维数.第六步，求最优解.对n维矩阵，找出不同行，不同列的n个“0”，每个“0”的位置代表一对配置关系，具体步骤如下：（1）先找只含有一个“0”的行

26、（或列），将该行（或列）中的“0”打“”（2）将带“”的“0”所在列（或行）中的“0”打“”（3）重复（1）步和（2）步至结束。若所有行列均含有多个“0”，则从“0”（4）的数目最少得行或列中任选一个“0”打“”第七步，打“”即为员工所对应的指派任务.6.3 匈牙利算法的C语言实现（附录）7.匈牙利算法的应用推广匈牙利算法不仅在企业员工指派问题上有重要的应用，而且它还解决了集体比赛项目中参赛队员的出场次序问题提供了一个科学的决策方法.例 设有A，B,C,D四个队员参加米接力赛跑，由于各队员的心理素质、交接棒技术、起跑以及冲刺速度等原因，所跑不同棒次所用时间（单位为秒）不尽相同，见下表1. 表1

27、（单位：秒）队员棒次1234A1010.0110.0110B10.0110.0110.0110.01C10.0110.0110.0110.02D1010.0110.0110.01利用匈牙利算法求解，得效益矩阵因此，得到两种最优指派方案：方案一：A跑第四棒，B跑第二棒，C跑第三棒，D跑第一棒；方案二：A跑第四棒，B跑第三棒，C跑第二棒，D跑第一棒，所需的总时间为10+10.01+10.01+10=40.02（秒）.8.结束语本文阐述了企业员工指派问题，在数学建模的思想基础上运用匈牙利算法对企业员工指派问题进行求解，并对匈牙利算法的缺点进行改进以及匈牙利算法的C语言实现并将其应用到现实的例子当中.

28、虽然，匈牙利算法有一些不足之处，但是匈牙利算法仍然是企业求解员工指派问题的一种好方法，它为企业进行员工指派任务时提供了巨大的帮助，匈牙利算法具有很强的实用性.虽然，本文尝试对匈牙利算法进行了一些技巧性的改进，但是需要指出的是，我对匈牙利算法的改进只是一种经验，未能有严谨的证明.参考文献1 束金龙，闻人凯线性规划理论及模型应用M北京：科学出版社，20032 胡运权，运筹学基础及应用（第五版）M北京：高等教育出版社，20103 胡运权，运筹学基础及应用（第五版）M.北京：高等教育出版社，20104 中国就业培训技术指导中心 组织编写，企业人力资源管理师（三级）M 北京：中国劳动社会保障出版社，20

29、075 程红萍 简化匈牙利算法求解的思考J.渭南师范学院学报，2007，22(5)：32-346 张联朋对指派问题匈牙利算法的两点改进J西安航空技术高等专科学校学报，2007，25(1)：64-667 袁迁，刘舒燕关于匈牙利算法的优化J武汉理工大学学报，2007，29(3)：146-1498 张联朋寻找独立元素的一种新方法J重庆职业技术学院学报，2007，16(1)：160-1619 林同曾主编运筹学 M北京：机械工业出版社，198610 杨文鹏，贺兴时，等新编运筹学教程M西安：陕西科学技术出版社，2005附录匈牙利算法程序如下：#include #include /#define M 5/#

30、define N 5#define MAXSIZE 10int M,N;int arrangement999999; /*二维耗费矩阵，i行是雇员i，j列是工作j，arrangementij是耗费*/int bestcost=999; /*bestcost是当前最优值*/int x999; /*x 是当前调度*/int bestx999; /*bestx 最优分配*/void backtrackarrage(int i,int cost);void outputresult();void swap(int i,int j);main() int i,j; printf(请输入行(人数)：M=)

31、; scanf(%d,&M); printf(请输入列(工作)数：N=); scanf(%d,&N); printf(*输入方式*n); printf(* 手动输入(I) 文件读入(F) *n); printf(*n); getchar(); if(getchar()=I) printf(你选择的是手动输入n); printf(请输入一个%d*%d矩阵(数字之间用空格间隔，换行按回车)n,M,N); for(i=0;iM;i+) for(j=0;jN;j+) scanf(%d,&arrangementij); else printf(你选择的是文件读入n); FILE *fp;fp=freop

32、en(input.txt,r,stdin);for(i=0;iM;i+) for(j=0;jN;j+) scanf(%d,&arrangementij); for(i=0;iN;i+) /*初始化当前调度*/ xi=i; backtrackarrage(0,0); /*回溯求解*/ outputresult(); /*输出结果*/ getch(); /*递归回溯函数，确定最优调度方案，i 是递归层数，cost是当前求得的解*/void backtrackarrage(int i,int cost) int j; if(i=N) if(costbestcost) bestcost=cost; f

33、or(j=0;jN;j+) bestxj=xj; else for(j=i;jN;j+) cost+=arrangementixj; if(costbestcost) swap(i,j); backtrackarrage(i+1,cost); swap(i,j); cost-=arrangementixj; /*交换函数 为了得到一个排序树的排序，即一个全排列*/void swap(int i,int j) int temp; temp=xi; xi=xj; xj=temp;void outputresult() int i;printf(计算结果是:n); printf(eventtpeople); for(i=0;iN;i+) printf(n %dt %d,i+1,bestxi+1); printf(nntbest cost:%dn,bestcost); 致谢感谢林耿指导老师对我论文细心、耐心的指导，感谢李涛同学对我C语言方面的指导，感谢舍友、同学对我精神上的鼓励！在他们的帮助下我认真、有序地完成了论文的写作工作，在此我非常感谢他们，祝他们身体健康、工作顺利、学习进步！