Математическое моделирование и компьютерное проектирование больших разветвленных трубопроводных сетей водоснабжения Кирхгофа–Штейнера

Введение

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

1. Преобразование заданной проектной организацией структуры распределительной сети водоснабжения в оптимальную трубопроводную сеть Кирхгофа$–$Штейнера.

2. Расчет общих затрат на создание и эксплуатацию сети водоснабжения, заданной на начальном этапе проектирования проектной организацией, в оптимальную трубопроводную сеть Кирхгофа$–$Штейнера. В общие затраты при этом входят: стоимость труб сети, энергетические затраты насосной станции на прокачку необходимого количества воды через трубопроводы, обеспечивающего в каждом узле потребления заданный расход воды и необходимый напор. Точки Штейнера не являются при этом узлами потребления, а являются лишь точками ветвления потоков.

3. Сравнение общих затрат на создание и эксплуатацию сети, структура которой представлена проектной организацией, и сопоставляемой ей сети Кирхгофа$–$ Штейнера.

4. Разработка программной системы.

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

Недостатком существующих методов решения этой задачи является то, что задача ставится и решается как чисто потоковая. В работах Сибирского энергетического института эта задача решалась уже как потоковая задача Кирхгофа, т. е. с учетом потоковых и потенциальных переменных. Дальнейшее снижение затрат на создание и эксплуатацию сети может быть достигнуто на пути создания потоковых сетей Кирхгофа$–$Штейнера.

B сетевой задаче Штейнера (СЗШ), в отличие от классической задачи Штейнера [1, 2], следует минимизировать не суммарную длину коммуникаций, а их общую стоимость.

B СЗШ величины весов ребер зависят от потока по ним. Для этих задач центральное свойство классической задачи Штейнера, состоящее в том, что ребра сети, инцидентные точке Штейнера, образуют друг с другом углы в 120° не выполняется, и поэтому разработанные алгоритмы декомпозиции неприменимы.

В работе E.N. Gilbert [3] впервые была дана формула вычисления углов, образуемых смежными ребрами, инцидентными точке Штейнера в случае, когда эти дуги имеют различные веса. B работах [4, 5] был представлен подход к решению СЗШ. Сетевая задача Штейнера является существенно многоэкстремальной, поэтому в работе [6] было введено понятие и дано определение ранга оптимальности решения сетевой задачи Штейнера. В свою очередь задача построения разветвленной потоковой сети Кирхгофа$–$Штейнера требует существенно большего времени компьютерного проектирования.

1. Потоковая сетевая задача Кирхгофа$–$Штейнера

1.1. Постановка сетевой задачи Кирхгофа$–$Штейнера (СЗКШ)

Задача (СЗКШ) На плоскости задан полный двухзвенный ориентированный геометрический граф Г(В,D), $n$ вершин которого $\left(x_i,y_i\right), i=\mathrm{1,.}\dots ,n$ фиксированы, a $\left(n-2\right)$ вершин $\left(x_i,y_i\right), i=n+\mathrm{1,.}\dots \mathrm{,2}n-2$ не фиксированы, $\left|{В}_{ф}\right|=n, \left|{В}_{Ш}\right|=n-\mathrm{2,} C_{ij}\left({\upsilon }_{ij},h_{ij}\right)$ $–$ удельная стоимость ij ветви, являющаяся вогнутой непрерывно возрастающей по потоку ${\upsilon }_{ij}$ и выпуклой непрерывно убывающей по удельной потере напора $h_{ij}$; $c_{ij}\left(0\right)=0$; $q_j>\mathrm{0,} j\in {В}_{ф}$ и $q_j=0$, $j\in {В}_{Ш}$; $q_j$ $–$ поток, потребляемый в j-м узле (вершине) сети.

Следует так определить координаты точек Штейнера и значения ${\upsilon }_{ij},h_{ij}$ по каждой ветви ij, что

$З\left(\upsilon ,h,{Н}_{НС}\right)=\frac{\rho {Н}_{НС}{Q}_{НС}T}{\eta }+ {\sum }_{\left(ij\right)\in D}{c}_{ij}\left({\upsilon }_{ij},h_{ij}\right)\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}\to min$ (1)

