当前位置:首页 >> 数学 >>

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


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

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)在求解著名的指派 问题时引用了这一结论,并对具体算法做了改进,仍然称为“匈牙利算法”.解 指派问题的匈牙利算法是从这样一个明显的事实出发的: 如果效率矩阵的所有元 素 a ij ? 0 ,而其中存在一组位于不同行不同列的零元素,则只要令对应于这些零 元素位置的 x ij ? 1 ,其余的 x ij ? 0 ,则 z ?
m m

??a
i ?1 j ?1

ij

x ij

就是问题的最优解.

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

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

2.2 指派问题的数学模型
设用 C ij ? 0 ? i , j ? 1, 2, L , n ? 表示指派第 i 人去完成第 j 项任务时所用的时 间,定义决策变量 x ij ? ?
? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务
n n ? m in Z ? ? ? C ij x ij ? i ?1 j ?1 ? n ? ? ? x ij ? 1, j ? 1, 2, L , n ? i ?1 ? n ? s .t ? x ij ? 1, j ? 1, 2, L n ? i ?1 ? x ? 1或 0, i , j ? 1, 2, L , n ij ?

,则指派问题可转

化为 0-1 线性规划问题:

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

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

3.2 匈牙利算法的解题步骤
第一步,对耗费矩阵 C 进行行(或列)约减,即每一行(或列)数据减去 本行(或列)数据中的最小数,得矩阵 C 1 ; 第二步,检查矩阵 C 1 ,若矩阵 C 1 各行各列均有“0” ,则跳过此步,否则进 行列(或行)约减,即每一列(或行)数据减去本列(或行)数据中的最小数, 得矩阵 C 2 ; 第三步, “0” 画盖 线.即画最少的线将矩阵 C 2 中的 0 全部覆盖住, 得矩阵 C 3 ; 第四步,数据转换.若“盖 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 符号
n m
C ij
x ij

字母符号说明

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

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

设用 C ij ? 0 ? i , j ? 1, 2, L , 5 ? 表示指派第 i 人去完成第 j 项任务时所用的时间, 定义决策变量 x ij ? ?
? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务

,则指派问题的数学模

型为:

5 5 ? m in Z ? ? ? C ij x ij ? i ?1 j ?1 ? 5 ? ? ? x ij ? 1, j ? 1, 2, L , 5 ? i ?1 ? 5 ? s .t ? x ij ? 1, j ? 1, 2, L 5 ? i ?1 ? x ? 1或 0, i , j ? 1, 2, L , 5 ij ?

模型的求解 由题意及匈牙利算法得效益矩阵
10 13 C ? 3 18 11 5 19 2 9 6 9 6 4 12 14 4 6 ? ? ? ?? 0 8 4 3 5 ?? ?? 0 ? 7 3
数据转换 进行列约减

18 12 4 17 19 0 13 0 0 0 0 4 0 3 3 8 4 0 2 3 8

11 14
进行行约减

5 7

0 13 0 0 0 4 6

4 0 2 3 8 0 13 0 0 0 0
?

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

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

5 ? ? ? ?? 1 15 10 11 4 0 6 11 10 3 0 5 10 2 4 3 5
画 “ 盖 0线 ”

9 5

3 5 0 3 1 7 0 0
? ?

0 ? ? ? ?? 0 3 1 8 4

2 4 3 2 0
?

13 1 0 0

2
重 复 画 “ 盖 0” 线 ?

13 4 0 0
? ?

? 转换, 记 ? 0 ? 数 据 ? ?标?得 ? 0 2 0

6 3 8

4 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 根据题意设用 C ij ? 0 ? i ? 1, 2, j ? 1, 2, 3 ? 表示指派第 i 人去完成第 j 项任 务时所用的时间,定义决策变量 x ij = ?
? 1 , 当 指 派 第 i人 去 完 成 第 j项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务

,则指

派问题的数学模型为:

2 3 ? m in Z = ? ? C ij 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 设用 C ij ? 0 ? i , j ? 1, 2, 3, 4 ? 表示指派第 i 人去完成第 j 项任务时所用的时间, 定义决 策变量 x ij ? ?
? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务

,则指派问题的数学模型为:

4 4 ? m in Z ? ? ? C ij x ij ? i ?1 j ?1 ? 4 ? ? ? x ij ? 1, j ? 1, 2 , 3, 4 ? i ?1 ? 4 ? s .t ? x ij ? 1, j ? 1, 2 , 3, 4 ? i ?1 ? x ij ? 1或 0 , i , j ? 1, 2 , 3, 4 ?

模型的求解 利 用



























10 C ? 13 3 0

10 13 3 0

5 19 2 0

5 19 2 0
? ?

5 ? ? ? ??
进行列约减

5 0 1 0

0 6 0 0

0 6 0 0

0 1 0

5

5 0
?

0

0

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

0

?

6 0 0
?

