Оптимизация размещения Р-центров в многосвязной области при заданных ограничениях

Размещено на http://www.allbest.ru/

2

Национальный университет гражданской защиты Украины (г. Харков, Украина)

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ Р-ЦЕНТРОВ В МНОГОСВЯЗНОЙ ОБЛАСТИ ПРИ ЗАДАННЫХ ОГРАНИЧЕНИЯХ

В.В. Комяк

В.М.Комяк

Р.В.Романов

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

Ключевые слова: связная сеть, многосвязная область, геометрическое и компьютерное моделирование, трудоемкость

геометрическое проектирование пожарный гидрант

Постановка проблемы

Одним из важных классов задач, направленных на снижение расходов сырья, материалов и других видов ресурсов, является класс задач геометрического проектирования [1]. К этому классу относятся задачи оптимального размещения геометрических объектов, задачи покрытия, разбиения, проведения оптимальних связывающих сетей.

Возможность сведения большого числа важных народнохозяйственных задач к классу задач геометрического проектирования вызвала необходимость всестороннего изучения задач этого класса и разработки эффективных методов их решения.

Анализ последних достижений и публикаций.

В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования (или средств обслуживания) на сетях или графах. Задачи размещения связаны с поиском наилучшего расположения таких систем обслуживания, как торговые центры, пожарные части, фабрики, аэропорты, склады и т.д. При этом в ряде задач о размещении пунктов обслуживания требуется так расположить пункт обслуживания на графе, чтобы сумма кратчайших расстояний от этого пункта до вершин графа была минимально возможной. Оптимальное в указанном смысле место расположения пункта называется медианой графа. Исходя из природы целевой функции, такие задачи называют минисуммными задачами размещения [2].

В этом классе задач рассматривается и минимаксная задача размещения, возникающая при выборе места для таких пунктов обслуживания, как пожарная часть, милицейский участок или больница. Функцией цели является минимальное среди максимальных расстояний от пункта обслуживания до возможного места вызова. Полученное при решении этой задачи место размещения пункта обслуживания называется р-центром графа [2]. Очень часто возникает задача о наилучшем размещении нескольких пунктов обслуживания. Эту задачу можно сформулировать так.

Найти наименьшее число, например, пожарных частей и такое их размещение, чтобы расстояние от возможного очага пожара до ближайшей к нему пожарной части не превышало наперед заданной величины. Если же число пожарных частей известно, то требуется разместить их так, чтобы было минимальным расстояние от возможного очага пожара до ближайшей к нему части.

В рассматриваемых задачах оптимизация осуществляется на существующем графе, который, как пример, может описывать сеть дорог. Если представить существующую сеть дорог в виде графа G и положить, что пожарные части размещаются в вершинах этого графа, то задача будет состоять в нахождении наименьшего числа m вершин (р-центров, р = 1, 2, 3, ...,m), при котором расстояние от выбранного центра до максимально удаленной допустимой точки на графе не превысит заданного значения. Полученное значение числа р будет определять количество пожарных частей, а координаты р-центров -- их оптимальные координаты размещения. В работах [2 -- 4] задачи решаются на существующем графе, который описывает сеть дорог. В работах [3 -- 4] рассматривается ряд дополнительных ограничений из предметной области пожарная безопасность. К классу задач геометрического проектирования относятся задачи построения оптимальных путей и связывающих сетей в многосвязных областях, которые представлены в работах [5,6].

Формулирование целей статьи (постановка задачи). В данной статье рассматривается следующая задача. Необходимо в многосвязной области построить сеть с минимальным количеством вершин, размещенных на некоторой ломаной, с ограничением на длину ее ребер. В задаче могут присутствовать ряд дополнительных ограничений.

Основная часть

Пусть задана некоторая область в R². В области расположены многоугольники S_i (i = 1,2, …,n) без взаимного пересечения и задана некоторая ломаная H₀, H₁, … . Рассмотрим область без многоугольников , которая является многосвязной.

Рассмотрим объект . Проведем сеть L в многосвязной области следующим образом. Пусть вершина сети (р-центр) принадлежит ломаной H₀, H₁, … . Положение р-центра выбирается на ломаной так, чтобы сеть, выходящая из р-центра, охватывала объект S_i при условии ограничения на длину образованной петли. На рис.1 р-центр совпадает с точкой .

Обозначим через длину построенной сети (петли ).

Рис. 1. Охват петлей объекта S_i

Тогда сформулированное выше ограничение запишется следующим образом

, (1)

где - максимально допустимая длина петли для объекта S_i.

Возникает следующая задача. Необходимо найти минимальное количество точек ( р-центров) (p₁, p₂,…, p_m) и разместить их на ломаной H₀, H₁, …так, чтобы сеть, проведенная в многосвязной области и огибающая объекты S_i (i = 1, 2,…, n), удовлетворяла следующим условиям: длина кратчайшего пути по сети от любой граничной точки многоугольника S_i (i = 1, 2,…, n) до ближайшего к ней р-центра не превышала соответствующего максимально-допустимого расстояния.

В работе [7] построена математическая модель задачи, а в работе [8] предложен метод решения, состоящий в построении области допустимых решений, описывающей ограничения задачи, и переборе точек из этой области с целью нахождения наилучшей согласно функции цели. Одним из этапов построения области допустимых решений является построение области допустимых размещений р-центра, удовлетворяющих условию (1) для единичного объекта S_i .

Механическим способом построения области допустимых размещений р-центра является следующий [8] . Берём нерастяжимую нить длиной и охватываем нитью объект S_i ; концы нити закрепляем на карандаше; натягиваем нить и вычерчиваем вокруг объекта линию, которая является границей области допустимого размещения р-центра для данного объекта. При этом длина линии от р-центра до любой внешней точки объекта S_i не будет превышать длину . Пример построения области допустимых размещений D (ОДР) для объекта S_i показан на рис. 2 (ОДР - заштрихована).

Рис. 2. Область допустимого размещения р-центра.

Пересечение области допустимых размещений D с ломаной - это область допустимых размещений р-центра на H₀, H₁, …. , обозначим ее .

В зависимости от взаимного положения ломаной H₀, H₁, … и объекта S_i область может иметь бесконечное множество точек, одну точку или быть пустой.

Свойство 1. Если , то ОДР - некоторая ломая (например, отрезок (рис. 3)), т.е. имеет бесконечное множество точек.

Свойство 2. Если , то область допустимых решений состоять из одной точки (рис. 4).

Рис.3. Область допустимых решений - отрезок Рис.4 Область допустимых решений - точка

Свойство 3. Если , то область допустимых решений - пустое множество.

Свойство 4. Если , но , где - минимальное расстояние от р-центра до объекта S_i (рис.5), то тогда увеличение числа р-центров приводит либо к полному охвату петлей объекта S_i (рис.6.а), либо частичному охвату (рис. 6.б).

Рис. 5. Полный охват петлей объектов

В первом случае количество р-центров определяется минимальным количеством объектов, на которые разбивается объект S_i , для каждого из которых выполняется (1) [8].

Во втором случае разработан подход [9], основанный на построении неоднородной, с точки зрения степени достижения граничной точки объекта S_i, области допустимых решений.

Рис.6.а. Полный охват петлей объекта при двух р-центрахРис.6.б. Частичный охват петлей объекта при двух р-центрах

Свойство 5. Если и , то нет ни одной точки на ломаной H₀, H₁, …. , для которой бы выполнялось условие (1).

Для выполнения условия (1) необходимо добавить часть ломаной, например (рис.7), возле объекта , либо увеличить максимально допустимое расстояние, чтобы выполнялись условия свойств 1 или свойства 2.

Рис.7. Увеличение ломаной отрезком

Для решения задач размещения р-центров на заданной ломаной с ограниченной длиной огибающих объекты ребер разработано ряд алгоритмов [10]. В зависимости от исходных данных, основываясь на изложенных в статье свойствах, методы геометрического моделирования позволяют учесть специфику задачи и выбирать характерный алгоритм решения, повышая тем самым эффективность (трудоемкость) метода.

Рассматриваемая задача размещения р-центров на заданной ломаной с ограниченной длиной огибающих объекты ребер находит применение при размещении пожарных гидрантов на сети водопровода [7 -- 9]. При решении прикладной задачи рассмотрены и другие ограничения из предметной области пожарной безопасности: должны учитываться плотность застройки районов и области запрета, т.е. уменьшение области обслуживания пожарных гидрантов в результате обхода рукавными линиями препятствий, таких как соседние здания, ограждения и т.п. с учетом минимальных нормированных расстояний; должны учитываться конструктивные особенности зданий (степень огнестойкости, этажность), так как от этажности здания зависит максимальное значение длины прокладки рукавных линий, а от степени огнестойкости здания - количество гидрантов, которое необходимо установить для противопожарной защиты объекта; размещение пожарных гидрантов должно обеспечивать подъезд пожарных автонасосов, т.е. размещение в труднодоступных, не имеющих твердого покрытия местах исключается.

Так создан алгоритм, который учитывает плотность застройки и области запрета в районе при построении области допустимого размещения пожарных гидрантов [10].

Разработан метод моделирования размещения пожарных гидрантов в районах городов с учетом ограничений задачи [11 -- 13], при этом:

-- предложен подход к построению парето-допустимого множества положений пожарных гидрантов на магистральной трассе водопровода, учитывающий, с одной стороны, нормированную длину рукавных линий, а с другой, покрытие зданий района города, для которого проектируется противопожарное водоснабжение;

-- предложен метод решения задачи рационального размещения пожарных гидрантов в районах городов, основанный на построении неоднородной области допустимых размещений пожарных гидрантов с точки зрения степени покрытия зданий.

По разработанному алгоритмическому обеспечению метода рационального размещения пожарных гидрантов в районах городов создан комплекс программ [14], который позволяет определить минимально допустимое количество пожарных гидрантов и места их рационального размещения. Программное обеспечение позволяет автоматизировать процесс получения трудоемких вариантов расчета противопожарной защиты районов городов.

На рис.8 представлен пример решения рассматриваемой задачи.

Рис. 8. Размещение пожарных гидрантов (точки на водопроводной сети) в Орджоникидзевском районе г. Харькова

Выводы и перспективы дальнейших исследований

В работе представлены результаты оптимизации моделирования размещения р-центров при заданных ограничениях, которые находят применение при решении задачи определения минимально допустимого количества пожарных гидрантов и мест их размещения в районах городов, которые максимально покрывают все сооружения района с точки зрения досягаемости рукавными линиями.

Дальнейшие исследования будут посвящены нахождению такой ломаной, на которой размещаются р-центры, чтобы выполнялось полное покрытие объектов области с точки зрения их досягаемости по огибающим ломанным.

ЛІТЕРАТУРА

1.Стоян Ю. Г. Основная задача геометрического проектирования. - Харьков: ИПМаш АН УССР, 1983. - 36 с. - (Препринт / ИПМаш АН Украины, №181).

2.Кристофидес Н. Теория графов Алгоритмический подход: Пер. с англ. - М.: Мир, 1978. - 432 с.

3.Коссе А.Г.. Метод раціонального розміщення пожежних депо при проектуванні та оновленні районів міста: автореф. дис. на здобуття наук. ступеня канд. техн. наук. : 21.06.02 «Пожежна безпека» / А.Г. Коссе. - Х., 2002. - 19 с.

4.Кязімов К.Т. Геометричне моделювання розміщення пожежних підрозділів в сільській місцевості на прикладі Азербайджану: автореф. дис. на здобуття наук. ступеня канд. техн. наук: спец. 05.01.01 «Прикладна геометрія, інженерна графіка» / К.Т.Кязімов. - К., 2010. - 24 с.

5.Смеляков С.В. Моделирование и оптимизация коммуникационных соединений в задачах геометрического проектирования: автореф. дис. на здобуття наук. ступеня докт. физ.-мат. наук: спец. 01.05.02 «Математичне моделювання та обчислювальны методи» / С.В.Смеляков. - Х., 1993. - 30 с.

6.Элементы теории геометрического проектирования / [Яковлев С.В., Гиль Н.И., Комяк В.М. и др.]; под ред. В.Л. Рвачева -- К.: Наукова думка, 1995. -- 241 с.

7.Комяк В.М. Математическая модель размещения пожарных гидрантов в районах городов / Комяк В.М., Романов Р.В. Проблемы пожарной безопасости: Сб.научн.тр. -- Вып. 27. -- Харьков: НУГЗУ, 2010. -- С.97 -- 103.

8.Комяк В.М. Алгоритм побудови області припустимого розміщення пожежних гідрантів для одиничних споруд / Комяк В.М., Романов Р.В.Прикладна геометрія та інженерна графіка. Праці / Таврійська державна агротехнічна академія - Вип.4, т.32. - Мелітополь: ТДАТА, 2006. -- С. 70 -- 73.

9.Романов Р.В. Метод решения оптимизационной задачи размещения пожарных гидрантов в районах городов / Романов Р.В. Проблемы пожарной безопасости: Сб.научн.тр. -- Вып26. -- Харьков: НУГЗУ, 2009. -- С.104 -- 112.

10.Р.В. Романов. Алгоритм урахування щільності забудови району при проектуванні розміщень пожежних гідрантів/ Геометричне та комп'ютерне моделювання: збірник наукових праць; Харк. держ. університет харчування та торгівлі. - Харків, 2006. - Вип. 14. - С. 206 -- 213.

11.Комяк В.М., Романов Р.В., Панкратов А.В. Модель и метод определения допустимых параметров размещения пожарных гидрантов в районе города/ Геометрическое и компьютерное моделирование: сборник научных трудов. Харк. гос. университет питания и торговли. - Вып. 25. - Харьков, 2009. - С. 27 - 32.

12.Панкратов О.В., Комяк В.М., Романов Р.В. Метод оптимізації розміщення пожежних гідрантів в районах міст/ Прикладна геометрія та інженерна графіка. Праці / Таврійський державний агротехнічний університет - Вип.4, т. 44. - Мелітополь: ТДАТУ, 2009. -- С. 142 -- 148.

13.Романов Р.В. Метод решения оптимизационной задачи размещения пожарных гидрантов в районах городов / Проблемы пожарной безопасности: сборник научных трудов. Вып. 26. - Харьков: УГЗУ, 2009. - С. 104 -- 112.

14.Панкратов А.В. Комп'ютерна програма “FirePlug” / О.В. Панкратов, Р.В. Романов, В.М. Комяк // Свідоцтво про реєстрацію авторського права на твір, № 34290, Україна. Міністерство освіти і науки. Державний департамент інтелектуальної власності. - 29.07.2010.

Размещено на Allbest.ru