Trabalho-unid2

Prévia do material em texto

OTIMIZAÇÃO DE DISTRIBUIÇÃO DE ENERGIA USANDO
FLUXO MÁXIMO CUSTO MÍNIMO
ENERGY DISTRIBUTION OTIMIZATION USING MAXIMUM FLOW MINI-
MUM COST
Lucas Pires de Souza Marcolino
lucas.marcolino.093@ufrn.edu.br
Tanhleno Teixeira de Sousa
tts.tanhleno@gmail.com
Professoras
elizabeth.goldbarg@ufrn.br, silvia@dimap.ufrn.br
RESUMO
No contexto do presente trabalho, conduziremos uma revisão do estado-da-arte e dos
trabalhos relevantes que abordam o problema de otimização da distribuição de energia
utilizando a teoria de grafos. Especificamente, investigaremos a aplicação do problema
de fluxo máximo - custo mínimo em redes para a solução desse desafio. Formaliza-
remos o problema real e apresentaremos sua modelagem em grafos, ressaltando a
importância e os benefícios dessa abordagem. Além disso, proporemos um algoritmo
para a resolução eficiente desse problema de otimização na distribuição de energia.
Através desse estudo, buscamos contribuir para a compreensão e o avanço das técni-
cas de otimização aplicadas ao setor energético.
Palavras-chave: otimização. distribuição de energia. fluxo máximo custo mínimo.
ABSTRACT
In the context of this work, we will conduct a state-of-the-art review and examine rele-
vant studies that address the optimization problem of energy distribution using graph
theory. Specifically, we will investigate the application of the maximum flow - minimum
cost problem in networks to solve this challenge. We will formalize the real-world pro-
blem and present its graph modeling, emphasizing the importance and benefits of this
approach. Additionally, we will propose an algorithm for efficiently solving this optimi-
zation problem in energy distribution. Through this study, we aim to contribute to the
understanding and advancement of optimization techniques applied in the energy sec-
tor.
Keywords: otimization. energy distribution. maximum flow minimum cost.
Universidade Federal do Rio Grande do Norte. Campus Natal. Curso Bacharelado em Tecnologia da
Informação. 15 de maio de 2023.
2
1 INTRODUÇÃO
Na sociedade moderna, a otimização de processos é fundamental para proporci-
onar melhorias em serviços e produtos, tornando a produção mais eficiente e redu-
zindo custos. Isso permite que empresas possam investir em inovação, melhorando a
qualidade de seus serviços e produtos, avançando a fronteira do desenvolvimento da
sociedade como um todo.
Uma ferramenta poderosa para a modelagem e solução de problemas que envol-
vem relações entre entidades é a teoria dos grafos. Desde o século XVIII, esta área
tem sido objeto de constante estudo e evolução, apresentando soluções para diversos
problemas em áreas como redes de transporte, telecomunicações, logística, bioinfor-
mática, distribuição de energia, entre outras.
Formalmente, um grafo é um par ordenado G = (V,E), em que V é o conjunto de
vértices e E é o conjunto de arestas, em que cada aresta é definida por um par de
vértices em V . Os grafos podem ser orientados ou não orientados, e sua capacidade
de abstração e flexibilidade para adicionar restrições faz com que seja uma ferramenta
útil para a solução de problemas.
Neste trabalho, traremos um algoritmo para otimizar a distribuição de energia em
uma determinada região, utilizando modelagem em grafos e sua respectiva solução
para o problema de fluxo máximo - custo mínimo. Para isso, descrevemos o problema
real, modelamos o problema em grafos e apresentamos uma revisão dos trabalhos
relevantes para a área. Também traremos uma abordagem algorítmica que utiliza a te-
oria dos grafos para resolver o problema real de otimização de distribuição de energia.
2 DESENVOLVIMENTO
Aqui onde iremos detalhar sobre o problema real, a modelagem em dados e discutir
sobre os estudos relevantes em relação aos dois.
2.1 Problema real
Ao pagar a conta de energia, o consumidor arca com diversos custos, incluindo o
consumo de energia, os custos de geração e de distribuição. Para reduzir o preço final
da energia para o cliente, uma estratégia eficaz é otimizar a distribuição de energia,
que frequentemente é um dos principais componentes do custo final.
É importante ressaltar que, além dos custos de distribuição, também existem os
custos de geração de energia. No entanto, a geração de energia elétrica e outras
formas de conversão de energia são limitadas por fatores naturais, como a disponibili-
dade de combustíveis fósseis, a necessidade de uma queda d’água para hidrelétricas
e as variações climáticas para usinas eólicas e solares. Além dessas limitações, te-
mos a eficiência limite de Carnot, que é o máximo teórico de eficiência que pode ser
alcançado na conversão de qualquer forma de energia. Portanto, é crucial que sejam
implementadas estratégias para otimizar a distribuição de energia, a fim de minimizar
os custos e maximizar a eficiência geral do sistema de energia.
Universidade Federal do Rio Grande do Norte. Campus Natal. Curso Bacharelado em Tecnologia da
Informação. 15 de maio de 2023.
3
2.2 Modelagem do problema em grafos
A otimização da distribuição de energia desempenha um papel fundamental na
redução dos custos para o consumidor final. Além dos gastos com a quantidade de
energia utilizada e o custo de geração, o custo de distribuição é um dos principais com-
ponentes que justificam o preço pago pelo cliente. Nesse contexto, a modelagem do
problema em grafos surge como uma abordagem eficiente e flexível para a resolução
desse desafio complexo.
Para realizar a modelagem do problema de otimização da distribuição de energia
em grafos, é necessário definir a estrutura do grafo, os vértices e as arestas, bem como
os atributos que representam cada componente do sistema de distribuição. Considera-
remos um grafo direcionado G = (V,E), em que V representa os vértices, que incluem
pontos de distribuição e pontos finais do processo de distribuição, e E representa as
arestas, que representam as conexões entre esses pontos no sistema de distribuição
de energia.
Cada aresta (u, v) do grafo possui uma função de custo c(e) associada, refletindo
o custo de distribuição entre os pontos u e v por unidade de fluxo. Além disso, temos
uma fonte s, que representa o ponto inicial de distribuição de energia, correspondente
ao gerador de energia, e uma lista de sumidouros t = [t1, t2,…, tn], que são os pontos
finais do processo de distribuição, como residências ou edifícios comerciais.
Para resolver o problema de otimização, buscamos encontrar o fluxo máximo f
de s para t que minimize o custo total de distribuição, levando em consideração as
capacidades mínimas u(u, v) e máximas U(u, v) de cada aresta (u, v). É importante
destacar que a capacidade máxima de transmissão por unidade de tempo é atribuída
aos pontos de distribuição intermediários no caminho entre a fonte e os sumidouros.
Isso implica que cada ponto de distribuição possui um valor máximo de fluxo de energia
e apresenta fluxo de entrada e saída.
Além disso, cada sumidouro ti pertencente a t possui uma demanda d que precisa
ser cumprida. Garantir que o fluxo máximo de energia da fonte para os sumidouros
atenda a essa demanda total é um requisito fundamental para garantir o suprimento
adequado de energia.
Ao incorporar esses elementos namodelagem do problema de distribuição de ener-
gia em grafos, obtemos uma representação abrangente e precisa do sistema. A formu-
lação matemática do problema, incluindo variáveis, restrições e objetivo de otimização,
permite a aplicação de algoritmos eficientes para encontrar soluções que minimizem
os custos de distribuição de energia.
Portanto, a modelagem em grafos apresenta-se como uma abordagem adequada
e promissora para resolver o desafiador problema de otimização da distribuição de
energia, possibilitando melhorias significativas nos custos e na eficiência do sistema,
beneficiando tanto as empresas de energia quanto os consumidores.
2.3 Proposta de algoritmo
Primeiramente, introduziremos um sumidouro t’ onde cada ti pertencente a t es-
tará conectado ao sumidouro t. Para isso, considere: c(ti, t’) = 0, u(ti,t’) = U(ti, t’) =
Universidade Federal do Rio Grande do Norte. Campus Natal. Curso Bacharelado em Tecnologia da
Informação. 15 de maio de 2023.
4
f(ti, t’) para todo ti pertencente a t. Além disso, em trabalhos posteriores serão ne-
cessárias adaptações do algoritmo para que a restrição da demanda também seja
cumprida.
O algoritmo utiliza uma lista de adjacência para armazenar a estrutura do grafo
direcionado. Para facilitar a implementação, também será utilizada listas de adjacência
indicando o grau de saída, OD, e o grau de entrada, ID, para cada nó. Também
teremos campos nas arestas indicando a capacidade, o fluxo e o custo por unidade de
fluxo.
No algoritmo, inicializa-se cada nó com distância infinita a partir da fonte s, exceto
esta. A partir disso, todos os nós que possuem grau de entrada maior que dois estarão
presente em um conjunto S1 e todos os nós que possuem grau de saída maior que dois
estarão em outro conjunto S2. Isso será feito com o intuito de salvar todos os caminhos
entre os vértices de S1 para S2 em um array bidimensional através de uma DFS.
Após esse processamento, caso exista mais de um caminho do vértice vi para
um vértice vj, a escolha dos caminhos serão feitas para respeitar as restrições do
problema.
3 LINKS IMPORTANTES
Emhttps://whatswatt.com.au/how-are-energy-prices-set/: :text=Understanding%20your
%20electricity%20bill%20is,network%20costs%20and%20government%20costs está
presente a distribuição de custos compostos pelo preço pago pelo cliente final na conta
de luz.
Emhttps://www.geeksforgeeks.org/minimum-cost-maximum-flow-from-a-graph-using-
bellman-ford-algorithm/ temos a definição de fluxo máximo custo mínimo bem como
outra abordagem algorítmica.
Emhttps://mundoeducacao.uol.com.br/fisica/ciclo-carnot.htm: :text=De%20acordo%20com%20Carnot%2C%20o,de%20calor%20que%20ela%20recebe
temos a explicação do que é o limite de Carnot.
4 CONSIDERAÇÕES FINAIS / CONCLUSÕES
Dessa forma, utilizando o algoritmo proposto é possível resolver de forma satis-
fatória o problema de otimização de distribuição de energia. Esperamos, assim, que
possamos contribuir para a compreensão e o avanço das técnicas de otimização apli-
cadas ao setor energético fomentando essa discussão.
5 REFERÊNCIAS BIBLIOGRÁFICAS
Sankowski, P.; Wirth, H.-C. Maximum Flow and Minimum-Cost Flow in Almost-
Linear Time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, p. 1682-
1696. Acesso em: 15/05/2023.
LIU, J. et al. Urban Regional Building Energy Planning Model under the Guidance
of Network Flow Theory. Processes, [S.l.], v. 11, n. 1, p. 8, dez. 2022. Disponível em:
Universidade Federal do Rio Grande do Norte. Campus Natal. Curso Bacharelado em Tecnologia da
Informação. 15 de maio de 2023.
5
https://www.mdpi.com/2227-9717/11/1/8. Acesso em: 15/05/2023.
XU, C. A Simple Solution to Maximum Flow at Minimum Cost. In: 2010 2nd In-
ternational Conference on Information Engineering and Computer Science. [S.l.: s.n.],
2010. Disponível em: https://ieeexplore.ieee.org/abstract/document/5677684. Acesso
em: 15/05/2023.
Universidade Federal do Rio Grande do Norte. Campus Natal. Curso Bacharelado em Tecnologia da
Informação. 15 de maio de 2023.
	Introdução
	Desenvolvimento
	Problema real
	Modelagem do problema em grafos
	Proposta de algoritmo
	Links importantes
	Considerações finais / Conclusões
	Referências bibliográficas