Квадратичная задача о назначении - Quadratic assignment problem

В квадратичная задача о назначениях (QAP) является одним из основных комбинаторная оптимизация проблемы в отрасли оптимизация или исследование операций в математика, из разряда расположение объектов проблемы, впервые представленные Купмансом и Бекманном^[1].

Проблема моделирует следующую реальную проблему:

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

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

Постановка задачи похожа на формулировку проблема назначения, за исключением того, что функция стоимости выражается через квадратичные неравенства, отсюда и название.

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

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

Учитывая два набора, п («объекты») и L («места») равного размера вместе с весовая функция ш : п × п → р и функция расстояния d : L × L → р. Найти биекция ж : п → L («присвоение») таким образом, чтобы функция стоимости:

{ displaystyle sum _ {a, b in P} вес (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 _ {п}}$ это набор ${ Displaystyle п раз п}$ матрицы перестановок, ${ displaystyle W}$ матрица весов и ${ displaystyle D}$ матрица расстояний.

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

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

Приложения

В дополнение к исходной формулировке местоположения завода, QAP представляет собой математическую модель для задачи размещения взаимосвязанных электронные компоненты на печатная плата или на микрочип, который является частью место и маршрут этап системы автоматизированного проектирования в электронной промышленности.

Смотрите также

Квадратичная проблема назначения узких мест

использованная литература

Заметки

^ Koopmans TC, Beckmann M (1957). Задачи назначения и место ведения хозяйственной деятельности. Econometrica 25 (1): 53-76.
^ Сахни, Сартадж; Гонсалес, Теофило (июль 1976 г.). «Проблемы P-полной аппроксимации». Журнал ACM. 23 (3): 555–565. Дои:10.1145/321958.321975. HDL:10338.dmlcz / 103883.

Источники

Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. W.H. Фримен. ISBN 0-7167-1045-5. A2.5: ND43, стр.218.

внешние ссылки

http://anjos.mgi.polymtl.ca/qaplib/ QAPLIB - библиотека задач квадратичного присвоения
http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Средство решения проблем с квадратичным назначением на основе Java
https://CRAN.R-project.org/package=qap - Пакет R qap: эвристика для задачи квадратичного присваивания

[1] Koopmans TC, Beckmann M (1957). Задачи назначения и место ведения хозяйственной деятельности. Econometrica 25 (1): 53-76.

[2] Сахни, Сартадж; Гонсалес, Теофило (июль 1976 г.). «Проблемы P-полной аппроксимации». Журнал ACM. 23 (3): 555–565. Дои:10.1145/321958.321975. HDL:10338.dmlcz / 103883.

[1]

[2]