Квадратичная задача о назначениях

Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов.

Задача моделирует следующую задачу из реальной жизни:

Есть множество n предприятий, которые могут быть расположены в n местах. Для каждой пары мест задано расстояние и для каждой пары производств задан вес или поток (т. e. количество материала (сырья или продукции), перевозимого между двумя производствами). Требуется расставить производства по местам (два производства нельзя размещать в одном месте) таким образом, что сумма расстояний, умноженных на соответствующие потоки, будет минимальной.

Интуитивно понятно, что предприятия с большим потоком следует размещать ближе друг к другу.

Формулировка задачи похожа на формулировку задачи о назначениях, различаются они целевой функцией — в квадратичной задаче она квадратична, что и отражает название.

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

Заданы два множества, P («производства») и L («точки размещения») равных размеров вместе с весовой функцией w : P × P → R и функцией расстояний d : L × L → R. Требуется найти биекцию f : P → L («назначение»), такую, что значение целевой функции:

${\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))}$

будет минимально.

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

${\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}$

В матричной форме:

${\displaystyle \min _{X\in \Pi _{n}}\operatorname {trace} (WXDX^{T})}$, где ${\displaystyle \Pi _{n}}$ — матрицы перестановок, W — матрица весов, а D — матрица расстояний.

Задача является NP-трудной, так что не существует алгоритма, решающего задачу за полиномиальное время, и даже маленькие задачи могут потребовать большого времени вычисления. Также было доказано, что задача не имеет аппроксимирующего алгоритма, работающего за полиномиальное время для любого (постоянного) множителя, если только не P = NP ^[1]. Задачу коммивояжёра можно рассматривать как специальный случай КЗН, если требовать, чтобы потоки связывали все производства в одном цикле с одним и тем же ненулевым значением потока. Многие другие стандартные задачи комбинаторной оптимизации могут быть записаны в этой форме.

Кроме изначальной формулировки размещения производства, КЗН является математической моделью задач размещения связанных электронных компонентов на печатных платах или интегральных схемах. Модель служит частью процесса размещения и разводки^[англ.] систем автоматизированного проектирования в электронной индустрии.

• Минимаксная квадратичная задача о назначениях^[англ.]

• Sartaj Sahni, Teofilo Gonzalez. . P-Complete Approximation Problems. — Journal of the ACM, 1976, 23 (3). — P. 555—565. — doi:10.1145/321958.321975..
• Michael R. Garey, David S. Johnson. . Computers and Intractability: A Guide to the Theory of NP-Completeness^[англ.]. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5. — P. 218.

• http://www.seas.upenn.edu/qaplib/ Архивная копия от 19 мая 2014 на Wayback Machine QAPLIB — A Quadratic Assignment Problem Library
• http://issuu.com/spconguy/docs/ant-algorithm-applied-to-the-quadratic-assignment- Архивная копия от 4 ноября 2016 на Wayback Machine — A QAP sample application
• Links to Quadratic Assignment Problem Solvers Архивная копия от 24 мая 2016 на Wayback Machine

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (3 ноября 2016) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (3 ноября 2016) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.