当前位置:首页 >> 人力资源管理 >>

匈牙利算法在企业员工指派问题的应用(最终版)


闽江学院 本科毕业论文
题 目 匈牙利算法在企业员工指派问题的应用 张雯 学生姓名 学 系 年 专 号 别 级 业

120080901139
数学系 2008 级 数学与应用数学 林耿 讲师 2012 年 4 月 10 日

指导教师 职 称

完成日期

闽江学院毕业论文诚信声明书
本人郑重声明: 兹提交的毕业论文(设计) 《匈牙利算法在企业员工指派问题

的应用》 ,是本人在指导老师 林耿 的指导下独立研究、 撰写的成果;
论文(设计)未剽窃、抄袭他人的学术观点、思想和成果,未篡改研究数 据,论文(设计)中所引用的文字、研究成果均已在论文(设计)中以明确 的方式标明;在毕业论文(设计)工作过程中,本人恪守学术规范,遵守 学校有关规定,依法享有和承担由此论文(设计)产生的权利和责任.

声明人(签名): 2012 年 4 月 10 日

摘要
在当今社会,竞争无处不在,企业的竞争也是如此.而员工指派问题又是企 业不得不面对的问题.因此,企业员工指派问题就显得非常重要了,谁能够在这 方面做的好,谁就能在竞争中多一分胜算.企业员工指派问题是指企业安排若干 人员去完成若干项任务(任务和人数不一定相等) ,并且要求完成的效率最高 . 对于这一问题,匈牙利算法就是一个很好的解法.本文首先给出企业员工指派问 题的数学模型,它分为两大类,一类是标准指派问题(即企业指派员工数与任务 数相等) , 另一类是非标准指派问题 (即企业指派员工数与任务数不相等) , 其次, 在对匈牙利算法及其原理深入理解的基础上, 利用匈牙利算法对企业员工指派问 题的数学模型进行求解.其中,用标准的匈牙利算法求解标准的指派问题,对于 非标准的指派问题,先把它进行适当的变换,然后用标准的匈牙利算法求解.再 次,讲述了匈牙利算法的一些缺点及其改进,把匈牙利算法用 C 语言表示出来, 并把它运用到实际的企业员工指派问题当中.最后,讲述了匈牙利算法的应用推 广. 关键词:匈牙利算法;员工指派问题;运筹学;效益矩阵

Abstract
In modern society, competition exists everywhere, so does the competition among enterprises. Staff assignment 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 that 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 assignment 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 algorithm, 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. 引言· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 2.指派问题的数学模型 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1
2.1 指派问题 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 2.2 指派问题的数学模型· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2

3.匈牙利算法的基本原理及解题步骤 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2
3.1 匈牙利算法的基本原理 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2 3.2 匈牙利算法的解题步骤 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 3

4.匈牙利算法求解员工指派问题的模型假设与符号说明 · · · · · · · · · · · · · · · · · · · · 3
4.1 匈牙利算法解员工指派问题的模型假设 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 3 4.2 符号说明 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4

5.企业员工指派问题的模型建立与求解 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4
5.1 标准指派问题(当 m=n 时,即为每个人都被指派一项任务) · · · · · · · · · · · · · · · 4 5.2 非标准指派问题 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 6

6.匈牙利算法的缺点、改进以及 C 语言实现 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 12
6.1 匈牙利算法的缺点 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 12 6.2 匈牙利算法的改进 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 14 6.3 匈牙利算法的 C 语言实现(附录) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 15

7.匈牙利算法的应用推广 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 15 8.结束语 · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 17 参考文献· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 18 附录· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 19 致谢· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 22

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

张雯 (闽江学院 数学系;福建 福州 350108)

1. 引言
当今社会, 人力资源规划在企业人力资源管理活动中具有重要的地位和作用. 人力资源规划是指为实施企业的发展战略,完成企业的生产经营目标,根据企业 内外环境和条件的变化,运用科学的方法,使企业的人力资源和需求达到平衡, 实现人力资源的合理配置,有效激励员工的过程.而企业员工指派问题在人力资 源规划中又是必不可少的,为了使人力资源管理的“大才大用,小才小用,人尽 其才,岗得其人,能位匹配”的基本原则 [ 4 ] 得以实现.因此,企业员工指派问题 就显得很重要了, 而匈牙利算法就是求解人员与工作任务配置合理化、科学化的 一个好方法. “匈牙利算法”最早是由匈牙利数学家考尼格(D.Koning)用来求矩阵中 0 元素的个数的一种方法, 由此他证明了“矩阵中独立 0 元素的最多个数等于能覆 盖所有 0 元素的最少直线数”. [ 7 ] 1955 年由库恩(W.W.Kuhn)在求解著名的指派 问题时引用了这一结论,并对具体算法做了改进,仍然称为“匈牙利算法”.解 指派问题的匈牙利算法是从这样一个明显的事实出发的: 如果效率矩阵的所有元 素 aij ? 0 ,而其中存在一组位于不同行不同列的零元素,则只要令对应于这些零 元素位置的 xij ? 1 ,其余的 xij ? 0 ,则 z ? ?? aij xij 就是问题的最优解.
i ?1 j ?1 m m

