Поиск решения с заданной точностью максиминной задачи размещения на плоскости

Рассматривается задача оптимального размещения в ограниченной области на плоскости с фиксированными в ней объектами. Заданы минимально допустимые расстояния между размещаемыми и фиксированными и размещаемых объектов между собой. Критерий – максимум минимального взвешенного расстояния от размещаемых объектов до фиксированных. Предложен квазиполиномиальный комбинаторный алгоритм решения задачи с заданной точностью. Представлены результаты вычислительного эксперимента с использованием модели целочисленного программирования и пакета IBM ILOG CPLEX.

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