招聘与配置-匈牙利法.
招聘与配置
匈牙利法 P96,98
假定甲单位有甲、乙、丙、丁、戊五个员工,需要在一定的生产技术组织条件下,完成A、B、C、D、E五项任务,每个员工完成每项工作所需要耗费的工作时间,如
2,6所示。
请求出:员工与任务之间应当如何进行配置,才能保证完成工作任务的时间最短,
表2,6 各员工完成任务时间汇总表 单位:小时
员工 甲 乙 丙 丁 戊 任务
10 5 9 18 11 A
13 19 6 12 14 B
3 2 4 4 5 C
18 9 12 17 15 D
11 6 14 19 10 E
注意:由于存在以下两种情况,匈牙利法的计算过程不唯一,最终矩阵的形式也不唯一,但最终配置结果一定相同,
1(约减时,可先进行行约减,再进行列约减;也可先进行列约减,再进行行约减。 2(“盖0”线的画法不唯一。
现列举两种解法如下:
解法一:
(以各个员工完成各项任务的时间构造矩阵一。 1
表2,7 矩阵一
10 5 9 18 11
13 19 6 12 14
3 2 4 4 5
18 9 12 17 15
11 6 14 19 10
2(对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。
表2,8 矩阵二
5 0 4 13 6
7 13 0 6 8
1 0 2 2 3
9 0 3 8 6
5 0 8 13 4
3(检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三。
表2,9 矩阵三
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
4(画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住,得图2,5。
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
图2,5 矩阵四
操作技巧:从含“0”最多的行或列开始画“盖0”线。
5(数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线得数目小于矩
阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:
,,)找出未被“盖0”线覆盖的数中的最小值,例中,1。 (1
,(2)将未被“盖0”线覆盖住的数减去。
,(3)将“盖0”线交叉点的数加上。
本例结果见表2,10 矩阵五。
表2,10 矩阵五
3 0 4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
6(重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。
本例最终矩阵见表2,11。
3 0 4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
矩阵五a
0 0 4 7 2
2 13 0 0 4
0 4 6 0 3
4 0 3 2 2
0 0 8 7 0
矩阵五b
表2,11 矩阵六
0 0 4 7 2
2 13 0 0 4
0 4 6 0 3
4 0 3 2 2
0 0 8 7 0
7(求最优解。对n维矩阵,找出不同行、不同列的n个“0”,每个“0”的位置代表一对配
置关系,具体步骤如下:
(1)先找只含有一个“0”的行(或列),将该行(或列)中的“0”打“?”。
,)将带“?”的“0”所在列(或行)中的“0”打“”。 (2
(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“0”的数目最少的
行或列中任选一个“0”打“?”。
其结果如表2,12矩阵七所示,即员工甲负责任务A,员工乙负责任务D,员工丙负责任
务B,员工丁负责任务C,员工戊负责任务E,参照表2,6各员工完成任务时间汇总表,得出
表2,13所示的员工配置最终结果。
表2,12 矩阵七
0 ? 0 4 7 2 ,
2 13 0 ? 0 4 ,
0 4 6 0 ? 3 ,,
4 0 ? 3 2 2
0 0 8 7 0 ? ,,
表2,13 员工配置最终结果 单位:小时
员工 甲 乙 丙 丁 戊 任务
10 A
6 B
4 C
9 D
10 E
解法二:
1(以各个员工完成各项任务的时间构造矩阵一。
表2,7 矩阵一
10 5 9 18 11
13 19 6 12 14
3 2 4 4 5
18 9 12 17 15
11 6 14 19 10 2(对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。
表2,8 矩阵二
5 0 4 13 6
7 13 0 6 8
1 0 2 2 3
9 0 3 8 6
5 0 8 13 4 3(检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列
数据减去本列数据中的最小数,得矩阵三。
表2,9 矩阵三
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
4(画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住,得图2,5。
4 0 4 11 3
6 13 0 4 5
0 0 2 0 0
8 0 3 6 3
4 0 8 11 1
图2,5 矩阵四
操作技巧:从含“0”最多的行或列开始画“盖0”线。
5(数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线得数目小于矩
阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:
,,(1)找出未被“盖0”线覆盖的数中的最小值,例中,1。
,(2)将未被“盖0”线覆盖住的数减去。
,(3)将“盖0”线交叉点的数加上。
本例结果见表2,10 矩阵五。
表2,10 矩阵五
3 0 4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
6(重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。
本例最终矩阵见表2,11。
3 0 4 10 2
5 13 0 3 4
0 1 3 0 0
7 0 3 5 2
3 0 8 10 0
矩阵五a
0 0 1 7 2
5 16 0 3 7
0 4 3 0 3
4 0 0 2 2
0 0 5 7 0
矩阵五b
表2,11 矩阵六
0 0 1 7 2
5 16 0 3 7
0 4 3 0 3
4 0 0 2 2
0 0 5 7 0
7(求最优解。对n维矩阵,找出不同行、不同列的n个“0”,每个“0”的位置代表一对配
置关系,具体步骤如下:
(1)先找只含有一个“0”的行(或列),将该行(或列)中的“0”打“?”。
,(2)将带“?”的“0”所在列(或行)中的“0”打“”。
(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“0”的数目最少的
行或列中任选一个“0”打“?”。
其结果如表2,12矩阵七所示,即员工甲负责任务A,员工乙负责任务D,员工丙负责任
务B,员工丁负责任务C,员工戊负责任务E,参照表2,6各员工完成任务时间汇总表,得出
表2,13所示的员工配置最终结果。
表2,12 矩阵七
0? 0 1 7 2
5 16 0 ? 3 7
0 4 3 0 ? 3 ,
4 0 ? 0 2 2 ,
0 0 5 7 0? ,,
表2,13 员工配置最终结果 单位:小时
员工 甲 乙 丙 丁 戊 任务
10 A
6 B
4 C
9 D
10 E
古今名言
敏而好学,不耻下问——孔子
业精于勤,荒于嬉;行成于思,毁于随——韩愈 兴于《诗》,立于礼,成于乐——孔子
己所不欲,勿施于人——孔子
读书破万卷,下笔如有神——杜甫
读书有三到,谓心到,眼到,口到——朱熹
立身以立学为先,立学以读书为本——欧阳修 读万卷书,行万里路——刘彝
黑发不知勤学早,白首方悔读书迟——颜真卿
书卷多情似故人,晨昏忧乐每相亲——于谦
书犹药也,善读之可以医愚——刘向
莫等闲,白了少年头,空悲切——岳飞
发奋识遍天下字,立志读尽人间书——苏轼
鸟欲高飞先振翅,人求上进先读书——李苦禅
立志宜思真品格,读书须尽苦功夫——阮元
非淡泊无以明志,非宁静无以致远——诸葛亮
熟读唐诗三百首,不会作诗也会吟——孙洙《唐诗三百首序》
书到用时方恨少,事非经过不知难——陆游
问渠那得清如许,为有源头活水来——朱熹
旧书不厌百回读,熟读精思子自知——苏轼
书痴者文必工,艺痴者技必良——蒲松龄
声明
访问者可将本资料提供的内容用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯本文档及相关权利人的合法权利。谢谢合作~