Условие задачи
Торговое предприятие собирается нанять пять сотрудников на следующие должности: 2-х менеджеров, 1-го администратора, 1-го технического консультанта и 1-го продавца. С просьбой о приёме на работу обратилось 6 претендентов. В результате проведенного собеседования соответствие претендентов имеющимся вакантным должностям оказалось выражено баллами соответствия (см. таблицу):
Назначить претендентов на должности так, чтобы сумма баллов была максимальной.
Указание. Так как менеджеров требуется два, то удвоим столбец менеджера. Кроме того, претендентов на одного больше, чем должностей, то добавим ещё фиктивный столбец.
Получаем матрицу соответствия:
Ответ
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (7) так, чтобы матрица не содержала бы отрицательных элементов:
в каждой строке будет как минимум один ноль.
