РЕШЕНИЕ ЗАДАЧИ ВЕБЕРА НА ПЛОСКОСТИ С МИНИМАКСНЫМ КРИТЕРИЕМ И ЗАПРЕЩЕННЫМИ ЗОНАМИ

Jazyk: ruština
Rok vydání: 2014
Předmět:
Zdroj: Известия Иркутского государственного университета. Серия: Математика.
ISSN: 2541-8785
1997-7670
Popis: Задачи размещения объектов различного вида составляют широкий класс в исследовании операций. Многообразие различных постановок задач оптимального размещения определяется областью, в которой располагаются объекты, различными ограничениями и видами критериев. Важным подклассом задач размещения взаимосвязанных объектов является задача Вебера. Рассматриваются два критерия оптимальности: минимизация суммарной стоимости связей между объектами или максимальной связи. Исследованием минимаксной задачи Вебера с прямоугольной метрикой занимались J. G. Morris, R. L. Francis, T. Ichimori. В данной статье рассматривается задача оптимального размещения объектов на плоскости с расположенными на ней фиксированными объектами и прямоугольными запрещенными зонами, со сторонами параллельными осям координат. Размещаемые объекты связаны между собой и с фиксированными. Критерием является минимизация максимальной стоимости связи между всеми объектами. Размещение внутри запрещенных зон не допускается. Для измерения расстояний используется прямоугольная метрика. Приводятся свойства задачи, модель целочисленного линейного программирования с булевыми переменными. Доказано, что существует оптимальное размещение в прямоугольной оболочке, построенной с помощью решения задач для каждого из размещаемых объектов отдельно. Разработаны варианты алгоритма ветвей и границ с различными оценками целевой функции. Проведен вычислительный эксперимент с использованием предложенного алгоритма и решения задачи с применением модели целочисленного линейного программирования и пакета IBM ILOG CPLEX. По результатам эксперимента можно сделать вывод, что применение доказанного свойства является перспективным как при решении задачи комбинаторными методами, так и с применением аппарата целочисленной оптимизации.
Location problems of various facilities are a wide class of operations research. The variety of statements of location problems is depends on the area in which are to be placed facilities and various restrictions and types of criteria. Important subclass of location problems of the interconnected facilities is the Weber problem. Two criteria of optimality are considered: minimization of total cost of communications between facilities or minimization of the maximum communication cost. Minimax Weber problem with a rectangular metrics is researched by J. G. Morris, R. L. Francis and T. Ichimori. In this paper, the problem of optimum location of facilities on the plane with the fixed facilities located on it and the rectangular forbidden gaps, with the borders parallel to axes of coordinates is considered. The located facilities are connected among themselves and with fixed facilities. The criterion is minimization of the maximum cost of communications between all facilities. Location in forbidden gaps is not allowed. The rectangular metrics is used. Properties of the problem, model of integer linear programming with Boolean variables are described. It is proved that it is sufficient to consider a subset of admissible solutions to find the optimum. Three variants of branch and bounds algorithm with different lower bounds on the goal function are developed. Computational experiment on comparison of efficiency of one of these algorithms and the IBM ILOG CPLEX is presented. Usage of the obtained property is perspective both in combinatorial methods as well as in integer programming methods for solving the problem.
Databáze: OpenAIRE
Externí odkaz: