EAD 350 1 Sem 2017 2ª aula contin caminho minimo caminho critico fluxo maximo

Prévia do material em texto

Modelos de Redes – 2ª aula - continuação
Algoritmos para cálculo de
Distância mínima (caminho mais curto) 
Distância máxima (caminho crítico)
Fluxo máximo
EAD 350
Prof. Nicolau Reinhard
1. Sem 2017
CAMINHO MAIS CURTO
Ano da aquisição Uso por 1 ano Uso por2 anos Uso por 3 anos
1º 4000 5400 9800
2º 4300 6200 8700
3º 4800 7100
4º 4900
Custo de Reposição por anos em operação
Problema (a ser resolvido em sala de aula): 
“Qual o custo mínimo para se ter 1 carro em operação durante todos os 4 anos?
Solução:
1. Formular o problema como um modelo de rede
2. Resolver usando o algoritmo de caminho mínimo (no software PAJEK)
Reposição de frota – formulação da rede para solução pelo PAJEK
Gráfico da solução 
ótima pelo PAJEK
Resultado:
Vértice Data
Mais tarde
1 0
2 3
3 5
4 7
5 10
6 9
7 11
8 13
9 17
Problema do Caminho Crítico (mais longo)
Problema do 
Fluxo Máximo 
Modelo de Rede de transporte com 
capacidades máximas dos ramos
Fluxo máximo entre A e D4
Fonte: Taha, H.,Pesquisa Operacional, 8ª ed, Pearson, pg 121
EAD 350 1 Sem 2017
3º Exercício: cálculo de fluxo máximo 
em redes usando o software Pajek
O exercício é individual e deve ser entregue 
até as 19:00 horas do dia da próxima aula.
Formato de entrega: apenas em documento 
WORD, contendo 
1. A identificação do aluno
2. Os dados para o Pajek
3. O valor do fluxo máximo pela rede
4. Os gráficos da rede inicial e do 
fluxo máximo 
99 10
80
Dicas para a resolução via PAJEK 
Crie uma única fonte (fictícia) e um único destino 
(fictício) finais. Para isto assuma que 
1. as 3 refinarias tem um único fornecedor (nó 9), 
que pode fornecer as quantidades diárias 
máximas indicadas no gráfico
2. Os terminais enviam a sua produção para um 
único destinatário (nó 10), com as demandas 
máximas indicadas no gráfico
3. Ao criar o arquivo (formato .txt) com os dados 
para o PAJEK, use o comando *arcs para indicar 
as capacidades (ao invés de “edges”).
Esta alteração já está indicada em negrito no gráfico.
Artifício de modelagem 
para atender a restrição de 
fonte única do PAJEK
Artifício de modelagem 
para atender a restrição de 
destino único do PAJEK