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

Описание Области

подробнее…

Постановка задачи

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

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

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

  Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

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

Задачу о назначениях можно считать, частным случаем транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность).

Практическими примерами задачи о назначениях можно считать:

  Назначение такси на маршрут с минимальным временем ожидания клиента.

  Распределение ремонтных бригад по участкам работ

Дано:

Исполнители, которых можно назначать только на одну работу.

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

Требуется:

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

кратко