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

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

Пусть имеются n работ и n кандидатов для их выполнения. Назначению i -го кандидата (i = 1.. n) на j –ю работу (j = 1.. n) соответствует определенная эффективность (прибыль, производительность) или затраты какого-либо ресурса с _ij. Требуется найти такие назначения кандидатов на все работы, которые обеспечат наибольшую эффективность, то есть минимум суммарных затрат или максимум прибыли (производительности). При этом каждого кандидата можно назначить только на одну должность и каждая работа может быть выполнена только одним кандидатом.

Математическая постановка задачи имеет вид:

где x_ij – искомая переменная:

В такой постановке данная задача относится к классу комбинаторных, решение которых путем прямого перебора невозможно при достаточно больших n, так как число вариантов назначений составляет n!