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

1. Забудский Г. Г. О минимаксной и минисуммной задачах размещения на плоскости с запрещенными областями / Г. Г. Забудский // XIII Байкальская международная школа-семинар «Методы оптимизации и их приложения» : тр. школы-семинара. – Иркутск : ИСЭ СО РАН, 2005. – Т. 1. –С. 455–460.

2. Забудский Г. Г. Построение моделей и решение задач размещения на плоскости с запрещенными зонами / Г. Г. Забудский // Автоматика и телемеханика. – 2006. – № 12. – С. 136–141.

3. Забудский Г.Г. Сужение области поиска решения задачи Вебера на плоскости с прямоугольными зонами / Г. Г. Забудский, И. В. Амзин // Автоматика и телемеханика. – 2012. – № 5. – С. 71–83.

4. Забудский Г. Г. О минимаксной задаче Вебера на плоскости с запрещенными зонами / Г. Г. Забудский, Н. С. Веремчук // Междунар. конф. «Дискретная оптимизация и исследование операций» : материалы конф. – Новосибирск : Изд-во Ин-та математики, 2013. – С. 123.

5. Забудский Г. Г. Решение минимаксной задачи Вебера на плоскости с запрещенными зонами / Г. Г. Забудский, Н. С. Веремчук // XVI Байкальская международная школа-семинар «Методы оптимизации и их приложения» : тез. докл. –Иркутск : ИСЭМ СО РАН, 2014. – С. 54.

6. Препарата Ф. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. –М. : Мир, 1989. – 478 с.

7. Dearing H.V. A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances / H.V. Dearing, R.L. Francis // Transportation Science. – 1974. – Vol. 8. – P. 126–141.

8. Ichimori T. A Shortest Path Approach to a Multifacility Minimax Location Problem with Rectilinear Distances / T. Ichimori // Journal of the Operation Research Society of Japan. – 1985. – N 4. – P. 269–284.

9. Klamroth K. Single-Facility Location Problems with Barriers / K. Klamroth. – Springer Series in Operation Research, 2002. – 197 p.

10. Morris J. G. A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems Where Distances are Rectangular / J. G. Morris // Operation Research Quarterly. – 1973. – Vol. 24. – P. 419–435.