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