Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.
Задача моделирует следующую задачу из реальной жизни:
Интуитивно понятно, что предприятия с большим потоком следует размещать ближе друг к другу.
Формулировка задачи похожа на формулировку задачи о назначениях, различаются они целевой функцией — в квадратичной задаче она квадратична, что и отражает название.
Формальное определение квадратичной задачи о назначениях следующее:
Обычно веса и расстояния рассматриваются как квадратные вещественные матрицы, так что целевую функцию можно выписать следующим образом:
В матричной форме:
Задача является NP-трудной, так что не существует алгоритма, решающего задачу за полиномиальное время, и даже маленькие задачи могут потребовать большого времени вычисления. Также было доказано, что задача не имеет аппроксимирующего алгоритма, работающего за полиномиальное время для любого (постоянного) множителя, если только не P = NP [1]. Задачу коммивояжёра можно рассматривать как специальный случай КЗН, если требовать, чтобы потоки связывали все производства в одном цикле с одним и тем же ненулевым значением потока. Многие другие стандартные задачи комбинаторной оптимизации могут быть записаны в этой форме.
Кроме изначальной формулировки размещения производства, КЗН является математической моделью задач размещения связанных электронных компонентов на печатных платах или интегральных схемах. Модель служит частью процесса размещения и разводки[en] систем автоматизированного проектирования в электронной индустрии.
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .