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

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

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

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

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

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

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

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

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

сведен к минимуму.

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

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

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

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

подлежит:

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

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

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

Асимптотика

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

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

и

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