Венгерский алгоритм

Задача о назначениях

Алгоритм решения задачи о назначении на узкие места

Задача о назначении на узкие места

ЛЕКЦИЯ 13. Задачи о назначении. Венгерский алгоритм

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

Имеется n рабочих мест на некотором конвейере и n рабочих, которых нужно на эти рабочие места расставить; известна производительность c_ij рабочего i на рабочем месте j. Тот факт, что при некотором распределении на рабочие места рабочий i_k попадает на рабочее место j_k можно описать следующей таблицей:

Имея способ s назначения на рабочие места, можно найти конкретную для этого способа минимальную производительность и заметить, что именно эта минимальная производительность и определяет скорость и производительность конвейера. То рабочее место, на котором реализуется минимальная производительность и называют узким местом в назначении.

Задача состоит в том, чтобы максимизировать

Шаг 0. Фиксируем матрицу производительностей и любое назначение на рабочие места. Пусть s - минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C; в клетку с номером (ij) в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.

Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n, то имеющееся назначение на рабочие места уже оптимально.

Постановки задачи:

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

Пример 13.2. C=(c_ij) – стоимость производства детали i на станке j нужно найти распределение станков так чтобы суммарная стоимость производства была минимальной.

Пример 13.3. Транспортная задача. Заданы пункты производства товара, пункты потребления товара. Требуется определить оптимальное взаимно-однозначное соответствие между пунктами производства и пунктами потребления, исходя из матрицы стоимостей перевозок C между соответствующими пунктами (т.е. минимизировать суммарную стоимость перевозки).

Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1. Аналогично спрос в каждом пункте назначения равен 1. Стоимость «перевозки» (прикрепления) работы i к станку j равна c_ij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу.

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

Пусть = 0, если j-я работа не выполняется на i-м станке, = 1, если j-я работа выполняется на i-м станке. Таким образом, решение задачи может быть записано в виде двумерного массива . Допустимое решение называется назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в каждом столбце этой матрицы.

Замечание 1. Для заданного значения n существует n! допустимых решений.

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

Минимизировать функцию , при ограничениях:

, (12.1)

, (12.2)

.

Ограничения (12.1) необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения (12.2) гарантируют, что каждому станку будет приписана ровно одна работа.

Пример 13.4. Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками. Стоимость производства детали i на станке j :

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

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

Замечание 2. Оптимальное решение задачи не изменится, если из любой строки или столбца матрицы стоимостей вычесть произвольную постоянную величину.

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

.

Оптимальное назначение: , , , остальные , .

К сожалению, не всегда удается определить решение так просто. Для таких случаев рассмотрим следующий алгоритм.

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

Шаг 2. (Определение назначений). На этом шаге можно использовать алгоритм поиска «наибольшего паросочетания с матрицей двудольного графа (существуют и другие возможности), если все =0 матрицы заменить на «1», а >0 на «0».

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

Шаг 3. (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:

а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

Замечание 3.Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.

Пример 13.5. Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей:

.

Итерация 1

Шаг 1. Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

.

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

.

Шаг 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость. Используем алгоритм поиска наибольшего паросочетания. Преобразуем матрицу в матрицу двудольного графа, затем в рабочую таблицу:

Находим паросочетание:

. Это паросочетание не совершенное, т.е. полного назначения нет. На Шаг 3.

Шаг 3. Модификация редуцированной матрицы.

.

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией.

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

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

.

Итерация 2.

Шаг 2. Выполняя вновь процедуру построения допустимого решения нулевой стоимости, получаем следующее оптимальное решение: . Оптимальное назначение: , , , , остальные , .