Этот метод впервые был предложен венгерским математиком Эгервари в 1931г. Длительное время работа оставалась малоизвестной. В 1953г. Математик Г.Кун перевел эту работу на английский язык, заново открыв её для специалистов, раз вил идеи Эгервари и усовершенствовал метод, который в честь первого автора и был назван венгерским.
Первоначально венгерский метод был применен к задаче выбора.
Постановка задачи. Предположим, что имеется различных работ
и
механизмов
, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма
при выполнении работы
обозначим
. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбор а или задачей о назначениях.
Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы
чтобы сумма была максимальна и при этом из каждой строки и столбца был выбран только один элемент.
Введем следующие понятия.
1. Нулевые элементы матрицы
называются независимыми нулями, если для любого
строка и столбец, на пересечении которых расположен элемент
, не содержат другие нули
(для всех
).
2. Две прямоугольные матрицы и
называются эквивалентными (
~
), если
для всех i, j. Задачи выбора, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).
3. Элементы, расположенные в выделенных строках или столбцах, называются выделенными элементами.