Предварительный этап.
Переходим от задачи на максимум к задаче на минимум, т. е. теперь перейдем от задачи на минимум с матрицей к задаче на минимум с эквивалентной ей матрицей, которая имела бы только неотрицательные элементы, и в каждой строке и каждом столбце которой было бы хотя бы по одному нулевому элементу. Для этого сначала прибавим к каждому столбцу матрицы наибольший из элементов соответствующего столбца матрицы (или, что-то же самое вычтем элементы каждого столбца матрицы из наибольшего элемента этого столбца; результат остается в соответствующей позиции). Получится неотрицательная матрица, в каждом столбце которой есть хотя бы один нуль. Теперь вычтем из каждой строки матрицы минимальный элемент этой строки, результат остается на месте уменьшаемых элементов. Полученная матрица D и будет неотрицательной матрицей, в каждом столбце и в каждой строке которой есть хотя бы один нуль.
Наименьшее возможное значение суммы элементов неотрицательной матрицы равно, очевидно, нулю. Таким образом, наша задача теперь сводится к выбору матрицы, или эквивалентной ей матрице с неотрицательными элементами нулевых элементов, по одному в каждом столбце и в каждой строке. Покажем, как это сделать. Неформальный смысл приводимого ниже алгоритма заключается в последовательных переходах от одного правильного неполного выбора нулей к другому, содержащему на один нуль больше, чем предыдущий, до тех пор, пока не получится полный правильный выбор. При этом на отдельных этапах может потребоваться переход к новой матрице, эквивалентной предыдущей.
Пусть уже проделаны предварительные преобразования матрицы эффективностей данной задачи и получена неотрицательная матрица, содержащая хотя бы по одному нулевому элементу в каждой строке и каждом столбце. Приведем основной этап алгоритма решения задачи о назначениях.
