A utilização de grafos na engenharia de produção

Faculdade Santa Rita – FASAR

Phillipe Henrique Corrêa Barros – [e-mail]

A Utilização de Grafos na Engenharia de Produção

Em matemática e ciência da computação, grafo é o objeto básico de estudo da teoria dos grafos. Tipicamente, um grafo é representado como um conjunto de pontos (vértices) ligados por retas (as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são representadas por "setas". Os grafos são muito úteis na representação de problemas da vida real, em vários campos profissionais. Por exemplo, pode-se representar um mapa de estradas através dos grafos e usar algoritmos específicos para determinar o caminho mais curto entre dois pontos, ou o caminho mais econômico. Assim, os grafos podem possuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo total em estudo será calculado a partir destes pesos. Grafos podem ser utilizados também em redes PERT no âmbito do planejamento de projetos. Neste caso, a cada aresta está associado o custo de execução, e as tarefas precedentes de uma outra serão suas afluentes. Outro exemplo é o caso das redes de computadores, sendo cada terminal representado por um vértice, o cabo de rede pelas arestas e o custo associado a latência, por exemplo, ou o número de máquinas que a comunicação atravessa entre os nós. É nestes princípios que assenta todo o protocolo IP que torna possível a Internet ser uma realidade. Grafos têm sido utilizados para representar o formalismo das redes complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido.

Grafos na Engenharia de Produção A teoria de grafos é um campo de conhecimento amplo que, devido a sua vasta aplicabilidade, tem atraído o interesse de pesquisadores em diversas áreas. No caso específico dos problemas encontrados em Engenharia de Produção, grafos são úteis, por exemplo, na modelagem de redes de distribuição, seqüenciamento de produção, e problemas