$\underset{i\in D_j^{+}}{}{\upsilon }_{ij}-\underset{k\in D_j^{-}}{}{\upsilon }_{jk}=g_j, \forall j\in B, j\ne 1$ (2)

$\underset{\text{j}\in {\text{D}}_{\text{j}}^{-}}{}{\upsilon }_{1\text{j}}={\text{Q}}_{\text{НС}},$ (3)

${\upsilon }_{\text{ij}}\ge \mathrm{0,}\forall \left(\text{i},\text{j}\right)\in \text{D }$ (4)

${\text{Н}}_{{\text{НС}}_{\text{i}}}={\text{Н}}_{\text{i}}+{\text{z}}_{\text{i}}-{\text{z}}_{\text{НС}}+{\displaystyle \sum }_{\left(\text{rs}\right)\in {\text{T}}_{\text{i}}}{\text{h}}_{\text{rs}}{\text{l}}_{\text{rs}}$ (5)

${\text{Н}}_{\text{НС}}=\underset{\text{i}}{\max }\left\{{\text{Н}}_{{\text{НС}}_{\text{i}}}\right\},$ (6)

 где $З\left(x,h\right)$ $–$ общие затраты на сеть; $\rho$ $–$ цена в рублях за 1 кВт/ч; ${Н}_{НС}$ $–$ напор на насосной станции; $Q_{НС}$ $–$ общий поток в сети; $T$ $–$ заданное время эксплуатации сети в часах; $\eta$ $–$ коэффициент полезного действия (КПД); $i$ $–$ номер вершины истока, $j$ $–$ номер вершины стока $\left(ij\right)$ -й ветви.

Поскольку возможных остовных деревьев графа Г(В, Д), построенных на n фиксированных точках и $\left(n-2\right)$ точках Штейнера, конечное число, и на каждом остовном дереве сети целевая функция непрерывна, то задача (1)$–$(6) имеет оптимальное решение.

1.2. Математическое моделирование задачи оптимального проектирования трубопроводной сети Кирхгофа$–$Штейнера

Функционирование сетей по переносу сетевого продукта (электричество, вода, газ, нефть) зависит не только от величин потоков ${\text{υ}}_{\text{ij}},\text{ ij}\in \mathcal{D}$ по ветвям сети, но и от потерь потенциала $h_{ij}, ij\in \mathcal{D}$ потока по ветвям. Затраты на создание и функционирование сети при этом складываются из стоимости коммуникаций трубопроводов сети и энергетических затрат на прохождение сетевого продукта по коммуникациям от источника к потребителям $–$ в нашем случае к фиксированным $\text{n}$ вершинам.

Как известно [4, 5], затраты на коммуникацию могут быть рассчитаны по формуле ${З}_{ij}=\left(k{\upsilon }_{ij}^{\alpha }{h}_{ij}^{\beta }+{\upsilon }_{ij}{h}_{ij}\right) l_{ij},$ где $0<\alpha <\mathrm{1,} \beta <\mathrm{0,} l_{ij}$ $–$ длина коммуникации. Первое слагаемое характеризует стоимость коммуникации, второе $–$ энергетические затраты на транспорт сетевого продукта по коммуникации. В таком случае получим

$\text{З}\left(\text{υ},\text{h}\right)={\displaystyle \sum }_{\text{ij}\in \mathcal{D}}\left({\text{kυ}}_{\text{ij}}^{\text{α}}{\text{h}}_{\text{ij}}^{\text{β}}+{\text{υ}}_{\text{ij}}{\text{h}}_{\text{ij}}\right)\sqrt{{\left({\text{x}}_{\text{i}}-{\text{x}}_{\text{j}}\right)}^2+{\left({\text{y}}_{\text{i}}-{\text{y}}_{\text{j}}\right)}^2}\to \text{min}.$ (7)

