PET MATEMÁTICA E MEIO AMBIENTE E CAMINHOS ÓTIMOS:  INTRODUÇÃO À OTIMIZAÇÃO COMBINATÓRIA

Davi Franco Tavares; Felipe Georges Barbier de Vasconcellos Pereira; Gisela Maria da Fonseca Pinto; Vinícius Leal do Forte; Eulina Coutinho Silva do Nascimento

Todos os Trabalhos

Trabalho

Título do Trabalho

PET MATEMÁTICA E MEIO AMBIENTE E CAMINHOS ÓTIMOS: INTRODUÇÃO À OTIMIZAÇÃO COMBINATÓRIA

Autores

Davi Franco Tavares
Felipe Georges Barbier de Vasconcellos Pereira
Gisela Maria da Fonseca Pinto
Vinícius Leal do Forte
Eulina Coutinho Silva do Nascimento

Modalidade

Resumo

Área temática

Ciências Exatas e da Terra - Matemática

Data de Publicação

22/04/2025

País da Publicação

Brasil

Idioma da Publicação

Português

Página do Trabalho

https://www.even3.com.br/anais/xi-raic-e-v-raidtec-ufrrj/929290-pet-matematica-e-meio-ambiente-e-caminhos-otimos---introducao-a-otimizacao-combinatoria

ISBN

978-65-272-1295-9

Palavras-Chave

Otimização Combinatória, Caminhos Ótimos, Teoria dos Grafos, Algoritmo de Dijkstra, Árvore Geradora Mínima, Educação Matemática.

Resumo

O estudo de otimização combinatória, particularmente no contexto de caminhos ótimos, é uma área fundamental dentro da pesquisa de fluxo de rede e da teoria dos grafos. A otimização combinatória lida com a busca das melhores soluções em espaços de solução discretos, e os algoritmos que abordam esses problemas são amplamente aplicados em diversas áreas, como logística, redes de comunicação e locomoção. No contexto da teoria dos grafos, um grafo é uma estrutura matemática que modela as relações entre objetos de uma coleção/conjunto. A otimização em grafos, como apresentado por [2], permite resolver problemas onde se busca a melhor rota, caminho ou fluxo dentro de uma rede, sendo os conceitos de caminhos mínimos e árvores geradoras mínimas essenciais para muitos desses problemas. Esses problemas são representados por nós e arestas, onde as arestas podem ter pesos que representam, por exemplo, distâncias, custos ou tempos. O problema do caminho mínimo é um exemplo clássico de otimização combinatória. Ele envolve encontrar o caminho de menor custo entre dois nós em um grafo ponderado. Este problema é abordado por diversos algoritmos, como o algoritmo de Dijkstra, que é eficiente em grafos com pesos não negativos, e o algoritmo de Bellman-Ford, que pode lidar com pesos negativos. Ambos os algoritmos são discutidos de forma detalhada em [3]. Outro exemplo relevante na otimização combinatória é o problema da árvore geradora mínima, onde o objetivo é conectar todos os nós de um grafo com o menor custo total possível. O algoritmo de Prim e o algoritmo de Kruskal são métodos tradicionais usados para resolver esse problema. Estes algoritmos são aplicados em redes de telecomunicações, onde é necessário conectar um conjunto de locais com o menor custo total de instalação de cabos. A combinação dessas técnicas e o estudo aprofundado dos conceitos teóricos e práticos fornecidos por [1] permite uma visão ampla e integrada da otimização combinatória. Esse texto não só apresenta os algoritmos em si, mas também discute suas aplicações em situações reais, como a otimização de cadeias de suprimentos e o planejamento de rotas para entregas. O projeto do grupo PET-Matemática visa introduzir esses conceitos para alunos de graduação, explorando tanto a teoria quanto a aplicação prática dos algoritmos de otimização combinatória. Através de atividades que simulam problemas reais, os alunos terão a oportunidade de aplicar as técnicas estudadas para resolver problemas de caminhos ótimos em grafos, promovendo o desenvolvimento de habilidades analíticas e críticas. Essas atividades serão aplicadas em formato de oficinas, sendo aplicadas principalmente em colóquios e semanas de integração. Cursos de exatas e financeiras serão o publico alvo dessas oficinas como matemática, Sistemas de informação, Economia e etc. Além disso, a elaboração de um artigo focado em introduzir a modelagem de problemas de otimização combinatória no ensino básico também está entre os objetivos do projeto. Este material servirá como uma ferramenta didática para demonstrar a relevância e a aplicabilidade da matemática discreta em contextos cotidianos, conectando conceitos avançados do ensino superior com a prática educativa em níveis de ensino anteriores. [1]HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à pesquisa operacional. McGraw Hill Brasil, 2013. [2]GOLDBARG, Marco; GOLDBARG, Elizabeth. Grafos: conceitos, algoritmos e aplicações. Elsevier, 2012. [3] Notas de aula do Prof. Caetano. Disponível em: https://shre.ink/caminhominimo

Título do Evento: XI Reunião Anual de Iniciação Científica da UFRRJ (RAIC 2024) & V Reunião Anual de Iniciação em Desenvolvimento Tecnológico e Inovação (RAIDTec 2024)
Cidade do Evento: Seropédica
Título dos Anais do Evento: Anais da XI Reunião Anual de Iniciação Científica da UFRRJ (RAIC) e V Reunião Anual de Iniciação em Desenvolvimento Tecnológico e Inovação (RAIDTec): Transição energética: impactos ambientais e sociais
Nome da Editora: Even3
Meio de Divulgação: Meio Digital

Como citar

TAVARES, Davi Franco et al.. PET MATEMÁTICA E MEIO AMBIENTE E CAMINHOS ÓTIMOS: INTRODUÇÃO À OTIMIZAÇÃO COMBINATÓRIA.. In: Anais da XI Reunião Anual de Iniciação Científica da UFRRJ (RAIC) e V Reunião Anual de Iniciação em Desenvolvimento Tecnológico e Inovação (RAIDTec): Transição energética: impactos ambientais e sociais. Anais...Seropédica(RJ) UFRRJ, 2024. Disponível em: https//www.even3.com.br/anais/xi-raic-e-v-raidtec-ufrrj/929290-PET-MATEMATICA-E-MEIO-AMBIENTE-E-CAMINHOS-OTIMOS---INTRODUCAO-A-OTIMIZACAO-COMBINATORIA. Acesso em: 07/12/2025