Торговое предприятие собирается нанять пять сотрудников на следующие должности

Модифицируем матрицу умножением всех элементов на (-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), то решение недопустимое.