В комбинаторной оптимизации под линейной задачей о назначениях на узкие места (linear bottleneck assignment problem, LBAP) понимается задача, похожая на задачу о назначениях^[1].

В простых словах задача ставится следующим образом:

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

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

Линейная задача о назначениях на узкие места была впервые изложена Фалкерсоном (Fulkerson), Гликсбергом (Glicksberg) и Гроссом (Gross) в работе, посвящённой распределению работ по машинам с целью минимизировать время выполнения заказа^[2].

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

Заданы два множества, A и T, вместе с весовой функцией C : A × T → R. Найти биекцию f : A → T такую, что функция стоимости:

${\displaystyle \max _{a\in A}C(a,f(a))}$

минимальна.

Обычно функция веса задаётся как квадратная вещественная матрица C, так что функцию стоимости можно записать следующим образом:

${\displaystyle \max _{a\in A}C_{a,f(a)}}$

${\displaystyle \min \,\max _{i,j}c_{i,j}x_{i,j}}$

при условиях:

${\displaystyle \sum _{j=1}^{n}x_{i,j}=1\ (i=1,2,\dots ,n),}$

${\displaystyle \sum _{i=1}^{n}x_{i,j}=1\ (j=1,2,\dots ,n),}$

${\displaystyle x_{i,j}\in \{0,1\}\ (i,j=1,2,\dots ,n)}$

Для решения задачи полезна следующая лемма:

Лемма.^[1] Пусть ${\displaystyle C=(c_{i,j})}$ — матрица цен задачи, Тогда

1. Оптимальное значение задачи определяется одним из элементов матрицы ${\displaystyle c_{i,j}}$.

2. Оптимальное решение зависит только от относительного порядка элементов матрицы, а не от их числовых значений

Пример. Пусть задана матрица

${\displaystyle C={\begin{pmatrix}\pi &{\sqrt {3}}&54392\\0&e^{3}&e^{3}\\{-}2&\sin {(\pi /8)}&4\\\end{pmatrix}}}$

Упорядочиваем элементы матрицы ${\displaystyle -2<0<\sin {(\pi /8)}<{\sqrt {3}}<\pi <4<e^{3}=e^{3}<54392}$.