Поскольку целевая функция выпукла и непрерывна по ${\text{h}}_{\text{ij}}$, то на оптимальном решении получим

 $\frac{\partial З}{\partial h_{ij}}=\left(k\beta {\upsilon }_{ij}^{\alpha }{h}_{ij}^{\beta -1}+{\upsilon }_{ij}\right)\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}=\mathrm{0,} ij\in \mathcal{D}$, то

 $h_{ij}^{\beta -1}=\frac{{\upsilon }_{ij}^{1-\alpha }}{-k\beta },h_{ij}={\left(-k\beta \right)}^{\frac{1}{1-\beta }}{\upsilon }_{ij}^{\frac{1-\alpha }{\beta -1}}$.

Отсюда получим

$З\left(\upsilon \right)={\displaystyle \sum }_{ij\in \mathcal{D}}{\left(-k\beta \right)}^{\frac{1}{1-\beta }}\left(\frac{\beta -1}{\beta }\right){\upsilon }_{ij}^{\frac{\beta -\alpha }{\beta -1}}\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}.$

Поскольку ${\left(-k\beta \right)}^{\frac{1}{1-\beta }}\left(\frac{\beta -1}{\beta }\right)-const,$ то целевая функция (7) примет вид  

${\displaystyle \sum }_{ij\in \mathcal{D}}{\upsilon }_{ij}^{\frac{\beta -\alpha }{\beta -1}}\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}\to min.$ (8)

Отсюда следует формула перехода от $c_{\text{ij}}({\text{υ}}_{\text{ij}},{\text{h}}_{\text{ij}})$ к ${\text{f}}_{\text{ij}}({\text{υ}}_{\text{ij}})$: ${\text{f}}_{\text{ij}}({\text{υ}}_{\text{ij}})={\text{υ}}_{\text{ij}}^{\frac{\text{β}-\text{α}}{\text{β}-1}}.$ Значения $\text{α},$ $\text{β}$, k зависят от материала труб [7, с. 53$–$55]. Например, для полиэтиленовых труб, наиболее часто используемых в проектировании больших сетей водоснабжения, $\alpha$ =1,95, $\beta$ =1,774, $\gamma =$ 4,774, $k$ = 0,001052.

2. Решение сетевой задачи Штейнера на основе динамической декомпозиции и ранговой оптимизации

Задача минимизации вогнутой возрастающей функции на транспортном многограннике, к которой относится и задача оптимизации разветвленной потоковой сети, рассматриваемая в работах [8$–$10], является существенно многоэкстремальной. В работах Сибирского энергетического института (СЭИ, г. Иркутск) [11$–$13], а также [14] был разработан общий метод решения задачи минимизации затрат на создание потоковых сетей.

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

Для потоковой сетевой задачи Штейнера оно состоит в следующем. Назовем фрагментом Р-го ранга вершины i сети Штейнера ее подсеть Pi, стягивающую множество вершин Р-достижимых из вершины i сети (без учета направления дуг), а сетью Штейнера Р-го ранга $–$ такую сеть, любой из фрагментов Р-го ранга которой оптимален.

Для построения метода декомпозиции потребуется формализация это понятия. Пусть ${\left\{{\upsilon }_{ij}^{*}\right\}}_{ij\in D},{\left\{x_i^{*},y_i^{*}\right\}}_{B_{ш}}$ $–$ некоторое допустимое решение задачи. Ту часть множества дуг, поток по которой отличен от нуля, и ту часть множества точек Штейнера, поток из которых отличен от нуля, обозначим соответственно $D^{*}$ и $B_{ш}^{*}$. Сформируем множество $B^{*}=B_{ф}\cup B_{Ш}^{*}$. Обозначим граф, включающий $B^{*}$, $D^{*}$ через ${Г}^{*}\left(B^{*},D^{*}\right)$. Выделим любую вершину i графа и обозначим множество его вершин, не более чем P-достижимых из i, $M_i^P,$ а $P_i^{* }$ $–$ подграф графа ${Г}^{*}\left(B^{*},D^{*}\right),$ построенный на этих точках.

Определение: назовем сеть Штейнера $\left\{{Г}^{*}\left(B^{*},D^{*}\right),{\left\{{\upsilon }_{ij}^{*}\right\}}_{ij\in D},{\left\{x_i^{*},y_i^{*}\right\}}_{B_{ш}{}^{*}}\right\}$ P оптимальной, если выполнено условие минимума:

