Описание Области
подробнее…
Постановка задачи
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
• Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами.
• Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.
Задачу о назначениях можно считать, частным случаем транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность).
Практическими примерами задачи о назначениях можно считать:
• Назначение такси на маршрут с минимальным временем ожидания клиента.
• Распределение ремонтных бригад по участкам работ
Дано:
Исполнители, которых можно назначать только на одну работу.
Работы, для выполнения которых можно назначать только одного исполнителя.
Требуется:
Определить назначение исполнителей на работы, составляющее минимум затрат на выполнение.
кратко