Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии, что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы имеет вид:
№ вакансия
Работник 1 2 3 4 5 6
Чертков 15 19 11 4 3 13
Демичев 14 6 5 7 0 9
Фурцева 16 7 19 13 3 7
Токин
0 10 9 1 14 16
Столяров 1 14 18 4 14 6
Носов 0 4 1 13 10 0
Решение
Нам нужны люди, набравшие наибольшее количество баллов. Сведем задачу, наоборот, к той, где нужно найти решение с наименьшим количеством баллов. Для этого заменим каждое значение матрицы на «19 минус это значение». Таким образом, чем больше был балл человека, тем меньше он станет, и найдя решение для минимального числа баллов, мы найдем решение для максимального числа баллов в исходной задаче:
4 0 8 15 16 6
5 13 14 12 19 10
3 12 0 6 16 12
19 9 10 18 5 3
18 5 1 15 5 13
19 15 18 6 9 19
Производим редукцию матрицы по строкам – вычитаем в каждой строке минимальный ее элемент.
4 0 8 15 16 6
0 8 9 7 14 5
3 12 0 6 16 12
16 6 7 15 2 0
17 4 0 14 4 12
13 9 12 0 3 13
Производим редукцию матрицы по столбцам – вычитаем в каждом столбце минимальный его элемент.
4 0 8 15 14 6
0 8 9 7 12 5
3 12 0 6 14 12
16 6 7 15 0 0
17 4 0 14 2 12
13 9 12 0 1 13
Пробуем найти решение, состоящее из одних нулей.
В первой строке лишь один ноль, и, очевидно, он должен войти в решение.
Во второй строке один ноль, в третьей строке и в шестой строке, также один ноль, они тоже войдут в решение.
В пятой строке один ноль, но его нельзя выбрать, потому что этот столбец уже занят.
В четвертой строке два нуля можно выбрать любой незанятый столбец.
Решение из одних нулей найти не получилось.
4 0 8 15 14 6
0 8 9 7 12 5
3 12 0 6 14 12
16 6 7 15 0 0
17 4 0 14 2 12
13 9 12 0 1 13
Вычеркнем строки и столбцы с возможно большим количеством нулевых элементов
. Во-первых, вычеркиваем столбец 3 и столбец 1, а также 1, 4 и 6 строки.
Остались невычеркнутыми следующие цифры:
4 0 8 15 14 6
0 8 9 7 12 5
3 12 0 6 14 12
16 6 7 15 0 0
17 4 0 14 2 12
13 9 12 0 1 13
Вычитаем из всех невычеркнутых цифр минимальную из них (2):
4 0 8 15 14 6
0 6 9 5 10 3
3 10 0 4 12 10
16 6 7 15 0 0
17 2 0 12 0 10
13 9 12 0 1 13
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
6 0 10 15 14 6
0 6 9 5 10 3
3 10 0 4 12 10
18 6 9 15 0 0
17 2 0 12 0 10
15 9 14 0 1 13
Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент
Задать вопрос
на новый заказ в Автор24.