2.指派问题的数学模型
2.1 指派问题
从运筹学中,我们知道工作中常遇到这样的问题:有 m 项任务需要 n 个人来 承担,每个人都能完成其中的每项任务,只是由于每个人的特点与专长不同,每 个人完成各项任务所需的时间、 费用或所产生的效益各不相同,又因为任务性质
1

的要求和管理上的需要等原因, 每项任务只能由一个人来完成,每个人也只能承 担其中的一项任务.问应指派哪个人去完成哪项任务才能使完成各项任务花费的 总时间最短或总费用最少,或所产生的总效益最佳.我们把这类最优匹配问题称 为指派问题. [10]

2.2 指派问题的数学模型
设用 Cij ? 0 ?i, j ? 1,2,L , n? 表示指派第 i 人去完成第 j 项任务时所用的时
? 1, 当指派第i人去完成第j项任务时 间,定义决策变量 xij ? ? ,则指派问题可转 ?0,当不指派第i人去完成第j项任务
n n ? min Z ? Cij xij ?? ? i ?1 j ?1 ? n ? xij ? 1, j ? 1, 2, L , n ? ? 化为 0-1 线性规划问题: ? i ?1 ? n ? s.t ? xij ? 1, j ? 1, 2, L n ? i ?1 ? x ? 1或0, i, j ? 1, 2, L , n ij ?

3.匈牙利算法的基本原理及解题步骤
3.1 匈牙利算法的基本原理
简要地讲,求指派问题的最优解就是要在 n 阶系数方阵中找到 n 个这样的元 素:它们分布在方阵的不同行、不同列上,并且这些元素之和为最小 [1] .而要使 这些元素之和为最小, 就要使其中的每一个元素尽可能的小——最好这些元素都 是其所在行和列上的最小元素. 而指派问题的最优解又有这样的性质(定理 1) [ 2 ] :如果从分配问题效率矩 阵? (列) 各元素中分别减去该行 (列) 的最小元素, 得到新的矩阵 ? ? Cij ? ? 的一行 ? Bij ? ? 为效率矩阵求得的最优解和用原效率矩阵 ? ? Cij ? ? 求得的最优解相同. 由于新矩阵 ? ,因此,求原指派问题 ? Bij ? ? 中每行、每列的最小元素均为“ 0” 的最优解就转化为在新矩阵 ? ? Bij ? ? 中找出 n 个分布在不同行、不同列上的“0”元 素(简称为独立 0 元素 [8 ] ) ,这些独立 0 元素就是新矩阵 ? ? Bij ? ? 的最优解,找到新 矩阵的最优解也就找到原矩阵的最优解了.
2

要在矩阵 ? ? Bij ? ? 中找到几个分布在不同行、不同列上的“0”元素,前提首先 是在矩阵 ? ? Bij ? ? 中确定存在几个这样的“0”元素.那么,如何判断在矩阵 ? ? Bij ? ?中 是否存在 n 个这样的独立 0 元素呢?考尼格(Koning)证明了这样一个定理(定 理 2) [3] : “覆盖所有’0’元素的最少直线数等于矩阵中独立 0 元素的最多个数.” 利用这一定理, 就可以通过寻找 “能覆盖所有 0 元素的最少直线” 来确定矩阵 ? ? Bij ? ? 中独立 0 元素的具体数量。 倘若矩阵 ? ? Bij ? ? 中独立 0 元素的数量小于矩阵的阶数 n, 就得继续对矩阵 ? ? Bij ? ? 进行化简,直到有了 n 个独立的 0 元素为止,找到这 n 个 独立 0 元素也就找到了原指派问题的最优解.这就是匈牙利算法的基本思路.

3.2 匈牙利算法的解题步骤
第一步,对耗费矩阵 C 进行行(或列)约减,即每一行(或列)数据减去 本行(或列)数据中的最小数,得矩阵 C1 ; 第二步,检查矩阵 C1 ,若矩阵 C1 各行各列均有“0” ,则跳过此步,否则进 行列(或行)约减,即每一列(或行)数据减去本列(或行)数据中的最小数, 得矩阵 C2 ; 第三步, 画盖 “0” 线.即画最少的线将矩阵 C2 中的 0 全部覆盖住, 得矩阵 C3 ; 第四步,数据转换.若“盖 0”线的数目等于矩阵的维数则直接跳到第六步, 若“盖 0”线的数目小于矩阵的维数则进行数据转换,进行数据转换的操作步骤 如下: (1)找出未被“盖 0”线覆盖的数中的最小值 ? (2)将未被“盖 0”线覆盖住得数减去 ? (3)将“盖 0”线交叉的数加上 ? 第五步,重复第三步和第四步,直到“盖 0”线的数目等于矩阵的维数. 第六步,求最优解.对 n 维矩阵,找出不同行,不同列的 n 个“0” ,每个“0” 的位置代表一对配置关系,具体步骤如下: (1)先找只含有一个“0”的行(或列) ,将该行(或列)中的“0”打“ ? ” (2)将带“ ? ”的“0”所在列(或行)中的“0”打“ ? ” (3)重复(1)步和(2)步至结束.若所有行列均含有多个“0” ,则从“0” (4)的数目最少得行或列中任选一个“0”打“ ? ” 第七步,打“ ? ”即为员工所对应的指派任务.

4.匈牙利算法求解员工指派问题的模型假设与符号说明
4.1 匈牙利算法解员工指派问题的模型假设
3

(1)员工数目与任务数目相等 (2)求解的是最小化问题,如工作时间最小化、费用最小化等.

4.2 符号说明
表格 4-2 符号 符号说明 表示企业指派的员工数 表示需要完成的任务数 表示指派第 i 人去完成第 j 项任务是所用的时间 表示决策变量 字母符号说明

n m
Cij
xij

5.企业员工指派问题的模型建立与求解
5.1 标准指派问题(当 m=n 时,即为每个人都被指派一项任务)
问题的提出 假定某企业有甲、乙、丙、丁、戊五个员工,需要在一定的生产技术组织条 件下,完成 A、B、C、D、E 五项任务,每个员工完成每项工作所需要耗费的工 作时间,如 5-1 所示. 表 5-1 某企业员工完成任务时间汇总表
员 任 务 工

单位:(小时)
丁 戊







A B C D E

10 13 3 18 11

5 19 2 9 6

9 6 4 12 14

18 12 4 17 19

11 14 5 15 10

请求出:员工与任务之间应当如何进行配置,才能保证完成工作任务的时间最 短?最短时间为多少? 模型的建立

4

设用 Cij ? 0 ?i, j ? 1,2,L ,5? 表示指派第 i 人去完成第 j 项任务时所用的时间,
? 1, 当指派第i人去完成第j项任务时 定义决策变量 xij ? ? ,则指派问题的数学模 ?0,当不指派第i人去完成第j项任务
5 5 ? min Z ? Cij xij ?? ? i ?1 j ?1 ? 5 ? xij ? 1, j ? 1, 2, L ,5 ? ? 型为: ? i ?1 ? 5 ? s.t ? xij ? 1, j ? 1, 2, L 5 ? i ?1 ? x ? 1或0, i, j ? 1, 2, L ,5 ij ?

模型的求解 由题意及匈牙利算法得效益矩阵

10

5

9 6 4

18 11

5

0

4 13 6 6 2 8 8 3 6

13 19 C? 3 2 18 11 9 6

12 14 7 13 0 进行行约减 ?1 0 2 4 5 ???? 9 5 5 0 0 4 3 0 0 0 0 0? 2
重复画“盖0”线 数据转换,标记得 ?

12 17 15 14 19 10 4 0 0 0 0 4 11 3 4 0 6 2 3 6 13 0

8 13 4 4 11 3 4 0 6 4 0
?

6 13 0 2 3 0? 13 4 0? 0?

5 0 3 7 0
?

进行列约减 ???? ?0

8 4

画“盖0线” ?0 0 ???? 3 8

8 11 1

4

8 11 1 2 4 3 2 0?

3 0 4 10 2 5 13 0 3 4 ???? ?0
数据转换

1 0 0

7 3

?0 0 ?????? 3 5 2 4 8 10 0 0? 3 0

6 3 8

0 2 7

?

由此可知当员工甲负责任务 A,员工乙负责任务 D,员工丙负责任务 B,员 工丁负责任务 C,员工戊负责任务 E 时,才能保证完成工作任务的时间最短,且 最短的时间 t=10+9+6+4+10=39 小时.
5

5.2 非标准指派问题
(1)当 m ? n 时,即企业指派的员工数小于要求完成的任务数 问题的提出

某企业安排 2 个员工,完成 3 项任务,每个员工完成每项工作的 时间如表 5-2 [ 4 ] 所示.
表 5-2
员工 任务

某企业员工完成任务时间汇总表一 甲 10 13 3

单位:(小时) 乙 5 19 2

A B C

求:应如何分配任务才能保证工作时间最短? 模型的建立 模型 1 根据题意设用 Cij ? 0 ?i ? 1,2, j ? 1,2,3? 表示指派第 i 人去完成第 j 项任

? 1,当指派第i人去完成第j项任务时 务时所用的时间,定义决策变量 x ij = ? ,则指 ?0,当不指派第i人去完成第j项任务
2 3 ? minZ = Cij x ij ?? ? i=1 j=1 ? 2 ? x ij = 1, j = 1, 2,3 ? ? 派问题的数学模型为: ? i=1 ? 2 ?s.t x ij = 1, j = 1, 2,3 ? ? i=1 ? x = 1或0,i = 1, 2, j = 1, 2,3 ij ?

因为该模型不能直接运用匈牙利算法求解,故我们进行如下分析:两员工负 责三项任务,则必有一个员工需承担两项任务,因此增加甲’和乙’,分别表示 他们完成第二项工作的情况,则上表变形为表 5-3. 表 5-3 某企业员工完成任务时间汇总表二 单位:(小时)
任 员 务 工

甲 10 13 3

甲’ 10 13 3

乙 5 19 2

乙’ 5 19 2

A B C

表 5-3 中,员工数目多于任务数目,添加虚任务 D,得表 5-4
6

表 5-4 某企业员工完成任务时间汇总表三 单位:(小时)
员 任 务 工

甲 10 13 3 0

甲’ 10 13 3 0

乙 5 19 2 0

乙’ 5 19 2 0

A B C D

此时模型 1 变形为模型 2 设用 Cij ? 0 ?i, j ? 1, 2,3, 4? 表示指派第 i 人去完成第 j 项任务时所用的时间, 定义决
? 1, 当指派第i人去完成第j项任务时 策变量 xij ? ? ,则指派问题的数学模型为: ?0,当不指派第i人去完成第j项任务
4 4 ? min Z ? Cij xij ?? ? i ?1 j ?1 ? 4 ? xij ? 1, j ? 1, 2,3, 4 ? ? ? i ?1 ? 4 ? s.t ? xij ? 1, j ? 1, 2,3, 4 ? i ?1 ? x ? 1或0, i, j ? 1, 2,3, 4 ij ?

模型的求解 利 用



























10 10 5 5 5 5 13 13 19 19 进行列约减 0 0 C? ???? ? 3 3 2 2 1 1 0 0 0 0 0 0
5 5 0? 1 0? 0? 6 0? 0? 0? 6 0? 0?
.

0 6 0 0

0 6 0 0

??? ? 线标记得
画“盖0?

0? 1 0?

7

即当乙完成 A、C 任务,甲完成 B 任务时,完成工作时间最短,最短时间 t=5+2+13=20 小时. (2)当 m ? n 时,即企业指派员工数大于要求完成的任务数 问题的提出 某企业目前有 5 名员工,需要完成 4 项任务,每个员工完成每项任务的工 作时间如表 5-5 [ 4 ] 所示. 表 5-5 某企业员工完成任务时间汇总表一 单位:(小时)
任 员 务 A B C D 工 甲 10 13 3 11 乙 5 19 2 6 丙 9 6 4 14 丁 18 12 4 19 戊 11 14 5 10

求:应如何分配任务才能保证工作时间最短? 模型的建立 模型 1 根据题意设用 Cij ? 0 ?i ? 1,2,L ,5, j ? 1,2,3,4? 表示指派第 i 人去完成第
j

































? 1, 当指派第i人去完成第j项任务时 xij ? ? , 则指派问题可转化为 0-1 线性规划问 ?0,当不指派第i人去完成第j项任务
5 4 ? min Z ? Cij xij ?? ? i ?1 j ?1 ? 5 ? xij ? 1, j ? 1, 2, L , 4 ? ? 题: ? i ?1 ? 5 ? s.t xij ? 1, j ? 1, 2, L 4 ? ? i ?1 ? x ? 1或0, i ? 1, 2, L ,5, j ? 1, 2,3, 4 ij ?

因为该模型不能直接运用匈牙利算法求解,故我们进行如下分析:五个员工负责 四项任务则必有一个员工没有任务,此时可增添一项虚任务 E,则各员工完成任 务 E 的时间均为 0,上表变形为 5-6
8

表 5-6 某企业员工完成任务时间汇总表二 单位:(小时)
任务 员工

甲 10 13 3 11 0

乙 5 19 2 6 0

丙 9 6 4 14 0

丁 18 12 4 19 0

戊 11 14 5 10 0

A B C D E

此时模型 1 变形为模型 2: 设用 Cij ? 0 ?i, j ? 1,2,L ,5? 表示指派第 i 人去完成第 j 项任务时所用的时间,
? 1, 当指派第i人去完成第j项任务时 定义决策变量 xij ? ? ,则指派问题可转化为 ?0,当不指派第i人去完成第j项任务

0-1 线性规划问题:
5 5 ? min Z ? ?? Cij xij ? i ?1 j ?1 ? 5 ? xij ? 1, j ? 1, 2, L , 5 ? ? ? i ?1 ? 5 ? s.t ? xij ? 1, j ? 1, 2, L 5 ? i ?1 ? x ? 1或0, i, j ? 1, 2, L , 5 ij ?

模型的求解 此时可用匈牙利算法计算,得效率矩阵

9

10

5

9 18 11

5

0

4 13 6 6 2 0 0 0 0 1 8 3 0 4 12 5 5 7 2 1 2 8 12 3 1 0 0

13 19 C? 3 2 11 0 0

6 12 14 7 13 0 进行行约减 ? ?1 0 2 4 4 5 ???? 画“盖0? 5 0 5 7 0 0 4 0 4 0 0 0 0 1 0? 3 0? 4 0 4 12 5 0

6 14 19 10

8 13 4

6 13 0
进行数据转换 ????? ?0

6 13 0

4 0 1 6
进行数据转换 ????? ? 0? 画“盖0?

画“盖0? ? ?0 2 1 2 ???? 8 12 3 4

1 1 2 5 1

0

0 9 5 1 9 0? 2 7 2 0? 0?

0

16 0?

1 0?

