--- title: "Задача о назначениях" source: "https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85" wiki: "systems-analysis.info/wiki" article: "Задача_о_назначениях" language: "ru" categories: - "Категория:Russian" - "Категория:Исследование операций" revision_id: 236 wiki_created_at: 2026-09-06T22:05:53Z wiki_modified_at: 2026-09-06T22:05:53Z downloaded_at: 2026-09-07T22:18:32Z --- # Задача о назначениях **Задача о назначениях** ((англ. assignment problem), AP) — классическая задача комбинаторной оптимизации, заключающаяся в нахождении взаимно‑однозначного соответствия между двумя равными по мощности множествами (агентами и задачами) с целью минимизации суммарной стоимости назначений[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). В терминах теории графов задача эквивалентна поиску **совершенного паросочетания** минимальной стоимости во взвешенном двудольном графе[\[2\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-kuhn1955-2). Задача относится к разделам исследования операций, линейного программирования и теории паросочетаний и представляет собой частный случай транспортной задачи с единичными объёмами поставок и спроса. В стандартной постановке задана квадратная **матрица стоимостей** $C = (c_{ij})$ размера $n \times n$, где $c_{ij}$ — стоимость назначения $i$‑го агента $j$‑й задаче. Требуется найти перестановку $\sigma$ множества $\{ 1,\ldots,n\}$, минимизирующую $\sum\limits_{i = 1}^{n}c_{i,\sigma(i)}$. Задача полиномиально разрешима: наиболее известный алгоритм — **венгерский метод** (алгоритм Куна–Манкреса) — решает её за $O(n^{3})$ операций[\[3\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-munkres1957-3). ## Исторический контекст и предпосылки Корни задачи о назначениях восходят к XIX веку. Карл Густав Якоби в 1830–1840‑х годах разработал алгоритм решения задачи в контексте систем дифференциальных уравнений; результаты были опубликованы посмертно в 1890 году на латинском языке[\[4\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-kuhn2012-4). В XX веке теоретическую базу заложили венгерские математики. Денеш Кёниг в 1931 году доказал теорему о равенстве размера максимального паросочетания и минимального вершинного покрытия в двудольных графах (**теорема Кёнига**). Енё Эгервари в том же году обобщил результат на взвешенный случай, показав конструктивный способ сведения взвешенной задачи к бинарной[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). Термин «assignment problem» впервые появился в 1952 году в работе Воутоу и Ордена. В 1955 году Гарольд Кун опубликовал **венгерский метод** ((англ. Hungarian method)), названный в честь Кёнига и Эгервари[\[2\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-kuhn1955-2). В 1957 году Джеймс Манкрес провёл строгий анализ алгоритма Куна и доказал его **сильную полиномиальность**, за что алгоритм стали называть алгоритмом Куна–Манкреса[\[3\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-munkres1957-3). Первоначальная оценка сложности составляла $O(n^{4})$. В 1971–1972 годах Джек Эдмондс и Ричард Карп, а также Томидзава независимо модифицировали алгоритм до $O(n^{3})$[\[6\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-edmonds1972-6). К 2007 году — пятидесятилетию работы Куна — насчитывались сотни вариаций задачи, систематизированных в обзоре Пентико[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). Наиболее полное изложение истории и алгоритмов содержится в монографии Буркарда, Делль'Амико и Мартелло (2012)[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). ## Математическая формулировка ### Целочисленная линейная программа Классическая задача о назначениях формулируется как задача **целочисленного линейного программирования** (ЦЛП). Пусть имеется множество агентов $I = \{ 1,\ldots,n\}$ и множество задач $J = \{ 1,\ldots,n\}$. Вводятся бинарные переменные $x_{ij} \in \{ 0,1\}$, где $x_{ij} = 1$, если агент $i$ назначен на задачу $j$[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1): $\min\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n}c_{ij}\, x_{ij}$ при ограничениях: $\sum\limits_{j = 1}^{n}x_{ij} = 1,\quad i = 1,\ldots,n\qquad\text{(каждый агент назначен ровно одной задаче)}$ $\sum\limits_{i = 1}^{n}x_{ij} = 1,\quad j = 1,\ldots,n\qquad\text{(каждая задача назначена ровно одному агенту)}$ Матрица $X = (x_{ij})$ при таких ограничениях представляет собой **перестановочную матрицу** — матрицу, в каждой строке и каждом столбце которой ровно одна единица. Множество всех допустимых решений задачи — множество всех перестановок $S_{n}$, число которых равно $n!$[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ### Тотальная унимодулярность и линейная релаксация Матрица ограничений задачи о назначениях является **тотально унимодулярной** ((англ. totally unimodular)): все миноры этой матрицы принимают значения из множества $\{ - 1,0,1\}$. Это свойство гарантирует, что все вершины **многогранника назначений** ((англ. assignment polytope, Birkhoff polytope)) являются целочисленными, то есть перестановочными матрицами. Следовательно, оптимальное решение линейной релаксации (замена $x_{ij} \in \{ 0,1\}$ на $0 \leq x_{ij} \leq 1$) автоматически целочисленно, и задача может быть решена методами линейного программирования без дополнительного требования целочисленности[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). Данный результат является частным случаем **теоремы Биркгофа–фон Неймана** ((англ. Birkhoff–von Neumann theorem)), утверждающей, что множество дважды стохастических матриц представляет собой выпуклую оболочку перестановочных матриц[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). ### Двойственная задача Двойственная задача линейного программирования имеет вид: $\max\sum\limits_{i = 1}^{n}u_{i} + \sum\limits_{j = 1}^{n}v_{j}$ при ограничениях: $u_{i} + v_{j} \leq c_{ij},\quad\forall\, i \in I,\ j \in J$ где $u_{i}$ и $v_{j}$ — **двойственные переменные** (**потенциалы**). По теореме сильной двойственности оптимальные значения прямой и двойственной задач совпадают. Условие **дополняющей нежёсткости** ((англ. complementary slackness)) утверждает, что в оптимальном решении $x_{ij} = 1$ возможно только при равенстве $u_{i} + v_{j} = c_{ij}$. Это свойство лежит в основе венгерского метода[\[2\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-kuhn1955-2). ## Связь с теорией паросочетаний и потоков ### Задача о паросочетании Задача о назначениях эквивалентна задаче нахождения **совершенного паросочетания минимальной стоимости** ((англ. minimum‑cost perfect matching)) в полном взвешенном двудольном графе $G = (U,V,E)$, где $|U| = |V| = n$, каждая вершина в $U$ соответствует агенту, каждая вершина в $V$ — задаче, а вес ребра $(i,j)$ равен $c_{ij}$[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). По **теореме Кёнига–Эгервари** размер максимального паросочетания в двудольном графе равен размеру минимального вершинного покрытия; для взвешенного случая это обобщается на равенство стоимости оптимального паросочетания и оптимального покрытия[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). ### Задача о минимальном стоимостном потоке Задача о назначениях также сводится к **задаче о потоке минимальной стоимости** ((англ. minimum‑cost flow)) в сети с источником $s$, стоком $t$ и двудольными вершинами. Источник соединяется с каждым агентом ребром пропускной способности 1 и нулевой стоимости; каждая задача соединяется со стоком аналогично; рёбра между агентами и задачами имеют пропускную способность 1 и стоимость $c_{ij}$. Максимальный поток стоимости $n$ в такой сети соответствует совершенному паросочетанию[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ## Алгоритмы решения Для линейной задачи о назначениях разработан ряд точных полиномиальных алгоритмов. Все они гарантируют нахождение глобального оптимума, но различаются по практической эффективности на различных классах входных данных. ### Венгерский метод (алгоритм Куна–Манкреса) **Венгерский метод** — классический комбинаторный алгоритм, представляющий собой реализацию **примально‑двойственного метода** для пары взаимно двойственных задач линейного программирования[\[2\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-kuhn1955-2). Алгоритм работает с двойственными переменными (потенциалами) $u_{i},v_{j}$ и порождённым **подграфом равенств** $G_{=} = \{(i,j):u_{i} + v_{j} = c_{ij}\}$. В матричной интерпретации алгоритм выполняет следующие шаги[\[3\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-munkres1957-3): 1. **Редукция по строкам:** из каждого элемента строки вычитается минимальный элемент этой строки. 2. **Редукция по столбцам:** из каждого элемента столбца вычитается минимальный элемент этого столбца. В результате матрица содержит нули, соответствующие потенциальным назначениям. 3. **Покрытие нулей:** находится минимальное число горизонтальных и вертикальных линий (строк и столбцов), покрывающих все нули. 4. **Проверка оптимальности:** если число линий равно $n$, в матрице существует совершенное паросочетание нулей — оптимальное решение найдено. 5. **Корректировка матрицы:** если число линий меньше $n$, выбирается минимальный непокрытый элемент $\delta$, вычитается из всех непокрытых элементов и прибавляется к элементам на пересечении двух линий. Возврат к шагу 3. Графовая реализация использует поиск **увеличивающих путей** ((англ. augmenting paths)) в подграфе равенств. На каждой итерации либо увеличивается размер текущего паросочетания, либо корректируются потенциалы, расширяя подграф равенств. Модификация Эдмондса–Карпа и Томидзавы обеспечивает сложность $O(n^{3})$ за счёт более эффективного поиска кратчайших увеличивающих путей и обновления потенциалов[\[6\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-edmonds1972-6). Исследуются также ускоренные варианты венгерского метода, в которых на каждом шаге создаётся более одного нового нуля, что уменьшает число итераций на практике при сохранении полиномиальной оценки сложности[\[8\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-ndlovu2020-8). ### Алгоритм Йонкера–Волгенанта (LAPJV) **Алгоритм Йонкера–Волгенанта** ((англ. Jonker–Volgenant algorithm), LAPJV), предложенный в 1987 году, основан на последовательном поиске **кратчайших увеличивающих путей** ((англ. shortest augmenting path)) с использованием потенциалов[\[9\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-jonker1987-9). Алгоритм имеет ту же асимптотическую сложность $O(n^{3})$, однако на практике часто работает существенно быстрее венгерского метода благодаря более эффективным структурам данных и стратегиям инициализации. Реализации LAPJV входят в стандартные библиотеки SciPy (`scipy.optimize.linear_sum_assignment`) и MATLAB[\[9\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-jonker1987-9). Для разреженных графов алгоритмы с кучами Фибоначчи достигают сложности $O(mn + n^{2}\log n)$, где $m$ — число рёбер[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ### Аукционный алгоритм **Аукционный алгоритм** ((англ. auction algorithm)), предложенный Димитрием Бертсекасом в 1980‑х годах, моделирует процесс назначения как аукцион: агенты итеративно «делают ставки» на задачи, повышая их «цены» до достижения равновесия[\[10\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-bertsekas1992-10). Алгоритм естественно допускает **параллельную реализацию**, поскольку ставки агентов могут вычисляться независимо, что делает его привлекательным для распределённых систем и реализаций на графических процессорах[\[10\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-bertsekas1992-10). ### Методы линейного программирования Благодаря тотальной унимодулярности задача может быть решена стандартными методами линейного программирования — симплекс‑методом или методом внутренних точек — без дополнительного требования целочисленности. На практике специализированные комбинаторные алгоритмы значительно превосходят общие LP‑солверы по скорости на задачах о назначениях, однако LP‑подход удобен при наличии дополнительных ограничений, выходящих за рамки классической постановки[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ### Сравнение алгоритмов | Алгоритм | Сложность | Тип решения | Особенности | |--------------------------|-----------------------------------------------|-------------|---------------------------------------------------| | Венгерский метод | $O(n^{3})$ | Точное | Классический; примально‑двойственный подход | | LAPJV (Йонкер–Волгенант) | $O(n^{3})$ | Точное | Часто быстрее на практике; реализован в SciPy | | Аукционный алгоритм | $O(n^{3})$ (с $\varepsilon$‑масштабированием) | Точное | Параллелизуем; подходит для распределённых систем | | Min‑cost flow | $O(n^{3})$ | Точное | Естественен при обобщениях с ограничениями потока | | Симплекс‑метод (LP) | Экспоненциальная в худшем случае | Точное | Универсален; медленнее специализированных методов | | Метод внутренних точек | $O(n^{3.5}\log n)$ | Точное | Полиномиальный LP‑метод; высокие константы | ## Варианты целевой функции Помимо классической линейной (суммарной) целевой функции исследуются иные критерии оптимальности, порождающие различные постановки задачи. ### Минимаксная (bottleneck) задача **Линейная минимаксная задача о назначениях** ((англ. Linear Bottleneck Assignment Problem), LBAP) минимизирует не сумму, а максимальную стоимость назначенного ребра[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7): $\min\limits_{\sigma \in S_{n}}\max\limits_{i = 1,\ldots,n}c_{i,\sigma(i)}$ LBAP разрешима за $O(n^{2.5})$ операций с помощью бинарного поиска по порогу стоимости с проверкой существования совершенного паросочетания в соответствующем подграфе[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). ### Лексикографическая задача В **лексикографической задаче о назначениях** вектор стоимостей назначений сортируется по невозрастанию и минимизируется в лексикографическом порядке. Данная постановка возникает, когда требуется обеспечить **справедливость** распределения — минимизировать наихудшую стоимость, затем вторую наихудшую и так далее[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ### Алгебраические обобщения Более общие варианты заменяют операции суммирования и минимизации операциями над **алгебраическими структурами** — например, полукольцами. Такой подход позволяет моделировать задачи на кратчайшие пути и другие задачи дискретной оптимизации в единой рамке[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ## Вариации и обобщения Классическая линейная задача о назначениях допускает многочисленные обобщения, отражающие различные практические требования. Большинство из них являются NP‑трудными. ### Несбалансированные и ограниченные назначения В практике часто число агентов не равно числу задач (**несбалансированная задача**, (англ. unbalanced assignment problem)). Стандартное решение — введение фиктивных агентов или задач с нулевой (при минимизации) или штрафной стоимостью[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). **Запрещённые назначения** ((англ. forbidden assignments)) моделируются присвоением соответствующим элементам матрицы стоимости $+ \infty$ (или достаточно большого числа) либо явным исключением рёбер в графовой постановке[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). При задачах **максимизации** (например, максимизации прибыли) применяют эквивалентное преобразование: $c'_{ij} = C_{\max} - p_{ij}$, где $p_{ij}$ — прибыль от назначения. ### Обобщённая задача о назначениях (GAP) **Обобщённая задача о назначениях** ((англ. Generalized Assignment Problem), GAP) вводит **ограничения на ресурсы** (ёмкости) агентов. Каждый агент $i$ обладает ресурсом объёма $b_{i}$; назначение задачи $j$ агенту $i$ потребляет $a_{ij}$ единиц ресурса и имеет стоимость $c_{ij}$. Требуется назначить каждую задачу ровно одному агенту с минимальной суммарной стоимостью при условии $\sum\limits_{j}a_{ij}\, x_{ij} \leq b_{i}$ для каждого $i$[\[11\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-chan2003-11). GAP является **NP‑трудной**. Для её решения разработаны точные методы (метод ветвей и границ; лагранжева релаксация) и эвристические подходы (жадные методы, локальный поиск, метаэвристики). Современные работы предлагают расширенные формулировки ((англ. extended formulations)) с более сильными линейными релаксациями и новыми классами валидных неравенств[\[12\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-gap_ext-12). ### Квадратичная задача о назначениях (QAP) **Квадратичная задача о назначениях** ((англ. Quadratic Assignment Problem), QAP) моделирует ситуации, где стоимость зависит от **пар** назначений. Классическая постановка включает матрицу потоков $F = (f_{kl})$ между объектами и матрицу расстояний $D = (d_{ij})$ между позициями[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1): $\min\limits_{\sigma \in S_{n}}\sum\limits_{k = 1}^{n}\sum\limits_{l = 1}^{n}f_{kl}\, d_{\sigma(k),\sigma(l)}$ QAP является NP‑трудной и одной из наиболее сложных задач комбинаторной оптимизации; точное решение возможно лишь для экземпляров умеренного размера (порядка нескольких десятков). На практике применяются метод ветвей и границ, табу-поиск, генетические алгоритмы и другие метаэвристики. Типичное приложение QAP — задача **размещения оборудования** ((англ. facility layout problem))[\[13\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-qap_survey-13). ### Другие расширения Многообразие практических приложений порождает ряд дополнительных обобщений классической задачи: - **Многократная задача о назначениях:** каждый агент может выполнять несколько задач при ограничениях по мощности[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). - **Стохастическая задача о назначениях:** стоимости или доступность ресурсов являются случайными величинами; решения строятся с учётом распределений и критериев риска[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). - **Динамическая (онлайн) задача:** задачи и агенты поступают во времени, решения принимаются последовательно без полной информации о будущих поступлениях[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). - **Многокритериальные постановки:** одновременный учёт нескольких критериев — стоимости, времени, качества[\[14\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-abu_bakar2019-14). ## Случайные и асимптотические аспекты Развита теория асимптотического поведения оптимального значения задачи о назначениях при **случайных стоимостях**. Для матрицы $C$, элементы которой являются независимыми одинаково распределёнными случайными величинами с экспоненциальным распределением (параметр 1), математическое ожидание оптимальной стоимости при $n \rightarrow \infty$ стремится к[\[15\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-aldous2001-15): $\lim\limits_{n \rightarrow \infty}{\mathbb{E}}\left\lbrack \min\limits_{\sigma \in S_{n}}\sum\limits_{i = 1}^{n}c_{i,\sigma(i)} \right\rbrack = \frac{\pi^{2}}{6} = \zeta(2) \approx 1,6449$ Этот результат, известный как **гипотеза Пароизи** и доказанный Линусоном и Вёстлундом в 2004 году, имеет значение для анализа средней сложности и поведения алгоритмов на случайных данных[\[15\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-aldous2001-15). ## Применения Задача о назначениях находит применение в широком спектре практических областей благодаря универсальности постановки: любая ситуация, требующая оптимального сопоставления двух множеств, может быть формализована как задача о назначениях. ### Исследование операций и производство Классические приложения включают назначение работников на рабочие места или смены, распределение работ по станкам для минимизации суммарного времени обработки, планирование смен и расписаний (назначение экипажей, бригад, преподавателей)[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). ### Логистика и транспорт В транспортной логистике задача используется для распределения транспортных средств по маршрутам (назначение такси клиентам с минимизацией времени подъезда, распределение вагонов по поездам, назначение ворот в аэропортах). Задача о назначениях также выступает как подзадача при решении более сложных задач маршрутизации, включая задачу коммивояжёра[\[14\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-abu_bakar2019-14). ### Компьютерное зрение и сопоставление данных В компьютерном зрении задача о назначениях применяется для **ассоциации данных** ((англ. data association)) при многообъектном слежении ((англ. multi‑object tracking)): на каждом кадре наблюдения сопоставляются с существующими треками[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). Другие применения включают сопоставление ключевых точек на изображениях, выравнивание сетей ((англ. network alignment)) и назначение задач процессорным ядрам в параллельных вычислениях[\[14\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-abu_bakar2019-14). ### Рецензирование статей и грантов **Задача о назначении рецензентов** ((англ. Reviewer Assignment Problem), RAP) формулируется как обобщённая задача о назначениях с целевой функцией максимизации суммы сходств экспертизы при ограничениях на нагрузку и конфликты интересов. Реальные системы — TPMS, Erie — решают эту задачу с помощью ЦЛП, генетических алгоритмов или min‑cost flow[\[16\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-aksoy2023-16). ### Экономика, биоинформатика и здравоохранение В экономике модели паросочетаний используются при анализе **рынков сопоставлений** ((англ. matching markets)) и механизмов распределения ресурсов. В биоинформатике задача применяется при выравнивании генных и белковых последовательностей, сопоставлении структурных элементов биомолекул. В здравоохранении — для назначения пациентов врачам, оптимизации распределения трансплантационных ресурсов и планирования палат[\[14\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-abu_bakar2019-14). ## Практическая эффективность На матрицах размером $n \leq 1000$ современные реализации (LAPJV) решают задачу за секунды на стандартном оборудовании. Для $n \approx 5000$ требуются оптимизированные реализации; для $n > 10^{4}$ — специализированные разреженные версии алгоритмов[\[9\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-jonker1987-9). | Размер задачи $n$ | Типичное время (LAPJV) | Примечание | |-------------------|-------------------------|----------------------------------------| | $10^{2}$ | миллисекунды | Любая реализация | | $10^{3}$ | секунды | Стандартные библиотеки (SciPy, MATLAB) | | $10^{4}$ | десятки секунд — минуты | Оптимизированные реализации | | $10^{5}$ | требуется специализация | Разреженные методы, параллелизация | Для GAP точные методы решают экземпляры до $n \approx 100\text{–}500$ в зависимости от структуры ёмкостей; бо́льшие экземпляры требуют эвристик. Для QAP точная оптимизация ограничена размерами порядка нескольких десятков[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5). ## Ограничения классической модели Классическая линейная задача о назначениях предполагает строгое соотношение один‑к‑одному между агентами и задачами, аддитивную линейную структуру целевой функции без взаимодействий между парами назначений, а также детерминированные и заранее известные стоимости $c_{ij}$[\[1\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard2012-1). В реальных задачах могут присутствовать ограничения совместимости и логические зависимости между назначениями, ограничения по мощности и ресурсам (приводящие к GAP), а также стохастические или нечётко заданные стоимости, требующие методов робастного или стохастического программирования[\[7\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-burkard_cela-7). ## Открытые проблемы и направления исследований Несмотря на полную теоретическую изученность классической линейной задачи, для её обобщений остаётся ряд открытых вопросов[\[5\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-pentico2007-5)[\[12\]](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_note-gap_ext-12): - **Формулировки и неравенства:** улучшение линейных релаксаций для GAP и связанных задач с целью сокращения вычислительных затрат при решении крупных экземпляров. - **Гибридные методы:** разработка алгоритмов, сочетающих точные методы и метаэвристики с гарантированной оценкой качества. - **Параллельные и распределённые реализации:** эффективное использование многопроцессорных систем, графических процессоров и облачных сред. - **Интеграция с машинным обучением:** использование нейронных сетей для оценки стоимостей, прогнозирования параметров и выбора эвристик в алгоритмах назначения. - **Онлайн‑алгоритмы:** динамические задачи с поступлением данных в реальном времени, требующие адаптивных решений без полной информации. - **Квантовые алгоритмы:** потенциальное применение квантовых вычислений для ускорения решения задач большой размерности. - **Справедливость и этика:** включение ограничений на **справедливость** ((англ. fairness constraints)) в модели назначения, особенно в социально значимых приложениях — здравоохранении, распределении должностей, рецензировании. ## Программные реализации - **SciPy:** `scipy.optimize.linear_sum_assignment` — реализация на основе LAPJV. - **Google OR-Tools:** линейные и обобщённые задачи о назначениях. - **CPLEX, Gurobi:** коммерческие LP/ILP‑солверы. - **LEMON:** библиотека для сетевых задач на C++. ## См. также - [Задача коммивояжёра](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0 "Задача коммивояжёра") - [Задача о назначении минимального количества исполнителей](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D0%B8_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9 "Задача о назначении минимального количества исполнителей") - [Анализ чувствительности](https://systems-analysis.info/wiki/%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D1%87%D1%83%D0%B2%D1%81%D1%82%D0%B2%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 "Анализ чувствительности") - [Выбор](https://systems-analysis.info/wiki/%D0%92%D1%8B%D0%B1%D0%BE%D1%80 "Выбор") ## Ссылки - Kuhn H. W. — The Hungarian Method for the Assignment Problem (оригинальная статья) - Burkard R. E., Çela E. — Linear Assignment Problems and Extensions (обзор) - Assignment problem — Wikipedia - Hungarian algorithm — Wikipedia ## Литература - Burkard, R. E., Dell'Amico, M., Martello, S. (2012). *Assignment Problems*. Revised ed. Philadelphia: SIAM. ISBN 978-1-61197-222-1. - Kuhn, H. W. (1955). *The Hungarian Method for the Assignment Problem*. Naval Research Logistics Quarterly, 2(1–2), 83–97. PDF. - Kuhn, H. W. (2012). *A tale of three eras: The discovery and rediscovery of the Hungarian Method*. European Journal of Operational Research, 219(3), 641–651. - Munkres, J. (1957). *Algorithms for the Assignment and Transportation Problems*. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. - Pentico, D. W. (2007). *Assignment problems: A golden anniversary survey*. European Journal of Operational Research, 176(2), 774–793. - Jonker, R., Volgenant, A. (1987). *A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems*. Computing, 38, 325–340. - Edmonds, J., Karp, R. M. (1972). *Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems*. Journal of the ACM, 19(2), 248–264. - Bertsekas, D. P. (1992). *Auction Algorithms for Network Flow Problems: A Tutorial Introduction*. Computational Optimization and Applications, 1, 7–66. - Aksoy, M., Yanik, S., Amasyali, M. F. (2023). *Reviewer Assignment Problem: A Systematic Review of the Literature*. arXiv:2304.00353. - Aldous, D. J. (2001). *The $\zeta(2)$ limit in the random assignment problem*. Random Structures and Algorithms, 18(4), 381–418. - Loiola, E. M. et al. (2007). *A survey for the quadratic assignment problem*. European Journal of Operational Research, 176(2), 657–690. ## Примечания 1. ↑ [1,00](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-0) [1,01](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-1) [1,02](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-2) [1,03](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-3) [1,04](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-4) [1,05](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-5) [1,06](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-6) [1,07](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-7) [1,08](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-8) [1,09](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard2012_1-9) Burkard, R. E., Dell'Amico, M., Martello, S. (2012). *Assignment Problems*. Revised ed. Philadelphia: SIAM. ISBN 978-1-61197-222-1. 2. ↑ [2,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-kuhn1955_2-0) [2,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-kuhn1955_2-1) [2,2](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-kuhn1955_2-2) [2,3](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-kuhn1955_2-3) Kuhn, H. W. (1955). *The Hungarian Method for the Assignment Problem*. Naval Research Logistics Quarterly, 2(1–2), 83–97. https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf 3. ↑ [3,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-munkres1957_3-0) [3,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-munkres1957_3-1) [3,2](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-munkres1957_3-2) Munkres, J. (1957). *Algorithms for the Assignment and Transportation Problems*. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. 4. [↑](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-kuhn2012_4-0) Kuhn, H. W. (2012). *A tale of three eras: The discovery and rediscovery of the Hungarian Method*. European Journal of Operational Research, 219(3), 641–651. DOI: 10.1016/j.ejor.2011.11.008. 5. ↑ [5,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-0) [5,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-1) [5,2](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-2) [5,3](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-3) [5,4](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-4) [5,5](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-5) [5,6](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-pentico2007_5-6) Pentico, D. W. (2007). *Assignment problems: A golden anniversary survey*. European Journal of Operational Research, 176(2), 774–793. DOI: 10.1016/j.ejor.2005.09.014. 6. ↑ [6,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-edmonds1972_6-0) [6,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-edmonds1972_6-1) Edmonds, J., Karp, R. M. (1972). *Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems*. Journal of the ACM, 19(2), 248–264. 7. ↑ [7,00](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-0) [7,01](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-1) [7,02](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-2) [7,03](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-3) [7,04](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-4) [7,05](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-5) [7,06](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-6) [7,07](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-7) [7,08](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-8) [7,09](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-9) [7,10](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-10) [7,11](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-burkard_cela_7-11) Burkard, R. E., Çela, E. *Linear Assignment Problems and Extensions*. Technical report, University of Technology Graz. https://www.andrew.cmu.edu/course/42-731/handouts/Burkard_LAP_review.pdf 8. [↑](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-ndlovu2020_8-0) Ndlovu, A. N. (2020). *Development of an Accelerating Hungarian Method for Assignment Problems*. SSRN Preprint. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3724157 9. ↑ [9,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-jonker1987_9-0) [9,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-jonker1987_9-1) [9,2](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-jonker1987_9-2) Jonker, R., Volgenant, A. (1987). *A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems*. Computing, 38, 325–340. 10. ↑ [10,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-bertsekas1992_10-0) [10,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-bertsekas1992_10-1) Bertsekas, D. P. (1992). *Auction Algorithms for Network Flow Problems: A Tutorial Introduction*. Computational Optimization and Applications, 1, 7–66. 11. [↑](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-chan2003_11-0) Chan, K. C. Y., Magnanti, T. L., Phillips, R. L. (2003). *Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach*. INFORMS Journal on Computing, 15(3), 249–271. DOI: 10.1287/ijoc.15.3.249.16075. 12. ↑ [12,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-gap_ext_12-0) [12,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-gap_ext_12-1) *A New Extended Formulation of the Generalized Assignment Problem and Some Associated Valid Inequalities* (2023). https://www.bohrium.com/paper-details/a-new-extended-formulation-of-the-generalized-assignment-problem-and-some-associated-valid-inequalities/ 13. [↑](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-qap_survey_13-0) Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., Querido, T. (2007). *A survey for the quadratic assignment problem*. European Journal of Operational Research, 176(2), 657–690. 14. ↑ [14,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-abu_bakar2019_14-0) [14,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-abu_bakar2019_14-1) [14,2](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-abu_bakar2019_14-2) [14,3](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-abu_bakar2019_14-3) Abu Bakar, A. R. et al. (2019). *A Brief Review on Classic Assignment Problem and its Applications*. IOSR Journal of Engineering, 9(9), 73–81. https://iosrjen.org/Papers/vol9_issue9/Series-1/M0909017381.pdf 15. ↑ [15,0](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-aldous2001_15-0) [15,1](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-aldous2001_15-1) Aldous, D. J. (2001). *The $\zeta(2)$ limit in the random assignment problem*. Random Structures and Algorithms, 18(4), 381–418. 16. [↑](https://systems-analysis.info/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#cite_ref-aksoy2023_16-0) Aksoy, M., Yanik, S., Amasyali, M. F. (2023). *Reviewer Assignment Problem: A Systematic Review of the Literature*. arXiv:2304.00353 \[cs.IR\]. https://arxiv.org/abs/2304.00353