Задача о квадратичном назначении узких мест
В математике квадратичная задача о назначении узких мест ( QBAP ) является одной из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций , из категории задач размещения объектов . [1]
Она связана с квадратичной задачей назначения так же, как линейная задача назначения узкого места связана с линейной задачей назначения , «сумма» заменяется на «макс» в целевой функции .
Задача моделирует следующую реальную проблему:
- Имеется набор из n объектов и набор из n локаций. Для каждой пары объектов расстояние указывается , а для каждой пары объектов указывается вес или поток (например, количество материалов, транспортируемых между двумя объектами). Проблема состоит в том, чтобы распределить все объекты по разным местам с целью минимизировать максимальное расстояние, умноженное на соответствующие потоки.
Вычислительная сложность
[ редактировать ]Проблема является NP-сложной , так как ее можно использовать для формулировки гамильтоновой проблемы цикла, используя потоки в образце цикла и расстояния, короткие для ребер графа и длинные для неребер. [2]
Особые случаи
[ редактировать ]Ссылки
[ редактировать ]- ^ Задачи с заданиями , Райнер Буркард , Мауро Дель'Амико, Сильвано Мартелло, 2009 г.
- ^ Буркард, RE; Финке, У. (1982), «О случайных квадратичных задачах назначения узких мест», Mathematical Programming , 23 (2): 227–232, doi : 10.1007/BF01583791 , MR 0657082 .