Описание Области
подробнее…
Постановка задачи
Задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.
В наиболее общей форме задача формулируется следующим образом:
• Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами.
• Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.
Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.
Задачу о назначениях можно считать, частным случаем транспортной задачи, для которой мощности поставщиков и потребности клиентов равны 1 (и обычно совпадает размерность).
Практическими примерами задачи о назначениях можно считать:
• Назначение такси на маршрут с минимальным временем ожидания клиента.
• Распределение ремонтных бригад по участкам работ
Дано:
Исполнители, которых можно назначать только на одну работу.
Работы, для выполнения которых можно назначать только одного исполнителя.
Требуется:
Определить назначение исполнителей на работы, составляющее минимум затрат на выполнение.
кратко
Особенности Объекта
подробнее…
Примечание. Для повышения эффективность уместно распределять меньшее число объектов на большее. Т.е. если число работ больше числа исполнителей, то выгодней распределить исполнителей, иначе работы по исполнителям.
Модель строится «от исполнителей», т.к. число исполнителей (10) меньше числа работ (20).
Число установок соответствует числу исполнителей. Установка отражает назначение исполнителя на работу.
Операции установки: назначение исполнителя на выполнение определенной работы.
Потоками операции являются часть работы, которая может выполняться данным исполнителем. Величина потока, равная 1 означает, что исполнитель выполняет всю работу.
Условия:
Для потоков операций установок задается ограничение баланса.
Для задания минимального и максимального объема работ используются ограничения на границы емкости в конце горизонта.
Для задания возможностей исполнителя по выполнению работ используются остатки емкостей и границы емкостей в конце горизонта.
Критерий – минимум суммарных затрат на выполнение работ. Для минимизации затрат используется критерий прибыли/издержек от выполнения операций. Для этого стоимость выполнения операции равна затратам от назначения исполнителя на работу, деленную на 2 (объем работы в операции учитывается дважды – один входящий (исполнителя), другой выходящий (работы)).
кратко
Схема Объекта
подробнее…
Рисунок. фрагмент потоковой схемы объекта «с именами»
кратко