ВЕНГЕРСКИЙ МЕТОД

Этот метод впервые был предложен венгерским математиком Эгервари в 1931г. Длительное время работа оставалась малоизвестной. В 1953г. Математик Г.Кун перевел эту работу на английский язык, заново открыв её для специалистов, раз вил идеи Эгервари и усовершенствовал метод, который в честь первого автора и был назван венгерским.

Первоначально венгерский метод был применен к задаче выбора.

Постановка задачи. Предположим, что имеется различных работ и механизмов , каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим . Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

Формально она записывается так. Необходимо выбрать такую последовательность элементов из матрицы

чтобы сумма была максимальна и при этом из каждой строки и столбца был выбран только один элемент.

Введем следующие понятия.

1. Нулевые элементы матрицы называются независимыми нулями, если для любого строка и столбец, на пересечении которых расположен элемент , не содержат другие нули (для всех ).

2. Две прямоугольные матрицы и называются эквивалентными (~ ), если для всех i, j . Задачи выбора, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

3. Элементы, расположенные в выделенных строках или столбцах, называются выделенными элементами.