II. Венгерский метод решения задачи о назначениях

2.1 Суть Венгерского метода

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

Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

Венгерский метод является одним из интереснейших и наиболее распространенных методов решения транспортных задач.

Рассмотрим основные идеи венгерского метода на примере решения задачи выбора (задачи о назначениях), которая является частным случаем Т-задачи, а затем обобщим этот метод для произвольной Т-задачи.

Постановка задачи. Предположим, что имеется различных работ и механизмов, каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим, i = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.¹⁶

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

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

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

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

2.2 Описание алгоритма венгерского метода

Метод представляет собой процедуру, состоящую из следующих шагов:

1.Находим в каждой строке матрицы С минимальный элемент и вычитаем его из каждого элемента этой строки. Если в полученной матрице окажутся столбцы, не содержащие нулевых элементов, то в каждом из них находим минимальный элемент и вычитаем его из всех элементов этого столбца. Таким образом, приходим к матрице, каждая строка и каждый столбец которой содержат, по меньшей мере, один нулевой элемент.

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

3.Ищется минимальное множество строк и столбцов, содержащие нули. Далее вне этого множества находим минимальный элемент и вычитаем его из всех элементов приведенной матрицы. Затем преобразуем матрицу таким образом, чтобы не было отрицательных элементов. Эта процедура эквивалентна следующей : минимальный элемент вычитаем из элементов, не содержащих нулевые строки и столбцы. На пересечении этих вычеркнутых строк и столбцов, содержащих нулевые элементы, этот минимальный элемент прибавляется элементам приведенной матрицы, а остальные элементы вычеркнутых столбцов и строк берутся без изменения.

Далее возвращаемся к шагу 2 и производим назначение. Шаги 2 и 3 выполняются до тех пор, пока не будет получено оптимальное решение.¹⁸