1. В каждой строке найти наименьшее значение и вычесть его из содержимого всех ячеек этой строки матрицы. (Получится по крайней мере один нуль в каждой строке.)

2. В столбце, не содержащем нулевых ячеек, найти наименьшее значение и вычесть его из содержимого всех ячеек этого столбца матрицы.

3. "Линейный тест". В матрице назначений провести минимальное число линий (горизонталей (по строкам) и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено

, т.к. назначения должны быть произведены в "пункты", соответствующие нулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутых строк и столбцов< n, перейти к шагу 4.

4. Среди невычеркнутых строк и столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий. Повторить шаг 3.

Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин (n=5). Матрица стоимостей каждой комбинации работа/машина приведена в таблице 2-1.

Таблица 2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной

Процедура решения задачи приведена в таблице 2-2.

Таблица 2-2. Процедура решения задачи о назначениях

Шаг 1

: приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы