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

 

Требуется распределить m работ (или исполнителей) по n станкам (рабочим местам). i-я работа, выполняемая на j-м станке, связана с затратами c_ij. Задача состоит в таком распределении работ по станкам (одна работа на один станок), которое соответствует минимуму суммарных затрат.

Это частный случай транспортной задачи. Работы - пункты отправления, станки - пункты назначения. Предложение в каждом пункте отправления равно 1, спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) i работы к j станку - c_ij. Если некоторую работу нельзя выполнить на некотором станке, то соответствующая стоимость полагается равной бесконечности (c_{ij =} ¥).

Прежде, чем решать задачу в рамках транспортной модели, необходимо устранить дисбаланс, добавив фиктивные работы или фиктивные станки в зависимости от начальных условий; поэтому, не ограничивая общности в дальнейшем, полагаем n = m.

Математическая модель:

Пусть -Булева переменная.

0, если i-я работа не выполняется на j-м станке и 1 в противном случае.

Тогда

при ограничениях

(кто-то должен выполнять работу)

(работа должна быть выполнена)

Специфическая структура задачи позволяет применять более эффективные методы решения.

Теорема 1. Оптимальное решение не изменится, если ко всем элементам любой строки (столбца) матрицы стоимости прибавить или вычесть постоянную величину (возможно различную для каждой строки (столбца)).

На основании этой теоремы можно построить новую матрицу с нулевыми элементами, и если это множество нулевых элементов (или их подмножества) будут соответствовать допустимому решению, то такое решение будет оптимальным, так как стоимость не может быть отрицательной.

Алгоритм решения:

1) из всех элементов каждой строки и каждого столбца матрицы C= c_ij вычитаем наименьший элемент соответствующей строки p_i (или столбца q_j).

2) проводим поиск допустимого решения, единичные элементы которого соответствуют нулевым коэффициентам модифицированной матрицы.

Определение: Модифицированная матрица стоимостей – матрица, из всех элементов каждой строки и каждого столбца которой нельзя вычесть никаких элементов, не получив отрицательных (это матрица, полученная преобразованиями из исходной матрицы, указанной в пункте 1).

Если такое допустимое решение существует, то оно оптимальное, в противном случае матрица C модифицируется еще один раз, но уже другим способом.

Алгоритм состоит из трех шагов:

1) редукция (сокращение) строк и столбцов

2) попытка определения назначения

3) модификация редуцированной матрицы

 

Шаг 1. Цель шага – получить максимально возможное число нулей в матрице C путем вычитания из элементов каждой строки и каждого столбца наименьших элементов соответствующих строк и столбцов.

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

Шаг 3. Если нулевых элементов недостаточно, то получить необходжимые новые нулевые элементы можно следующим образом. Для этого определим минимальное множество строк и столбцов редуцированной матрицы, содержащей все нулевые элементы, и найдем минимальный элемент матрицы вне множества элементов, составляющих совокупность выбранных строк и столбцов. Если значение найденного элемента вычесть из других элементов матрицы C, то получим отрицательные величины, и по крайней мере один элемент, не принадлежащий множеству элементов, входящих в выделенные строки и столбцы, будет равен 0.

Однако, назначение нулевой стоимости будет не оптимальным, так как C содержит отрицательные элементы. Для того, чтобы матрица C не содержала отрицательные элементы, прибавляем абсолютную величину наименьшего отрицательного элемента ко всем элементам выделенных строк и столбцов. При этом к элементам, расположенным на пересечениях выделенных строк и столбцов, данная величина прибавляется дважды, и, таким образом, все отрицательные элементы преобразовываются в нулевые или положительные. В результате шага 3 получаем новую редуцированную матрицу, которая содержит хотя бы на один ноль больше, который расположен вне строк и столбцов выделенного множества, и таким образом за конечное число шагов 3 мы придем к оптимальному решению.

Пример:

q₃=2

(1,1) (2,3) (3,2) – оптимальное назначение.

На самом деле стоимость будет равна Z = p₁+p₂+p₃+q₃

 

Но, к сожалению, не всегда удается определить допустимое назначение таким образом. Поэтому рассмотрим следующий пример:

Оптимальное назначение: (1, 1) (2, 3) (3, 2) (4, 4)