Menorcaminho

Universidade Federal de Itajubá
Instituto de Engenharia de Produção e Gestão

Pesquisa Operacional
Redes
Prof. Dr. José Arnaldo Barra Montevechi

1

Problemas de rede
• Casos especiais de problemas de programação linear que são mais bem analisados através de uma representação gráfica.
• Importantes problemas de otimização, tais como problemas de logística e de energia, produção e outros, são eficientemente resolvidos e modelados como problemas de rede.

2

1

Problemas de rede
• Modelos de rede facilitam a visualização das relações entre os componentes do sistema, aumentando o entendimento do problema e de seus possíveis resultados.
• É uma modelagem muita usada.

3

Terminologia
• Redes, nós e arcos:

Nós
Arcos

4

2

Problemas de rede
(Classificação usual)

• Problemas de transporte e rede de distribuição; • Problemas de menor caminho;
• Problemas de fluxo máximo.

5

Problemas de
Distribuição
• Problemas que consideram múltiplas fontes, centros consumidores e locais intermediários por onde os produtos simplesmente passam são denominados problemas de distribuição.
• O problema de transporte já estudado é uma simplificação do problema de rede de distribuição. 6

3

Problemas de
Distribuição – exemplo
• Uma montadora de carros esta iniciando as suas operações no Brasil, construindo 2 fábricas: uma na Bahia e outra em São Paulo. A montadora esta estudando a forma de distribuição de seus carros para as diversas revendas, localizadas nos estados: Goiás, Rio de
Janeiro, Minas Gerais, Paraná, Santa Catarina e
Rio Grande do Sul, que minimize o custo total de distribuição.
7

Problemas de
Distribuição – exemplo
• As capacidades instaladas de cada uma das fábricas, as demandas das revendas, bem como os custos unitários de transporte entre fábricas e revendas estão evidenciados no diagrama a seguir. 8

4

Problemas de
Distribuição – exemplo
40

BA
1

-500

25

GO
5

150

20
MG
3

30

200
20

SP
2

-600

Demandas

20

(1400)

RJ
4

15

350

20

35

PR
6

300

SC
7

150