$min{\displaystyle \sum }_{ij\in \mathcal{D}}{f}_{ij}\left({\upsilon }_{ij}\right)\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2} ={\displaystyle \sum }_{ij\in {\mathcal{D}}^{*}}{f}_i\left({\upsilon }_{ij}{}^{*}\right)\sqrt{{\left(x_i{}^{*}-x_j{}^{*}\right)}^2+{\left(y_i{}^{*}-y_j{}^{*}\right)}^2,}$ (9)

где ${\upsilon }_{ij}={\upsilon }_{ij}^{*}$, $\forall ij\notin P_i{}^{*}; x_i=x_i^{*}$, $y_i=y_i^{*}$ $\forall i\notin P_i{}^{*}$

Метод динамической декомпозиции построения Р-оптимальной сети Штейнера состоит из следующих этапов:

1. В связи с экспоненциальным ростом структур Штейнера при поиске P-оптимального решения следует стартовать с решения, достаточно близкого по значению целевого функционала к оптимуму в задаче (5)$–$(9). В качестве такового берется P-оптимальное решение сетевой задачи построения терминальной сети, т.е. сети без точек Штейнера, а также сетей, представленных проектными организациями.

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

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

Рис. 1. Схема элементарной потоковой сети Штейнера

Fig. 1. Schematic diagram of the elementary Steiner flow network

3. Преобразование терминальной сети в сеть Штейнера

3.1. Элементарные узловые структуры сети Штейнера

Решением задачи (1)$–$(6) является остовное дерево заданного графа возможных соединений узлов сети. Преобразование терминального остовного дерева в сеть Штейнера осуществляется путем развертывания его узлов в структуры Штейнера. Каждый такой узел содержит вершину, из которой поступает поток в узел (исток), и вершины, в которые доставляется поток из узла (стоки). В сетевых системах, как правило, могут быть узлы с одним, двумя и тремя выходными потоками. Все эти структуры назовем элементарными узловыми структурами.

Развертывание элементарных узловых структур в узловые структуры Штейнера осуществляется в соответствии с фундаментальными свойствами точек Штейнера:

1. Степени точек Штейнера равны 3, а степени фиксированных (терминальных) точек не превосходят 3.

2. Дуги остовного дерева, инцидентные каждой точке Штейнера, образуют смежные друг с другом углы, которые определяются по формуле

$\cos \left({\alpha }_{i,j}\right)=\frac{f_k^2\left({\upsilon }_k\right)-f_i^2\left({\upsilon }_i\right)-f_j^2\left({\upsilon }_j\right)}{2f_i\left({\upsilon }_i\right)f_j\left({\upsilon }_j\right)},$

где $\cos \left({\alpha }_{i,j}\right)$ $–$ косинус угла между отрезками, соединяющими точку $\left(x,y\right)$ с точками $\left(x_i,y_i\right)$ и $\left(x_j,y_j\right)$ (рис. 1).

3. Число точек Штейнера не превосходит $\left(n-2\right)$, где $\text{n}$ $–$ количество вершин сети.

4. Дуги дерева сети пересекаются только в вершинах дерева.

Узловые структуры Штейнера, построенные в соответствии с этими фундаментальными свойствами, представлены на рис. 2. Узловая структура (а) развертывается в структуру Штейнера единственным образом, т.к. имеется только одно соответствующее ей остовное дерево Штейнера. Элементарная узловая структура (б) может развертываться в два альтернативных остовных дерева, получающихся одно из другого, как зеркальное отображение при удалении нумерации вершин. Наконец, наиболее сложная элементарная узловая структура (в), содержащая 5 терминальных точек, развертывается в 8 остовных деревьев, которые получаются из пары зеркальных деревьев поворотами в плоскости с наложением вершин $–$ всего по 4 поворота каждого из взаимозеркальных остовных деревьев. По каждой из структур построены соответствующие матрицы переходов от элементарных узловых структур в элементарные альтернативные структуры Штейнера, в которых указаны и преобразования потоков исходя из заданных потоков по ветвям элементарных узловых структур (рис. 2 а, б, в).

