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

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

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

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

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

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

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

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

${ Displaystyle макс _ {а в А} С (а, е (а))}$

сводится к минимуму.

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

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

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

${ Displaystyle мин , макс _ {я, 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 х_ {ij} в {0,1 } (я, j = 1,2, точки, п)}$

Асимптотика

Позволять ${ 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).}$

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