Dissertação - Jorge Cipriano Fernandes dos Santos

Uma nova proposta de resolução para o problema das p-medianas ponderado

Autor: Jorge Cipriano Fernandes dos Santos (Currículo Lattes)

Resumo

Neste trabalho é apresentada uma nova abordagem para resolver o problema das p-medianas ponderado, a qual modela importantes e complexos problemas de localização. A partir de um estudo sobre a medida de centralidade de autovetor, foi observado uma forte relação entre determinação do vetor centro com a determinação da mediana de saída de um grafo não-dirigido, onde a centralidade de autovetor hierarquiza os vértices segundo a importância de cada um. Um algoritmo que combina o Método das Potências com o algoritmo clássico de Teitz e Bart é desenvolvido com o intuito de possibilitar uma maior avaliação sobre os resultados observados. Testes computacionais realizados com redes pequenas e médias geradas aleatoriamente mostraram que a busca da centralidade de autovetor de um vértice aponta para uma solução das medianas, indicando que o Método das Potências pode ser um fator determinístico da solução inicial para o método de Teitz e Bart.

TEXTO COMPLETO

Palavras-chave: P-medianasMétodo de potênciasProblemas de localização