Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.
Венгерский алгоритм — один из многих алгоритмов, разработанный для решения линейной задачи о назначениях за полиномиальное время от числа работ.
Задача о назначениях является частным случаем транспортной задачи, которая является частным случаем задачи нахождения потока минимальной стоимости, а она, в свою очередь, является частным случаем задачи линейного программирования. Любую из этих задач можно решить симплекс-методом, но каждая специализация имеет свой более эффективный алгоритм, опирающийся на особенности структуры задачи.
Если целевая функция выражается через квадраты, говорят о квадратичной задаче о назначениях.
Предположим, что таксомоторная компания имеет три свободные машины (исполнители), и три заказчика (работы), желающих получить такси как можно быстрее. Фирма заботится о времени доставки такси к заказчику, так что для каждой машины стоимость определяется временем, с какой машина доберётся до места ожидания, определённого заказчиком. Решением задачи о назначениях будет распределение машин по заказчикам такое, что суммарная стоимость (суммарное время ожидания) минимальна.
Задачу о назначениях можно сделать более гибкой. В вышеприведенном примере могут оказаться не три, а четыре свободных такси, но заказчика по-прежнему три. Можно назначить четвёртого фиктивного заказчика с нулевой стоимостью, распределение же машины на фиктивного заказчика означает — «ничего не делай».
Аналогичный приём можно использовать в случае, когда число заказов может превышать число доступных машин, и машина может быть назначена на выполнение нескольких работ, а также когда работа может быть назначена нескольким исполнителям (например, если заказчик — группа, не помещающаяся в одно такси). Можно также поставить задачу увеличения дохода, а не минимизацию цены.
Формальная постановка задачи о назначениях:
Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел так, что целевую функцию можно записать в виде:
Задача называется «линейной», поскольку и целевая функция, и ограничения содержат только линейные выражения.
Задачу можно представить как задачу линейного программирования c целевой функцией
и ограничениями
Переменная представляет назначение исполнителя на работу , принимая значение 1 если исполнитель назначен на эту работу и 0 в противном случае. В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями. Этот факт следует из абсолютной унимодулярности матрицы. Первое ограничение требует, чтобы каждому исполнителю была назначена в точности одна задача, второе требует, чтобы для каждой задачи был назначен один исполнитель.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .