Article · Русский
Квадрати́чная зада́ча о назначе́ниях (КЗН, англ. Quadratic assignment problem, QAP) — одна из фундаментальных задач комбинаторной оптимизации в области оптимизации или исследования операций, принадлежащая категории задач размещения объектов. Задача моделирует следующую задачу из реальной жизни: Есть множество n предприятий, которые могут быть расположены в n местах. Для каждой пары мест задано расстояние и для каждой пары производств задан вес или поток (т. e. количество материала (сырья или продукции), перевозимого между двумя производствами). Требуется расставить производства по местам (два производства нельзя размещать в одном месте) таким образом, что сумма расстояний, умноженных на соответствующие потоки, будет минимальной. Интуитивно понятно, что предприятия с большим потоком следует размещать ближе друг к другу. Формулировка задачи похожа на формулировку задачи о назначениях, различаются они целевой функцией — в квадратичной задаче она квадратична, что и отражает название.
Abstract from DBpedia / Wikipedia · CC BY-SA