4. Задача «о назначениях»

Пусть есть N работников и N рабочих мест (работ). Известно время выполнения каждым работником каждой из работ. Необходимо так распределить работников по рабочим местам, чтобы каждый работник выполнял одну работу, каждая работа выполнялась одним работником при минимальном времени выполнения работ. Классическим примером этой задачи может быть распределение спортсменов по этапам эстафеты.

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

Задача решается венгерским методом.

Алгоритм венгерского метода при минимизации целевой функции:

1. В каждой строке матрицы задачи находят минимальный элемент и вычитают его из всех элементов строки.

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

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

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

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

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

7. Если решение не оптимальное, проводят минимальное число пересекающихся горизонтальных и вертикальных прямых через все нули. Среди не зачеркнутых этими прямыми чисел находят минимум. Этот минимум вычитают из всех незачеркнутых чисел и прибавляют ко всем числам на пересечении прямых. Переходят на шаг 3 данного алгоритма.

Пример. Существуют четыре базы А₁, А₂, А₃, А₄ и четыре торговые точки В₁, В₂, В₃, В₄. Расстояния от баз до торговых точек заданы матрицей:

Нужно так прикрепить базы к торговым точкам, чтобы суммарное расстояние было минимальным.

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

В итоге, … прикрепляется к …, … – к …, … – к …, … – к …. Чтобы найти суммарное расстояние, нужно сложить числа, которые расположены в исходной матрице на месте отмеченных нулей: S =

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