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

120080901139

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 ·································

1. 引言

m m

??a
i ?1 j ?1

ij

x ij

2.指派问题的数学模型
2.1 指派问题

1

2.2 指派问题的数学模型

? 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 ?

，则指派问题可转

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

2

3.2 匈牙利算法的解题步骤

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

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

4.2 符号说明

n m
C ij
x ij

5.企业员工指派问题的模型建立与求解
5.1 标准指派问题（当 m=n 时，即为每个人都被指派一项任务）

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

? 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

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

13 4 0 0
? ?

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

6 3 8

4 0
?

2 7

5

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

[4]

A B C

? 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 ?

A B C

6

A B C D

? 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

?

6 0 0
?

6 0 0
?

1 0
?

1 0
?

.

?

?

7

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 线性规划问

8

A B C D E

? 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 ? 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

10

A B C D E

9 6 4 12 14

18 12 4 17 19

11 14 5 15 10

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

? ，这样

??b
i ?1 j ?1

n

m

ij

x ij

D E

1 8

10 13

7 5

2 0

4 9

? 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

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

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

? ? ??

1 10 0 0

?? ? ? ? ?

1 12 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 ? ? ??

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

??? ?

1 12 0

0 ??? ?

?

0

?

4 2 0
?

9 0
?

1 12 0
?

2 0
?

5 0
?

1

4

R ? s u m? 和每列的最小元素的个数总和 C ? su m ?

.（2）若 R ?sum ? 和 C ? su m ? 均大于

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

14

s 列的最小元素. （3） R ?m 若 u

7.匈牙利算法的应用推广

15

1 10 10.01 10.01 10

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

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 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

16

8.结束语

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

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

22

a i j n n ij ij x 就是问题的最 第二部分结合我的基础知识对匈牙利算法的分析与展望 一.基础知识运用 企业员工指派问题的模型建立与求解 1.标准指派问题(...