Задача о назначении

Пусть имеется неделимых ресурсов , назначаемых только один раз, и объектов потребителей ресурсов, каждый из которых может потребить только один ресурс. Обозначим - затраты, связанные с назначением ресурса на объект . Задача состоит в определении такого плана назначения, при котором суммарная стоимость назначения минимальна.

Примеры задач приведены в таблице:

ресурсы	объекты	критерий
рабочие	рабочие места	время
автобусы	маршруты	затраты

Определим переменную причем , если ресурс назначен на объект , и , если отсутствует назначение ресурса на объект . Тогда задача состоит в минимизации целевой функции стоимости назначений

при ограничениях первой группы, задающих использование каждого ресурса ровно 1 раз.

.

Вторая группа ограничений гарантирует объекту использование одного ресурса

Задача о назначениях - это пример целочисленной задачи линейного программирования. Она решается специальным методом, хотя может быть решена методом решения ТЗ.

Глава 4. ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ (ЦП)