21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
I-018 - INVESTIGAÇÃO DE MÉTODOS DE SELEÇÃO AUTOMÁTICA DE
CIRCUITOS USANDO A TEORIA DOS GRAFOS PARA A ANÁLISE DE
REDES HIDRÁULICAS
Robert Schiaveto de Souza(1)
Engenheiro Civil pela Universidade Federal de Mato Grosso do Sul. Doutor em Hidráulica e
Saneamento pela Escola de Engenharia de São Carlos/USP. Professor Adjunto do
Departamento de Hidráulica e Transportes do Centro de Ciências Exatas e Tecnologia da
Universidade Federal de Mato Grosso do Sul.
Mauro Polizer
Engenheiro Civil pela Escola de Engenharia de Lins. Professor Titular e Pesquisador do
Departamento de Hidráulica e Transportes do Centro de Ciências Exatas e Tecnologia da
Universidade Federal de Mato Grosso do Sul.
Fazal Hussain Chaudhry
Engenheiro Civil pela Universidade Federal de Punjab - Paquistão, Mestre em Engenharia Hidráulica pela
Asian Institute of Technology - Thayland e PHD em Engenharia Civil pela Colorado State University - EUA.
Professor Titular da Escola de Engenharia de São Carlos/USP.
Endereço(1): Rua José Antonio Pereira, 2609, Apt. 1101-Bairro Monte Castelo-CEP 79010-190-Campo
Grande-MS. Tel: +55 (67) 782 6696 - Fax: +55 (67) 787 3311 Ramal 2215 - e-mail: [email protected].
RESUMO
Com o objetivo de permitir que modelos hidráulicos para análise de redes de distribuição de água sejam
utilizados para redes de maiores dimensões em micro-computadores e torná-los mais eficientes
principalmente em problemas de otimização de redes, a esparsidade pode ser explorada, uma vez que o
sistema de equações resultante é tipicamente esparso, com uma estrutura arbitrária por causa da dependência
da natureza local e da conectividade, ou seja, da dependência da geometria da rede.
Na formulação em termos de vazões para se obter a hidráulica de uma rede, a esparsidade é dependente não
só da geometria da rede, como também da escolha dos circuitos necessários para a sua análise, tornando
necessário a definição prévia dos mesmos. As dificuldades observadas principalmente quanto a convergência
(número de iterações e tempo computacional) e quanto a memória computacional podem ser minimizadas
através de uma escolha adequada destes circuitos.
Alguns algoritmos para a seleção automática de circuitos tem sido desenvolvidos e apresentados e se baseiam
em técnicas baseadas na teoria dos grafos.
Neste trabalho é realizado um estudo da eficiência dos métodos encontrados na literatura científica para a
seleção automática dos circuitos de uma rede hidráulica quando a esparsidade do sistema resultante é
explorada. Pretende-se desta forma avaliar e aperfeiçoar os modelos hidráulicos que requerem a seleção de
circuitos visando a redução da memória e tempo computacional requeridos na obtenção da solução final da
hidráulica de uma rede.
PALAVRAS-CHAVE: Redes Hidráulicas, Teoria dos Grafos, Circuitos Naturais, Sistemas de Distribuição
de Água.
INTRODUÇÃO
A análise em regime permanente de sistemas de distribuição de água é um problema de grande importância
na engenharia hidráulica.
A solução para problemas de redes é obtida quando as vazões satisfazem as equações da continuidade em
cada nó e a equação de circuito em cada canalização. Estas equações são não-lineares tornando necessário a
ABES – Trabalho Técnicos
1
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
utilização de métodos numéricos iterativos, iniciando com uma solução aproximada que é aperfeiçoada
esperançosamente a cada iteração.
A confiabilidade dos algoritmos aplicados na análise de redes é de grande importância. Solução com lenta
convergência ou mesmo fracasso na sua obtenção é um inconveniente principalmente nos estudos de
otimização onde a rede é avaliada inúmeras vezes.
Freqüentemente problemas de análise de redes de distribuição de água não podem ser resolvidos porque
envolvem grandes matrizes e conseqüentemente quase que impossíveis de serem resolvidos na memória
computacional disponível, além de exigirem excessivo processamento (CHANDRASHEKAR 1975).
Com o objetivo de permitir que os modelos sejam utilizados para redes de maiores dimensões em microcomputadores e torná-los mais eficientes principalmente em problemas de otimização de redes, a esparsidade
pode ser explorada, uma vez que o sistema de equações resultante é tipicamente esparso, com uma estrutura
arbitrária por causa da dependência da natureza local e da conectividade, ou seja, da dependência da
geometria da rede. Existem muitas técnicas para tratar matrizes esparsas (TEWARSON 1973). Grandes
matrizes esparsas são geralmente armazenadas em computador em uma forma condensada. Em outras
palavras, somente os elementos não nulos de tais matrizes com as informações de indexação necessárias são
armazenadas. O objetivo de se explorar a esparsidade se resume basicamente em se obter uma economia
substancial de memória e de tempo computacional.
Na formulação em termos de vazões para se obter a hidráulica de uma rede, a esparsidade é dependente não
só da geometria da rede, como também da escolha dos circuitos necessários para a sua análise, tornando
necessário a definição prévia dos mesmos (SOUZA 1994). As dificuldades observadas principalmente quanto
a convergência (número de iterações e tempo computacional) e quanto a memória computacional podem ser
minimizadas através de uma escolha adequada destes circuitos.
Alguns algoritmos para a seleção automática de circuitos tem sido desenvolvidos e apresentados (NIELSEN
1989 e EPP e FOWLER 1970) e se baseiam em técnicas baseadas na teoria dos grafos (SAVULESCO 1980).
Neste trabalho é realizado um estudo da eficiência dos dois métodos encontrados na literatura científica para
a seleção automática dos circuitos de uma rede hidráulica quando a esparsidade do sistema resultante é
explorada. Pretende-se desta forma avaliar e aperfeiçoar os modelos hidráulicos que requerem a seleção de
circuitos visando a redução do número de iterações e conseqüente tempo computacional na obtenção da
solução final da hidráulica de uma rede.
FORMULAÇÃO DO PROBLEMA
Na formulação em termos das vazões, o sistema de equações é de ordem (m-n) dependente da escolha dos
(m-n) circuitos necessários para a sua análise, sendo m o número de trechos de tubulações e n o número de
nós da rede.
[
A formulação proposta por NIELSEN(1989) é dada pela equação (1), onde D k−1 = diag d 1−1 (q 1 ),..., d m−1 (q m )
d k−1
α
Kk qk
]
K −k β H βk
ou q k =
com β = 1 / α ; sendo γ = 1 para LTM (método da
Hk =
teoria linear) e γ = α para NR (método de Newton-Raphson); q k é o vetor de vazões nos trechos; A r é a
matriz de incidência (m x r) dos nós de reservatório; A é a matriz de incidência (m x n) dos nós interiores;
h r é o vetor (r x 1) de energia nos nós de reservatórios; C é qualquer matriz de ordem mx(m-n) tal que
com
=
K k−1 q αk `−1 ;
A t C = 0 . Esse sistema é não linear de m-n equações.
q k +1 = q k − γ −1 C[C t D k C] −1 C t (D k q k + A r h r )
2
equação (1)
ABES – Trabalho Técnicos
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
Os circuitos estão representados pela matriz C, e consequentemente representados na matriz dos coeficientes
do sistema C t D k C . Quanto menor for o número de trechos que compõem cada circuito, maior a esparsidade
do sistema.
MÉTODOS DE SELEÇÃO DE CIRCUITOS
Dois principais algoritmos para a seleção automática de circuitos encontrados na literatura científica foram
implementados e estudados, e são apresentados nesta seção com base numa simples rede ilustrada na figura
1.
4
5
4
3
10
11
7
1
3
2
9
6
5
2
1
8
6
8
7
9
12
10
Figura 1: Rede simples.
Método de NIELSEN
NIELSEN (1989) propôs um algoritmo para a seleção automática dos m-n circuitos em função de uma
permutação da matriz de incidência:
 − F −1G 
C = P

 I 
equação (2)
onde A t P = [F / G ] . As colunas de A t P são exatamente as colunas de A t em uma ordem permutada. A
matriz F é não singular e tem n colunas, e a matriz G possui (m-n) colunas.
Na verdade, cada permutação representa uma seleção distinta de circuitos da rede. No entanto na prática,
uma permutação aleatória pode resultar em uma escolha de circuitos complexos gerando uma matriz C e/ou
C t D k C não esparsa. Em decorrência disto, um controle da esparsidade do sistema pode ser feito,
restringindo a uma permutação da matriz de incidência que resulte em um número mínimo de elementos não
nulos da matriz C e/ou C t D k C . Este processo no entanto consome tempo adicional de cálculo e dependendo
do tipo de análise que se pretende fazer da rede hidráulica pode não ser interessante.
Para a rede simples da figura 1, os três circuitos ótimos são compostos pelos trechos 3, 4, 5, 6, 7 (circuito 1);
trechos 7, 9, 10, 11 (circuito 2); e 6, 8, 9, 12 (circuito 3). As matrizes C e A t representam os circuitos e a
geometria da rede respectivamente, e são dadas por:
ABES – Trabalho Técnicos
3
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
0
0

± 1

± 1
± 1

±1
C = 
±1

0
0

0

0
 0
0
0
0
0
0
0
±1
0
±1
±1
±1
0
0
0 
0

0
0

± 1
0

± 1
± 1

0

0
± 1
0
0
0
0
0
0
 0 ±1 ±1 0 ±1 0
± 1 ± 1 0
0
0
0
0
0
0
0
0
0 

± 1 0
0
0
0
0
0
0
0
0
0
0


0 ±1 ±1 0
0
0
0
0
0
0
0
0


±
±
±
0
0
0
1
0
0
1
0
0
1
0
0
At = 

0
0
0
0 ±1 ±1 0 ±1 0
0
0
0
0
0
0
0 ±1 ±1 0 ±1 0
0
0
0


0
0
0
0
0
0
0
0 ±1 ±1 0 
0
0
0
0
0
0
0
0
0
1
0 ± 1 ± 1


 0
0
0
0
0
0
0 ±1 0
0
0 ± 1
onde na matriz C as colunas representam os circuitos e as linhas os trechos, e na matriz A t as colunas
representam os trechos e as linhas os nós da rede.
Método de EPP e FOWLER
Uma alternativa para a seleção dos m-n circuitos da rede, ou seja, para definir a matriz C, é a seleção
automática dos circuitos naturais, fornecendo diretamente os trechos que compõem cada circuito. Os circuitos
naturais de uma rede de distribuição de água são aqueles que são compostos por um número mínimo de
trechos. Portanto é o critério ótimo para a seleção de circuitos que resulta em um sistema com esparsidade
máxima. Um algoritmo para seleção automática dos circuitos naturais de uma rede foi descrito por EPP e
FOWLER (1970) e é descrito a seguir.
Por definição, um nó é de grau n g , onde n g é o número de tubos conectados à ele. Então na figura 1, o nó 3
é de grau 1, o nó 2 de grau 2, o nó 1 de grau 3, e assim por diante. É fácil determinar os tubos que não
pertencem aos circuitos, começando em um nó de grau 1, e trabalhando com os nós de grau 2, até um nó de
grau maior que 2 ser alcançado.
Temporariamente "remova" a cauda (tubos 1 e 2) da rede. Note que com esses tubos removidos, o nó 1 agora
é de grau 2. Definindo os nós de grau 2 como os nós chaves, então para definir um circuito, qualquer nó
chave é selecionado (por exemplo o nó 1). Os dois nós conectados por tubos ao nó chave são então
conhecidos (ou seja, os nós 4 e 7). O menor caminho entre esses dois nós que não passa através do nó chave é
então determinado.
No exemplo, o caminho será constituído pelos tubos 4, 7 e 6. Assim os tubos 3, 4, 7, 6, e 5 definem o
primeiro circuito natural. Os tubos 3 e 5 agora são temporariamente removidos da rede e então o nó 4 agora
tem grau 1 e o nó 7 tem grau 2 e é um nó chave. Assim, o tubo 4 é uma cauda e portanto é removido e o
algoritmo é repetido para um novo nó chave, ou seja, o nó 7. Se a qualquer momento somente nós de grau
maior do que 2 estão presentes, arbitrariamente escolhe-se o nó de grau menor e repete-se o mesmo
procedimento. Desta maneira o conjunto de circuitos naturais de uma rede é encontrado.
Um algoritmo, no entanto é necessário para se obter o menor caminho entre dois nós da rede. O menor
caminho entre dois nós N 1 e N 2 é uma série de N tubos conectados tal que qualquer outra série de tubos
interligando os dois nós contém no mínimo N tubos. Três listas L1 , L 2 , L 3 são utilizadas para determinar
o menor caminho, e seu desenvolvimento é descrito a seguir:
1) Entrar com o nó terminal N 1 na primeira posição da lista L1 . Colocar o valor de um ponteiro P1 igual a
1.
2) Chamar K = L1 (P1 ) , ou seja, K tem o valor do conteúdo da lista L1 da posição P1 .
3) Escolher um nó que está conectado ao nó K mas que não foi ainda escolhido. Fazer J igual ao número
deste nó.
4) Se o nó J já está na lista L1 , ir para o passo (8).
5) Entrar com o número do nó, isto é J na próxima posição disponível de L1 .
4
ABES – Trabalho Técnicos
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
6) Entrar com o valor de K na J-ésima posição da lista L 2 .
7) Entrar com o número do tubo que interliga os nós K e J na J-ésima posição da lista L 3 .
8) Se o valor de J é igual a N 2 (isto é, J é o outro nó terminal ), ir para o passo (11).
9) Se há nós conectados ao nó K mas que ainda não foram escolhidos, ir para o passo (3).
10) Incrementar o ponteiro P1 de 1 e ir para o passo (2).
11) Colocar o valor de um ponteiro P2 igual a 1.
12) Fazer K= N 2 .
13) Se K é igual a N 1 , ou seja, o nó inicial, então parar, porque todos os tubos do caminho mínimo foram
achados.
14) Chamar TUBO[ P2 ]= L 3 [K], ou seja, L 3 [K] é o P2 - ésimo interliga os nós N 1 e N 2 .
15) Fazer K= L 2 [K].
16) Incrementar P2 de 1 e ir para o passo (13).
No exemplo envolvendo o algoritmo descrito anteriormente, achou-se o menor caminho entre os nós 4 e 7 da
figura 1 sem contar com os tubos 3 e 5 (esses podem ser considerados removidos da rede). A ordem na qual
cada lista foi preenchida está mostrada à direita de cada célula na Tabela 1.
Tabela 1: Seleção dos circuitos naturais
L1
L2
L3
1
4
1
2
5
2
3
8
5
4
6
8
5
9
11
4
3
4
6
9
14
5
9
7
7
7
15
6
16
6
8
5
6
10
9
8
12
11
10
11
12
4
10
17
7
13
RESULTADOS E DISCUSSÕES
Para estudar a eficiência dos métodos de seleção de circuitos mencionados anteriormente, selecionou-se duas
redes exemplos. A primeira constituída de 35 trechos, 16 nós e 3 reservatórios (Fig. 2), enquanto que a
segunda com 27 trechos, 21 nós e 1 reservatório (Fig. 3).
ABES – Trabalho Técnicos
5
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
13
3
19
20
VRP
7
14
VR
34
10
16
17
18
9
21
31
18
4
32
15
5
2
8
30
16
11
14
22
8
7
13
19
35
4
23
15
29
28
6
25
27
26
2
5
9
12
6
12
24
1
3
10
1
11
33
B
17
Figura 2: Rede exemplo 1.
26
27
20
22
21
B
25
24
22
16
23
17
21
18
19
19
18
20
14
15
17
15
12
VR
10
8
13
16
14
11
13
9
10
9
11
12
VRP
8
6
7
4
5
6
7
5
4
3
1
1
2
2
3
Figura 3: Rede exemplo 2.
Onde :
Nó interior
Reservatório
Válvula de retenção
Válvula redutora de pressão
Bomba
A Tabela 2 apresenta o tempo de processamento em unidades de tempo (ut) para a seleção dos circuitos.
Observa-se que o algoritmo proposto por EPP e FOWLER (1970), além de fornecer os circuitos naturais da
rede permitindo a obtenção de um sistema com esparsidade ótima, é muito mais eficiente do que o proposto
por NIELSEN (1989).
6
ABES – Trabalho Técnicos
21º Congresso Brasileiro de Engenharia Sanitária e Ambiental
Tabela 2: Tempo de processamento para a seleção de circuitos.
Tempo (ut)
Tempo (s)
Rede 1
EPP e FOWLER
0.28
NIELSEN
13.62
Rede 2
EPP e FOWLER
NIELSEN
0.16
8.40
CONCLUSÕES
A seleção dos circuitos para a obtenção da solução final da hidráulica de uma rede é um procedimento
importante para se obter maior eficiência no comportamento de convergência do processo iterativo,
principalmente quando a esparsidade do sistema de equações resultante for explorada e a formulação
hidráulica em termos das vazões é utilizada.
Este trabalho teve por finalidade fazer uma revisão e um reexame dos modelos teóricos utilizados para a
seleção automática dos circuitos de uma rede. Um modelo consistente e eficiente para análise de redes pode
ser obtido quando um algoritmo automático para a seleção de circuitos naturais da rede é utilizado na
formulação das vazões.
O aperfeiçoamento dos aspectos computacionais da análise de redes de distribuição de água realizado neste
trabalho possibilitará a análise de redes com maior eficiência e servirá como um instrumento de cálculo para
estudantes de engenharia civil e projetistas no meio profissional da engenharia hidráulica.
REFERÊNCIAS BIBLIOGRÁFICAS
1.
2.
3.
4.
5.
6.
CHANDRASHEKAR, M., STEWART, K. H. Sparsity Oriented Analysis of Large Pipe Networks. Journal of
the Hidraulic Division, v. 101, n. HY4, p. 341-355, 1975.
EPP, R., FOWLER, A. G. Efficient Code for Steady-State Flows in Networks. Journal of the Hydraulics
Division, v. 96, n. HY1, p. 43-56, 1970.
NIELSEN, H. B. Methods for Analyzing Pipe Networks. Journal of Hidraulics Engineering, v. 115, n.2, p.
139-157, 1989.
SAVULESCO, S. C. Grafos, Dígrafos e Redes Elétricas : Aplicação na Pesquisa Operacional. São Paulo :
Instituto Brasileiro de Edições Científicas, 1980.
TEWARSON, R. P. Sparse Matrices. New York, Academics Press, 1973. 160p.
SOUZA, R. S. Aspectos Computacionais da Análise de Redes de Distribuição de Água com Componentes
Hidráulicos em Regime Permanente. São Carlos. Dissertação de Mestrado - Escola de Engenharia de São
Carlos, Universidade de São Paulo, 1994.
ABES – Trabalho Técnicos
7