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

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

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

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

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

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

Формальное математическое определение

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

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

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

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

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

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

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

\min _{X\in \Pi _{n}}\operatorname {trace} (WXDX^{T})

, где

\Pi _{n}

— матрицы перестановок, W — матрица весов, а D — матрица расстояний.

Вычислительная сложность

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

Приложения

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

См. также

Минимаксная квадратичная задача о назначениях

Примечания

Sahni & Gonzalez, 1976.

Литература

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/ QAPLIB — A Quadratic Assignment Problem Library
http://issuu.com/spconguy/docs/ant-algorithm-applied-to-the-quadratic-assignment- — A QAP sample application
Links to Quadratic Assignment Problem Solvers

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_aff9c0dbc13146e1-1] Sahni & Gonzalez, 1976.