Рис. 2. Развертка исходных структур сети в узловые структуры Штейнера

Fig. 2. Decomposition of the original network structures into Steiner nodal structures

3.2. Оптимизация параметров на каждой из альтернативных узловых структур сети Штейнера

Оптимизация параметров на каждой из альтернативных узловых структур формируемой сети Штейнера проводится на основе последовательного решения на каждой структуре элементарных (3-точечных) сетевых задач Штейнера (ЭСЗШ)

$З={\displaystyle \sum }_{i=1}^{З}f\left(q_i\right)\sqrt{{\left(x_i-x\right)}^2+{\left(y_i-y\right)}^2}\to min,$

$q_1=q_2+q_3$.

градиентным методом:

$\left\{\begin{array}{c}{x}^{j+1}=x^j-\frac{\partial З}{\partial x}\left(x^j,y^j\right) {\alpha }^j=x^j+{\displaystyle \sum }_{i=1}^{З}f\left(q_i\right)\frac{x_i-x^j}{\sqrt{{\left(x_i-x\right)}^2+{\left(y_i-y\right)}^2}}{\alpha }^j\\ y^{j+1}=y^j-\frac{\partial З}{\partial x}\left(x^j,y^j\right) {\alpha }^j=y^j+{\displaystyle \sum }_{i=1}^{З}f\left(q_i\right)\frac{y_i-y^j}{\sqrt{{\left(x_i-x\right)}^2+{\left(y_i-y\right)}^2}}{\alpha }^j\end{array}\right.$

Дробление шага ${\text{α}}^{\text{j}}$ проводится при нарушении условия

$\text{З}\left({\text{x}}^{\text{j}+1},{\text{y}}^{\text{j}+1}\right)-\text{З}\left({\text{x}}^{\text{j}},{\text{y}}^{\text{j}}\right)\le \mathcal{E}{\text{α}}^{\text{j}}{\left({\text{x}}^{\text{j}},{\text{y}}^{\text{j}}\right)}^2$ , $\mathcal{E}=\mathrm{0,5}$.

Решение задачи прекращается при достижении заданной точности: $0\le \frac{{\text{З}}^{\text{j}}-{\text{З}}^{\text{j}+1}}{{\text{З}}^{\text{j}}}\le \mathrm{0,001}$.

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

3.3. Построение сети Штейнера 2-го ранга оптимальности с оптимальным количеством точек Штейнера

Целью этого этапа оптимизации является построение такой сети Штейнера, любая подсеть Р-й размерности которой оптимальна. Задача решается методом динамической декомпозиции. Пусть i $–$ текущая вершина сети Штейнера в процессе оптимизации структуры сети. Обозначим:

• Pi $–$ подсеть сети Штейнера, стягивающая множество ${\text{M}}_i^{\text{P}}$ вершин не более чем Р-достижимых из i;
• ${\text{M}}_i^{\text{P}-1}$ $–$ множество вершин (P-1)-достижимых из вершины i;
• ${\overline{M}}_i^P$ $–$ P-достижимых, но не (P-1)-достижимых вершин $–$ внутренний контур сети;
• ${\overline{M}}_i^{P+1}$ $–$ (P+1)-достижимых, но не P-достижимых вершин $–$ внешний контур сети;

Схема алгоритма построения сети:

1. Выделяется текущая вершина i сети Штейнера.

2. Определяются Pi $–$ подсеть и множества ${\text{M}}_i^{\text{P}-1}$, ${\overline{M}}_i^P$, ${\overline{M}}_i^{P+1}$.

3. Устраняются все дуги между вершинами из ${\text{M}}_i^{\text{P}}$ Pi -й подсети.

4. Решается задача оптимизации координат точек Штейнера сформированной подсети и определяется ее стоимость. При этом точки Штейнера множества вершин ${\text{M}}_i^{\text{P}-1}$ подвижны и могут менять структуру подсети, точки множества ${\overline{M}}_i^P,$ составляющие внешний контур, могут изменять координаты, но не структуру подсети, точки множества ${\overline{M}}_i^{P+1},$ образующие внешний контур подсети, фиксированы для соблюдения граничных условий подсети с остальной сетью Штейнера.

5. Пункт 4 повторяется для всех генерируемых альтернативных подсетей Штейнера текущей вершины i с отбором оптимальной по стоимости коммуникаций. Далее переходим к оптимизации Pi+1-й подсети сети Штейнера.

Процесс оптимизации структуры сети завершается при построении такой сети Штейнера, любая подсеть Р-го ранга которой оптимальна.

Переходим к удалению из полученной 2-оптимальной сети Штейнера неэффективных точек Штейнера

6. Удаление из полученной 2-оптимальной потоковой сети Штейнера тех точек Штейнера, которые расположены достаточно близко к узлам потоковой сети, т.е.

 $\sqrt{{\left(x_i-x_{jШ}\right)}^2+{\left(y_i-y_{jШ}\right)}^2}\le r,$

где ( $x_i,y_i$ ) $–$ координаты узловой точки i, ( $x_{jШ},y_{jШ}$ ) $–$ координаты точки Штейнера, связанной ветвью ij с вершиной i, r $–$ заданная величина.

7. Слияние точек Штейнера, связанных ветвью и находящихся на расстоянии

 $\sqrt{{\left(x_{iШ}-x_{jШ}\right)}^2+{\left(y_{iШ}-y_{jШ}\right)}^2}\le r.$

8. Оптимизация координат оставшихся k точек Штейнера градиентным методом по отношению к 2-достижимым вершинам сети.

9. Оценка значения $\left({\text{З}}_k+kC\right)$, где ${\text{З}}_k$ $–$ стоимость сети Штейнера с k вершинами Штейнера, $C$ $–$ стоимость одного узла соединения трубопроводов сети в точке Штейнера.

10. Оценка разности значений ${\Delta }_{\overline{k},k} =\left({\text{З}}_{\overline{k}}+\overline{k}C\right)-\left({\text{З}}_k+kC\right)$, где $\overline{k}$ $–$ количество точек Штейнера на предыдущем цикле оптимизации i-й подсети, $k-на данном цикле$.

11. Если ${\Delta }_{\overline{k}}^k\ge 0$, то $r:=r_0+\tau$, $\tau =\frac{1}{10}{r}_0$, где $r_0$ $–$ значение $r$ на начальном цикле оптимизации количества точек Штейнера, то переходим на 6.

В противном случае завершается процедура оптимизации количества точек Штейнера в сети.

3.4. Алгоритм построения трубопроводной сети Кирхгофа$–$Штейнера 2-го ранга оптимальности

Блок-схема алгоритма построения 2-оптимальной потоковой сети Кирхгофа$–$Штейнера.

Рис. 3. Блок-схема алгоритма построения потоковой сети Кирхгофа$–$Штейнера 2-го ранга оптимальности

Fig. 3. Block diagram of the algorithm for constructing the Kirchhoff-Steiner flow network of the 2nd rank of optimality

4. Минимизация общих затрат на сеть

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

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

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

4.1. Определение начальной энергии ${Э}_0$

Считаем удельные потери напора $h_i$ по каждой ветви дерева по формуле

$h_i={\left(\frac{\alpha b}{\gamma p}\right)}^{\frac{\gamma }{\alpha +\gamma }}{k}^{\frac{\alpha }{\alpha +\gamma }}{x}_i^{\frac{\alpha \beta -\gamma }{\alpha +\gamma }},$

где коэффициенты $\alpha ,\beta ,\gamma ,b,p,k$ зависят от материала труб [7]. Например, для полиэтиленовых труб, активно применяющихся для проектирования распределительных трубопроводных сетей, $b=17400$ $–$ цена в рублях за 1 метр трубы диаметром 1 метр; $p=\mathrm{5,68}$ $–$ цена за 1 киловатт час; $i$ $–$ номер ветви; $x_i$ $–$ поток по ветви.

Считаем ${Э}_0$ по формуле

${Э}_0= {\displaystyle \sum }_{i=0}^n{x}_i{h}_i{l}_i$,

где $i$ $–$ номер ветви дерева; $x_i$ $–$ поток по ветви; $l_i$ $–$ длина ветви; $h_i$ $–$ удельные потери напора по ветви.

4.2. Алгоритм подсчета напора на насосной станции (Н_НС)

1) Вычисляем величину M по формуле

