Квадратичная проблема назначения узких мест - Quadratic bottleneck assignment problem
В математике квадратичная задача о назначении узких мест (QBAP) является одним из фундаментальных комбинаторная оптимизация проблемы в отрасли оптимизация или же исследование операций, из разряда расположение объектов проблемы.[1]
Это связано с квадратичная задача о назначениях так же, как линейная задача о назначении узких мест относится к линейная задача о назначении, "сумма" заменяется на "макс" в целевая функция.
Проблема моделирует следующую реальную проблему:
- Есть набор п помещения и набор п локации. Для каждой пары местоположений расстояние задается и для каждой пары объектов a масса или же поток указывается (например, количество припасов, перемещаемых между двумя объектами). Проблема состоит в том, чтобы распределить все объекты по разным местам с целью минимизировать максимальное расстояние, умноженное на соответствующие потоки.
Вычислительная сложность
Проблема в NP-жесткий, поскольку его можно использовать для формулирования Гамильтонов цикл проблема с использованием потоков в шаблоне цикла и расстояний, коротких для ребер графа и длинных для не ребер.[2]
Особые случаи
Рекомендации
- ^ Проблемы с назначением, к Райнер Буркард, Мауро Дель'Амико, Сильвано Мартелло, 2009
- ^ Burkard, R.E .; Финке, У. (1982), "О случайных квадратичных задачах назначения узких мест", Математическое программирование, 23 (2): 227–232, Дои:10.1007 / BF01583791, МИСТЕР 0657082.