Assignment_PLN_LP1. Задача о назначениях. Минимум затрат исполнителей на выполнение работ. Объемное агрегированное планирование. 1 интервал.

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

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

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

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

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

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

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

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

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

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

Дано:

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

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

Требуется:

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

кратко

Примечание. Для повышения эффективность уместно распределять меньшее число объектов на большее. Т.е. если число работ больше числа исполнителей, то выгодней распределить исполнителей, иначе работы по исполнителям.

Модель строится «от исполнителей», т.к. число исполнителей (10) меньше числа работ (20).

Число установок соответствует числу исполнителей. Установка отражает назначение исполнителя на работу.

Операции установки: назначение исполнителя на выполнение определенной работы.

Потоками операции являются часть работы, которая может выполняться данным исполнителем. Величина потока, равная 1 означает, что исполнитель выполняет всю работу.

Условия:

Для потоков операций установок задается ограничение баланса.

Для задания минимального и максимального объема работ используются ограничения на границы емкости в конце горизонта.

Для задания возможностей исполнителя по выполнению работ используются остатки емкостей и границы емкостей в конце горизонта.

Критерий – минимум суммарных затрат на выполнение работ. Для минимизации затрат используется критерий прибыли/издержек от выполнения операций. Для этого стоимость выполнения операции равна затратам от назначения исполнителя на работу, деленную на 2 (объем работы в операции учитывается дважды – один входящий (исполнителя), другой выходящий (работы)).

кратко

Рисунок. фрагмент потоковой схемы объекта «с именами»

кратко

Заданы стоимости выполнения работ исполнителями.

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Критерий задачи – минимум стоимости выполнения операций, что соответствует минимальной стоимости назначения работы исполнителям.

кратко

Назначение исполнителям работы

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Запасы свободных исполнителей.

Рисунок. Фрагменты формы – стадия, емкость

Примечание. Изначально все исполнители свободны (значение 1). В результате свободные исполнители останутся без изменения, а занятые станут равны 0.

Выполненные работы.

Рисунок. Фрагменты формы – стадия, емкость

Примечание. Изначально все работы не выполненные (значение 0). В результате невыполненные работы останутся без изменения, а выполненные станут равны 1. Можно задавать обязательно выполняемые работы ограничениями на емкости.

кратко

Распределение работ по исполнителям

Рисунок. Фрагмент формы с результатами расчетов

Выполненные работы

Рисунок. Фрагмент формы емкостей с результатами расчетов

Занятые исполнители и выполненные работы:

Рисунок. Гистограммы изменения состояния емкостей

Объяснения решения

Рисунок. Фрагмент трассы объяснений Решателя LP

Размерность задачи и характеристики расчета

Размерность задачи:

Стадий 1, Установок 10, Операций 200, Емкостей 30, Интервалов 1, Переменных 1060, Ограничений 1524.

Характеристики расчета:

Минут до оптимального 00:00:00,240

Решатель LpSolve, сервер Intel Core i5-4570 3,2GHz.

кратко