Modulo 6 - Redes-Transporte - Método do Custo Mínimo e MODI

Prévia do material em texto

Módulo 6 
Otimização de Fluxo em Redes (Grafos)
56
Método do Custo Mínimo
Método MODI
Prof. Ms. Antonio dos Santos
Introdução
Grafos podem ser usados para modelarmodelarmodelarmodelar oooo fluxofluxofluxofluxo dededede
materiaismateriaismateriaismateriais numa rede:
� Líquidos fluindo por tubos;
� Peças por linhas de montagem;
57
� Corrente por redes elétricas;
� Informações por redes de comunicação;
� Distribuição de produtos aos centros consumidores (transportes).
O material percorre uma rede desde uma origem,
onde ele é produzido, até um sorvedorsorvedorsorvedorsorvedor, onde ele é
consumido.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
• Planejamento de transportes (rodoviário, aéreo);
• Distribuição física de materiais (logística);
• Planejamento da operação de um sistema hidrelétrico 
(recursos hídricos);
Áreas de Aplicação:
58
(recursos hídricos);
• Transmissão de energia elétrica-rede;
• Redes de telecomunicações;
• Planejamento de Atividades- PERT- CPM.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
ConceituaçãoConceituaçãoConceituaçãoConceituação: Um grafo é uma entidade formada por nós e 
arcos
NóNóNóNó: intersecção de arcos;
ArcoArcoArcoArco: meio de transporte dos fluxos na rede;
FluxoFluxoFluxoFluxo: quantidade que circula no arco.
Otimização em Grafos
59
FluxoFluxoFluxoFluxo: quantidade que circula no arco.
1 2
3 4
(1)
(5)(2)
(3)
(4)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Fluxo de Custo Mínimo
� The Minimum Cost Flow Problem
Este problema possui papel principal entre os
modelos de otimização em redes, uma vez que este
engloba uma enorme quantidade de aplicações e
60
engloba uma enorme quantidade de aplicações e
pode ser resolvido de maneira extremamente
eficiente.
O Problema de Transporte, de Designação, de
Caminho Mais Curto e de Fluxo Máximo são casos
especiais do Problema de Fluxo de Custo Mínimo.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Fluxo de Custo Mínimo
� A rede é representada por um Dígrafo;
� No mínimo um dos nós é a origem;
� No mínimo um dos nós é um destino;
� Todos os nós restantes são entrepostos intermediários;
61
� Todos os nós restantes são entrepostos intermediários;
� A rede possui arcos com capacidade suficiente para habilitar
todos os fluxos gerados nos nós de fornecimento para
alcançar os nós de demanda;
� O custo do fluxo através de cada arco é proporcional a
quantidade daquele fluxo, onde o custo por unidade de
fluxo é conhecido.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Fluxo de Custo Mínimo
O objetivo é minimizar o custo total da passagem de
uma dada quantidade de fluxo através do grafo (um
objetivo alternativo é maximizar o lucro total para
realizar a mesma atividade.
62
Pode-se imaginar uma situação na qual se queira
trabalhar com o menor fluxo possível
No entanto, a absoluta maioria das situações práticas
acarreta o interesse em que se use ao máximo a
capacidade disponível, o que nos faz pensar em
minimizar o custo dentre os fluxos máximo existentes.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problemas de fluxos a 
custo mínimo (PFCM) 
A cada arco associa-se 
2
b1
b2
b3
X1,2 X2,3
Problema de Fluxo de Custo Mínimo
C1,2
C2,3
63
A cada arco associa-se 
um fluxo Xij e custo 
unitário Cij
A cada nó associa-se 
uma demanda bi
1
3
4
b1
b4
X3,4
X1,4
X1,3C1,3
C1,4
C3,4
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Transporte:
Oferta = Demanda
64
A condição necessária e suficiente para um problema de
transporte com n fábricas e m centros consumidores tenha
solução é dada por:
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
solução é dada por:
Total da Capacidade = Total da Demanda
∑ fi = ∑ dj
n m
i =1 j =1
Problema de Transporte:
Oferta diferente da Demanda
65
A regra das variáveis fantasma (Dummy):
No caso da Capacidade ≥ Demanda devemos introduzir um 
destino fantasma.
No caso da Capacidade ≤ Demanda devemos introduzir uma 
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
No caso da Capacidade ≤ Demanda devemos introduzir uma 
origem fantasma.
Todos os custos relacionados as variáveis fantasma serão 
nulos
A origem ou destino fantasma será dado pela diferença entre 
o total ofertado e o total demandado. 
Método do Custo Mínimo
Oferta = Demanda
Seja o Problema de Transporte abaixo determinar a solução de 
menor custo pelo Método do Custo Mínimo.
ORIGEM DEMANDA
66
ORIGEM DEMANDA
50 O1 
D1 100
100 O2
D2 170
120 O3
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Método do Custo Mínimo
ORIGEM DEMANDA
50 O1 
C1,1=10
C1,2=12
C2,1=20X1,1
67
50 O1 
D1 100
100 O2
D2 170
120 O3
Xij = quantidade do local “i” para o local “j”.
C2,2= 8
C3,1= 6
C3,2= 15
X1,2
X2,1
X2,2
X3,1
X3,2
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Método do Custo Mínimo
Passo 1: 
Selecionar a 1ª.rota mais barata e 
alocar a máxima carga permitida.
1ª rota mais barata: C3,1 = 6 
Alocar carga = 100
68
Alocar carga = 100
Passo 2: 
Selecionar a 2ª.rota mais barata e 
alocar a máxima carga permitida.
2ª. Rota mais barata: C2,2 = 8
Alocar carga = 100
100
100
50
20
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Método do Custo Mínimo
Passo 3: Continuar na seqüência até
que todas as cargas sejam alocadas.
3ª. Rota mais barata: C1,1 = 10 Para D1 a carga já está completa
4ª. Rota mais barata: C1,2 = 12 Alocar carga = 50
69
5ª. Rota mais barata: C1,2 = 15 Alocar carga = 20
Passo 4: Calcular o Custo Total:
[O3 D1] + [ O2 D2] + [O1 D2] + [O3 D2]
(6 x 100) + ( 8 x 100) + ( 12 x 50) + (15 x 20)
Custo Total = $ 2300,00
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Exercício 1: Problema de Transporte
Caso Computadores Goiaba
� A Computadores Goiaba possui 3 fábricas localizadas no Rio, São
Paulo e Belo Horizonte. A produção deve ser entregue em Recife,
Salvador e Manaus. Considerando os custos de transporte unitários, as
capacidades de produção das fábricas e as demandas dos centros
consumidores que estão especificados na tabela a seguir, determine
quanto deve ser produzido e entregue por cada fábrica em cada centro
70
Centro Consumidor
Fábrica Recife Salvador Manaus Capacidade
Rio 25 20 30 2000
São Paulo 30 25 25 1500
B.Horizonte 20 15 23 1500
Demanda 2000 2000 1000
quanto deve ser produzido e entregue por cada fábrica em cada centro
consumidor de forma a minimizar os custos de transporte.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Transporte:
Programação Linear
� Existem 9 variáveis para expressar a quantidade 
transportada em cada uma das possíveisvias. 
� xij = Quantidade transportada da fábrica i para o centro 
consumidor j.
71
consumidor j.





−
−
−
=
HorizonteBelo3
PauloSão2
Rio1
i





−
−
−
=
Manaus3
Salvador2
Recife1
j
Problema de Transporte:
Programação Linear: Variáveis de Decisão
RIO REC
x11
x12
x13
x21
Centro 
Consumidor
Fábrica REC SSA MAN
72
SP
BHZ
SSA
MAN
x21
x22
x23
x31
x32
x33
Fábrica REC SSA MAN
Rio x11 x12 x13
SP x21 x22 x23
BH x31 x32 x33
Problema de Transporte:
Programação Linear: Modelagem
s.a
231520
252530302025
333231
232221131211
+++
+++++
xxx
xxxxxxMin
73
0
1000
2000
2000
1500
1500
2000
s.a
332313
322212
312111
333231
232221
131211
≥
=++
=++
=++
=++
=++
=++
ijx
xxx
xxx
xxx
xxx
xxx
xxx
Problema de Transporte:
Exercício 2
� A Labor Ltda. é um laboratório de manipulação que possui 
duas filiais, uma no Centro e uma na Barra. A Labor presta 
serviços de entrega para seis bairros distintos. Os dados de 
capacidade das filiais, a demanda por bairro e os custos de 
transporte encontram-se na tabela abaixo.
74
transporte encontram-se na tabela abaixo.
� Resolva pelo Método do Custo Mínimo.
Filiais Capacidade Custos de Transporte
Ipanema Copacabana Centro Barra Leblon Tijuca
Centro 2500 7 9 1 12 7 4
Barra 2000 4 5 12 1 3 8
Demanda 1400 1060 400 150 870 620
Problema de Transporte: Exercício 2
Melhorando a solução do Método do Custo Mínimo
MÉTODO MODI (Modified Distribution)
� A
Solução inicial 1) Rota mais cara: X12 (9,0) 
Filiais Capacidade Custos de Transporte
Ipanema Copacabana Centro Barra Leblon Tijuca
Centro 2500 7 9 1 12 7 4
Barra 2000 4 5 12 1 3 8
Demanda 1400 1060 400 150 870 620
75
Solução inicial 1) Rota mais cara: X12 (9,0) 
X13 = 400 x 1 2) Vale a pena usar a rota X22 - Enviar 1 unidade em X22 (+5)
X24 = 150 x 1 3) Reduzir fluxo de X12 – Retirar 1 unidade em X12 (-9)
X25 = 870 x 3 4) Barra deixa de atender (Ipanema). Retirar 1 unid. em X21 (-4)
X21 = 980 x 4 5) Centro atende Ipanema . Enviar 1 unidade em X11 (+7)
X16 = 620 x 4 SOMA (Variação Líquida) (+5 –9 -4 +7) = (-1)
X11 = 420 x 7 Conclusão: Vale a pena pois vai diminuir o custo. 
X12 = 1060 x 9 Quantas unidades? Se utilizar X22 vou reduzir X21 em 980 unid.
CT = 22.040,00
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Transporte: Exercício 2
Melhorando a solução do Método do Custo Mínimo
MÉTODO MODI (Modified Distribution) 
Solução Inicial Nova Solução 
X13 = 400 x 1 (permanece) X13 = 400 x 1 = 400,00
X24 = 150 x 1 (permanece) X24 = 150 x 1 = 150,00 
X25 = 870 x 3 (permanece) X25 = 870 x 3 = 2.610,00
X21 = 980 x 4 retirar 980 unidades X21 = 0 0,00 
76
X21 = 980 x 4 retirar 980 unidades X21 = 0 0,00 
X16 = 620 x 4 (permanece) X16 = 620 x 4 = 2.480,00 
X11 = 420 x 7 enviar +980 unidades (980 + 420) X11 = 1400 x 7= 9.800,00
X12 = 1060 x 9 retirar 980 unidades (1060 – 980) X12 = 80 x 9 = 720,00 
X22 = 0 enviar 980 unidades X22 = 980 x 5 = 4.900,00
NOVO CUSTO TOTAL = 21.060,00 
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Problema de Transporte:
Exercício 3
Uma vinícola possui três fábricas e três armazéns. A empresa deseja saber quantos
tonéis de vinho deve enviar de cada fábrica para cada armazém de forma a minimizar
o seu custo de transporte. As capacidades das fábricas e dos armazéns (em número de
tonéis) bem como os custos de transporte por tonel encontram-se na tabela abaixo.
a) Resolva este problema através do Método do Custo Mínimo
b) Aplique o Método “MODI” para encontrar a solução ótima.
77
b) Aplique o Método “MODI” para encontrar a solução ótima.
Capacidade
das Fábricas
Fábricas A1 A2 A3
F1 20 16 24 200
F2 10 10 8 500
F3 12 18 10 200
Demanda 200 400 300
Armazéns
Custos de Transporte
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos