journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

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

Ключевые слова RU

Литература RU
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.

Название EN

Авторы EN

Аннотация EN
<p>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.</p>

Ключевые слова EN

Литература EN
1. Zabudsky G.G. About Minimax and Minsum Location Problems on Plane with Forbidden Gaps (in Russian). Materials of 13th Baikal International Triannual School-Seminar "Methods of Optimization and Their Applications", Irkutsk, 2005,vol. 1, pp. 455-460. 2. Zabudskii G.G. Model Building and Location Problem Solving in a Plane with Forbidden Gaps. Automation and Remote Control, 2006, vol. 67, issue 12, pp. 1986-1990. 3. Zabudskii G.G., Amzin I.V. Search Region Contraction of the Weber Problem Solution on the Plane with Rectangular Forbidden Zones. Automation and Remote Control, 2012, vol. 73, issue 5, pp. 821–830. 4. Zabudsky G.G., Veremchuk N.S. Minimax Weber Problem on Plane with Forbidden Gaps (in Russian). Materials of International conference "Discrete Optimization and Operations Research", Novosibirsk, Institute of mathematics,2013, p. 123. 5. Zabudsky G.G., Veremchuk N.S. Solving Minimax Weber Problem on Plane with Forbidden Gaps (in Russian). Materials of 16th Baikal International Triannual School-Seminar "Methods of Optimization and Their Applications", Irkutsk, 2014,p. 54. 6. Preparata P., Shamos M. Computational Geometry: an Introduction. Springer-Verlag, 1985, 478 p. 7. Dearing H.V., Francis R.L. A Network Flow Solution to a Multifacility Minimax Location Problem Involving Rectilinear Distances. Transportation Science, 1974, vol. 8, p. 126-141. 8. Ichimori T. A Shortest Path Approach to a Multifacility Minimax Location Problem with Rectilinear Distances. Journal of the Operation Research Society of Japan, 1985, no 4, p. 269-284. 9. Klamroth K. Single-Facility Location Problems with Barriers. 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. OperationResearch Quarterly, 1973, vol. 24, рp. 419-435.