Abstract: В докладе приведены модели и методы решения задачи оптимального размещения взаимосвязанных объектов на плоскости с учетом областей (зон), в которых не допускается размещение. В качестве критерия оптимальности выбирается минимизация суммарной стоимости связей между объектами. Классическая задача без ограничений − это задача Вебера. Наличие прямоугольных зон приводят к тому, что допустимая область становится несвязной и невыпуклой, что приводит к невозможности применения алгоритмов для классической формулировки. Найдены свойства задачи, например сужение исходной области, в которой достаточно осуществлять поиск оптимального решения. Предложен способ построения модели целочисленного программирования (ЦП) с помощью аппарата вычислительной геометрии. Разработаны комбинаторный алгоритм ветвей и границ и эвристический. Проведены численные эксперименты по сравнению эффективности разработанных алгоритмов.

Cite: Забудский Г.Г.
Задача Вебера на плоскости в прямоугольной метрике с запрещенными зонами
XVI Международная молодежная научно-практическая конференция с элементами научной школы «ПРИКЛАДНАЯ МАТЕМАТИКА И ФУНДАМЕНТАЛЬНАЯ ИНФОРМАТИКА» 18-22 мая 2026