«Спецпроект: анализ научных исследований» 2014 год

Шарипов Р. Ш., Файзуллина А. Г.

Набережночелнинский институт К( П)ФУ, Российская Федерация

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ТРЕХТОЧЕЧНОЙ ЗАДАЧИ ШТЕЙНЕРА В ПОСТРОЕНИИ СЕТЕЙ КРАТЧАЙШИХ ДОРОГ РЕАЛЬНОГО ОБЪЕКТА СТРОИТЕЛЬСТВА

 

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

Данная задача впервые была рассмотрена Якобом Штейнером, он занимался поиском одной точки, сумма расстояний от которой до всех точек заданного множества была бы минимальной.

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

Существует два варианта решения данной задачи.

1)    Если каждый из углов между отрезками, соединяющий точку Штейнера с каждой из заданных точек – вершин треугольника, составляет 120 градусов.

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

2) Угол, образованный отрезками, соединяющими эту точку с другими заданными, равен или больше 120 градусов.

Если же один из углов треугольника с вершинами в этих точках ³ 120 ° , то сеть состоит из 2 ребер – сторон этого угла. Если все углы < 120 ° , то сеть Штейнера состоит из 3 ребер, соединяющих дополнительную точку Штейнера с тремя вершинами.

Рассмотрим данную задачу на примере практической деятельности предприятия – построения дорожной сети на реальном участке автомобильной дороги, обслуживаемой ЗАО «Трест Камдорстрой ». Перед нами стоит задача соединить три населенных пункта одной минимальной сетью дорог: с. Покровское, с . Старая Мурзиха , с. Новая Мурзиха . Решим поставленную задачу с помощью приложения, созданного в программной среде Delphi .

  Указанные населенные пункты имеют свои координаты (широта, долгота):

–        c . Покровское – 55.709706, 51.718111;

–        с . Старая Мурзиха – 55.738515, 51.647015;

–        с. Новая Мурзиха – 55.743154, 51.665554.

Введем данные значения в нашу программу и рассчитаем точку Штейнера:

 

Рис. 1. Построение точки Штейнера

 

После нажатия на форме кнопки «Рассчитать точку Штейнера», приложение осуществляет расчет и выводит координаты точки Штейнера:

X = 55,743154;

Y = 51,665554.

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

Приложение также позволяет определить длину пути, от полученной нами точки Штейнера до населенных пунктов:

–        от с . Покровское до точки Штейнера – 6,2 км ;

–        от с . Старая Мурзиха до точки Штейнера – 1,9 км ;

–        от с. Новая Мурзиха до точки Штейнера – 0 км (т. к. точка совпала).

Общая длина маршрута от c . Покровское до с . Старая Мурзиха составляет 8,1 км .

Теперь рассмотрим стоимость постройки полученного нового участка дороги. На вкладке «Стоимость постройки» мы можем рассчитать стоимость дорожного строительства. Для этого необходимо указать цену за 1 км дороги.

В данном случае мы выбрали среднюю цену, указанную в контрактах ЗАО «Трест Камдорстрой » и других дорожно-строительных организаций для этого вида работ [2]. Стоимость равняется 55 091 401,2 рублей.

В итоге получаем:

–        от с . Покровское до точки Штейнера – 341 566 687,44 рублей;

–        от с . Старая Мурзиха до точки Штейнера – 104 673 662,28 рублей;

–        от с. Новая Мурзиха до точки Штейнера – 0 рублей (т. к. точка совпала).

Всего необходимо затратить 446 240 349,72 рублей.

Таким образом, мы получили точку Штейнера для указанных вершин: с. Покровское (55,709706; 51,718111), с . Старая Мурзиха (55,738515; 51,647015). Точка Штейнера совпадает с координатами с . Новая Мурзиха (55,743154; 51,665554). Полученная минимальная длина маршрута – 8,1 км . Предполагаемая стоимость строительства дороги на указанном участке при средней цене 55 091 401,2 рублей за км – 446 240 349,72 рублей.

Данная стоимость и длина пути являются наименьшими, среди других предложенных вариантов реконструкции проектным управлением предприятия.

 

Рис. 2. Предлагаемая новая дорога

 

Итак, мы построили кратчайшую сеть дорог для соединения трех населенных пунктов, используя трехточечную задачу Штейнера. Приближенное расположение полученной нами дороги изображено на рис. 2. В точке P отображено место выезда из автодороги М-7 «Волга» к указанным населенным пунктам.

 

Список использованных источников:

1.              Протасов В. Ю. Максимумы и минимумы в геометрии // В. Ю. Протасов. – М.: МЦНМО, 2005. – 54 с.

2.              Реестр закупок и заказов. Портал закупок [Электронный ресурс] // Официальный сайт РФ в сети Интернет для размещения информации о размещении заказов на поставки товаров, выполнение работ, оказание услуг. – Режим доступа: http://www.zakupki.gov.ru/epz/order