Торговое предприятие собирается нанять пять сотрудников на следующие должности
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Торговое предприятие собирается нанять пять сотрудников на следующие должности: 2-х менеджеров, 1-го администратора, 1-го технического консультанта и 1-го продавца. С просьбой о приёме на работу обратилось 6 претендентов. В результате проведенного собеседования соответствие претендентов имеющимся вакантным должностям оказалось выражено баллами соответствия (см. таблицу):
менеджер администратор консультант продавец
Ивановский 5 7 3 5
Петраков 2 4 6 5
Сидоров 1 7 5 1
Волкова 3 6 5 0
Белкина 2 7 0 6
Черепахина 3 3 3 7
Назначить претендентов на должности так, чтобы сумма баллов была максимальной.
Указание. Так как менеджеров требуется два, то удвоим столбец менеджера. Кроме того, претендентов на одного больше, чем должностей, то добавим ещё фиктивный столбец.
Получаем матрицу соответствия:
Нужно полное решение этой работы?
Ответ
Cmax = 0 + 5 + 6 + 3 + 7 + 7 = 28,(3;6), (1;1), (2;4), (4;2), (5;3), (6;5)
Или
Cmax = 0 + 5 + 6 + 7 + 3 + 7 = 28, (5;6), (1;1), (2;4), (3;3), (4;2), (6;5)
Решение
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (7) так, чтобы матрица не содержала бы отрицательных элементов:
2 2 0 4 2 7
5 5 3 1 2 7
6 6 0 2 6 7
4 4 1 2 7 7
5 5 0 7 1 7
4 4 4 4 0 7
в каждой строке будет как минимум один ноль.
2 2 0 4 2 7 0
4 4 2 0 1 6 1
6 6 0 2 6 7 0
3 3 0 1 6 6 1
5 5 0 7 1 7 0
4 4 4 4 0 7 0
Затем такую же операцию проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
0 0 0 4 2 1
2 2 2 0 1 0
4 4 0 2 6 1
1 1 0 1 6 0
3 3 0 7 1 1
2 2 4 4 0 1
2 2 0 0 0 6
Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 6), (2; 4).Фиксируем нулевое значение в клетке (2, 6). Другие нули в строке 2 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 6), (2; 4).В итоге получаем следующую матрицу:
[-0-] [-0-] [0] 4 2 1
2 2 2 [-0-] 1 [0]
4 4 [-0-] 2 6 1
1 1 [-0-] 1 6 [-0-]
3 3 [-0-] 7 1 1
2 2 4 4 0 1
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 2), то решение недопустимое.Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:столбец 3, строку 1, строку 2, столбец 5, строку 4Получаем сокращенную матрицу (элементы выделены):
0 0 0 4 2 1
2 2 2 0 1 0
4 4 0 2 6 1
1 1 0 1 6 0
3 3 0 7 1 1
2 2 4 4 0 1
Минимальный элемент сокращенной матрицы (min(4, 4, 2, 1, 3, 3, 7, 1, 2, 2, 4, 1) = 1) вычитаем из всех ее элементов:
0 0 0 4 2 1
2 2 2 0 1 0
3 3 0 1 6 0
1 1 0 1 6 0
2 2 0 6 1 0
1 1 4 3 0 0
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
0 0 1 4 3 1
2 2 3 0 2 0
3 3 0 1 6 0
1 1 1 1 7 0
2 2 0 6 1 0
1 1 4 3 0 0
В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.Фиксируем нулевое значение в клетке (1, 2)
. Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 3)Фиксируем нулевое значение в клетке (2, 6). Другие нули в строке 2 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 3)Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 3)В итоге получаем следующую матрицу:
[-0-] [0] 1 4 3 1
2 2 3 [-0-] 2 [0]
3 3 [0] 1 6 [-0-]
1 1 1 1 7 [-0-]
2 2 [-0-] 6 1 [-0-]
1 1 4 3 0 [-0-]
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 3), то решение недопустимое.
Задать вопрос
на новый заказ в Автор24.
