短信预约提醒成功
计算题
1. 某车间产品装配组有王成、赵云、江平、李鹏四位员工。现有A、B、C、D四项任务，在现有生产技术组织条件下，每位员工完成每项工作所需要的工时如表2-2-2所示。请运用匈牙利法求出员工与任务的配置情况，以保证完成任务的总时间最短，并求出完成任务的最短时间。(P96~98)(20分)
答;计算步骤如下：(8分)
1) 建立矩陈
|
10 |
5 |
9 |
18 |
（―5） |
|
13 |
18 |
6 |
12 |
（―6） |
|
3 |
2 |
4 |
4 |
（―2） |
|
18 |
9 |
10 |
16 |
（―9） |
2) 对以上矩阵进行约减，即每一行数据减去本行的最小数，得新矩阵为：
|
5 |
0 |
4 |
13 |
|
7 |
12 |
0 |
16 |
|
1 |
0 |
2 |
2 |
|
9 |
0 |
1 |
7 |
矩阵中第一列和第四列都不含“0”，因此转入第三步，进行列约减。
3) 对以上矩阵进行列约减，即第一列约减去本行数据中的最小数，得新矩阵为：
|
4 |
0 |
4 |
11 |
|
6 |
12 |
0 |
4 |
|
0 |
0 |
2 |
0 |
|
8 |
0 |
1 |
5 |
4) 在上述矩阵中画“盖0”线。即画最少的线将矩阵中的0全部覆盖住。
“盖0”线只有3条，小于矩阵的维数4，因此转入第五步，进行数据转换
5) 数据转换。上述矩阵中未被“盖0”线覆盖的最小数为1，将矩阵中未被“盖0”线覆盖的数减去1，“盖0”给交叉点处的数加1，得新矩阵为：
|
3 |
0 |
3 |
10 |
|
6 |
13 |
0 |
4 |
|
0 |
1 |
2 |
0 |
|
7 |
0 |
0 |
4 |
6) 在上述矩阵中画“盖0”线，“盖0”线只有3条，小于矩阵的维数4，因此转入第七步，进行数据转换
7) 数据转换。上述矩阵中未被“盖0”线覆盖的最小数为3，将矩阵中未被“盖0”线覆盖的数减去3，“盖0”给交叉点处的数加3，得新矩阵为：
|
0 |
0 |
3 |
7 |
|
3 |
13 |
0 |
1 |
|
0 |
4 |
5 |
0 |
|
4 |
0 |
0 |
1 |
1) 在上述矩阵中画“盖0”线。“盖0”线有4条，等于矩阵的维数4，因此转入第九步，示得最化解。
2) 求最优解。
① 最后一列只含有一个“0”，将该列中的“0”打“√”
② 将第三行中另外一个“0”打“×”
③ 将第一列中另外一个“0”打“√”
④ 将第一行中另外一个“0”打“×”
⑤ 将第二列中另外一个“0”打“√”
⑥ 将第四行中另外一个“0”打“×”
⑦ 将第三列中另外一个“0”打“√”
最终结果见以下矩阵。
|
0√ |
0× |
3 |
7 |
|
3 |
13 |
0 |
1 |
|
0× |
4 |
5 |
0√ |
|
4 |
0√ |
0× |
1 |
参照表2-2-2，最短时间为：(3+2+4+) 4小时=3.25小时(12分)
表2-2-2 每个员工完成四项工作任务的工时统计表(单位：工时)
|
工作任务 |
王成 |
赵云 |
江平 |
李鹏 |
|
A |
10 |
5 |
9 |
18 |
|
B |
13 |
8 |
6 |
12 |
|
C |
3 |
2 |
4 |
4 |
|
D |
18 |
9 |
10 |
16 |
