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

本科毕JK份文题目匈牙利算法在企业员工指派问题的应用学生姓名，且乡卫二L寸7系别年级专业指导教师职称完成日期120080901139笠笠至且坚豆豆数学与应用数学进血2012年4月10日摘要在当今社会，竞争元处不在，企业的竞争也是如此而员工指派问题又是企业不得不面对的问题因此，企业员工指派问题就显得非常重要了，谁能够在这方面做的好，你就能在竞争中多一分胜算企业员工指派间越是指企业安排若干人员会完成若干项任务任务和人数不一定相等，并且妥求克成的效率最高对于这一问题，匈牙利算法就是一个很好的解法本文首先给出企LL虱工指派问是在的数学棋型，它分为两大类，一类是标准指派问题1111企业指派员王欲与任务在生相等，另一类是非标准指派问题即企业指派员工数与任务数不相等，其次，在对匈才和JN法及其原理深入理解的基础上，利用匈牙利算法对企立员工指派问趣的数学棋型进行求解其中，用标准的匈牙利算法求解标准的指派问题，对于非标准的指派|可绳，先才巳它进行适当的交换，然后1日标准的匈牙利JJ去求解再次，讲述了匈牙利算法的一些缺点及其改进，才巳匈牙利算法用C语言农示出来，并把它运用到实际的企业员玉指派问题当中最后，讲述了匈牙利算法的应用椎厂关键词匈牙利算法员工指派问题运筹学效益矩阵ABSTRACTI0MODERNSOCI巳LY，COMPETILIONEXISTSEV巳RYWH巳RE，SODO巳SLHECOMPELITIOLLAMONGENTERPRISESSTAFFASSIGNMENTISOFGREATIMPORTANCETOENTERPRISESTHOSEWHODOWELLINILWILLGELMORECHANCES10WININTH巳COMPETILIONENTERPRISESLALASSIGNMENLISLHALENTERPRISESASSIGNANUMB巳ROFEMPLOYEESTOACCOMPLISHSOMETASKSINHIGHEFFICIENCYTHCMNUBEROFTASKSISNOTNECESSARILYEQLLIVALCNT10THATOFASSIGN巳DSTAFFTOSOLVELHISPROBLEM,LH巳HLLNGARYALGORILHMISLHEBESLCHOICEINTHISLHESIS,THEALLLHOLTIRSTLYILLLISTRATESTHEENLERPRISESTATLASSIGNMENT,WHICHINCLLLDESNORMALASS地NMENTPROBLEMANDABNONNALASSIGNMENLPROBLEMSENDLY，THEAULHOR50LVESLHEENLERPRISESTAFFASSIGNMENTWITHTHEHLLNGARYALGORITHMINTWOWAYSONEISNORMALHLLNGARYALGORITHMUSEDTOSOLVETHENORMALASSIGNMENTPROBLEM,THEOTHERISABNORMALHLLNGARYALGORILHMLISEDTOSOLVETHEABNORMALASSIGNMENTPROBLEMTHIRDLY,THEAULHOR归INTSOLLTSOMEDEFECTSAND0位ERSSOMEIMPLOVEMENTSOFTHEHLLNGARYALGORITHM,ANDWRITEITINCLAUGLLAG巳ATLAST,TBEALLTHORGIV巳SS0111EEXAMPL巳SOFTHCAPPCATIONOFTHEHLLNGARYALGORITHMKEYW0RDSHLLNGARYALGORITHMSTAFFASSIGNMENTPROBLEMOPERATIONSRESEARCHPROTTMATRIX目录1引言I2指派问题的数学模型“I21指派问题122指派问题的数学模型呻巾叶3匈牙利算法的基本原理及解题步骤231匈牙利算法的基本原理232匈牙利算法的解题步骤34匈牙利算法求解员工指派问题的模型假设与符号说明341匈牙利算法解员工指派问题的模型假设342符号说明，45企业员工指派问题的模型建立与求解451标准指派问题当RNN时，LLL为每个人都被指派一项任务452非标准指派问题66匈牙利算法的缺点、改进以及C语言实现1261匈牙利算法的缺点川川川川1口262匈牙利算法的改进川0川0川0川川0川0川0川63匈牙利算I法去的C语言实现附录157匈牙利算法的应用推广158结束语“17参考文献18附录19致谢22匈牙利算法在企业员工指派问题的应用张雯闽江学院数学系福建福州I3501081引言当今社会，人力资源规划在企业人力资拥管理活动巾具有重要的地位和I作用人力资源规划是指为实施企业的发展战略，完成企业的生产经营目标，根据企业内外环境和条件的变化，运用科学的方法，使企业的人力资源和需求达到平衡，实现人力资源的合理配置，有效、撒切J员工的过程而企业员工指派问题在人为资源规划中又是必不可少的，为了使人力资源管理的“大才大用，小才小用，人尽其才，向得其人，能位匹配“的基本原则II得以实现，因此，企业员工指抵问题就显得很重要了，而匈牙利算法就是求解人员与工作任务配置合理化、科学化的一个好方法“匈牙利算法“最早是由匈牙利数学家考尼格IJ飞就是问题的最忧解2指派问题的数学模型21指派问题从运挥学巾，我们知道工作中常遇到这样的问题有M项任务需要N个人来承担，每个人都能完成其中的每项任务，只是由于每个人的特点与专长不同，每个人完成各项任务所需的时间、费用或所产生的效益，备不相同，又因为任务性质论文的要求和L管理上的需要等原因，每项任务只能由一个人来完成，每个人也只能承担其中的一项任务问应指派哪个人去完成哪项任务才能使究成各项任务花费的总时间最短或总费用最少，或所产生的总效益最佳A我们把这类最优匹配问题称为指派问题110122指派问题的数学模型设用CIJ0I,JJ,2,L，N表示指派第I入去完成第J项任务时所用的时F1，当指派第I人去完成第JJIJ任务时间，定义决策变童心斗，则指派问题可转Y10，当不指派第I人去完成第J项任务MLJL化为01线性规划问题LIJI,JI,2,L,NL句Z又1“JMEDXU1或0，I，JL，2，L,N3匈牙利算法的基本原理及解题步骤31匈牙利算法的基本原理简要地讲求指派问题的最优角早就是要在N阶系数方阵中找到N个这样的元素它们分布在/阵的不同行、不同列上，并且这些元索之和为战小111而要使这些元素之和为越小，就要使其中的每一个元素尽可能的小一一敲好这些元素都是其所在行和列上的最小元素而指派问题的最忧解又有这样的性质定理1ZI如果从分配问题效率矩L辱的一行列各元素中分别减去该行歹1的最小元去得到新的矩阵鸟为效率矩阵求得的最优解利用原效率矩阵CIJJ求得的最忧解相同由于新矩阵乓中每行、每列的刷、元素均为，因此求原指派问题的战优解就转化为在新矩阵川中找出N个分布在不同行、不同列上的元素简称为独立0元素181，这些独立0元素就是新矩阵刑的最优解，找到新炬阵的最忧解也就找到原矩阵的最忧解了论文要在矩阵鸟中找到几个分布在不同行、不同列上的元素，前提首先是在矩阵BJJJRL确定存在儿个这样的TLO“元素那么，如何判断在矩阵民中是否存在N个这样的独立0元素呢考尼格KONING证明了过丰学一个定理定理231“覆盖所有0元素的最少直线数等于如II碍中独立0元索的最多个数“利用这一定理，就可以通过寻找“能覆盖所有0元素的最少直线“来确切I阵叶中独立0元素的具体数量。倘若矩阵川中独立。元素的数量小子矩阵的阶数N，就得继续对矩阵鸟进行化筒，直到有了N个独立的0元素为止，找到这N个独立0元素也就找到了原指派问题的最优解这就是匈牙利算法的基本思路32匈牙利算法的解题步骤第一步，对耗费矩阵C进行行或歹IJ约减，即每一行或列数据减去本行或列数据中的最小数，得矩阵C，第二步，检查矩阵C“若矩阵C，各有各列均有“0飞则跳过此步，否则进行列或行约戚，即每一列或行数据减去本列或行数据中的最小数，得矩阵C2第二步，画盖“0“线且11面IL革少的线将矩阵C2中的。全部覆盖住，得矩阵C3第四步，数据转换若“盖。“线的数目等于矩阵的维数则直接跳到第六步9者“盖0“线的数目小于矩阵的维数则进行数据转换，进行数据转快的操作步骤如下1找I未被“盖。“线攫盖的数中的最小值21寄来被“盖。“线覆盖住得数减去3将“盖。“线交叉的数加上第五步，重复第三步和第四步，直到“盖。“线的数目等于矩阵的维数第六步，求最优解对N维矩碎，找出不同行，不同列的N个“0飞每个“0“的位置代表一对配置关系，具体步骤如下1先找只含有一个“0“的行成功J,1等该行或列，尸的“0“打“2将带“的“0“所在歹IJ或行R的“0“打“X“3重复I步和2步至结束若所有行列均含有多个“0“，则从“0“4的数目最少得行或列1任地一个“0“打“第七步，打“即为员工所对L应的指派任务4匈牙利算法求解员工指派问题的模型假设与符号说明41匈牙利算法解员工指派问题的模型假设论文1员工数目与任务数目相等2求解的是最小化问题，如工作时间监小化、费用4小化等42符号说明表格42字匈符号说明符号符号说明N表示企业指派的员工数M表示需要完成的任务数CIJ表不指派第I人去完成第J项任务是所用的时间X表示决策变盘5企业员工指派问题的模型建立与求解51标准指派问题当MN时，即为每个人都被指派一项任务问题的提出假定某企业有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要槌费的工作时间，自日51所示表51某企业员工完成任务时间汇总表单位小时海之IFL乙两丁戊A10591811B131961214C32445D189121715E116141910请求出员工与任务之间应当如何进行自己置，才能保证完成工作任务的时间最短。最短时间为多少模型的建立论文设川CJ0I,JI,2,L，5表示指派第T人去完成第J项任务时所川的时FNJR1，当指派第I人去完成第J项任务时定义决策变J此XH，则指派问题的数学技U10，气不指派第I人去完成第J项任务MINZ泣CJIJ时J1型为L,I,JI,2,L,5SI乞川J1,2,L5XIJ1成O，I，J1,2,L,5模型的求解山JT2I扳倒牙利抨法衍效益声LILTF105918L3L9612244L891217L1614194。6130坦坦护O2803403045130盟主与L“，X，31114515104114。68103。5。4L36713。68诫争11。2239。3865。8134344118363481HNU叮A叶内线敏T扭转换标记刽703523081N“X，、，、面IIII山此间虫1J，5IT甲负出毛任务A，员工乙负责任务D，员E丙负W任务8，员工丁负沈任务C约T戊负责任务E肘，才能保证完成工作任务的时间以炬，11I成矩的时间T109641039小时论文52非标准指派问题1当M11时，即企业指派的员工数小于要求完成的任务数问题的提出某企业安排2个员工，完成3项任务，每个员工完成每项工作的时间如表5_2141月IT示表52某企业员工完成任务时间汇总表一单位小时言甲乙A105B1319C32求应如何分配任务才能保证工作时间最短模型的建立模型L根据题意设用CJ01,2,1，2，3表示指派第I人去完成第J项任L，当指派第I人去完成第联任务时务则所用的时间，定义决策变量XJI10，当不指派第I人去完成第J声任务派问题的数学模型为STMINZLLCHLXJ1,J1,2,3LXJJ1,J1,2,3XJ1或O，I1,2,J1,2,3，则指因为该模型不能直接运用匈牙利算法求解，故我们进行如下分析两员工负责三项任务，则必有一个员工需承担两项任务，因此均加甲和乙，分别表示他们完成第二项工作的情况，则上衰变形为表53表53某企业员工完成任务时间汇总表二单位小时TT也生甲甲乙乙A10LO55B13L31919C3322表53巾，员工数目多于任务数目添加殷任务0，得表54论文即当乙完成A、C任务，甲完成B任务时，完成工作时间最短，最短时间1521320小时2当M0II，2，L，5，JI，2，3，4表示指派第T人去完成第量R1，当指派第I人去完成第J项任务时，则指派问题可转化为01线性规划L闷。10，当不指派第I人去完成第J项任务变策泱义定L同时的用所4叶JNN“务任项JFD川SYM7LUULXIJ1,J1,2,L,4L句1，户口，L41或0，II，2，L,5,JL,2,3,4ST题因为该模型不能直接适用匈牙利算法求解，故我们进行如下分析五个员工负责四项任务则必有一个员工没有任务，此时可增添一项虚任务E，则各员工完成任务E的时间均为0，上衰变形为56论文表56某企业员工究成任务时间汇总表二单位小时话足之甲乙丙丁J戈A10591811B131961214C32445D116141910E。此时模型L变形为模型2设用CUOIJ12,L，5表示指派第I人去完成第J项任务时所用的时间，F1当指派第1人去，完成第J项任务时定义决策变量乓斗，则指派问题可转化为10，当不指派第1人去完成第J项任务。1线性规划问题STMINZLLCIJXLX，,J1,2,L,5LXIJ1,J叶，2，L5XU1或O，I，J1,2,L,5模型的求解此时可用匈牙利算法计算，得效率1巨阵论文10591811131961214C32445116141910。541367168进行行约、战在。23翻UJO线5陆，、A飞RU4。4125613057叫线。224。812。4L12561B57N,飞J41OI,J1,2,L，5表示指派第T人去完成第J项任务时所用的时间，定义F1，当指派第I人去完成第J项任务时决策变量乓斗，则指派问题可转化为0110，当不指派第1人去完成第J项任务线性规划J问题模型的求解论文MINZLLCIJ立XIJL，JI，2，L,5STLXJI,JI,2,L5XIJL或0，I，JI，2，L,5此时1JJ“以J十J创牙军JJ1法求解,得效率女L阵9141088139。76。13756。1375CIJ617151514选FHT1磁23。10724。9638135。98135。98017494。36。1211523。5。955349。5T11当市分配D任务，乙分配B任务，两分配E任务，丁分配A任务，戊分配C任务时，他们元成的任务收益最大，最大值元6匈牙利算法的缺点、改进以及C语言实现61匈牙利算法的缺点1“创牙利TF法“在各种己发表的教材、专著和研究成果1，1西古求IJI“，、小型分III问题，效能知11碎的阶数通信不超过20，夜很难发现“创牙利57法，行在的问题JJJ实士，问牙利算法在处理一些特殊数据时并不有效，算法不LIX敛，无法找出最优FJLJ6J2在匈牙利拟议的求解步骤“I，效率矩阵既可以先进行“行约础“也叫先进行“YJ约减“，并没有说是先进行“行约诚“还是先进行“列约诚“但是，有时先进行“行约诚“比先“歹JJ约减“复杂，增加了许多步有时却非“反，我们米看下山例1L论文1518212419232218例JI2I效率知阵151AI26171619172123171先I挂H“行约I成气15182124。369JL9232218边行CU行1勺I，154。A2617161910。317212317。46。26944。336。49川以抗4D负IUJJ2201。20。5。14。OX。49争G2X2。R、CE曲14OX2先进行“列约础“1518224。5719232218进行“9IJ约减“466AI2617161911。217212317247。论文。157IHIITITLIINCLUDEII“DEFINEM5IILTDEFLNE5DCFINCMAXSIZE10INTM,N附录INTARRANGEMENL999J999J1二维拉费矩阵I行是店1I,J别是1作JARRANGEMENTIJJ是耗费1INLBCSCOSL999INTX999JINTBESX999JLBESTCOSL是当前最优值1/均是当前调度1LBESLX最优分配1VOIDBACKLN1CKARRAGEINLI,INLCOSLVOIDOUPULRCSULLVOIDSWAPINLI,INJMAINO1NL1,JPRINLL“IJL输入行人数帖SCANFC剿，削P1INLFCI古输入列丁丁作数