$M={\displaystyle \sum }_{i=1}^n{x}_i^{\frac{\alpha \left(\beta +1\right)}{\alpha +\gamma }}{l}_i$.

2) Для каждой ветви $j$ вычисляется $h_j$ (удельная потеря напора по j-й ветви) по формуле

$h_j=\frac{{Э}_0{x}_j^{\frac{\alpha \beta -\gamma }{\alpha +\gamma }}}{M}$.

3) Для каждой вершины $i$ находим $T_i$ $–$ траекторию из веток, ведущую из источника в i-ю вершину.

4) Для каждой вершины $i$ находим ${Н}_{Н{С}_i}$ (т.е. напор на насосной станции, который требуется для обеспечения этой вершины $i$ требуемым ей напором) по формуле

${Н}_{Н{С}_i}={Н}_i+z_i-z_{НС}+{\displaystyle \sum }_{j\in T_i}{h}_j{l}_j$,

где ${Н}_i$ $–$ нормативный напор в i-й вершине, $z_i$ $–$ высота i-й вершины, $z_{НС}$ $–$ высота насосной станции (точнее, высота вершины, где находится насосная станция), ${\displaystyle \sum }_{j\in T_i}{h}_j{l}_j$ $–$ полные потери напора по j-й дуге, j $–$ номер дуг дерева (ветви).

