Венгерский алгоритм — это алгоритм оптимизации, который предназначен для решения задачи о назначениях за полиномиальное время.
Введение
Венгерский алгоритм разработал и опубликовал Гарольд Кун (Harold Kuhn) в 1955-ом году. Кун присвоил алгоритму наименование «венгерский», так как он в существенной мере базировался на более ранних работах двух венгерских специалистов, а именно, Денеша Кенига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry).
В 1957-ом году Джеймс Манкрес (James Munkres) сумел показать, что данный алгоритм способен работать за строго полиномиальное время, то есть, за время порядка полинома от n, которое не зависит от величины стоимостей. По этой причине в литературе этот алгоритм фигурирует не только как венгерский, но и как алгоритм Куна-Манкреса или алгоритм Манкреса.
Кстати, относительно уже недавно, а именно, в 2006-ом году, стало известно, что точно такой же алгоритм изобрел раньше на целый век до Куна немецкий математик Карл Густав Якоби (Carl Gustav Jacobi). Оказалось, что его работа «About the research of the order of a system of arbitrary ordinary differential equations», которая была напечатана посмертно в 1890-ом году и содержала помимо других результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, и поэтому ее публикация оказалась незамеченной среди математиков.
Необходимо отметить, что задача о назначениях представляет собой частный случай классической транспортной задачи и, следовательно, может считаться задачей транспортного типа. Также следует помнить, что применение к задаче о назначениях симплексного метода не является эффективным вариантом, поскольку каждое ее допустимое базисное решение может считаться вырожденным. Совокупность специфических особенностей задачи о назначениях явилась стимулом к разработке эффективной методики ее решения, которая известна как венгерский метод.
К частному случаю транспортной задачи относится задача о назначениях, в которой количество пунктов производства равняется количеству пунктов назначения, то есть, транспортная таблица обладает формой квадрата. Помимо этого, во всех пунктах назначения объем потребности равняется единице, и величина предложения всех пунктов производства также равняется единице. Каждую задачу о назначениях можно решить с применением методов линейного программирования или алгоритма решения транспортной задачи. Тем не менее так как данная задача имеет особую структуру, был выработан специальный алгоритм, который получил наименование Венгерского алгоритма.
Венгерский алгоритм
Венгерский алгоритм считается одним из самых интересных и самых распространенных методик решения транспортной задачи. Представим главные идеи венгерского алгоритма на примере решения задачи выбора, то есть, задачи о назначениях, представляющей собой частный случай транспортной задачи, а далее можно обобщить данный метод для произвольных транспортных задач.
Допустим, что есть различные работы и механизмы, каждый из которых способен исполнять любую работу, но с различным уровнем эффективности. Производительность механизмов при исполнении работ можно обозначить:
i = 1, ..., n; j = 1, ..., n.
Необходимо таким образом выполнить распределение механизмов по работам, чтобы обеспечить максимальный суммарный эффект от их применения. Подобные задачи именуются задачами выбора или задачами о назначениях.
Формально такая задача может быть описана следующим образом. Следует сделать выбор такой последовательности компонентов из матрицы, чтобы сумма стала максимальной, причем из каждой строки и столбца «С» может быть выбран лишь один компонент.
Нулевые компоненты матрицы «С» именуются независимыми нулями, когда каждая строка и столбец, на пересечении которых располагается компонент, не содержат другие такие компоненты.
Две прямоугольные матрицы «С» и «D» именуются эквивалентными (C ~ D), если от одной можно перейти к другой с помощью конечного числа элементарных преобразований. Задачи о назначениях, которые определяются эквивалентными матрицами, считаются эквивалентными, то есть, оптимальные решения одной из них являются оптимальными и для второй. Причем, справедливо и обратное утверждение.
Венгерский алгоритм является процедурой, которая состоит из следующих операций:
- Следует найти во всех строках матрицы «С» минимальный компонент и вычесть его из каждого компонента данной строки. Если в сформированной в итоге матрице появятся столбцы, которые не содержат нулевых компонентов, то в каждом из них следует найти минимальный компонент и вычесть его из каждого компонента данного столбца. То есть, выполняется переход к матрице, все строки и все столбцы которой будут содержать, по крайней мере, один нулевой компонент.
- Если в сформированной матрице можно сделать выбор по одному нулевому компоненту таким образом, чтобы соответствующие этим компонентам решения будут допустимыми, то есть, всем исполнителям назначается одна работа и каждая работа исполняется одним исполнителем, то данное (нулевое) назначение является оптимальным. В противном случае необходимо перейти к следующему пункту.
- Далее следует найти минимальное множество строк и столбцов, которые содержат нули. Затем вне этого множества необходимо найти минимальный компонент и вычесть его из всех компонентов приведенной матрицы. После чего нужно преобразовать матрицу так, чтобы исключить наличие отрицательных компонентов. Эту процедуру иначе можно сформулировать так: минимальный компонент следует вычесть из компонентов, которые не содержат нулевые строки и столбцы. На пересечении данных вычеркнутых строк и столбцов, которые содержат нулевые компоненты, этот минимальный компонент следует прибавить к компонентам приведенной матрицы, а оставшиеся компоненты вычеркнутых столбцов и строк должны браться без изменений.
Далее следует вернуться ко второму шагу и произвести назначение. Шаги два и три необходимо выполнять до тех пор, пока не будет достигнуто оптимальное решение.
