Идея Венгерского метода

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

Идея заключается в том, что исходная задача максимизации в начале меняется на эквивалентную задачу минимизации (умножается целевая функция на –1), затем элементы эквивалентной матрицы С путем эквивалентных преобразований из теоремы делаются не отрицательными. Затем с помощью эквивалентных преобразований у матрицы С строится полная система независимых нулей и записывается ответ. Строится план задачи, у которой единицы строятся как раз на месте независимых нулей.

Определение. Элементы матрицы С, заданные на некотором этапе, которые стоят или в строке, или в столбце, выделяются знаком “+” будем называть выделенными элементами, а остальные будем называть невыделенными.

Замечание к блоку 8. На самом деле, при построении новых невыделенных нулей, число h отнимается от элементов в невыделенных строках и прибавляется к элементам в выделенных столбцах. И поэтому это преобразование является эквивалентным.