6 0 0
?

1 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 根据题意设用 C ij ? 0 ? i ? 1, 2, L , 5, j ? 1, 2, 3, 4 ? 表示指派第 i 人去完成第
j

































? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 x ij ? ? ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务
5 4 ? m in Z ? ? ? C ij x ij ? i ?1 j ?1 ? 5 ? ? ? x ij ? 1, j ? 1, 2, L , 4 ? i ?1 ? 5 ? s .t ? x ij ? 1, j ? 1, 2, L 4 ? i ?1 ? x ij ? 1或 0, i ? 1, 2, L , 5, j ? 1, 2, 3, 4 ?

, 则指派问题可转化为 0-1 线性规划问

题:

因为该模型不能直接运用匈牙利算法求解,故我们进行如下分析:五个员工负责 四项任务则必有一个员工没有任务,此时可增添一项虚任务 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: 设用 C ij ? 0 ? i , j ? 1, 2, L , 5 ? 表示指派第 i 人去完成第 j 项任务时所用的时间, 定义决策变量 x ij ? ?
? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务

,则指派问题可转化为

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

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

9

10 13 C ? 3 11 0

5 19 2 6 0

9 6 4 14 0 4 6

18 12 4 19 0 0 13 0 0 1 0
?

11 14
进行行约减

5 7

0 13 0 0 0 4 6

4 0 2 8 0

13 6 2 13 0 0 13 0 0 1 4 0 2 8 1

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

? 盖0 ? 5 ? 画 “ ? ?? 1 10 0 4 0 2 8 1 1 0
?

5 0 12 5 1 12 0 5 7
画“盖0

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

进行数据转换

? 2 ? ? ? ?? 0 3 0 9 5 1 9 0
?

4 0 2 7 2 0 0
? ?

16 3 0
?

2 5 1

4

即当甲分配 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 ?
m ax C ij

?i

? 1, 2 , L n , j ? 1, 2 , L m ?

,令 b

i j

? e ? C ij

?i

? 1, 2, L n , j ? 1, 2,

Lm

? ,这样

我们就可以将最大化问题转化为最小化问题了,即 m in f ?

??b
i ?1 j ?1

n

m

ij

x ij

由题意知表 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

模型的建立 设用 C ij ? 0 ? i , j ? 1, 2, L , 5 ? 表示指派第 i 人去完成第 j 项任务时所用的时间,定义 决策变量 x ij ? ?
? 1, 当 指 派 第 i 人 去 完 成 第 j 项 任 务 时 ? 0, 当 不 指 派 第 i 人 去 完 成 第 j 项 任 务
5 5 ? m in Z ? ? ? C ij x ij ? i ?1 j ?1 ? 5 ? ? ? x ij ? 1, j ? 1, 2, L , 5 ? i ?1 ? 5 ? s .t ? x ij ? 1, j ? 1, 2, L 5 ? i ?1 ? x ? 1或 0, i , j ? 1, 2, L , 5 ij ?

,则指派问题可转化为 0-1

线性规划问题:

模型的求解

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

13 0 3 9 13

9 13 1 6 5

0 7 1 1 0

7 5 0 3 9

? 14 ? ? ? ? 2
4 9 0 8

8 6

13 0 3 9 13

8 12 0 5 4

0 7 1 1 0

7 5
数据转换

4 6

9 0 3 9 9

4 12 0 5 0

0 11 5 5 0

3 5 0 3 5

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

? 2 0 ????
3 9 0 4

0 8

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

9 0
?

4 12 0
?

0

?

3 5 0
?

11 5 5 0
?

3 9 9

5 0
?

3 5

4

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

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

12

1 5

1 8 2 3 1 7 2 1

2 1 2 2 1 6 2 3

2 4 1 8 1 9 1 7

例题:效率矩阵 [ 5 ]

A?

1 9 2 6 1 7

1.先进行“行约减” :
15 A ? 19 26 17 18 23 17 21 21 22 16 23 0 ?? ? ? ? ?
进行“列约减”

24 18 19 17 2 4 0 3 0 2 0 1 6 4 0 6 4 2 0 4 4 2 0
?

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

3 5 1 4 0 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

1 10 0

9 0 3 0 9 0 5 0 9 0
?

1 10 0 0

? ? ??

画 盖 0线

1 10 0 0

?? ? ? ? ?

进行数据转换

1 12 0

? ? ??

画 盖 0线

1 12 0

0 ?? ? ?
标记得

?

0

?

1 12 0
?

2 0
?

5 0
?

1

4

2.先进行“列约减” :

15 A? 19 26 17

18 23 17 21

21 22 16 23

24 18 19 17

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

1 6 0 4

5 6 0 7

7 1 2 0

4 11 2

13

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

1 5 0 4 1 3 0 2

5 5 0 7 5 3 0 5

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

0 ? ? ??
画 盖 0线