即当甲分配 C 任务, 乙分配 A 任务,丙分配 B 任务,戊分配 D 任务时,工 作时间最短,最短时间 t=3+5+6+10=24 小时. (3)当所求问题为求最大化值时 问题的提出 某企业目前有 5 名员工完成 5 项任务,每个员工完成各项任务所获得的利 润如表 5-7 [ 4 ] 所示.


任务



表 5-7 某企业员工完成任务收益汇总表一 单位:(万元) 甲 乙 丙 丁 戊 10 13 3 18 11 5 19 2 9 6
10

A B C D E

9 6 4 12 14

18 12 4 17 19

11 14 5 15 10

求:如何给甲、乙、丙、丁、戊分配任务,使他们完成任务总收益最大? 问题分析 因为匈牙利算法求得是最小化问题, 故我们需把最大化问题转化为最小化问 题,我们取 e ? max C ? i ? 1, 2, L
ij

n, j ? 1, 2, L m ? ,令 bij ? e ? Cij ? i ? 1,2, L n, j ?1,2, Lm
n m i ?1 j ?1

? ,这样

我们就可以将最大化问题转化为最小化问题了,即 min f ? ?? bij xij 由题意知表 5-7 中最大的数据为 19,用 19 分别减去其中的各个数据,则数 据表转化为表 5-8. 表 5-8 某企业员工完成任务收益汇总表二 单位:(万元)
员 任 务 A B C 9 6 16 14 0 17 10 13 15 1 7 15 8 5 14 工 甲 乙 丙 丁 戊

D E

1 8

10 13

7 5

2 0

4 9

模型的建立 设用 Cij ? 0 ?i, j ? 1,2,L ,5? 表示指派第 i 人去完成第 j 项任务时所用的时间,定义
? 1, 当指派第i人去完成第j项任务时 决策变量 xij ? ? ,则指派问题可转化为 0-1 ?0,当不指派第i人去完成第j项任务
5 5 ? min Z ? Cij xij ?? ? i ?1 j ?1 ? 5 ? xij ? 1, j ? 1, 2, L ,5 ? ? 线性规划问题: ? i ?1 ? 5 ? s.t ? xij ? 1, j ? 1, 2, L 5 ? i ?1 ? x ? 1或0, i, j ? 1, 2, L ,5 ij ?

模型的求解

11

此 时 可 以 用 匈 牙 利 算 法 求 解 , 得 效 率 矩 阵
9 6 C ? 16 1 8 14 0 17 10 13 10 13 15 7 5 1 7 15 2 0 8 5
进行行约减

8 6 0 8

13 0 3 9 13

9 13 1 6 5

0 7 1 1 0

7 5 0 3 9

?2 14 ????
4 9

8 6

13 0 3 9 13

8 12 0 5 4

0 7 1 1 0

7 5
数据转换

4 6 0 4

9 0 3 9 9

4 12 0 5 0

0 11 5 5 0

3 5 0 3 5

???? ?2 画“盖0?
进行列约减

? 2 0 ????
3 9

0 8

4 6
画“盖0? ???? ? ? 2

9 0? 3 9 9

4 12 0? 5 0
?

0? 11 5 5 0
?

3 5 0? 3 5

0? 4

即当甲分配 D 任务,乙分配 B 任务,丙分配 E 任务,丁分配 A 任务,戊分配 C 任务时,他们完成的任务收益最大,最大值为 18+19+14+18+5=74 万元.

6.匈牙利算法的缺点、改进以及 C 语言实现
6.1 匈牙利算法的缺点 1.“匈牙利算法”在各种已发表的教材、专著和研究成果中,通常求解中、 小型分配问题,效能矩阵的阶数通常不超过 20,故很难发现“匈牙利算法”存 在的问题.事实上,匈牙利算法在处理一些特殊数据时并不有效,算法不收敛, 无法找出最优解 [ 6 ] . 2.在匈牙利算法的求解步骤中,效率矩阵既可以先进行“行约减”也可先进 行“列约减” ,并没有说是先进行“行约减”还是先进行“列约减” ,但是,有时 先进行“行约减”要比先“列约减”复杂,增加了许多步,有时却相反,我们来 看下面例题.

12

例题:效率矩阵 [5 ]

15 19 A? 26 17

18 23 17 21

21 22 16 23

24 18 19 17

1.先进行“行约减” :

15 19 A? 26 17

18 23 17 21

21 22 16 23

24 0 18 1 进行“行约减” ????? ? 19 10 17 0 2 4 0 3 0 2 0 1 4 2 0? 4 6 4 0 6 4 2 0 4 9 0 0 1 画盖0线 ???? 3 10 0 0 9 0 0 1 画盖 0 线 ???? 5 12 0 0 9 0? 5 0?

3 5 1 4 2 4 0 3 0 2 0 1

6 4 0 6 6 4 0 6 4 2 0 4

9 0 3 0 9 0 3 0 9 0 5 0

0 1 进行“列约减” ????? ? 10 0 0 1 进行数据转换 ????? ? 12 0 0? 1 标记得 ??? ? 12 0?
2.先进行“列约减” :

