Formulação de Problemas
de Programação Linear em
Recursos Hídricos
Exemplos e solução via Excel
Prof. Benedito C. Silva
IRN/UNIFEI
Dimensionamento econômico de uma
adutora
Dimensionar uma linha adutora com dois pontos de derivação de
vazões (B e C). Admite-se que o trecho AB possa ser dimensionado
com diâmetro D1=250mm e D2=200mm, uma vez que ambos atendem
ao requisito de velocidade máxima para a vazão nesse trecho (40 l/s).
Da mesma forma, no trecho BC admite-se os diâmetros D3=200mm e
D4=150mm são compatíveis com a vazão neste trecho (14 l/s).
10m
A
40 l/s
500m
B
0m
14 l/s
26 l/s
400m
C
14 l/s
Cada tubulação de um certo diâmetro tem um custo por metro
linear ($/m) e cada vazão produz uma perda de caga unitária
(m/m), conforme tabela abaixo.
Diâmetro
(mm)
Perda de carga unitária J (m/m)
Vazão de 40 l/s
Vazão de 14 l/s
Custo Unitário
($/m)
250
0,0025
---
5
200
0,0071
0,0010
4
150
---
0,0042
3
Deseja-se fazer o dimensionamento de mínimo custo,
atendendo a uma pressão mínima de 5 mca no
ponto C.
Resolvendo via EXCEL
Equacionamento do problema:
Min C = 5X1 + 4X2 + 4X3 + 3X4
s.a.
X1 + X2 = 500
X3 + X4 = 400
0,0025X1 + 0,0071X2 + 0,001X3 + 0,0042X4 ≤ 5
Não negatividade
X1, X2, X3, X4 ≥ 0
Resolvendo via EXCEL
Atribuir valores iniciais
para as variáveis do
problema
Serão usados na F.O.
Criar uma célula com a
equação da F. O.
A equação deve ser
dependente das células da
variáveis
Resolvendo via EXCEL
Valor da F.O. para todas as
variáveis iguais a 1
Valor da F.O. para um
novo valor de X1
Mudanças nas
variáveis alteram
automaticamente o
valor da F.O.
Resolvendo via EXCEL
O mesmo de ser feito para
as equações das restrições
principais
Somente o lado esquerdo
das restrições
Resolvendo via EXCEL
As restrições de não
negatividade não precisam ser
escritas
Resolvendo via EXCEL
O Solver...
Resolvendo via EXCEL
Caso o Solver não apareça no menu Dados...
Resolvendo via EXCEL
O Solver...
Resolvendo via EXCEL
Adicionando restrição...
Resolvendo via EXCEL
Não esquecer da
não negatividade
das variáveis
Resolvendo via EXCEL
Valores encontrados pelo
Solver
Otimização do transporte entre captação
e distribuição de água
Seja uma certa região que conta com três mananciais (Mi) e quatro reservatórios
(Rj) distribuidores de água. Cada manancial tem uma capacidade de suprimento
hídrico (hm3/mês) e em cada reservatório concentra-se uma demanda
(hm3/mês). O abastecimento de cada reservatório pode ser feito a partir de
qualquer manancial, exceção feita em relação à ligação entre M3 e R4. Os
custos unitário ($/hm3) de transporte (bombeamento) são apresentados na
tabela a seguir.
Custos unitário de transporte de
água ($/hm3)
R1
R2
R3
R4
Capacidade do
Manancial
(hm3/mês)
M1
16
13
22
17
70
M2
14
13
19
15
90
M3
19
20
23
---
80
Demandas nos
reservatórios
(hm3/mês)
60
80
40
60
---
Otimização do transporte entre captação
e distribuição de água
Deseja-se planejar a alocação de água aos
reservatórios de maneira ótima, visando a
minimização dos custos totais de transporte.
Otimização do transporte entre captação
e distribuição de água
R1
Vazão do Manancial
M1 para o
reservatório R1
X1,1
M1
M2
X3,1
X2,1
X1,2
R2
X2,2 X
3,2
X2,3
X1,3
X3,3
M3
X2,4
R3
X1,4
R4
Produção e tratamento ótimo de
resíduos de uma indústria
Uma indústria de manufaturados possui uma estação de
tratamento de resíduos (ETR), operada pela própria
indústria. O preço de venda do produto fabricado pela
indústria é de $10/unidade. No entanto o custo de
produção desse mesmo produto é de $3/unidade. No
processo de fabricação utilizado são geradas duas
unidades de resíduos para cada unidade de produto
fabricado.
Deseja-se decidir sobre: (a) a quantidade diária a ser
produzida; (b) a quantidade diária de resíduos sem
tratamento a ser lançada no curso d’água. Deve ser
buscar o máximo benefício líquido total.
Produção e tratamento ótimo de
resíduos de uma indústria
A ETR tem capacidade máxima para tratar 10 unidades
de resíduos diários, com eficiência para remover 80% do
resíduo. O custo do tratamento é de $0,60/unidade de
resíduo tratado. Seguindo o princípio do “usuário
pagador”, também existe uma taxa de $2/unidade de
resíduo não tratado no curso d’água.
O comitê da bacia local estabeleceu o limite máximo de 4
unidades diárias de resíduos a serem lançados no curso
d’água para esta indústria.
Produção e tratamento ótimo de
resíduos de uma indústria
Indústria
X1 (quantidade diária produzida)
2X1 (resíduos)
(2X1 –X2)
X2(resíduos lançados
diretamente)
E. T. R.
0,20(2X1-X2)
(resíduos
remanescentes)
Operação de reservatório
Considere um reservatório que através de suas vazões defluentes
alimenta usina hidrelétrica, localizada imediatamente a jusante, um
sistema de irrigação, também a jusante, e mantém a vazão ecológica
do rio.
Vazões até 180.106 m3/mês podem ser usadas para alimentar as
turbinas da usina, sendo o excesso descarregado pelos vertedores.
Os limites máximos de água que podem ser desviados para irrigação
são apresentados na coluna 4 da tabela a seguir, sendo que a
irrigação ocorre apenas em 6 meses do ano.
A vazão mínima para fins ecológicos é de 20.106 m3/mês.
A capacidade de armazenamento do reservatório é de 600.106 m3.
Operação de reservatório
A receita obtida pelo suprimento de água para a irrigação é de $900
por milhão de m3 fornecido.
Cada milhão de m3 de água usado para geração de energia resulta
em lucro de $400.
O problema consiste em determinar a sequencia de defluências
mensais do reservatório que maximiza a receita, dadas as vazões de
entrada na tabela a seguir.
Operação de reservatório
Mês
Vazão
afluente
(106m3)
Demanda de
irrigação
(106m3)
JAN
95
0
FEV
112
0
MAR
170
0
ABR
250
0
MAI
265
50
JUN
62
150
JUL
35
260
AGO
18
260
SET
55
190
OUT
88
100
NOV
85
0
DEZ
90
0
Alocação de carga de poluição
Agências reguladoras impuseram critérios de qualidade da água,
exigindo que a concentração de um determinado poluente não
exceda 120mg/l (0,12 kg/m3) em qualquer ponto de um sistema
de rios. Quatro estações de tratamento descarregam resíduos
tratados nesse sistema. Outras fontes de poluição no local são
desprezíveis. As estações de tratamento são operadas de forma
coordenada para alcançar os padrões de qualidade, com objetivo
de minimizar os custos diários de operação das 4 estações.
Conforme a água escoa pelo cursos dos rios. Há uma processo
natural de redução da carga de poluentes. As taxas e redução
para cada trecho do sistema são: P1,3=10%, P2,3= 20%,
P3,4=15%
A tabela a seguir apresenta os dados técnicos de cada estação
de tratamento. Deve determinar a quantidade de poluente a ser
removido por cada estação a fim de minimizar o custo total.
Alocação de carga de poluição
Estação
Carga de
poluente
gerada pela
cidade
(1000kg/dia)
1
510
2,50
0,92
39,1
3378
2
430
1,80
0,90
45,5
3931
3
960
4,00
0,91
98,2
8484
4
920
3,50
0,92
115
9936
Custo de
tratamento Eficiência
($/1000 kg Máxima
removido)
Vazão total
na cidade
(m3/s)
Vazão total
na cidade
(1000m3/dia)
Alocação de água
Considere o sistema rio/reservatório apresentado na figura a
seguir. O reservatório A e B, localizados no nós 1 e 2 , possuem
capacidades de 750.106 e 900.106 m3, respectivamente. Os
armazenamentos iniciais nos reservatórios A e B no início do
intervalo de tempo são 460.106 e 215.106 m3, respectivamente.
Descargas de água são feitas para manter um vazão mínima no
curso d’água e para atender às necessidades de desvio de água.
Vazões mínimas para os trechos são:
Trecho
1-4
2-3
3-4
4-5
Abaixo de 5
Vazão
(106m3)
0
5
10
10
30
A disponibilidade e a demanda de água para cada nó são apresentadas
na tabela a seguir. A disponibilidade de água para cada nó consiste do
armazenamento do reservatório no início do intervalo de tempo e a
vazão local entrando no trecho de rio acima do nó, durante o período de
tempo.
Alocação de água
A demanda na tabela a seguir é uma meta de abastecimento para
cada nó. Se a disponibilidade é insuficiente para atender a
demanda, a alocação é feita de acordo com as prioridades
relativas tabeladas, sendo 5 a maior prioridade.
Nó
Armzenamento
inicial (106m3)
Vazão
local
(106m3)
Disponibilidade
total
(106m3)
Demanda
máxima
(106m3)
Prioridade
relativa
1
460
375
835
90
4
2
215
290
505
125
3
3
-
25
25
475
2
4
-
75
75
-
-
5
-
120
120
360
5
Determinar a melhor alocação da água disponível no sistema
290
Res B
2
125
5
475
375
Res A
1
25
3
10
0
75
90
4
10
360
120
5
30
Programação Linear por Redes de Fluxo
Em um modelo de redes de fluxo o sistema é representado como uma coleção
de nós e arcos. Para um sistema de rios e reservatórios, os nós são os pontos
de reservatórios, retiradas de água, confluências de tributários e outros pontos
de interesse. Nós são conectados por arcos, que representam os caminhos por
onde o fluxo é conduzido.
O formato geral de um problema de programação linear por redes de fluxo é:
Minimizar
𝐶𝑖𝑗 𝑞𝑖𝑗
Para todos os arcos
Sujeito a
𝑞𝑖𝑗 -
𝑞𝑗𝑖 = 0
𝑙𝑖𝑗 ≤ 𝑞𝑖𝑗 ≤ 𝑢𝑖𝑗
Para todos os nós
Para todos os arcos
Programação Linear por Redes de Fluxo
Onde: qij é a vazão no arco que conecta o nó i ao nó j; cij é um fator de
penalidade, custo ou peso para qij; lij é o limite mínimo para qij; uij é o limite
máximo para qij; qji é a vazão no arco que conecta o nó j ao nó i.
Alocação de água
Resolver o problema anterior utilizando Programação
Linear por Redes de Fluxo
Programação Linear Binária (zero-um)
Casos especiais da programação linear:
- PL Inteira: as variáveis de decisão são inteiras
- PL Inteira mista: algumas variáveis devem assumir valores inteiros
- PL Binária: uma ou mais variáveis são binárias (0 ou 1)
Softwares que possuem algoritmos para solução de programação linear
geralmente são capazes de resolver esses casos.
Construção de sistema de abastecimento
Um sistema de abastecimento de água deverá atender a 4 novos
consumidores de água.
O sistema possui 3 fontes possíveis (A, B e C) que podem
atender a estes usuários.
Os custo dos sistemas de captação para as fontes A, B e C são,
respectivamente: $14.200.000, $ 8.500.000 e $17.100.000.
Podem ser selecionadas uma, duas ou três fontes para serem
construídas.
Um sistema de tubulação deve ser construído para cada um dos
quatro consumidores, ao menos para uma das fontes de
suprimento.
A Tabela a seguir apresenta os custos de construção das linhas
de tubulação, as demandas de cada consumidor e a capacidade
de suprimento de cada fonte.
Custo da tubulação ($)
Cons. 1
Cons. 2
Cons. 3
Cons. 4
Capacidade
(m3/dia)
A
2.200.000
8300000
8.200.000
5.200.000
340.000
B
4.600.000
6100000
2.400.000
9.800.000
235.000
C
1.700.000
5800000
1.300.000
3.600.000
480.000
Demanda
(m3/dia)
135.000
98.000
64.000
192.000
-
Fonte
Utilizar programação linear binária para determinar quais
fontes de suprimento e linhas de tubulação devem ser
construídas
Seleção de projetos hídricos
10 projetos de estrutura estão sendo considerados dentro do
planejamento de uma bacia hidrográfica (reservatórios, sistemas de
bombeamento, hidrelétricas, controle de cheias, ...).
Os custos de investimento e as receitas líquidas anuais de cada
empreendimento estão tabeladas a seguir.
O valor máximo que pode ser investido nos projeto é $750milhões.
Os projetos 2 e 3 só podem ser implementados se 6 for construído.
O projeto 10 só pode ser construído se 8 e 9 também forem.
O projeto 4 não pode ser selecionado se 3 for selecionado.
Ao menos 1 e não mais do que 3 dos seguintes projetos podem ser
selecionados: 5, 6, 7 e/ou 8.
Utilizar programação linear binária para selecionar os projetos que
deverão ser implementados, considerando a maximização da
receita líquida.
Empreendimento
Custo de investimento
($ milhões)
Receita Líquida
Anual ($ milhões)
1
120
4
2
150
3
3
90
5
4
210
9
5
160
7
6
180
6
7
90
4
8
100
5
9
80
2
10
140
7