Сужение области поиска решения задачи Вебера на плоскости с прямоугольными запрещенными зонами

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

Статья представлена к публикации членом редколлегии: П. Ю. Чеботарев