O USO DA DOMINÂNCIA NO PROBLEMA DA ÁRVORE GERADORA MÍNIMA COM PARÂMETROS FUZZY
O problema da árvore geradora mínima com parâmetros fuzzy é um dos principais problemas da programação matemática fuzzy, visto que possui aplicações nas mais diversas áreas, como, por exemplo, redes de distribuição de energia, armazenamento de informações e transportes. Neste trabalho é proposto um algoritmo exato para o problema da árvore geradora mínima com estrutura crisp e parâmetros fuzzy. Trata-se de uma adaptação do algoritmo clássico de Prim, utilizando a relação de dominância de alguns trabalhos da literatura que tratam do problema de caminho mínimo fuzzy. As incertezas nos pesos são abordadas por meio da teoria dos conjuntos fuzzy e as árvores geradoras do conjunto solução são armazenadas usando o conceito de rótulos. O algoritmo proposto foi testado em três diferentes redes, compatíveis às instâncias dos principais trabalhos da literatura.
O USO DA DOMINÂNCIA NO PROBLEMA DA ÁRVORE GERADORA MÍNIMA COM PARÂMETROS FUZZY
-
DOI: 10.22533/at.ed.4932225034
-
Palavras-chave: algoritmo de Prim; programação matemática; teoria de grafos; teoria dos conjuntos fuzzy.
-
Keywords: fuzzy sets theory; graphs theory; mathematical programming; Prim’s algorithm.
-
Abstract:
The minimum spanning tree problem with fuzzy parameters is one of the main problems in fuzzy mathematical programming, as it has applications in several areas, such as, power distribution networks, information storage and transportation. This work proposed an exact algorithm to the problem of minimum spanning tree problem with crisp structure and fuzzy parameters. It is an adaptation of the classic algorithm Prim, using the dominance relationship based on some literature review dealing with the fuzzy shortest path problem. The uncertainties in the weights are addressed using the Fuzzy Set Theory, while the spanning trees in the solution set are stored using the concept of labels. The proposed algorithm was tested on three different networks, compatible with the instances found in the main literature reviews in the area.
-
Número de páginas: 26
- Fabio Hernandes
- Mauro Henrique Mulati
- Lucas Fernando Frighetto
