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

Задача о назначениях ((англ. assignment problem), AP) — классическая задача комбинаторной оптимизации, заключающаяся в нахождении взаимно‑однозначного соответствия между двумя равными по мощности множествами (агентами и задачами) с целью минимизации суммарной стоимости назначений. В терминах теории графов задача эквивалентна поиску совершенного паросочетания минимальной стоимости во взвешенном двудольном графе. Задача относится к разделам исследования операций, линейного программирования и теории паросочетаний и представляет собой частный случай транспортной задачи с единичными объёмами поставок и спроса.

В стандартной постановке задана квадратная матрица стоимостей $C=(c_{ij})$ размера $n\times n$, где $c_{ij}$ — стоимость назначения $i$‑го агента $j$‑й задаче. Требуется найти перестановку $\sigma$ множества $\{1,\dots ,n\}$, минимизирующую $\sum _{i=1}^n{c}_{i,\sigma (i)}$. Задача полиномиально разрешима: наиболее известный алгоритм — венгерский метод (алгоритм Куна–Манкреса) — решает её за $O(n^3)$ операций.

Исторический контекст и предпосылки

Корни задачи о назначениях восходят к XIX веку. Карл Густав Якоби в 1830–1840‑х годах разработал алгоритм решения задачи в контексте систем дифференциальных уравнений; результаты были опубликованы посмертно в 1890 году на латинском языке.

В XX веке теоретическую базу заложили венгерские математики. Денеш Кёниг в 1931 году доказал теорему о равенстве размера максимального паросочетания и минимального вершинного покрытия в двудольных графах (теорема Кёнига). Енё Эгервари в том же году обобщил результат на взвешенный случай, показав конструктивный способ сведения взвешенной задачи к бинарной.

Термин «assignment problem» впервые появился в 1952 году в работе Воутоу и Ордена. В 1955 году Гарольд Кун опубликовал венгерский метод ((англ. Hungarian method)), названный в честь Кёнига и Эгервари. В 1957 году Джеймс Манкрес провёл строгий анализ алгоритма Куна и доказал его сильную полиномиальность, за что алгоритм стали называть алгоритмом Куна–Манкреса. Первоначальная оценка сложности составляла $O(n^4)$. В 1971–1972 годах Джек Эдмондс и Ричард Карп, а также Томидзава независимо модифицировали алгоритм до $O(n^3)$.

К 2007 году — пятидесятилетию работы Куна — насчитывались сотни вариаций задачи, систематизированных в обзоре Пентико. Наиболее полное изложение истории и алгоритмов содержится в монографии Буркарда, Делль'Амико и Мартелло (2012).

Математическая формулировка

Целочисленная линейная программа

Классическая задача о назначениях формулируется как задача целочисленного линейного программирования (ЦЛП). Пусть имеется множество агентов $I=\{1,\dots ,n\}$ и множество задач $J=\{1,\dots ,n\}$. Вводятся бинарные переменные $x_{ij}\in \{0,1\}$, где $x_{ij}=1$, если агент $i$ назначен на задачу $j$:

$\min \sum _{i=1}^n\sum _{j=1}^n{c}_{ij}{x}_{ij}$

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

$\sum _{j=1}^n{x}_{ij}=1,i=1,\dots ,n\text{(каждый агент назначен ровно одной задаче)}$

$\sum _{i=1}^n{x}_{ij}=1,j=1,\dots ,n\text{(каждая задача назначена ровно одному агенту)}$

Матрица $X=(x_{ij})$ при таких ограничениях представляет собой перестановочную матрицу — матрицу, в каждой строке и каждом столбце которой ровно одна единица. Множество всех допустимых решений задачи — множество всех перестановок $S_n$, число которых равно $n!$.

Тотальная унимодулярность и линейная релаксация

Матрица ограничений задачи о назначениях является тотально унимодулярной ((англ. totally unimodular)): все миноры этой матрицы принимают значения из множества $\{-1,0,1\}$. Это свойство гарантирует, что все вершины многогранника назначений ((англ. assignment polytope, Birkhoff polytope)) являются целочисленными, то есть перестановочными матрицами. Следовательно, оптимальное решение линейной релаксации (замена $x_{ij}\in \{0,1\}$ на $0\le x_{ij}\le 1$) автоматически целочисленно, и задача может быть решена методами линейного программирования без дополнительного требования целочисленности.