Заменяем наименьший элемент −2 на 0, следующий за ним 0 заменяем на 1, затем ${\displaystyle \sin {(\pi /8)}}$ заменяем на 2 и так далее. Получим следующую матрицу: ${\displaystyle C'={\begin{pmatrix}4&3&7\\1&6&6\\0&2&5\\\end{pmatrix}}}$.

Оптимальным решением задачи будет перестановка {2, 1, 3} с максимальным значением для матрицы ${\displaystyle C'}$ 5, что соответствует значению 4 в исходной матрице ${\displaystyle C}$.

Идея использования метода пороговых значений принадлежит Гарфинкелю (Garfinkel)^[3].

Присваиваем начальные значения ${\displaystyle t_{\min }=\min _{i,j}{c_{i,j}},t_{\max }=\max _{i,j}{c_{i,j}}}$.
Если ${\displaystyle t_{\min }=t_{\max }}$, то
  оптимальное значение = ${\displaystyle t_{\min }}$ и любая перестановка {1, 2, . . . , n} оптимальна.
В противном случае, 
  пока существуют ${\displaystyle c_{i,j}:t_{\min }<c_{i,j}<t_{\max }}$, выполнить
    Находим медиану, t чисел ${\displaystyle t_{\min }<c_{i,j}<t_{\max }}$
    Строим граф ${\displaystyle T}$
    Если ${\displaystyle T}$ содержит совершенное паросочетание, то принимаем 
      ${\displaystyle t_{\min }=t}$
    иначе принимаем 
      ${\displaystyle t_{\max }=t}$ 
    конец если
  конец цикла
  Если проверка существования совершенного паросочетания для  ${\displaystyle t_{\min }}$ не выполнялась, выполним её.
  Строим граф ${\displaystyle T}$ для ${\displaystyle t_{\min }}$
  Если ${\displaystyle T}$ содержит совершенное паросочетание, принимаем
    ${\displaystyle t_{\max }=t_{\min }}$
  конец если
конец если

Оптимальное значение будет равно ${\displaystyle t_{\max }}$, и оптимальное решение можно найти из соответствующего графа.

Как видим, на каждом шаге цикла 'пороговый алгоритм' проходит два этапа. На первом этапе выбирается 'пороговое значение' ${\displaystyle t}$ и 'пороговая матрица' ${\displaystyle T}$, которая определяется следующим образом:

${\displaystyle T_{i,j}=}$

1, если ${\displaystyle c_{ij}>t}$

0 в противном случае.

На втором этапе проверяется, существует ли назначение с нулевой ценой (для матрицы цен ${\displaystyle T}$). Для проверки этого конструируется двудольный граф G = (U, V; E) с |U| = |V| = n и дуги ${\displaystyle [i,j]\in E}$ тогда и только тогда, когда ${\displaystyle T_{i,j}=0}$. (Другими словами, мы должны проверить, содержит ли двудольный граф, соответствующий пороговой матрице, совершенное паросочетание или нет). Минимальное пороговое значение ${\displaystyle t}$, для которого соответствующий двудольный граф содержит совершенное паросочетание, является оптимальным значением задачи. Существует несколько путей реализации порогового алгоритма. Одна из возможностей — использовать двоичный поиск на первом этапе. Это приведёт к ${\displaystyle O(M(n)\log(n))}$ алгоритму, где ${\displaystyle M(n)}$ — временна́я сложность проверки существования совершенного паросочетания. Мы можем использовать матричный алгоритм Ибарра и Морана^[4] для выяснения, существует ли совершенное паросочетание. Тогда оптимальное решение может быть найдено с битовой сложностью ${\displaystyle O(n^{\beta }\log ^{k}n)}$. Для умножения двух n × n матриц нужно ${\displaystyle O(n^{\beta })}$ арифметических операций и k — некоторое целое число, возникающее из действий над длинными целыми числами. Копперсмит (Coppersmith) и Виноград (Winograd)^[5] показали, что умножение матриц можно сделать с ${\displaystyle \beta =2{,}376}$. Если мы хотим получить соответствующее оптимальное решение, мы можем использовать метод Альта, Блюма, Мелхорна и Паула (Alt, Blum, Mehlhorn, Paul)^[6] и получим полную сложность ${\displaystyle O\left(n^{2{,}5}\left/{\sqrt {\log(n)}}\right.\right)}$ в случае плотной матрицы. Здесь плотность означает, что число ненулевых элементов ${\displaystyle T_{i,j}}$ матрицы равно ${\displaystyle O(n^{2})}$.

Этот метод теоретически является лучшим из известных методов решения задачи.

Тесно связан с пороговым методом следующий двойственный алгоритм.

Вычислим ${\displaystyle t=\max _{k=1,2,\dots ,n}(\min _{r=1,2,\dots ,n}c_{r,k},\min _{j=1,2,\dots ,n}c_{k,j})}$
Положим ${\displaystyle M=\varnothing }$  (пустое множество).
Пока |M| < n, выполнять
  Определим двудольный граф G, соответствующий пороговому значению t.
  Найдем максимальное паросочетание в G.
  Если |M| < n, то
    Пусть ${\displaystyle R\subseteq U}$ и ${\displaystyle J\subseteq V}$ — множества вершин в минимальном покрытии графа G.
    Положим ${\displaystyle t=\min _{r\in R,j\in J}c_{r,j}}$
  конец если
конец цикла

Алгоритм использует некоторую информацию о пороговом значении t, а именно — тот факт, что оптимальное значение не может быть меньше максимального значения из минимальных элементов в строках, а также максимального значения из минимальных элементов в столбцах матрицы C. Таким образом, в качестве первого порогового значения можно взять ${\displaystyle t=\max _{1\leqslant k\leqslant n}(\min _{1\leqslant r\leqslant n}c_{r,k},\min _{1\leqslant j\leqslant n}c_{k,j})}$

Двойтвенный метод начинает с этого значения t и создаёт минимальные наборы (индексов) столбцов ${\displaystyle J}$ и строк ${\displaystyle R}$, покрывающие все элементы матрицы ${\displaystyle c_{r,j}\leqslant t}$. Это можно сделать, найдя максимальный набор дуг в графе G, задающих паросочетание. Здесь граф G — это двудольный граф с дугами (r,j), для которых ${\displaystyle c_{r,j}\leqslant t}$. Если паросочетание не содержит все строки и столбцы, существуют элементы матрицы, определяющие оптимальное значение, и эти элементы больше t. Вследствие этого, мы можем принять новое значение ${\displaystyle t=\min _{r\in R,j\in J}c_{r,j}}$ и построить новый граф G. Этот граф содержит все рёбра предыдущего графа и как минимум одно новое ребро, так что мы можем начать поиск максимального паросочетания с уже найденного на предыдущем шаге. Продолжаем, пока не найдём совершенное паросочетание.

Ещё одним подходом к решению задачи может служить использование идей венгерского метода^[7]. В России этот метод известен под названием 'Алгоритм Гросса'. Изложим метод в реализации Деригса и Циммермана^[8].

Введём несколько определений.

Дополняющим путём паросочетания называется путь, содержащий дуги паросочетания, при этом из двух соседних дуг одна обязательно принадлежит паросочетанию (т.е. дуги перемежаются — за дугой из паросочетания идёт дуга, не принадлежащая ему, и наоборот).

Пусть ${\displaystyle P=([i_{1},j_{1}],[i_{2},j_{1}],[i_{2},j_{2}],\dots ,[i_{k},j_{k}])}$ — дополняющий путь для паросочетания M.

Размер узкого места ${\displaystyle \ell (P)}$ определяется как

${\displaystyle \ell (P)=\max(c([i_{1},j_{1}]),c([i_{2},j_{2}]),\dots ,c([i_{k},j_{k}]))}$.

Дополняющий путь называется b-кратчайшим путём, если размер узкого места минимален среди всех дополняющих путей M.

Пусть ${\displaystyle G=(U,V;E)}$ — двудольный граф с длинами дуг ${\displaystyle c_{i,j}}$ для дуг ${\displaystyle [i,j]\in E}$
Найдем нижнюю границу t для целевой функции
     (т.е. ${\displaystyle t=\max {(\max _{u\in U}\min _{v\in V}c_{u,v},\max _{v\in V}\min _{u\in U}c_{u},v)}}$)
Находим максимальное паросочетание M в графе G, имеющего дуги [i, j] если ${\displaystyle c_{i,j}\leqslant t}$
если |M| = |U|, то мы получили оптимальное решение t с оптимальным отношением M, и завершаем работу.
конец если
Пусть L — множество элементов U, для которых нет паросочетания.
пока L не пусто, выполнить
  Выберем вершину ${\displaystyle i\in L}$
  Положим ${\displaystyle L=L\backslash \{i\}}$
  P = Dijkstra(i)
  Комментарий: Функция Dijkstra(i) возвращает дополняющий путь, начинающийся в вершине i
  Если путь не найден, то
    Положим ${\displaystyle M=M\ominus P}$
    Положим ${\displaystyle t=\max(t,\ell (P))}$
  конец если
конец пока
Комментарий: M — максимальное паросочетание с минимальной ценой t.

B-кратчайший дополняющий путь находится функцией Dijkstra().

Во время поиска b-кратчайшего пути помечаем вершину ${\displaystyle x\in U}$ значением ${\displaystyle ({\overline {\alpha }}(x),{\overline {\beta }}(x))}$, где ${\displaystyle {\overline {\alpha }}(x)}$ является размером узкого места b-кратчайшего пути из ${\displaystyle i_{1}}$ в эту вершину, а ${\displaystyle {\overline {\beta }}(x)}$ означает непосредственного предшественника в b-кратчайшем пути из ${\displaystyle i_{1}}$ в вершину ${\displaystyle x}$.

Аналогичным образом помечаем вершину ${\displaystyle x\in V}$ значением ${\displaystyle (\alpha (x),\beta (x))}$, где ${\displaystyle \alpha (x)}$ является размером узкого места b-кратчайшего пути из ${\displaystyle i_{1}}$ в эту вершину, а ${\displaystyle \beta (x)}$ означает непосредственного предшественника в b-кратчайшем пути из ${\displaystyle i_{1}}$ в вершину ${\displaystyle x}$.

Функция Dijkstra(i)
Комментарий: Модифицированный алгоритм Дейкстры для задачи о назначениях для узких мест.
Помечаем все вершины ${\displaystyle j\in V}$, положив ${\displaystyle (\alpha (j),\beta (j))=(\infty ,\varnothing )}$.
Положим R = V Комментарий: R содержит непросмотренные вершины V
α(i) = t, P = пусто
Для всех соседей ${\displaystyle j\in R}$ вершины i выполнить
  Если ${\displaystyle \alpha (j)>\max({\overline {\alpha }}(i),c_{i,j})}$, то
    Положим ${\displaystyle \alpha (j)=\max({\overline {\alpha }}(i),c_{i,j})}$
    ${\displaystyle \beta (j)=i}$
  конец если
конец цикла
пока R пусто, выполнять
  Найдём вершину ${\displaystyle r\in R}$ с минимальным ${\displaystyle \alpha (r)}$;
  Если ${\displaystyle \alpha (r)=\infty }$, то 
    Положим ${\displaystyle R=\varnothing }$
  иначе
    если r не входит в паросочетание, то
      Находим путь P, образованный последовательностью вершин ${\displaystyle (i,\dots ,{\overline {\beta }}(\beta (r)),\beta (r),r)}$
      Положим ${\displaystyle \ell (P)=\alpha (r)}$
      ${\displaystyle R=\varnothing }$
    Иначе
      Пусть [s, r] — ребро паросочетания
      Помечаем s: ${\displaystyle ({\overline {\alpha }}(s),{\overline {\beta }}(s))=(\alpha (r),r)}$
      Положим ${\displaystyle R=R\backslash \{r\}}$
      Для всех соседей ${\displaystyle j\in R}$ вершины s выполнить
        Если ${\displaystyle \alpha (j)>\max({\overline {\alpha }}(s),c_{s,j})}$, то
          Положим ${\displaystyle \alpha (j)=\max({\overline {\alpha }}(s),c_{s,j})}$
          ${\displaystyle \beta (j)=s}$
        конец если
      конец цикла
    конец если
  конец если
конец пока

Пусть ${\displaystyle c_{n}^{*}}$ обозначает оптимальное значение функции для n исполнителей и n работ. Если цены ${\displaystyle c_{ij}}$ выбираются из равномерного распределения на отрезке (0,1), то^[9]

${\displaystyle E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n}}+O\left({\frac {(\log n)^{2}}{n^{7/5}}}\right)}$

и

${\displaystyle \mathrm {Var} [c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O\left({\frac {(\log n)^{2}}{n^{7/3}}}\right).}$

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.