2.4. Задача о назначениях и ее решение с помощью алгоритма венгерского метода

ПОСТАНОВКА ЗАДАЧИ О НАЗНАЧЕНИЯХ

Имеется n работ и n исполнителей этих работ. Обозначим через i номер исполнителя (i = 1, 2,..., n), а через j – номер работы (j = 1, 2,..., n). Каждый исполнитель может выполнять любую из работ, но только одну. Каждая работа должна выполняться одним исполнителем. Известны числа – затраты (прибыли), связанные с выполнением j-й работы i-м исполнителем. Требуется так распределить исполнителей по работам, чтобы суммарные затраты (суммарная прибыль) были минимальны (была максимальной). Таким образом, задача о назначениях решается либо на максимум, либо на минимум в зависимости от смысла чисел . Из чисел можно составить матрицу, которую называют матрицей эффективности.

Математическая модель задачи о назначениях

Для построения математической модели введем неизвестные со следующим смыслом:

если i-й исполнитель не назначается на j-ю работу;

если i-й исполнитель назначается на j-ю работу.

Получаем задачу: найти план назначения при котором минимизируется (максимизируется) суммарная полезность назначения, т. е.

при следующих ограничениях. Каждый исполнитель назначается только на одну работу:

Каждая работа выполняется только одним исполнителем:

Условия неотрицательности и целочисленности:

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

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

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

I этап. Приведение матрицы С.

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

II этап. Поиск назначения.

Выбираем один из нулей, помечаем его, например, точкой или звездочкой или обводим его другим цветом (в дальнейшем, звездочкой), а остальные нули строки и столбца, в которых стоит выбранный помеченный нуль, перечеркиваем. Далее переходим к следующему нулю. И так до тех пор, пока каждый нуль будет либо помечен, либо перечеркнут. Помеченные нули составят назначения, например, если помечен нуль в 3-й строке и 5-м столбце, то третий исполнитель назначается на 5-ю работу. Назначение может оказаться полным (количество помеченных нулей = n). Тогда задача решена. Если назначение неполное, переходим к следующему этапу.

Замечание. Пометку рекомендуется начинать со строк и столбцов,

содержащих минимальное количество нулей.

III этап. Выделение в матрице C подматрицы, не содержащей нулей.

По-другому, цель III этапа состоит в том, чтобы перечеркнуть все

нули минимальным набором горизонтальных и вертикальных линий.

IIIа) помечаем (точкой, звездочкой) строки, не содержащие помеченных нулей;

IIIб) помечаем столбцы, содержащие перечеркнутый нуль в одной из

помеченных строк;

IIIв) помечаем строки, содержащие помеченный нуль хотя бы в одном из помеченных столбцов. От IIIв) опять переходим к IIIб).

Пункты IIIб) и IIIв) повторяются до тех пор, пока есть что помечать.

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

IY этап. Перемещение нулей.

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

Переходим на II этап. Пометку следует начинать со вновь полученного нуля. И так до тех пор, пока не получим полное назначение.

Пример 2.4.1.

Решить на максимум задачу о назначениях с матрицей эффективности С:

В нижней строке матрицы С указаны максимальные элементы столбцов. После вычитания, получена матрица . Во 2-й и 5-й строках нет нулей. Минимальные элементы в них 3 и 1. Вычитая их, получаем приведенную матрицу :

.

Назначение неполное, т.к. помечено 4 нуля а не 5. Помечаем 5-ю строку (в ней нет помеченных нулей). Далее помечаем 2-й столбец (в нем  стоит в помеченной строке). Помечаем 4-ю строку (в ней 0^* стоит в помеченном столбце). Больше помечать нечего. В результате получаем:

.

Мысленно вычеркиваем строки 1, 2, 3 и 2-й столбец. Из оставшихся элементов выбираем минимальный (1), вычитаем его из невычеркнутых столбцов и прибавляем к вычеркнутым строкам. Получаем:

Производим пометку и вычеркивание нулей (пометку начинаем со вновь полученного нуля), а затем пометку строк и столбцов:

Получено полное назначение: 1 исп.  4 раб., 2  3, 3  5, 4  2,

5  1.

Эффективность данного назначения составит

Ответ: для получения максимальной эффективности назначения, равной 46, следует назначить первого исполнителя на четвертую работу, второго – на третью, третьего – на пятую, четвертого – на вторую, пятого – на первую.