Задача о назначении
Пусть имеется неделимых ресурсов
, назначаемых только один раз, и
объектов
потребителей ресурсов, каждый из которых может потребить только один ресурс. Обозначим
- затраты, связанные с назначением ресурса
на объект
. Задача состоит в определении такого плана назначения, при котором суммарная стоимость назначения минимальна.
Примеры задач приведены в таблице:
ресурсы | объекты | критерий |
рабочие | рабочие места | время |
автобусы | маршруты | затраты |
Определим переменную причем
, если ресурс
назначен на объект
, и
, если отсутствует назначение ресурса
на объект
. Тогда задача состоит в минимизации целевой функции стоимости назначений
при ограничениях первой группы, задающих использование каждого ресурса ровно 1 раз.
.
Вторая группа ограничений гарантирует объекту использование одного ресурса
Задача о назначениях - это пример целочисленной задачи линейного программирования. Она решается специальным методом, хотя может быть решена методом решения ТЗ.
Глава 4. ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ (ЦП)