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

Для данных сотрудников и работ () нужно назначить сотрудников для выполнения работ с целью минимизации общих расходов на выполнение всех работ, так чтобы каждая работа выполнялась лишь одним сотрудником, а каждый сотрудник может выполнять самое большее одну работу. Расходы на выполнение работы сотрудником составляют . Обозначим Введем бинарные решающие переменные :

Задача о назначениях имеет вид:

при ограничениях

(только один сотрудник должен выполнять работу ),

(сотрудник может выполнять не более одной работы),