Teoria dos grafos e uma aplicação de problema de caminho mínimo utilizando programação linear

Abstract

O mundo está rodeado de conjuntos de objetos que se relacionam de alguma forma, sejam em relações de amizade, comerciais, econômicas, organizacionais, entre outras. Existem estruturas matemáticas que representam essas relações graficamente. Os Grafos são estruturas gráficas que representam um conjunto de objetos e suas relações. Para realização deste trabalho utilizou-se de uma pesquisa descritiva por meio de uma revisão bibliográfica acerca dos temas abordados. O objetivo deste trabalho é introduzir a teoria dos grafos, seus conceitos e definições, e apresentar uma aplicação real envolvendo o problema de caminho mínimo. O problema consiste em um taxista que deve partir de um ponto e chegar a outro utilizando o caminho com menor distância. Este foi descrito por meio de grafos e pesquisa operacional, valendo-se da programação linear. Utilizou-se os softwares LINDO e Solver para resolução do problema. O resultado obtido por meio da modelagem como problema de programação linear foi validado utilizando o resultado determinado por meio do google maps.