ПОИСК РЕШЕНИЯ С ЗАДАННОЙ ТОЧНОСТЬЮ МАКСИМИННОЙ ЗАДАЧИ РАЗМЕЩЕНИЯ НА ПЛОСКОСТИ

摘要

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