1 5 0 4 1 3 0 2

5 5 0 7 5 3 0 5

7 0 2 0 9 0 4 0

3 11 2 0

3 11 2 0 1 11 0

????? ?

进行数据转换

1 11 0

0

0 2 0 1

4 2 0 4

9 0 5 0

0

0 2 0 1

4 2 0 4

9 0 5 0

? ? ? ??
进行数据转换

1 12 0

??? ?
画盖 0线

1 12 0

0 ??? ?
标记得

?

0

?

4 2 0
?

9 0
?

1 12 0
?

2 0
?

5 0
?

1

4

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

.(2)若 R ?sum ? 和 C ? su m ? 均大于

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

14

对所得的效率矩阵的每行减去该行的最小元素.反之,当 R ? su m ? ? C ? su m ? 时,则 先对效率矩阵的每行减去该行的最小元素, 再对所得效率矩阵的每列元素减去该
s 列的最小元素. (3) R ?m 若 u

且 ? 和 C ? su m ? 不满足均大于 n , 当 R ? su m ? ? C ? su m ? 时,

则先对效率矩阵的每列减去该列的最小元素, 再对所得的效率矩阵的每行减去该 行的最小元素.反之,R ? su m ? ? C ? su m ? 时,则先对效率矩阵的每行减去该行的最 小元素,再对所得的效率矩阵的每列减去该列的最小元素. 第二步,检查矩阵 C 1 ,若矩阵 C 1 各行各列均有“0” ,则跳过此步,否则进 行列(或行)约减,即每一列(或行)数据减去本列(或行)数据中的最小数, 得矩阵 C 2 第三步, “0” 画盖 线.即画最少的线将矩阵 C 2 中的 0 全部覆盖住, 得矩阵 C 3 ; 第四步,数据转换.若“盖 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 ? 1 0 0 米接力赛跑,由于各队员的心理素

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

15

棒次





1 10 10.01 10.01 10

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

3 10.01 10.01 10.01 10.01
1 0 .0 1 1 0 .0 1 1 0 .0 1 1 0 .0 1 1 0 .0 1 1 0 .0 1 1 0 .0 1 1 0 .0 1 10 1 0 .0 1 1 0 .2 1 0 .0 1

4 10 10.01 10.02 10.01

A B C D

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

1 0 .0 1 1 0 .0 1 10

0

0 .0 1 0 0 0 .0 1

0 .0 1 0 0 0 .0 1

0 0 0 .0 1 0 .0 1

0

0 .0 1 0 0 0 .0 1

0 .0 1 0 0 0 .0 1

0 0 0 .0 1 0 .0 1

???? ?
进行行约减

0 0 0

??? ?
画盖 0线

0 0 0

0 ? ?? ?
标记

? ? ? ?

0 .0 1 0 0
? ?

0 .0 1 0 0
? ?

0 0

? ?

0 或 0 0 0

? ? ? ?

0 .0 1 0 0
? ?

0 .0 1 0 0
? ?

0 0

? ?

0 0 0

0 .0 1 0 .0 1

0 .0 1 0 .0 1

0 .0 1

0 .0 1

0 .0 1

0 .0 1

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

16

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

17

参考文献
[1] 束金龙,闻人凯.线性规划理论与模型应用[M] .北京:科学出版社,2003. [2] 胡运权,运筹学基础及应用(第五版) .北京:高等教育出版社,2010. [M] [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


相关文章:
浅析指派问题的匈牙利解法成稿
数学与应用数学 指导教师:苏孟龙 学号:040414057 ...关键词:指派问题;匈牙利解法;最小零元素消耗法;对角...如给工人分派工作,给车辆分配道路,给 工人分配机床...
求解指派问题的匈牙利算法.doc
求解指派问题的匈牙利算法.doc_理学_高等教育_教育专区。该文档结合实际例子对指派问题的匈牙利算法做了详细的分析求解 3.2 求解指派问题的匈牙利算法 由于指派问题的...
运筹学指派问题的匈牙利法实验报告
运筹学指派问题的匈牙利法实验报告_数学_自然科学_专业资料。指派问题的匈牙利法实验报告 运筹学课程设计报告 专业: 班级: 学号: 姓名: 2012 年 6 月 20 日 ...
指派问题的匈牙利解法
指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值;然后在此基础上 再把每列元素减去本列中的最小值。 ?4 ? ?7 ?6 ? ?6 ?6 ? 2、 8 ...
运筹学指派问题的匈牙利法
运筹学指派问题的匈牙利法_数学_自然科学_专业资料。指派问题的匈牙利法运筹学课程设计 指派问题的匈牙利法 专业: 姓名: 学号: 1. 算法思想:匈牙利算法的基本思想是...
指派问题的匈牙利解法
第五讲_分配问题(指派问题... 44页 免费 分配问题与匈牙利法-毕德春... 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
更多相关标签: