Tranalho P

Pesquisa Operacional
Programação em Redes
Profa. Alessandra Martins Coelho

outubro/2013

Problema de programação em redes • Modelado por meio de uma estrutura de grafo ou rede que consiste em diversos nós, cada nó deve estar conectado a um ou mais arcos.
• Aplicações:
– Produção, transporte, localização de facilidades, gestão de projetos, finanças, entre outras
– Muitos podem ser formulados como problemas de programação linear e resolvidos pelo método simplex

• Modelagem em redes:
– Facilitar a visualização e a compreensão das características do sistema

Problema de programação em redes • Exemplos de problemas:
– Transporte (clássico)
– Transbordo
– Designação de tarefas
– Caminho mais curto
– Fluxo máximo
– Árvore geradora mínima

A terminologia de Grafos e Redes
• Grafo:
– Um grafo é uma estrutura representada como um conjunto de pontos (vértices, nós) ligados por retas
(arestas).
– Dependendo da aplicação, as arestas podem ser direcionadas (arcos), e são representadas por setas.

A terminologia de Grafos e Redes
• Os vértices podem representar facilidades
(como fábricas, centros de distribuição, terminais ou portos marítimos), estações de trabalho ou Interseções;
• As arestas fazem conexões entre pares de nós, podendo representar caminhos, rotas, fios cabos, canis, entre outros.
G= (V,A)

A terminologia de Grafos e Redes
• Muitas vezes, as arestas (ou arcos) de um grafo que fazem conexões entre os nós estão associados a uma variável numérica chamada fluxo (como distância entre os nós, custo de transporte, tempo despendido, dimensão do fio, quantidade de peças transportadas, entre outras).
• Os nós de um grafo podem estar associados a uma variável numérica chamada capacidade, (podendo representar a capacidade de carga e descarga, suprimentos, demanda, entre outros).
• Um grafo cujas arestas(arcos) e/ou nós estão associados à variável numérica fluxo e/ou capacidade é chamado de rede

Rede
• Os nós podem ser subdivididos em três tipos: – oferta ou fontes
–