5) Находим ${Н}_{НС}$ как максимум из всех ${Н}_{Н{С}_i}$, т. е.

 ${Н}_{НС}=\underset{i}{\max }\left\{{Н}_{Н{С}_i}\right\}$.

4.3. Алгоритм подсчета полных затрат (З₀)

Следует определить З0 $–$ полные затраты на сеть, то есть

${З}_0={З}_{энерг.}+{З}_{труб}$,

где ${З}_{энерг.}= \frac{\rho {Н}_{НС}{Q}_{НС}T}{\eta }$ $–$ энергетические затраты на эксплуатацию сети в течение заданного времени $T$; $\rho =\mathrm{5,68}$ $–$ это цена за 1 киловатт час; ${Н}_{НС}$ $–$ напор на насосной станции; $Q_{НС}$ $–$ общий поток в сеть (его можно найти как сумму потреблений во всех вершинах или сумму потоков всех ветвей, выходящих из вершины-источника); $T=365*24=8670 ч.$ $–$ время эксплуатации сети в часах; $\eta =\mathrm{0,7}\left(70 \text{\%}\right)$ $–$ коэффициент полезного действия.

${З}_{труб}= {\displaystyle \sum }_{i=1}^n{c}_i{l}_i,$

где ${З}_{труб}$ $–$ затраты на трубы в рублях; $i$ $–$ номер ветви; $l_i$ $–$ длина i-й ветви; $c_i$ $–$ удельная цена i-й ветви. Вычисляется она так:

$c_i=b{d}_i^{\alpha },$

где $b$ $–$ цена за 1 метр трубы диаметром 1 метр; $d_i$ $–$ диаметр i-й ветви. Вычисляется диаметр по формуле Дарси$–$Вейсбаха:

$d_i={\left(\frac{k{x}_i{}^{\beta }}{h_i}\right)}^{\frac{1}{\gamma }}$,

где $\beta$, $\gamma$, $k$ $–$ это коэффициенты из таблицы (для пластмассы); $x_i$ $–$ поток по ветви; $h_i$ $–$ удельные потери напора по ветви.

Для полиэтиленовых труб, используемых активно при проектировании распределительных сетей, $b=17400$.

4.4. Алгоритм оптимизации полных затрат на сеть

1) Находится ${Э}_0$ и ${З}_0$.

2) Уменьшается ${Э}_0$ на 1 %, и это значение присваивается в ${Э}_1$, т. е. ${Э}_1={Э}_0*\mathrm{0,99}$.

