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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

В наиболее общей форме задача формулируется следующим образом:

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

Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют ввиду линейную задачу о назначениях.

Алгоритмы и обобщения[править | править вики-текст]

Венгерский алгоритм – один из многих алгоритмов, разработанный для решения линейной задачи о назначениях за полиномиальное время от числа работ.

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

Если целевая функция выражается через квадраты, говорят о квадратичной задаче о назначениях.

Пример[править | править вики-текст]

Предположим, что таксомоторная компания имеет три свободные машины (исполнители), и три заказчика (работы), желающих получить такси как можно быстрее. Фирма заботится о времени доставки такси к заказчику, так что для каждой машины "стоимость" определяется скоростью, с какой машина доберётся до места ожидания, определённого заказчиком. Решением задачи о назначениях будет распределение машин по заказчикам, такое, что суммарная цена (суммарное время ожидания) минимально.

Задачу о назначениях можно сделать более гибкой. В вышеприведенном примере могут оказаться не три, а четыре свободных такси, но заказчика, по-прежнему, три. Можно назначить четвертую задачу, которую можно назвать "сиди тихо, ничего не делай", с ценой 0 для машины, которой она назначается. Задача может быть решена обычным методом и снова даст наилучшее решение.

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

Формальное математическое определение[править | править вики-текст]

Формальная постановка задачи о назначениях:

Даны два множества, A и T, одного размера и задана функция стоимости C : A × TR.
Необходимо найти биекцию f : AT, такую, что целевая функция:
\sum_{a\in A}C(a,f(a))
минимальна.

Обычно функция стоимости задается как квадратная матрица C, состоящая из вещественных чисел, так что целевую функцию можно записать в виде:

\sum_{a\in A}C_{a,f(a)}

Задача называется "линейной", поскольку и целевая функция, и ограничения содержат только линейные выражения.

Задачу можно представить как задачу линейного программирования c целевой функцией

\sum_{i\in A}\sum_{j\in T}C(i,j)x_{ij}

и ограничениями

\sum_{j\in T}x_{ij}=1 для i\in A,
\sum_{i\in A}x_{ij}=1 для j\in T,
x_{ij}\ge 0 для i,j\in A,T.

Переменная x_{ij} представляет назначение исполнителя i на работу j, принимая значение 1 если исполнитель назначен на эту работу и 0 в противном случае. В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями. Этот факт следует из абсолютной унимодулярности матрицы. Первое ограничение требует, чтобы каждому исполнителю была назначена в точности одна задача, второе требует, чтобы для каждой задачи был назначен один исполнитель.

Смотрите также[править | править вики-текст]

Дальнейшее чтение[править | править вики-текст]

  • Еаха, Хемди А., Введение в исследование операций, 7-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2005: гл 5.4 Задача о назначениях.
  • Г. Вагнер, Основы исследования операций: Пер. с англ.- Издательство «Мир», М., 1972. Том 1, Приложение I.2 Решение задачи о назначениях.
  • Р.Акоф, М.Сасиени, Основы исследования операций, Издательство «Мир», М. 1971. Глава 5 Распределительные задачи: назначение и размещение ресурсов.
  • Brualdi Richard A. Combinatorial matrix classes. — Cambridge: Cambridge University Press, 2006. — Vol. 108. — ISBN 0-521-86565-4.
  • Burkard Rainer Assignment Problems (Revised reprint). — SIAM, 2012. — ISBN 978-1-61197-222-1.