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

1 Постановка задачи

Пусть имеется $n$ агентов и $m$ задач, которые могут быть распределены между этими агентами. Каждому агенту может быть выделена только одна задача, и каждая задача может быть выделена только одному агенту. Стоимость присвоения $i$-й задачи $j$-му агенту равна $c(i, j)$. В случае $c(i, j) = \infty$ задача $j$ не может быть назначена агенту $i$.

Задача о назначениях: сформировать допустимое множество назначений $A = \{ (i_1, j_1), \ldots, (i_k, j_k) \}$, $k = \min \{m, n\}$, имеющее макисмальную суммарную стоимость:

$C(A) = \sum_{s = 1}^k c(i_s, j_s) \to \max.$

2 Варианты задачи

При $m = n$ задача называется линейной: каждому агенту достаётся ровно одна задача, и каждая задача достаётся ровно одному агенту.

В случае единичных весов возникает задача о наибольшем паросочетании в двудольном графе: назначить как можно больше задач.

3 Алгоритмы решения задачи

• Венгерский алгоритм для линейной задачи, сложность $O(n^4)$ (может быть уменьшена до $O(n^3)$);
• Алгоритм аукциона;
• Алгоритм Гопкрофта-Карпа для задачи с единичными ценами, сложность $O(m \sqrt{n})$.