Fluxo de Redes e Logística de Distribuição

Universidade Estadual do Oeste do Paraná
Campus de Cascavel
Curso de Bacharelado em Ciência da Computação
Pesquisa Operacional

Fluxo de Redes e Logística de Distribuição

Cascavel, 2013
1 INTRODUÇÃO

A primeira noção que se pode ter ao se falar em fluxo de redes pode ser o abastecimento de água através de um sistema de encanamento, sistemas de abastecimento de mercadorias em um conjunto de localidades, ou até mesmo a quantidade de dados que percorre uma rede de computadores. O Problema do Fluxo Máximo em Redes corresponde a calcular uma quantidade máxima de unidades de um produto que passam por esses sistemas. Algoritmos específicos para determinados tipos de problemas podem ser mais convenientes para a sua solução do que algoritmos mais genéricos. Para cada problema de otimização, deve-se, primeiramente, verificar se ele pode ser resolvido por um determinado algoritmo exato. No entanto, para muitas tarefas de otimização, não existe algoritmo eficiente, como, por exemplo, uma grande variedade de problemas do mundo real que pode ser modelada como problemas de otimização combinatória. Em geral, problemas complexos e de larga-escala são considerados difíceis de resolver e não podem ser resolvidos de maneira eficiente por técnicas determinísticas.

2 CONCEITOS BÁSICOS

Uma rede de fluxo é um grafo direcionado onde cada aresta tem uma capacidade e um fluxo associados. Um grafo é uma estrutura composta por um conjunto X de elementos chamados vértices ou nós e um conjunto A de pares de vértices, chamados arcos ou arestas. A representação gráfica de um grafo é feita por pontos (vértices) e linhas (arestas) unindo estes pontos. O fluxo na aresta não pode ultrapassar sua capacidade. Além disso, um fluxo deve satisfazer a restrição de conservação de fluxo, ou seja, a quantidade de fluxo que entra em um vértice é a mesma que sai, com exceção de um nó fonte (denotado por s), de onde só sai fluxo e um nó