Решение задачи Вебера на плоскости с минимаксным критерием и запрещенными зонами

Задачи размещения объектов различного вида составляют широкий класс в исследовании операций. Многообразие различных постановок задач оптимального размещения определяется областью, в которой располагаются объекты, различными ограничениями и видами критериев. Важным подклассом задач размещения взаимосвязанных объектов является задача Вебера. Рассматриваются два критерия оптимальности: минимизация суммарной стоимости связей между объектами или максимальной связи. Исследованием минимаксной задачи Вебера с прямоугольной метрикой занимались J. G. Morris, R. L. Francis, T. Ichimori. В данной статье рассматривается задача оптимального размещения объектов на плоскости с расположенными на ней фиксированными объектами и прямоугольными запрещенными зонами, со сторонами параллельными осям координат. Размещаемые объекты связаны между собой и с фиксированными. Критерием является минимизация максимальной стоимости связи между всеми объектами. Размещение внутри запрещенных зон не допускается. Для измерения расстояний используется прямоугольная метрика. Приводятся свойства задачи, модель целочисленного линейного программирования с булевыми переменными. Доказано, что существует оптимальное размещение в прямоугольной оболочке, построенной с помощью решения задач для каждого из размещаемых объектов отдельно. Разработаны варианты алгоритма ветвей и границ с различными оценками целевой функции. Проведен вычислительный эксперимент с использованием предложенного алгоритма и решения задачи с применением модели целочисленного линейного программирования и пакета IBM ILOG CPLEX. По результатам эксперимента можно сделать вывод, что применение доказанного свойства является перспективным как при решении задачи комбинаторными методами, так и с применением аппарата целочисленной оптимизации.