3) Находится ${З}_1$ по двум последним алгоритмам («Алгоритм подсчета напора на насосной станции» и «Алгоритм подсчета полных затрат»), только вместо ${Э}_0$ используется ${Э}_1$.

4) Переменной $i$ присваивается значение 1.

5) Пока ${З}_{i-1}>{З}_i,$ выполняются следующие операции:

5.1. Увеличивается $i$ на единицу.

5.2. ${Э}_i={Э}_{i-1}*\mathrm{0,99}$.

5.3. Находится ${З}_i$ по двум последним алгоритмам, используя в качестве значения энергии значение ${Э}_i$.

6) Так как ${З}_{i-1}\le {З}_i$, то ${З}_{i-1}$ и есть оптимальные общие затраты на сеть.

5. Результаты вычислительного эксперимента компьютерного моделирования сети Кирхгофа$–$Штейнера

Эксперимент $–$ преобразование разветвленной потоковой сети, представленной проектной организацией, в сеть Кирхгофа$–$Штейнера:

Рис. 4. Исходная схема структуры потоковой сети, заданная проектной организацией

Fig. 4. Initial diagram of the flow network structure specified by the design organization

Таблица 1. Информация по оптимизации исходной потоковой сети

Table 1. Information on optimization of the original streaming network

Итоговая информация по оптимизации сети:

Затраты на трубы = 49446741,91 руб. Энергетические затраты = 33843055,19 руб. Напор на насосной станции = 278,75 м. Полные затраты = 83289797,11 руб.

Далее следует информация по спроектированному компьютерной системой преобразованию исходной сети (рис. 4) в сеть Кирхгофа$–$Штейнера.

Рис. 5. Структура потоковой сети Кирхгофа$–$Штейнера

Fig. 5. Structure of the Kirchhoff-Steiner flow network

Таблица 2. Информация по оптимизации потоковой сети Кирхгофа–Штейнера

Table 2. Information on the optimization of the Kirchhoff-Steiner flow network

Итоговая информация по оптимизации сети:

Затраты на трубы = 44366252,1032027 руб.

Энергетические затраты = 31219929,76 руб.

Напор на насосной станции = 259,82 м.

Полные затраты = 75586181,86 руб.

Ниже в табл. 3 представлены итоговые результаты по преобразованию сети, представленной проектной организацией, в сеть Кирхгофа$–$Штейнера.

6. Общие результаты вычислительного эксперимента

Таблица 3. Сравнительный анализ по результатам оптимизации

Table 3. Comparative analysis of optimization results

1. Наилучшей потоковой сетью Кирхгофа$–$Штейнера является сеть со схемой, изображенной на рис. 5.

2. В зависимости от структуры рассматриваемых сетей разность затрат на заданную своей структурой потоковую сеть Кирхгофа и Кирхгофа$–$Штейнера различается примерно на 9,4 %.

Заключение

Отметим основные научные и научно-практические результаты представленной работы:

1. Разработан метод преобразования заданного проектной организацией проекта структуры распределительной сети водоснабжения в оптимальную трубопроводную сеть Кирхгофа$–$Штейнера.

2. Разработан метод расчета общих затрат на создание и эксплуатацию сети водоснабжения, заданной на начальном этапе проектирования проектной организацией, в оптимальную трубопроводную сеть Кирхгофа$–$Штейнера. В общие затраты при этом входят: стоимость труб сети, энергетические затраты насосной станции на прокачку необходимого количества воды через трубопроводы, обеспечивающего в каждом узле потребления заданный расход воды и необходимый напор. Точки Штейнера не являются при этом узлами потребления, а являются лишь точками ветвления потоков.

3. Разработана программная система проведения расчетов параметров сети, общих затрат на создание и эксплуатацию сети, структура которой задана проектной организацией, и сопоставляемой ей сети Кирхгофа$–$Штейнера.

Метод и компьютерная система предназначены для проектирования больших разветвленных трубопроводных сетей регионального и межрегионального водоснабжения. Потоковые сети Кирхгофа$–$Штейнера обеспечивают экономический эффект порядка 6% от затрат на создание и эксплуатацию потоковых сетей водоснабжения.