Данный результат является частным случаем теоремы Биркгофа–фон Неймана ((англ. Birkhoff–von Neumann theorem)), утверждающей, что множество дважды стохастических матриц представляет собой выпуклую оболочку перестановочных матриц.

Двойственная задача

Двойственная задача линейного программирования имеет вид:

$\max \sum _{i=1}^n{u}_i+\sum _{j=1}^n{v}_j$

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

$$\begin{gathered} u_i+v_j\le c_{ij},\mathrm{\forall }i\in I, \\ j\in J \end{gathered}$$

где $u_i$ и $v_j$ — двойственные переменные (потенциалы). По теореме сильной двойственности оптимальные значения прямой и двойственной задач совпадают. Условие дополняющей нежёсткости ((англ. complementary slackness)) утверждает, что в оптимальном решении $x_{ij}=1$ возможно только при равенстве $u_i+v_j=c_{ij}$. Это свойство лежит в основе венгерского метода.

Связь с теорией паросочетаний и потоков

Задача о паросочетании

Задача о назначениях эквивалентна задаче нахождения совершенного паросочетания минимальной стоимости ((англ. minimum‑cost perfect matching)) в полном взвешенном двудольном графе $G=(U,V,E)$, где $|U|=|V|=n$, каждая вершина в $U$ соответствует агенту, каждая вершина в $V$ — задаче, а вес ребра $(i,j)$ равен $c_{ij}$.

По теореме Кёнига–Эгервари размер максимального паросочетания в двудольном графе равен размеру минимального вершинного покрытия; для взвешенного случая это обобщается на равенство стоимости оптимального паросочетания и оптимального покрытия.

Задача о минимальном стоимостном потоке

Задача о назначениях также сводится к задаче о потоке минимальной стоимости ((англ. minimum‑cost flow)) в сети с источником $s$, стоком $t$ и двудольными вершинами. Источник соединяется с каждым агентом ребром пропускной способности 1 и нулевой стоимости; каждая задача соединяется со стоком аналогично; рёбра между агентами и задачами имеют пропускную способность 1 и стоимость $c_{ij}$. Максимальный поток стоимости $n$ в такой сети соответствует совершенному паросочетанию.

Алгоритмы решения

Для линейной задачи о назначениях разработан ряд точных полиномиальных алгоритмов. Все они гарантируют нахождение глобального оптимума, но различаются по практической эффективности на различных классах входных данных.

Венгерский метод (алгоритм Куна–Манкреса)

Венгерский метод — классический комбинаторный алгоритм, представляющий собой реализацию примально‑двойственного метода для пары взаимно двойственных задач линейного программирования. Алгоритм работает с двойственными переменными (потенциалами) $u_i,v_j$ и порождённым подграфом равенств $G_{=}=\{(i,j):u_i+v_j=c_{ij}\}$.

В матричной интерпретации алгоритм выполняет следующие шаги:

1. Редукция по строкам: из каждого элемента строки вычитается минимальный элемент этой строки.
2. Редукция по столбцам: из каждого элемента столбца вычитается минимальный элемент этого столбца. В результате матрица содержит нули, соответствующие потенциальным назначениям.
3. Покрытие нулей: находится минимальное число горизонтальных и вертикальных линий (строк и столбцов), покрывающих все нули.
4. Проверка оптимальности: если число линий равно $n$, в матрице существует совершенное паросочетание нулей — оптимальное решение найдено.
5. Корректировка матрицы: если число линий меньше $n$, выбирается минимальный непокрытый элемент $\delta$, вычитается из всех непокрытых элементов и прибавляется к элементам на пересечении двух линий. Возврат к шагу 3.

Графовая реализация использует поиск увеличивающих путей ((англ. augmenting paths)) в подграфе равенств. На каждой итерации либо увеличивается размер текущего паросочетания, либо корректируются потенциалы, расширяя подграф равенств. Модификация Эдмондса–Карпа и Томидзавы обеспечивает сложность $O(n^3)$ за счёт более эффективного поиска кратчайших увеличивающих путей и обновления потенциалов.

Исследуются также ускоренные варианты венгерского метода, в которых на каждом шаге создаётся более одного нового нуля, что уменьшает число итераций на практике при сохранении полиномиальной оценки сложности.

