2015-06-04
1716
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.
Венгерский алгоритм – один из многих алгоритмов, разработанный для решения линейной задачи о назначениях за полиномиальное время от числа работ.
Задача о назначениях является частным случаем транспортной задачи, которая является частным случаем задачи нахождения потока минимальной стоимости, а она, в свою очередь, является частным случаем задачи линейного программирования. Любую из этих задач можно решить симплекс-методом, но каждая специализация имеет свой более эффективный алгоритм, опирающийся на особенности структуры задачи.
|
|
|
Если целевая функция выражается через квадраты, говорят о квадратичной задаче о назначениях.
Формальная постановка задачи о назначениях:
Даны два множества, A и T, одного размера и задана функция стоимости C: A × T → R.
Необходимо найти биекцию f: A → T, такую, что целевая функция:
минимальна.
Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел, так что целевую функцию можно записать в виде:
Задача называется "линейной", поскольку и целевая функция, и ограничения содержат только линейные выражения.
Задачу можно представить как задачу линейного программирования c целевой функцией
и ограничениями
для 
,
для 
,
для 
.
Переменная 
представляет назначение исполнителя 
на работу 
, принимая значение 1 если исполнитель назначен на эту работу и 0 в противном случае. В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями. Этот факт следует из абсолютной унимодулярности матрицы. Первое ограничение требует, чтобы каждому исполнителю была назначена в точности одна задача, второе требует, чтобы для каждой зад задачи был назначен один исполнитель.
