Modelos de planeamento e
gestão de recursos hídricos
19 de Novembro
Metodologias de análise
• Sistema real vs sistema simplificado
• Modelação
– Matemática;
– Física;
• Análise de sistemas:
– Simulação;
– Optimização:
•
•
•
•
Programação linear;
Programação dinâmica;
Métodos baseados em gradientes;
Métodos heurísticos
–
–
–
Redes neuronais;
Algoritmos genéticos;
Simulated Annealing;
• ….
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
154
Problemas tipo
• Planeamento
– Que alterações profundas há a realizar no sistema para
satisfazer os usos / fins do sistema ?
– Longo prazo;
• Gestão
– Qual a política de operação do sistema, tendo em conta a sua
configuração (condições naturais, infra-estruturas, usos/fins) ?
– Médio prazo;
• Gestão em tempo real
– Qual a decisão apropriada para o próximo período tendo em
conta o estado do sistema ?
– Curto prazo.
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
155
Exemplos
• Planeamento:
– Como resolver os problemas de cheias de uma determinada
localidade ?
– Como resolver os problemas de abastecimento de uma região ?
– Como resolver os problemas de contaminação de um curso de
água ?
• Gestão:
– Qual deve ser a política de exploração de uma albufeira para
satisfazer certos fins ?
• Gestão em tempo real:
– Que volumes de água devo atribuir a cada uso esta semana
tendo em conta o estado do sistema e as previsões de
afluências ?
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
156
Formulação
• Dado um problema:
– Alternativa 1 –> Implicações (benefícios, custos)
– Alternativa 2 –> Implicações (benefícios, custos)
…..
– Alternativa n –> Implicações (benefícios, custos)
• Qual é a alternativa mais apropriada ?
• Problema: Existe um número muito elevado, por vezes infinito,
de alternativas para solucionar o problema.
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
157
Resolução
1. Identificação de soluções viáveis (admissíveis), i.e.
que satisfazem as condicionantes do problema;
2. Avaliação dos benefícios e custos de cada
alternativa.
3. Identificação da melhor alternativa.
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
158
Técnicas de resolução
• Simulação
– Modelo matemático que estima o desempenho do sistema se
adoptada determinada solução;
– O utilizador testa várias alternativas e avalia os resultados;
– Por tentativa e erro, é identificada a melhor alternativa;
Alternativa 1
Modelo
Implicações
Alternativa 2
Modelo
Implicações
Alternativa i
Modelo
Implicações
Alternativa n
Modelo
Implicações
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
Análise
Comparação
Melhor
alternativa
159
Técnicas de resolução
• Optimização
–
–
–
–
Identificação de possível solução;
Estimativa do desempenho do sistema;
Aperfeiçoamento da solução;
Identificação da melhor alternativa de forma automática;
Alternativa x
Simulação
Implicações
Gera novas alternativas
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
Melhor
alternativa
160
Vantagens e desvantagens
• Simulação
– Permite simular o sistema de
forma mais realista;
– Exige a identificação manual
das alternativas viáveis;
– Exige identificação da melhor
alternativa por tentativa e
erro;
– Quando existe um número
infinito de alternativas, é
difícil identificar a melhor.
• Optimização
– Simulação simplificada do
sistema;
– Identificação da melhor
solução de forma automática.
– A solução identificada como
melhor pode não ser a melhor
no mundo real.
Solução:
• Utilizar optimização para identificar a “melhor” solução;
• Avaliar a solução por simulação e proceder a aperfeiçoamentos;
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
161
Formulação de um problema de optimização
• Cada alternativa é representada pelos valores que um conjunto de
variáveis assume.
• Variáveis de decisão: X1, X2, ….,Xn
• Função objectivo: B(X1, X2, ….,Xn) (e.g. beneficios ou custos da
alternativa)
• Max B(X1, X2, ….,Xn)
Sujeito a
F1(X1, X2, ….,Xn) <= b1
F2(X1, X2, ….,Xn) <= b2
.......
Fn(X1, X2, ….,Xn) <= bn
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
162
Técnicas de optimização
• Programação linear
–
Só podem ser incluídas equações lineares
•
g(X1, X2, …, Xn) = c1 X1 + c2 X2 + … + cn Xn
•
e.g. não é possível assumir que o custo de uma solução varia com o quadrado de uma variável
• Programação dinâmica
–
A função objectivo tem de ser separável.
•
–
F(X1, X2, …, Xn) = f1(x1) + f1(x2) + … + fn(xn)
Maldição da dimensão
• Programação não linear
–
Não há garantia de identificação da melhor solução.
• Técnicas heurísticas
–
Redes neuronais;
–
Algoritmos genéticos;
–
Simulated annealing (recozimento simulado);
• Programação inteira
–
Variante da PL que permite considerar variáveis não contínuas
• Programação dinâmica estocástica; teoria do controlo
–
Variantes da PD
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
163
Programação linear
• As variáveis são contínuas;
• Todas as equações são lineares;
• Formulação padrão (forma canónica;)
– Max C1X1 + C2X2 + … + CnXn
– Sujeito a
•
•
•
•
•
a11 X1 + a12 X2 + … a11 Xn <= b1
a21 X1 + a22 X2 + … a21 Xn <= b2
…
am1 X1 + am2 X2 + … amn Xn <= bm
X1>=0, X2>=0, …., Xn>=0
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
164
Exemplo 1
Mitigação de cheias
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
165
Ex.1 - Mitigação de cheias
• Uma pequena cidade, que sofre frequentemente cheias, está a
estudar as duas soluções tecnicamente viáveis para mitigar este
problema. A primeira solução consiste em construir um dique que
custa 200 mil euros por cada metro de altura, sendo possível
construir diques até um máximo de 4 m. Cada metro de altura do
dique reduz o risco de cheia em 5%.
• A outra solução é a definição de um volume de encaixe de cheias
numa albufeira localizada a montante da cidade. A entidade que
gere essa albufeira está disposta vender o direito de utilização da
capacidade de armazenamento, até um volume de 10 dam3, por
150 mil euros por cada dam3. Cada dam3 de volume de encaixe de
cheias reduz o risco de cheia em 3%.
• Actualmente, sem qualquer medida de protecção, o risco de cheia é
50%. A cidade pretende saber qual é a solução mais barata que
reduza o risco de cheia para um valor inferior a 10 %
– Qual é a solução mais barata para atingir o risco de cheia pretendido ?
– Quanto é custaria reduzir o risco de cheia para 9 % ?
– Quanto a cidade estaria disposta a pagar pela possibilidade de utilizar
mais um dam3 de capacidade de armazenamento na albufeira ?
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
166
Ex.1 - Mitigação de cheias
Formulação / Resolução
Função objectivo: Minimizar custos
Variáveis de decisão:
• Volume de encaixe de cheias, V (dam3)
• Altura do dique, H (m)
H
8
Solução óptima
V = 6.6 dam3
H=4m
Custo = 1790
milhares de euros
Min 200H + 150V (milhares de euros)
Sujeito a:
4
V <= 10 dam3
Soluções
Admissíveis
H <= 4 m
50 – 5H – 3V <= 10
V>=0; H>=0
IST: Gestão Integrada de Bacias Hidrográficas
10
© Rodrigo Proença de Oliveira, 2008
13,3
V
167
Programação linear
• Todas as equações (restrições e função
objectivo) são lineares e são
representadas por rectas no espaço
das soluções;
• A zona das soluções admissíveis é um
polígono convexo;
• A solução óptima é sempre um dos
vértices do polígono;
• O número de restrições condicionantes
é igual (ou superior) ao número de
variáveis.
Polígono não convexo
Polígono convexo
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
168
Preços-sombra
• Cada restrição tem um preço-sombra (incluindo as de não
negatividade);
• Definição:
–
Variação do valor da função objectivo decorrente do incremento em uma
unidade do lado direito da equação;
• Significado:
–
Custo unitário do recurso associado à restrição;
• Restrições:
–
–
Condicionantes -> preço-sombra <> 0.
Não condicionantes -> preço-sombra = 0
Max C1X1 + C2X2 + … + CnXn
Preços sombra
Sujeito a
a11 X1 + a12 X2 + … a11 Xn <= b1
a21 X1 + a22 X2 + … a21 Xn <= b2
Y1
Y2
.......
…..
am1 X1 + am2 X2 + … amn Xn <= bm
X1 >=0
Yn
z1
X2 >=0
…
Xn >=0
z2
…
zn
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
Custos reduzidos
169
Ex.1 - Mitigação de cheias
Cálculo de preços sombra
Problema original
Min 200H + 150V (milhares de euros)
Sujeito a:
V < 10 dam3
H<4m
50 – 5H – 3V <= 10
V>=0; H>=0
Solução óptima original
V = 6.6 dam3; H = 4 m
Custo = 1790 milhares de euros
Preço sombra de H <= 4
H<= 5
Nova solução óptima
V = 5 dam3; H = 5 m
Custo = 1550 milhares de euros
Preço sombra = 1790–1550 = 240 milhares de euros/m
Preço sombra de 50-5H-3V<=10
50-5H-3V<=11
Nova solução óptima
V = 4.6 dam3; H = 4 m
Custo = 1490 milhares de euros
Preço sombra = 1790– 1490= 300 milhares de euros/(%risco)
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
H
5
4
10
13,3
V
10
13,3
V
H
4
170
Ex.1 - Mitigação de cheias
Preços sombra
• Quanto é custaria reduzir o risco de cheia para 9%?
– Preço sombra da restrição do risco de cheia
– Custo = 300 milhares de euros/(%risco)
• Quanto a cidade estaria disposta a pagar pela possibilidade de
utilizar mais um dam3 de capacidade de armazenamento na
albufeira?
– Preço sombra da restrição sobre o volume de encaixe de
cheias;
– 0 milhares de euros/dam3
– Só está a utilizar 6.6 dam3 dos 10 dam3 que tem disponíveis.
• Quanto a cidade está a pagar pela imposição de não permitir a
construção de um dique com uma altura superior a 4 m?
– Preço sombra da restrição sobre a altura máxima do dique;
– Custo = 240 milhares de euros/m
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
171
Ex.1 - Mitigação de cheias
Análise de sensibilidade
• Max Z=c1H+c2V
– c1 = 200
– c2 = 150
• Qual é a sensibilidade da solução
encontrada a variações dos
coeficientes da função objectivo
•
•
•
•
•
•
Max Z=c1H+c2V
H = 1/c2 x Z- c2/c1 x V
c2/c1 > 8/13.3
c2 > 0,6 x c1
Se c1 = 200 -> c2 > 120
Se c2 = 150 -> c1 < 250
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
H
4
10
13,3
V
172
Exemplo 2
Abastecimento de água
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
173
Ex.2 - Abastecimento de água
•
•
•
•
Uma cidade necessita de garantir um abastecimento de água de 500 dam3 por
ano. Para resolver este problema existem duas soluções: a construção de uma
barragem num local próximo da cidade ou a construção de um sistema de
adução a partir de um aquífero existente localizada a uma grande distância da
cidade.
O local escolhido para construir a barragem permite o armazenamento de água
até um máximo de 20 000 dam3. Cada dam3 de armazenamento custa 500
euros e proporciona um abastecimento garantido de 0,04 dam3/ano.
Os custos de construção do sistema de adução são de 50 mil euros por
dam3/ano de capacidade de transporte. Dado que o aquífero que alimenta o
sistema de adução só pode garantir o fornecimento de máximo de 800
dam3/ano não há interesse em construir um sistema com uma capacidade de
transporte superior a esse valor.
A construção destas duas infra-estruturas exige uma rede logística para fazer
chegar máquinas e materiais à região. A fim de reduzir o impacto da
construção na região foi acordado com a população limitar o número de
camiões que transitam a 50/dia. A construção de cada 1000 dam3 de
armazenamento da albufeira exige 2 camiões/dia. A construção de cada 100
dam3/ano de capacidade de transporte exige 5 camião por dia.
– Qual é a solução mais barata ?
– Quanto é que custa o acordo de limitar o número de camiões?
– Quanto é que a cidade estaria disposta a pagara para conseguir um maior
abastecimento garantido por parte da albufeira a montante do sistema de
adução?
IST: Gestão Integrada de Bacias Hidrográficas
© Rodrigo Proença de Oliveira, 2008
174
Ex.2 - Abastecimento de água
Formulação / Resolução
•
•
•
•
Variáveis de decisão
– V – Volume de armazenamento (mil dam3)
– A – Capacidade de adução (dam3/ano)
Função objectivo
– Min 500V + 50A (milhares de euros)
Restrições:
– Local de construção: V <= 20
– Recarga do aquífero: A <= 800
– Necessidades de água: 40V + A >= 500
– Acordo: 2V + 0,05A <= 50
– V >=0; A >=0.
Solução óptima
– A = 0 dam3/ano
– V = 12,5 mil dam3
– Custo = 6250 mil euros
IST: Gestão Integrada de Bacias Hidrográficas
•
A
1000
800
500
V
12,5
20
25
Preços sombra
– Local de construção: 0 euros/dam3
– Necessidades:
• Nova solução: A=0, V=12,525,
Custo=6262.5
• Preço sombra: 12,5 mil
euros/dam3/ano
– Acordo: 0
© Rodrigo Proença de Oliveira, 2008
175