Задача квадратичного назначения ( ПКА ) является одним из основных комбинаторных оптимизационных задач в отрасли оптимизации или операциях исследования в области математики , из категории из Дислокация проблем первого введенных Купманс и Бекманом. [1]
Проблема моделирует следующую реальную проблему:
- Есть набор из n объектов и набор из n мест. Для каждой пары местоположений указывается расстояние, и для каждой пары помещений указывается вес или поток (например, количество припасов, перемещаемых между двумя объектами). Проблема состоит в том, чтобы назначить все объекты в разные места с целью минимизировать сумму расстояний, умноженных на соответствующие потоки.
Интуитивно функция стоимости побуждает предприятия с высокими потоками между собой размещать близко друг к другу.
Постановка задачи похожа на постановку задачи о назначении , за исключением того, что функция стоимости выражается в терминах квадратичных неравенств, отсюда и название.
Формальное математическое определение [ править ]
Формальное определение квадратичной задачи о назначениях выглядит следующим образом:
- Указанные два набора, Р ( "объекты") и L ( "место"), одинакового размера, вместе с весовой функцией ш : P × P → R и функцией расстояния D : L × L → R . Найдите биекцию f : P → L («присваивание») такую, что функция стоимости:
- сводится к минимуму.
Обычно функции веса и расстояния рассматриваются как квадратные матрицы с действительными значениями , поэтому функция стоимости записывается как:
В матричной записи:
где - набор матриц перестановок, - матрица весов и - матрица расстояний.
Вычислительная сложность [ править ]
Проблема является NP-сложной , поэтому не существует известного алгоритма для решения этой проблемы за полиномиальное время, и даже в небольших случаях может потребоваться длительное время вычислений. Также было доказано, что в задаче нет алгоритма аппроксимации, работающего за полиномиальное время для любого (постоянного) фактора, если только P = NP. [2] задача коммивояжера может рассматриваться как частный случай QAP , если предположить , что потоки соединить все объекты только вдоль одного кольца, все потоки имеют одинаковое ненулевое значение (константа). В таком виде можно записать многие другие задачи стандартных задач комбинаторной оптимизации .
Приложения [ править ]
В дополнение к исходной формулировке местоположения предприятия, QAP представляет собой математическую модель для задачи размещения взаимосвязанных электронных компонентов на печатной плате или на микрочипе , которая является частью этапа и этапа автоматизированного проектирования в электронной промышленности. .
См. Также [ править ]
Ссылки [ править ]
- Примечания
- ^ Купманс ТС, Бекман М (1957). Задачи назначения и место ведения хозяйственной деятельности. Эконометрика 25 (1): 53-76.
- ^ Сахни, Сартадж; Гонсалес, Теофило (июль 1976 г.). «Проблемы P-полной аппроксимации». Журнал ACM . 23 (3): 555–565. DOI : 10.1145 / 321958.321975 . hdl : 10338.dmlcz / 103883 .
- Источники
- Майкл Р. Гарей и Дэвид С. Джонсон (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . WH Freeman. 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: эвристика для задачи квадратичного присваивания