0? 2 0? 1

0 1 5 7 15 18 21 24 19 23 22 18 进行“列约减” 4 6 6 1 ????? ? A? 11 0 0 2 26 17 16 19
17 21 23 17

2 4 7 0

13

0
进行“行约减” ????? ?

1

5 5 0 7 5 3 0 5

7

0

1

5 5 0 7 5 3 0 5

7 0 2 0 9 0 4 0

3 5 11 0 2 0 4 1

0 画盖0线 3 5 ???? 2 11 0 0 9 2 0 4 1

进行数据转换 ????? ?

1 3 11 0 0 2

0 画盖0线 1 3 ???? 4 11 0 0 0 2

0
进行数据转换 ???? ?

0 4 9 2 2 0 1 4 0
画盖 0 线 ??? ?

0 1 0

0 4 9 2 2 0 1 4 0

1 0

12 0 0 5

12 0 0 5

0? 0? 4 9 1 2 2 0? 标记得 ??? ? 12 0? 0? 5 0? 1 4 0?
由此可见,先进行“行约减”比先进行“列约减”更简单. 6.2 匈牙利算法的改进 综合上面两道例题, 我们知道匈牙利算法还是有一些不足的,经过我反复的 实验、观察效率矩阵的特殊性,现对效率矩阵进行改进,改进之后,就能少了许 多麻烦的步骤,知道是先进行“行约减”还是先进行“列约减”.匈牙利算法的 改进如下: 第一步,简化效率矩阵 . ( 1 )统计效率矩阵每行的最小元素的个数总和

R ? sum? 和每列的最小元素的个数总和 C ? sum? .(2)若 R ?sum ? 和 C ? sum? 均大于

n ,且当 R ? sum? ? C ? sum? 时,则先对效率矩阵的每列减去该列的最小元素,再
14

对所得的效率矩阵的每行减去该行的最小元素.反之,当 R ? sum? ? C ? sum? 时,则 先对效率矩阵的每行减去该行的最小元素, 再对所得效率矩阵的每列元素减去该 列的最小元素( . 3) 若 R? u s m
且当 R ? sum? ? C ? sum? 时, ? 和 C ? sum? 不满足均大于 n ,

则先对效率矩阵的每列减去该列的最小元素, 再对所得的效率矩阵的每行减去该 行的最小元素.反之,R ? sum? ? C ? sum? 时,则先对效率矩阵的每行减去该行的最 小元素,再对所得的效率矩阵的每列减去该列的最小元素. 第二步,检查矩阵 C1 ,若矩阵 C1 各行各列均有“0” ,则跳过此步,否则进 行列(或行)约减,即每一列(或行)数据减去本列(或行)数据中的最小数, 得矩阵 C2 第三步, 画盖 “0” 线.即画最少的线将矩阵 C2 中的 0 全部覆盖住, 得矩阵 C3 ; 第四步,数据转换.若“盖 0”线的数目等于矩阵的维数则直接跳到第六步, 若“盖 0”线的数目小于矩阵的维数则进行数据转换,进行数据转换的操作步骤 如下: (1)找出未被“盖 0”线覆盖的数中的最小值 ? (2)将未被“盖 0”线覆盖住得数减去 ? (3)将“盖 0”线交叉的数加上 ? 第五步,重复第三步和第四步,直到“盖 0”线的数目等于矩阵的维数. 第六步,求最优解.对 n 维矩阵,找出不同行,不同列的 n 个“0” ,每个“0” 的位置代表一对配置关系,具体步骤如下: (1)先找只含有一个“0”的行(或列) ,将该行(或列)中的“0”打“ ? ” (2)将带“ ? ”的“0”所在列(或行)中的“0”打“ ? ” (3)重复(1)步和(2)步至结束。若所有行列均含有多个“0” ,则从“0” (4)的数目最少得行或列中任选一个“0”打“ ? ” 第七步,打“ ? ”即为员工所对应的指派任务. 6.3 匈牙利算法的 C 语言实现(附录)

7.匈牙利算法的应用推广
匈牙利算法不仅在企业员工指派问题上有重要的应用, 而且它还解决了集体 比赛项目中参赛队员的出场次序问题提供了一个科学的决策方法. 例 设有 A,B,C,D 四个队员参加 4 ? 100 米接力赛跑,由于各队员的心理素

质、 交接棒技术、 起跑以及冲刺速度等原因, 所跑不同棒次所用时间 (单位为秒) 不尽相同,见下表 1 [9 ] .
15

棒次





1 10 10.01 10.01 10

表 1(单位:秒) 2 10.01 10.01 10.01 10.01

3 10.01 10.01 10.01 10.01

4 10 10.01 10.02 10.01

A B C D

10 10.01 利用匈牙利算法求解,得效益矩阵 M = 10.01 10

10.01 10.01 10.01 10.01

10.01 10 10.01 10.01 10.01 10.2 10.01 10.01

0
进行行约减 ???? ?

0.01 0 0 0.01

0.01 0 0 0.01

0 0 0.01 0.01
画盖 0 线 ??? ?

0 0 0 0

0.01 0 0 0.01

0.01 0 0 0.01

0 0 0.01 0.01

0 0 0

标记 ??? ?

0? 0? 0? 0?

0.01 0.01 0? 0? 0? 0?

0? 0? 0.01



0? 0? 0? 0?

0.01 0.01 0? 0? 0? 0?

0? 0? 0.01

0.01 0.01 0.01

0.01 0.01 0.01

因此,得到两种最优指派方案:方案一:A 跑第四棒,B 跑第二棒,C 跑第 三棒,D 跑第一棒;方案二:A 跑第四棒,B 跑第三棒,C 跑第二棒,D 跑第一 棒,所需的总时间为 10+10.01+10.01+10=40.02(秒).

16

8.结束语
本文阐述了企业员工指派问题, 在数学建模的思想基础上运用匈牙利算法对 企业员工指派问题进行求解, 并对匈牙利算法的缺点进行改进以及匈牙利算法的 C 语言实现并将其应用到现实的例子当中.虽然,匈牙利算法有一些不足之处,但 是匈牙利算法仍然是企业求解员工指派问题的一种好方法, 它为企业进行员工指 派任务时提供了巨大的帮助,匈牙利算法具有很强的实用性.虽然,本文尝试对 匈牙利算法进行了一些技巧性的改进,但是需要指出的是,我对匈牙利算法的改 进只是一种经验,未能有严谨的证明.

17

参考文献
[1] 束金龙,闻人凯.线性规划理论与模型应用[M] .北京:科学出版社,2003. [2] 胡运权,运筹学基础及应用(第五版) [M] .北京:高等教育出版社,2010. [3] 胡运权,运筹学基础及应用(第五版) [M.] .北京:高等教育出版社,2010. [4] 中国就业培训技术指导中心 组织编写,企业人力资源管理师(三级)[M]. 北京:中 国劳动社会保障出版社,2007. [5] 程红萍. 简化匈牙利算法求解的思考[J].渭南师范学院学报,2007,22(5):32-34. [6] 张联朋.对指派问题匈牙利算法的两点改进[J].西安航空技术高等专科学校学报, 2007,25(1):64-66. [7] 袁迁, 刘舒燕. 关于匈牙利算法的优化[J]. 武汉理工大学学报, 2007, 29(3): 146-149. [8] 张联朋.寻找独立元素的一种新方法[J].重庆职业技术学院学报,2007,16(1): 160-161. [9] 林同曾主编.运筹学 [M].北京:机械工业出版社,1986. [10] 杨文鹏,贺兴时,等.新编运筹学教程[M].西安:陕西科学技术出版社,2005.

18

附录
匈牙利算法程序如下: #include<stdio.h> #include<malloc.h> //#define M 5 //#define N 5 #define MAXSIZE 10 int M,N; int arrangement[999][999]; /*二维耗费矩阵,i 行是雇员 i,j 列是工作 j,arrangement[i][j]是耗费*/ int bestcost=999; int x[999]; int bestx[999]; /*bestcost 是当前最优值*/ /*x 是当前调度*/ /*bestx 最优分配*/

void backtrackarrage(int i,int cost); void outputresult(); void swap(int i,int j); main() { int i,j; printf("请输入行(人数):M="); 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;i<M;i++) for(j=0;j<N;j++) scanf("%d",&arrangement[i][j]); }else{
19

printf("你选择的是文件读入\n"); FILE *fp; fp=freopen("input.txt","r",stdin); for(i=0;i<M;i++) for(j=0;j<N;j++) scanf("%d",&arrangement[i][j]); } for(i=0;i<N;i++) x[i]=i; backtrackarrage(0,0); outputresult(); // getch(); } /*递归回溯函数,确定最优调度方案,i 是递归层数,cost 是当前求得的解*/ void backtrackarrage(int i,int cost) { int j; /*初始化当前调度*/

/*回溯求解*/ /*输出结果*/

if(i==N) { if(cost<bestcost) { bestcost=cost; for(j=0;j<N;j++) bestx[j]=x[j]; } } else{ for(j=i;j<N;j++) { cost+=arrangement[i][x[j]]; if(cost<bestcost)
20

{ swap(i,j); backtrackarrage(i+1,cost); swap(i,j); } cost-=arrangement[i][x[j]]; } } } /*交换函数 为了得到一个排序树的排序,即一个全排列*/ void swap(int i,int j) { int temp; temp=x[i]; x[i]=x[j]; x[j]=temp; } void outputresult() { int i; printf("计算结果是:\n"); printf("event\tpeople"); for(i=0;i<N;i++) printf("\n %d\t %d",i+1,bestx[i]+1); printf("\n\n\tbest cost:%d\n",bestcost); }

21

致谢
感谢林耿指导老师对我论文细心、耐心的指导,感谢李涛同学对我 C 语言方 面的指导,感谢舍友、同学对我精神上的鼓励!在他们的帮助下我认真、有序地 完成了论文的写作工作,在此我非常感谢他们,祝他们身体健康、工作顺利、学 习进步!

22


