Уровень задачи

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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

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

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

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

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

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

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

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

4 Литература

  1. Kuhn, H W. “The Hungarian Method for the Assignment Problem.” Naval Research Logistics Quarterly 2, no. 1 (March 1955): 83–97. doi:10.1002/nav.3800020109.
  2. Kuhn, H W. “Variants of the Hungarian Method for Assignment Problems.” Naval Research Logistics Quarterly 3, no. 4 (December 1956): 253–58. doi:10.1002/nav.3800030404.
  3. Munkres, James. “Algorithms for the Assignment and Transportation Problems.” Journal of the Society for Industrial and Applied Mathematics 5, no. 1 (March 1957): 32–38. doi:10.1137/0105003.
  4. Tomizawa, N. “On Some Techniques Useful for Solution of Transportation Network Problems.” Networks 1, no. 2 (1971): 173–94. doi:10.1002/net.3230010206.
  5. Bertsekas, Dimitri P. “Auction Algorithms for Network Flow Problems: a Tutorial Introduction.” Computational Optimization and Applications 1 (1992): 7–66.
  6. Zavlanos, Michael M, Leonid Spesivtsev, and George J Pappas. “A Distributed Auction Algorithm for the Assignment Problem,” Proceedings of IEEE CDC'08, 1212–17, IEEE, 2008. doi:10.1109/CDC.2008.4739098.
  7. Hopcroft, John E, and Richard M Karp. “An $N^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs.” SIAM Journal on Computing 2, no. 4 (1973): 225–31. doi:10.1137/0202019.