Задача о линейном назначении узких мест - Linear bottleneck assignment problem - Wikipedia

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

Проще говоря, проблема формулируется следующим образом:

Есть ряд агенты и ряд задачи. Любого агента можно назначить для выполнения любой задачи, влекущей за собой некоторые Стоимость это может варьироваться в зависимости от назначения агенту задачи. Требуется выполнить все задачи, назначив каждой задаче ровно один агент таким образом, чтобы максимальная стоимость среди индивидуальных заданий сведена к минимуму.

Период, термин "горлышко бутылки "объясняется распространенным типом приложения проблемы, где стоимость - это продолжительность задачи, выполняемой агентом. В этом параметре" максимальная стоимость "- это" максимальная продолжительность ", которая является узким местом для расписания общая работа, которая должна быть минимизирована.

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

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

Учитывая два набора, А и Твместе с весовая функция C : А × Т → р. Найти биекция ж : А → Т так что функция стоимости:

${\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_{ij}x_{ij}}$

при условии:

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

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

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

Асимптотика

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

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

и

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

Рекомендации

1. Проблемы с назначением, к Райнер Буркард, Мауро Дель'Амико, Сильвано Мартелло, 2009, Глава 6.2 "Линейная проблема назначения узких мест "(стр. 172)
2. Майкл З. Спайви, «Асимптотические моменты проблемы назначения узких мест», Математика исследования операций, 36 (2): 205-226, 2011.