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

Задача о назначениях может быть сформулирована следующим образом. Имеется n ра- бочих и m работ и задана стоимость назначения рабочего i на работу j для всех i и j. Каждый рабочий может быть назначен не более, чем на одну работу, и каждая работа мо- жет выполняться не более, чем одним рабочим. Требуется найти допустимое назначение, при котором суммарная стоимость F минимальна.

Если рабочий не может выполнять какую-то работу, соответствующая стоимость равна бесконечности. Не ограничивая общности, можно считать, что n = m. Иначе можно ввести фиктивных рабочих или фиктивные работы с нулевыми стоимостями.

Очевидно, что задача о назначениях является частным случаем транспортной задачи, в ко- тором рабочие и работы могут рассматриваться как пункты производства и потребления, а запрос или заявка в каждом пункте равна единице. Для ее решения можно воспользо- ваться методом решения ТЗ. Однако, существует более эффективный метод ее решения, называемый венгерским.

Рассмотрим задачу о назначениях, заданную следующей матрицей стоимостей назначе-

ния.

Вначале вычтем из каждого элемента строки наименьший элемент этой строки по всем строкам. Получим матрицу

Найдем сумму вычтенных чисел ∆ = 17. Далее вычтем из каждого элемента столбца

наименьший элемент этого столбца по всем столбцам. Получим матрицу

Найдем новую сумму ∆ = 20. Задача о назначениях с полученной матрицей стоимостей эквивалентна исходной задаче о назначениях. Для получения стоимости оптимального на- значения исходной задачи необходимо к стоимости оптимального назначения новой задачи прибавить сумму вычтенных чисел: F = F + ∆.

Последняя полученная матрица называется приведенной.

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

Повторяем Общий шаг. На этот раз существуют n нулевых элементов в разных строках и

столбцах:

Они и определяют оптимальное назначение: рабочий 1 на работу 1, рабочий 2 на работу

3 и т.д. Стоимость назначения равна 21.

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

Дата добавления: 2015-07-08