相关文章:
匈牙利算法在企业员工指派问题的应用(最终版).doc
匈牙利算法在企业员工指派问题的应用(最终版) - 闽江学院 本科毕业论文 题目
毕业设计与论文(匈牙利算法在企业员工指派问题的应用)_....pdf
毕业设计与论文(匈牙利算法在企业员工指派问题的应用) - 本科毕Jk.‘份文 题目 匈牙利 算法在企业员工指派问题 的 应用 学生姓名 ,且乡 寸~ 卫二L '7 ...
匈牙利算法的应用.doc
通常可以采用运筹学的 数量分析方法, 例如, 在解决员工任务指派问题时, 企业普遍采用的一种方法匈牙利法, 就是实现人员与工作任务配置合理化、科学化的典型方法...
匈牙利算法在企业员工指派问题的应用(最终版).doc
匈牙利算法在企业员工指派问题的应用(最终版)_数学_自然科学_专业资料。闽江学院
指派问题_匈牙利算法.ppt
指派问题_匈牙利算法_计算机软件应用_IT/计算机_专业资料。?管理与人文学院 1999...如任务分配问题、匹配问题 6 4.6 任务分配问题例4.6.1 有四个熟练工人,他们都...
论匈牙利算法在指派问题管理工作中的应用_论文.pdf
匈牙利算法在指派问题管理工作中的应用 - ? 214 ? 价值工程 论匈牙利算法在指派问题管理工作中的应用 Application of Hungary Algorithm in As...
分配问题与匈牙利法_图文.ppt
配实例进行分析研究,最终得出人员与岗位 配置的最优化解,从而为企业的人事决策提...关键词: 员工任务分配;匈牙利法;指派;最优化解 匈牙利法应用的实证分析 1、...
指派问题的匈牙利法.ppt
指派问题的匈牙利法_工学_高等教育_教育专区。指派问题的匈牙利法指派问题指派问题是一种特殊的整数规划问题 一、问题的提出 设有m个工人,能做n件事,但效率不 同...
匈牙利算法求解教学任务指派问题.doc
应用匈牙利算法建立指派模型,求解复杂因素下的教学任务...将具有并联环节的人员指派问题转化为典型的指派问 题...决策问题,任何 一个参数的改变都可能影响最终的指派...
指派问题匈牙利法_图文.ppt
指派问题的匈牙利解法 约化矩阵性质应用 ? 2 3 5 7? ? ? ? 3 5 2 8?...匈牙利算法在企业员工指... 27页 3下载券 运筹学指派问题的匈牙利... ...
匈牙利法应用实例.pdf
匈牙利法应用实例_企业管理_经管营销_专业资料。人力资源管理师员工任务指派方法 ...匈牙利法解决员工任务合理指派问题 时,应当具备以下两个约束条件 1.员工数目与...
指派问题的匈牙利法_图文.ppt
指派问题的匈牙利法_法律资料_人文社科_专业资料。指派问题指派问题是一种特殊的整数规划问题 一、问题的提出 设有m个工人,能做n件事,但效率不 同,并规定每个...
运用匈牙利法算法.ppt
匈牙利法的起源和提出 2.匈牙利法运用员工指派时...匈牙利法是求解及小型(优化方向为极小) 指派问题的...匈牙利法的具体计算方法 ? 假定甲单位有甲、乙、丙...
指派问题与匈牙利算法_图文.ppt
的特征及其应用; 求解方法有:解一般整数规划用分枝定界法、割平面法; 解0-1...运筹学指派问题的匈牙利... 15页 2下载券 匈牙利算法在企业员工指... 27...
指派问题匈牙利法_图文.ppt
指派问题的匈牙利解法 约化矩阵性质应用 ? 2 3 5 7? ? ? ? 3 5 2 8?...匈牙利算法在企业员工指... 27页 3下载券 运筹学指派问题的匈牙利... ...
指派问题的算法.doc
公司的运营与管理中,管理者总是希望把人员最佳分派以发挥其最 大工作效率,从而...通过运用 匈牙利算法和 0-1 整数规划同时对指派问题求解, 我们发现用 0-1 ...
五种计算公式.doc
人力资源管理师三级(三版)计算题汇总历年考点:定员,劳动成本,人工成本核算,招聘...三、匈牙利分析法 在解决员工任务指派问题企业普遍采用匈牙利法 应用条件:...
基于改进匈牙利算法的多技能人员调度方法_图文.pdf
指派问题人员调度问题中的经典问题 m ...1 经典匈牙利算法应用上的不足1.1 经典匈牙利...improvedHungaryalgorithm 那么, Tviq 增加一个单位。...
第26章 基于匈牙利算法的指派问题优化分析_图文.ppt
第26章 基于匈牙利算法的指派问题优化分析_数学_自然...分析与应用 表26-1 效率矩阵指派问题人员 甲乙丙丁...
分配问题与匈牙利算法_图文.ppt
匈牙利法第一步:变换指派问题的系数矩阵(cij)为(...人员 甲 工作 A 7 B 5 C 9 D 8 E 11 乙丙...使用百度前必读 | 文库协议 | 广告服务 | 企业...
更多相关标签: