Алгоритм "веерной" оптимизации параметров разветвленных трубопроводных сетей

УДК 519.6

АЛГОРИТМ «ВЕЕРНОЙ» ОПТИМИЗАЦИИ ПАРАМЕТРОВ РАЗВЕТВЛЕННЫХ ТРУБОПРОВОДНЫХ СЕТЕЙ

© 2005 г. Б.Р. Байрактаров, В. Ч. Кудаев

The aim of the optimization of the parameters of ranched out pipelined systems with one source in root vertex is regarded in the article. An effective algorithm of solving the problem is offered. It is based on the method of dynamic programming.

Трубопроводные сети как сложная система есть совокупность взаимосвязанных и

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

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

Сформулированная задача ранее

рассматривалась в [1, 2]. Была построена математическая модель, разработаны метод и алгоритм ее решения. Задача решалась в рамках создания САПР закрытых оросительных сетей. В данной статье предлагается новый эффективный метод и алгоритм решения этой задачи.

Постановка задачи

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

Пусть , д/, у/, И/ - длина, м, расход, л/с, скорость течения воды на /-м участке, м/с, и потери напора, м, на единице длины трубопровода, где / = 2, п ; Q - общий расход воды, подаваемой в

сеть;

Z ,., H f, H -

' г 1 поверхности земли, напоры в узлах сети,

станции, где 1 = 1, п ;

v„

и vn

v  < v < v

min — i — max \ /

и на напоры, которые в узлах сети должны быть не менее, чем заданные «свободные» напоры

Hj = H hill + Zi - Z. > Hс;,

,еТг

где /, 1 = 1,2,...,п; Н - напор на насосной станции; множество номеров участков, входящих в

Тг -

траекторию от насосной станции до вершины с номером 1 (например, на сети рис. 1 Т19 = {18,16,12,2}).

Рис. 1

Скорость течения воды на участке выражается

4q

известной из гидравлики формулой v =

nd2

где d -

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

геодезическая отметка

требуемые минимальные искомый напор на насосной

h =

0,00148 q2(1 + ^I867)^d-5,3 при v < 1,2 v

0,001735 q2d-5,3 при v > 1,2,

допустимый

диапазон скоростей течения воды на участках сети. Кроме того, задается упорядоченное по возрастанию множество Б = {йп} стандартных диаметров труб (сортамент) и соответствующее ему множество С = {ст} стоимостей одного погонного метра (очевидно, также упорядоченное).

Задача решается при ограничениях на скорость течения воды

а для асбестоцементных и полиэтиленовых труб используются формулы

h = 0,00091 q 2(1 + ^о,19 d519 и

h = 0,00105 q1,774 d

v

- 4,774

соответственно (здесь д, ё и у - величины расхода, внутреннего диаметра и скорости потока соответственно).

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

труб сети и стоимости энергетических затрат, а именно:

W(H,h) = «2C(И,)l, + ßQH .

i=2

где а и в - нормативные коэффициенты; С (hi) -выпуклая, кусочно-линейная функция [2], выражающая стоимость единицы длины участка; Н - искомый напор на насосной станции. Здесь, очевидно, первое слагаемое - это стоимость труб сети, второе выражает энергетические затраты на сеть. Ясно, что уменьшение стоимости труб сети приводит к увеличению энергетических затрат (приходится увеличивать напор в сети, а следовательно, увеличивать мощность насосов).

Построение функции С

При заданном значении расхода д, на / - м участке из сортамента Б выбирается ровно к, различных упорядоченных диаметров,

удовлетворяющих условию (1). Для них вычисляются потери напора кп,к2,...,кщ.

Рассмотрим на плоскости (С, к,) (рис.2) дискретное множество точек, заданных координатами (ст,кт), причем таких, что

те [1, к ] (т - целое).

V! ьа V К

Рис. 2

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

к,1 < к, < кк

и очевидно, соответствующее значение С (к,) будет удовлетворять неравенству Сг < С (к,) < С1, то к, и соответствующее ему значение функции можно представить в виде линейной комбинации вершин

этого

многоугольника

И = z^ht

t=i

С(И,)=z^C.

Имеет место следующее

Утверждение. При любом значении к, удовлетворяющем неравенству (4), на , - м участке можно оптимально уложить не более чем два стандартных диаметра.

Действительно, ввиду линейности функционал С(к, ) достигает своего минимального значения только на границе области, которая является выпуклым многоугольником с вершинами в точках (ст,кт), либо на его вершинах. Таким образом, для I - го участка найдутся два таких номера п и е [1, к, ], что

< < ^ , к = + (1 - Л>к , где Л' е [0,1] .

Тогда, очевидно, имеет место равенство

С (к) = Л*с7+ (1 -Л*)с^.

Таким образом, Ж(Н, к) является кусочно-линейной функцией. Математическая модель задачи заключается в минимизации функции (3) при ограничениях (1) и (2).

Алгоритм «веерной» оптимизации

Предположим, что напор Н в корневой вершине сети задан. Тогда задача сводится к нахождению минимума функционала

Ж

1=2

при ограничениях (1) и (2).

Как показано выше, задача имеет размерность 2(п-1), где п- количество узлов сети относительно к, .

Для минимизации функционала (5) строится итерационный процесс относительно к, :

к?+1 > = к<?> + Дк(м+1 >, причем за первоначальное

значение к0 принимается значение кп (потери

напора самого большого допустимого диаметра на данном участке), и, очевидно, стоимость - го участка будет С(к,) = С(кп), т.е. начальное значение

целевой функции Ж 0(к) будет наибольшим.

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

Hmin = max \ Z hili + Zi - Zi + H

j \ieTj

j

При Н > Нт1П можно вычислить Н] в] -м узле по формуле

Н] = Н* - ^ к,1, + -1], V] = 2,3,п, что

,еТ]

обеспечит выполнение технических требований:

Н} > Н],V] = 2,3,к,п .

Величину АН] = Н] - Н ссв назовем ресурсом ]-го

узла.

Далее формируем вектор- градиент Е= {Е,},

где Е, = тах

С

hiT- hi

т

т = 1,2, к, кг, / = 2,3, к, п .

В отличие от предложенного в [2] способа выбора направления наискорейшего спуска, состоящего в выборе координаты /, для которой величина максимальна, в предлагаемом

алгоритме «веерной» оптимизации направление спуска Я = {гу} определяется таким образом, что он

может осуществляться сразу по нескольким координатам, а именно:

определяем координату / из условия Е * = тах {Ег};

/

формируем множество Р( = {ру}, у = 1,2, к, тг -1, mi - количество смежных участков к / - му узлу

(номер участка совпадает с номером концевой вершины). Это множество будет пустым, если участок тупиковый, так как mi = 1, например, для

/=6, 7, 8 и т.д. (рис. 3).

Рис. 3

Вычисляем значение градиента E' по формуле:

E

если P = 0,

E =

2 E}-,если р *0.

i<=-P

соотношения s = •

11, если Е' < Е I тг -1, если Е' > Е*

ri ='

i при 5 = 1

Pi при s > 1, где j = 1, 2,..5.

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

¡АН,

AHt <Ah%T,

AHt >Акт

где AH% = min{AHt},

Ah^ = Нт - h%

и целое

Определяем количество координат вектора Я из

те[1,к].

Величина АН^ > 0 есть ресурс участка с номером

Процесс спуска продолжается до тех пор, пока имеются участки с положительными ресурсами, причем если ресурс для какого-либо участка исчерпан (равен нулю), то считаются исчерпанными ресурсы всех участков из множества Т^ .

В исходной задаче (1) - (3), необходимо определить и оптимальное значение напора Н в корневой вершине сети. Построив первоначальное

значение И0, определим начальное значение напора в корневой вершине Н(0) = Н тт из соотношения (6) и строим итерационный процесс

Н (^+1) = Н) + АН , на каждом шаге которого определяются оптимальные значения Иг. Здесь АН

- заданный постоянный шаг изменения напора.

Ввиду выпуклости функционала (3) на каком-то

шаге получим оптимальное значение функционала.

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

Литература

1. Кудаев В.Ч. //Изв. КБНЦ РАН. 2002. Т. 8. № 1. С. 18 -27.

2. Байрактаров Б.Р. // Математическое моделирование. 1998. Т. 10. № 2. С. 41 - 47.

3. Абрамов Н.Н. Расчет водопроводных сетей. М., 1976.

направление спуска Я = {гу-} формируется следующим образом:

Кабардино-Балкарский государственный университет

10 ноября 2004 г.