Линейная задача о назначениях в узких местах

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

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

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

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

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

Формальное определение

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

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

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

Формулировка задачи как задачи математического программирования

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

Методы решения

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

Лемма.[1] Пусть — матрица цен задачи, Тогда

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

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

Упорядочиваем элементы матрицы .

Заменяем наименьший элемент −2 на 0, следующий за ним 0 заменяем на 1, затем заменяем на 2 и так далее. Получим следующую матрицу: .

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

Пороговый алгоритм

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

Присваиваем начальные значения .
Если , то
  оптимальное значение =  и любая перестановка {1, 2, . . . , n} оптимальна.
В противном случае, 
  пока существуют , выполнить
    Находим медиану, t чисел 
    Строим граф 
    Если  содержит совершенное паросочетание, то принимаем 
      
    иначе принимаем 
       
    конец если
  конец цикла
  Если проверка существования совершенного паросочетания для   не выполнялась, выполним её.
  Строим граф  для 
  Если  содержит совершенное паросочетание, принимаем
    
  конец если
конец если

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

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

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

На втором этапе проверяется, существует ли назначение с нулевой ценой (для матрицы цен ). Для проверки этого конструируется двудольный граф G = (U, V; E) с |U| = |V| = n и дуги тогда и только тогда, когда . (Другими словами, мы должны проверить, содержит ли двудольный граф, соответствующий пороговой матрице, совершенное паросочетание или нет). Минимальное пороговое значение , для которого соответствующий двудольный граф содержит совершенное паросочетание, является оптимальным значением задачи. Существует несколько путей реализации порогового алгоритма. Одна из возможностей — использовать двоичный поиск на первом этапе. Это приведёт к алгоритму, где — временна́я сложность проверки существования совершенного паросочетания. Мы можем использовать матричный алгоритм Ибарра и Морана[4] для выяснения, существует ли совершенное паросочетание. Тогда оптимальное решение может быть найдено с битовой сложностью . Для умножения двух n × n матриц нужно арифметических операций и k — некоторое целое число, возникающее из действий над длинными целыми числами. Копперсмит (Coppersmith) и Виноград (Winograd)[5] показали, что умножение матриц можно сделать с . Если мы хотим получить соответствующее оптимальное решение, мы можем использовать метод Альта, Блюма, Мелхорна и Паула (Alt, Blum, Mehlhorn, Paul)[6] и получим полную сложность в случае плотной матрицы. Здесь плотность означает, что число ненулевых элементов матрицы равно .

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

Двойственный алгоритм

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

Вычислим 
Положим   (пустое множество).
Пока |M| < n, выполнять
  Определим двудольный граф G, соответствующий пороговому значению t.
  Найдем максимальное паросочетание в G.
  Если |M| < n, то
    Пусть  и  — множества вершин в минимальном покрытии графа G.
    Положим 
  конец если
конец цикла

Алгоритм использует некоторую информацию о пороговом значении t, а именно — тот факт, что оптимальное значение не может быть меньше максимального значения из минимальных элементов в строках, а также максимального значения из минимальных элементов в столбцах матрицы C. Таким образом, в качестве первого порогового значения можно взять

Двойтвенный метод начинает с этого значения t и создаёт минимальные наборы (индексов) столбцов и строк , покрывающие все элементы матрицы . Это можно сделать, найдя максимальный набор дуг в графе G, задающих паросочетание. Здесь граф G — это двудольный граф с дугами (r,j), для которых . Если паросочетание не содержит все строки и столбцы, существуют элементы матрицы, определяющие оптимальное значение, и эти элементы больше t. Вследствие этого, мы можем принять новое значение и построить новый граф G. Этот граф содержит все рёбра предыдущего графа и как минимум одно новое ребро, так что мы можем начать поиск максимального паросочетания с уже найденного на предыдущем шаге. Продолжаем, пока не найдём совершенное паросочетание.

Алгоритм последовательных приращений

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

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

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

Пусть — дополняющий путь для паросочетания M.

Размер узкого места определяется как

.

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

Пусть  — двудольный граф с длинами дуг  для дуг 
Найдем нижнюю границу t для целевой функции
     (т.е. )
Находим максимальное паросочетание M в графе G, имеющего дуги [i, j] если 
если |M| = |U|, то мы получили оптимальное решение t с оптимальным отношением M, и завершаем работу.
конец если
Пусть L — множество элементов U, для которых нет паросочетания.
пока L не пусто, выполнить
  Выберем вершину 
  Положим 
  P = Dijkstra(i)
  Комментарий: Функция Dijkstra(i) возвращает дополняющий путь, начинающийся в вершине i
  Если путь не найден, то
    Положим 
    Положим 
  конец если
конец пока
Комментарий: M — максимальное паросочетание с минимальной ценой t.

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

Во время поиска b-кратчайшего пути помечаем вершину значением , где является размером узкого места b-кратчайшего пути из в эту вершину, а означает непосредственного предшественника в b-кратчайшем пути из в вершину .

Аналогичным образом помечаем вершину значением , где является размером узкого места b-кратчайшего пути из в эту вершину, а означает непосредственного предшественника в b-кратчайшем пути из в вершину .

Функция Dijkstra(i)
Комментарий: Модифицированный алгоритм Дейкстры для задачи о назначениях для узких мест.
Помечаем все вершины , положив .
Положим R = V Комментарий: R содержит непросмотренные вершины V
α(i) = t, P = пусто
Для всех соседей  вершины i выполнить
  Если , то
    Положим 
    
  конец если
конец цикла
пока R пусто, выполнять
  Найдём вершину  с минимальным ;
  Если , то 
    Положим 
  иначе
    если r не входит в паросочетание, то
      Находим путь P, образованный последовательностью вершин 
      Положим 
      
    Иначе
      Пусть [s, r] — ребро паросочетания
      Помечаем s: 
      Положим 
      Для всех соседей  вершины s выполнить
        Если , то
          Положим 
          
        конец если
      конец цикла
    конец если
  конец если
конец пока

Асимптотическое поведение

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

и

Ссылки

  1. Assignment Problems, Rainer Burkard, Mauro Dell’Amico, Silvano Martello, 2009, глава 6.2 «Linear Bottleneck Assignment Problem» (стр. 172)
  2. D.R. Fulkerson, I. Glicksberg, and O. Gross. A production line assignment problem. Tech. Rep. RM-1102, The Rand Corporation, Santa Monica, CA, 1953.)
  3. R. Garfinkel. An improved algorithm for the bottleneck assignment problem. Oper. Res., 19:1747–1751, 1971.
  4. O.H. Ibarra and S. Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. Inform. Process. Lett., 13:12–15, 1981.
  5. D. Coppersmith and S.Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computing, 9:251–280, 1990.
  6. H. Alt, N. Blum, K. Mehlhorn, and M. Paul. Computing a maximum cardinality matching in a bipartite graph in time . Inform. Process. Lett., 37:237–240, 1991.
  7. O. Gross. The bottleneck assignment problem. Tech. Rep. P-1630, The Rand Corporation,Santa Monica, CA, 1959.
  8. U. Derigs and U. Zimmermann. An augmenting path method for solving linear bottleneck assignment problems. Computing, 19:285–295, 1978.
  9. Michael Z. Spivey, "Asymptotic Moments of the Bottleneck Assignment Problem," Mathematics of Operations Research, 36 (2): 205-226, 2011.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.