Алгоритм Йонкера–Волгенанта (LAPJV)

Алгоритм Йонкера–Волгенанта ((англ. Jonker–Volgenant algorithm), LAPJV), предложенный в 1987 году, основан на последовательном поиске кратчайших увеличивающих путей ((англ. shortest augmenting path)) с использованием потенциалов. Алгоритм имеет ту же асимптотическую сложность $O(n^3)$, однако на практике часто работает существенно быстрее венгерского метода благодаря более эффективным структурам данных и стратегиям инициализации. Реализации LAPJV входят в стандартные библиотеки SciPy (scipy.optimize.linear_sum_assignment) и MATLAB.

Для разреженных графов алгоритмы с кучами Фибоначчи достигают сложности $O(mn+n^2\log n)$, где $m$ — число рёбер.

Аукционный алгоритм

Аукционный алгоритм ((англ. auction algorithm)), предложенный Димитрием Бертсекасом в 1980‑х годах, моделирует процесс назначения как аукцион: агенты итеративно «делают ставки» на задачи, повышая их «цены» до достижения равновесия. Алгоритм естественно допускает параллельную реализацию, поскольку ставки агентов могут вычисляться независимо, что делает его привлекательным для распределённых систем и реализаций на графических процессорах.

Методы линейного программирования

Благодаря тотальной унимодулярности задача может быть решена стандартными методами линейного программирования — симплекс‑методом или методом внутренних точек — без дополнительного требования целочисленности. На практике специализированные комбинаторные алгоритмы значительно превосходят общие LP‑солверы по скорости на задачах о назначениях, однако LP‑подход удобен при наличии дополнительных ограничений, выходящих за рамки классической постановки.

Сравнение алгоритмов

Алгоритм	Сложность	Тип решения	Особенности
Венгерский метод	$O(n^3)$	Точное	Классический; примально‑двойственный подход
LAPJV (Йонкер–Волгенант)	$O(n^3)$	Точное	Часто быстрее на практике; реализован в SciPy
Аукционный алгоритм	$O(n^3)$ (с $\epsilon$‑масштабированием)	Точное	Параллелизуем; подходит для распределённых систем
Min‑cost flow	$O(n^3)$	Точное	Естественен при обобщениях с ограничениями потока
Симплекс‑метод (LP)	Экспоненциальная в худшем случае	Точное	Универсален; медленнее специализированных методов
Метод внутренних точек	$O(n^{3.5}\log n)$	Точное	Полиномиальный LP‑метод; высокие константы

Варианты целевой функции

Помимо классической линейной (суммарной) целевой функции исследуются иные критерии оптимальности, порождающие различные постановки задачи.

Минимаксная (bottleneck) задача

Линейная минимаксная задача о назначениях ((англ. Linear Bottleneck Assignment Problem), LBAP) минимизирует не сумму, а максимальную стоимость назначенного ребра:

$\underset{\sigma \in S_n}{\min }\underset{i=1,\dots ,n}{\max }{c}_{i,\sigma (i)}$

LBAP разрешима за $O(n^{2.5})$ операций с помощью бинарного поиска по порогу стоимости с проверкой существования совершенного паросочетания в соответствующем подграфе.

Лексикографическая задача

В лексикографической задаче о назначениях вектор стоимостей назначений сортируется по невозрастанию и минимизируется в лексикографическом порядке. Данная постановка возникает, когда требуется обеспечить справедливость распределения — минимизировать наихудшую стоимость, затем вторую наихудшую и так далее.

Алгебраические обобщения

Более общие варианты заменяют операции суммирования и минимизации операциями над алгебраическими структурами — например, полукольцами. Такой подход позволяет моделировать задачи на кратчайшие пути и другие задачи дискретной оптимизации в единой рамке.

Вариации и обобщения

Классическая линейная задача о назначениях допускает многочисленные обобщения, отражающие различные практические требования. Большинство из них являются NP‑трудными.

Несбалансированные и ограниченные назначения

В практике часто число агентов не равно числу задач (несбалансированная задача, (англ. unbalanced assignment problem)). Стандартное решение — введение фиктивных агентов или задач с нулевой (при минимизации) или штрафной стоимостью.

Запрещённые назначения ((англ. forbidden assignments)) моделируются присвоением соответствующим элементам матрицы стоимости $+\mathrm{\infty }$ (или достаточно большого числа) либо явным исключением рёбер в графовой постановке.

При задачах максимизации (например, максимизации прибыли) применяют эквивалентное преобразование: $c{\text{'}}_{ij}=C_{\max }-p_{ij}$, где $p_{ij}$ — прибыль от назначения.

Обобщённая задача о назначениях (GAP)

Обобщённая задача о назначениях ((англ. Generalized Assignment Problem), GAP) вводит ограничения на ресурсы (ёмкости) агентов. Каждый агент $i$ обладает ресурсом объёма $b_i$; назначение задачи $j$ агенту $i$ потребляет $a_{ij}$ единиц ресурса и имеет стоимость $c_{ij}$. Требуется назначить каждую задачу ровно одному агенту с минимальной суммарной стоимостью при условии $\sum _j{a}_{ij}{x}_{ij}\le b_i$ для каждого $i$.

GAP является NP‑трудной. Для её решения разработаны точные методы (метод ветвей и границ; лагранжева релаксация) и эвристические подходы (жадные методы, локальный поиск, метаэвристики). Современные работы предлагают расширенные формулировки ((англ. extended formulations)) с более сильными линейными релаксациями и новыми классами валидных неравенств.

Квадратичная задача о назначениях (QAP)

Квадратичная задача о назначениях ((англ. Quadratic Assignment Problem), QAP) моделирует ситуации, где стоимость зависит от пар назначений. Классическая постановка включает матрицу потоков $F=(f_{kl})$ между объектами и матрицу расстояний $D=(d_{ij})$ между позициями:

$\underset{\sigma \in S_n}{\min }\sum _{k=1}^n\sum _{l=1}^n{f}_{kl}{d}_{\sigma (k),\sigma (l)}$

QAP является NP‑трудной и одной из наиболее сложных задач комбинаторной оптимизации; точное решение возможно лишь для экземпляров умеренного размера (порядка нескольких десятков). На практике применяются метод ветвей и границ, табу-поиск, генетические алгоритмы и другие метаэвристики. Типичное приложение QAP — задача размещения оборудования ((англ. facility layout problem)).

Другие расширения

Многообразие практических приложений порождает ряд дополнительных обобщений классической задачи:

• Многократная задача о назначениях: каждый агент может выполнять несколько задач при ограничениях по мощности.
• Стохастическая задача о назначениях: стоимости или доступность ресурсов являются случайными величинами; решения строятся с учётом распределений и критериев риска.
• Динамическая (онлайн) задача: задачи и агенты поступают во времени, решения принимаются последовательно без полной информации о будущих поступлениях.
• Многокритериальные постановки: одновременный учёт нескольких критериев — стоимости, времени, качества.

Случайные и асимптотические аспекты

Развита теория асимптотического поведения оптимального значения задачи о назначениях при случайных стоимостях. Для матрицы $C$, элементы которой являются независимыми одинаково распределёнными случайными величинами с экспоненциальным распределением (параметр 1), математическое ожидание оптимальной стоимости при $n\to \mathrm{\infty }$ стремится к:

$\underset{n\to \mathrm{\infty }}{\lim }\mathbb{𝔼}\left[\underset{\sigma \in S_n}{\min }\sum _{i=1}^n{c}_{i,\sigma (i)}\right]=\frac{{\pi }^2}{6}=\zeta (2)\approx 1,6449$

Этот результат, известный как гипотеза Пароизи и доказанный Линусоном и Вёстлундом в 2004 году, имеет значение для анализа средней сложности и поведения алгоритмов на случайных данных.

Применения

Задача о назначениях находит применение в широком спектре практических областей благодаря универсальности постановки: любая ситуация, требующая оптимального сопоставления двух множеств, может быть формализована как задача о назначениях.

Исследование операций и производство

Классические приложения включают назначение работников на рабочие места или смены, распределение работ по станкам для минимизации суммарного времени обработки, планирование смен и расписаний (назначение экипажей, бригад, преподавателей).

Логистика и транспорт

В транспортной логистике задача используется для распределения транспортных средств по маршрутам (назначение такси клиентам с минимизацией времени подъезда, распределение вагонов по поездам, назначение ворот в аэропортах). Задача о назначениях также выступает как подзадача при решении более сложных задач маршрутизации, включая задачу коммивояжёра.

Компьютерное зрение и сопоставление данных

В компьютерном зрении задача о назначениях применяется для ассоциации данных ((англ. data association)) при многообъектном слежении ((англ. multi‑object tracking)): на каждом кадре наблюдения сопоставляются с существующими треками. Другие применения включают сопоставление ключевых точек на изображениях, выравнивание сетей ((англ. network alignment)) и назначение задач процессорным ядрам в параллельных вычислениях.

Рецензирование статей и грантов

Задача о назначении рецензентов ((англ. Reviewer Assignment Problem), RAP) формулируется как обобщённая задача о назначениях с целевой функцией максимизации суммы сходств экспертизы при ограничениях на нагрузку и конфликты интересов. Реальные системы — TPMS, Erie — решают эту задачу с помощью ЦЛП, генетических алгоритмов или min‑cost flow.

Экономика, биоинформатика и здравоохранение

В экономике модели паросочетаний используются при анализе рынков сопоставлений ((англ. matching markets)) и механизмов распределения ресурсов. В биоинформатике задача применяется при выравнивании генных и белковых последовательностей, сопоставлении структурных элементов биомолекул. В здравоохранении — для назначения пациентов врачам, оптимизации распределения трансплантационных ресурсов и планирования палат.

Практическая эффективность

На матрицах размером $n\le 1000$ современные реализации (LAPJV) решают задачу за секунды на стандартном оборудовании. Для $n\approx 5000$ требуются оптимизированные реализации; для $n>10^4$ — специализированные разреженные версии алгоритмов.

Размер задачи $n$	Типичное время (LAPJV)	Примечание
$10^2$	миллисекунды	Любая реализация
$10^3$	секунды	Стандартные библиотеки (SciPy, MATLAB)
$10^4$	десятки секунд — минуты	Оптимизированные реализации
$10^5$	требуется специализация	Разреженные методы, параллелизация

Для GAP точные методы решают экземпляры до $n\approx 100\text{–}500$ в зависимости от структуры ёмкостей; бо́льшие экземпляры требуют эвристик. Для QAP точная оптимизация ограничена размерами порядка нескольких десятков.

Ограничения классической модели

Классическая линейная задача о назначениях предполагает строгое соотношение один‑к‑одному между агентами и задачами, аддитивную линейную структуру целевой функции без взаимодействий между парами назначений, а также детерминированные и заранее известные стоимости $c_{ij}$. В реальных задачах могут присутствовать ограничения совместимости и логические зависимости между назначениями, ограничения по мощности и ресурсам (приводящие к GAP), а также стохастические или нечётко заданные стоимости, требующие методов робастного или стохастического программирования.

Открытые проблемы и направления исследований

Несмотря на полную теоретическую изученность классической линейной задачи, для её обобщений остаётся ряд открытых вопросов:

• Формулировки и неравенства: улучшение линейных релаксаций для GAP и связанных задач с целью сокращения вычислительных затрат при решении крупных экземпляров.
• Гибридные методы: разработка алгоритмов, сочетающих точные методы и метаэвристики с гарантированной оценкой качества.
• Параллельные и распределённые реализации: эффективное использование многопроцессорных систем, графических процессоров и облачных сред.
• Интеграция с машинным обучением: использование нейронных сетей для оценки стоимостей, прогнозирования параметров и выбора эвристик в алгоритмах назначения.
• Онлайн‑алгоритмы: динамические задачи с поступлением данных в реальном времени, требующие адаптивных решений без полной информации.
• Квантовые алгоритмы: потенциальное применение квантовых вычислений для ускорения решения задач большой размерности.
• Справедливость и этика: включение ограничений на справедливость ((англ. fairness constraints)) в модели назначения, особенно в социально значимых приложениях — здравоохранении, распределении должностей, рецензировании.

Программные реализации

• SciPy: scipy.optimize.linear_sum_assignment — реализация на основе LAPJV.
• Google OR-Tools: линейные и обобщённые задачи о назначениях.
• CPLEX, Gurobi: коммерческие LP/ILP‑солверы.
• LEMON: библиотека для сетевых задач на C++.

См. также

• Транспортная задача
• Задача коммивояжёра
• Задача о потоке минимальной стоимости
• Обобщённая задача о назначениях

Ссылки

• 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.