Aula 11 - Transportes (Solução Inicial)

Prévia do material em texto

IND1502 – Pesquisa Operacional I
Aula 11
Prof. Rafael Martinelli / Prof. Silvio Hamacher
martinelli@puc-rio.br
Departamento de Engenharia Industrial - PUC-Rio
Relembrando aula passada...
 Modelos de Transporte:
 Classe especial de modelos de 
otimização que lidam com o 
problema do transporte de itens 
entre origens e destinos;
 Estrutura particular permite que 
sejam desenvolvidos algoritmos 
eficientes para a solução de tais 
problemas;
 Para tal adota-se uma 
representação particular, que 
definimos como o tableau de 
transporte;
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
1
2
3
1
2
3
𝑐11
𝑐12𝑐21
𝑐13
𝑐31
𝑐32
𝑐33
𝑐22
𝑐23
𝑐11 𝑐12 𝑐13
𝑥11 𝑥12 𝑥13
𝑐21 𝑐22 𝑐23
𝑥21 𝑥22 𝑥23
𝑐31 𝑐32 𝑐33
𝑥31 𝑥32 𝑥33
O
ri
ge
n
s
Destinos
2
Relembrando aula passada...
 Modelando o problema de transporte:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
3
4
5
1
2
Seattle
San-Diego
New -York
Chicago
Topeka
Plantas
Distância de envio
OfertasMercados
New York Chicago Topeka
Seattle 2,5 1,7 1,8 350
San Diego 2,5 1,8 1,4 650
Demandas 325 400 275
2,5 1,7 1,8
350
2,5 1,8 1,4
650
325 400 275
Seattle
San Diego
New York Chicago Topeka
3
Relembrando aula passada...
 Casos particulares:
 Problemas desbalanceados (oferta ≠ demanda)
 Caso 1: Demanda > Oferta (Oferta escassa)
 Criar oferta (linha ) dummy;
 Caso 2: Oferta > Demanda (Demanda escassa)
 Criar demanda (coluna) dummy;
 Arcos inexistentes ou desativados;
 Atribuir o custo 𝑀 (Big M – valor suficientemente
grande) ao custo unitário de transporte do arco;
 Considerando vários produtos simultaneamente;
 Decompor em problemas individuais;
 Caso de Transbordo
 Tratar os nós de transbordo como origens e destinos, 
atribuir os 𝑀 as conexões inexistentes e ajustar os
valores de demanda e oferta;
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
4
Relembrando aula passada...
 Aplicação da modelagem para outros contextos:
 Ex.: Planejamento da produção/estocagem
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
Transporte Estoques/Produção
Origem 𝑖 Período de produção 𝑖
Destino 𝑗 Período de demanda 𝑗
Oferta na origem 
𝑖
Capacidade Produtiva 
no período 𝑖
Demanda no 
destino 𝑗
Demanda no período 𝑗
Custo unitário de 
transporte de 𝑖
para 𝑗
Custo de produção e 
inventário do período 𝑖
para o período 𝑗
Montante
transportado da 
origem 𝑖 para o 
destino 𝑗
Total produzido no 
período 𝑖 para atender a 
demanda do período 𝑗
1 2 3 4
1
4 4.5 5 5.5 50
2
6 4 4.5 5 180
3
8 6 4 4.5 280
4
10 8 3.5 4 270
100 200 180 300
Demanda 
Capacidade
5
Modelos de Transporte
 A modelagem de problemas através de modelos de 
transporte se dá em três etapas:
1. Montagem do tableau de transporte e balanceamento 
da instância;
2. Geração de uma solução inicial factível;
3. Otimização;
 Uma solução inicial tem sua “qualidade” medida de acordo 
com a sua proximidade relativa ao ótimo;
 Ou seja: quão melhor a solução inicial for, menos 
iterações serão necessárias para que se atinja o ótimo.
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
6
Modelos de Transporte
 Vamos considerar um problema de transportes com 𝑚
origens e 𝑛 destinos que esteja balanceado.
 Desta forma, teremos um sistema de equações composto 
por 𝑚 + 𝑛 restrições de igualdade;
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
1
2
𝑚
4
5
𝑛
... ...
Oferta Total = σ𝑖=1,…,𝑚 𝑎𝑖 Demanda Total = σ𝑗=1,…,𝑛 𝑏𝑗=
7
Modelos de Transporte
 Tendo em mente o que vimos até 
aqui, é importante lembrarmos das 
dificuldades que tínhamos no Simplex 
quando precisávamos obter uma 
solução inicial factível para 
problemas com restrições de 
igualdade;
 Método das Duas Fases: variáveis 
artificias e função objetivo artificial 
para a obtenção de uma primeira 
solução viável;
 Felizmente, a estrutura particular dos 
problemas de transporte torna 
simples o processo de obtenção de 
uma primeira solução básica viável;
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
x1
x2
(1.1)
2
1,5 (1.2)
4
(2)
1ª fase: viabilização:
x1(1.1)
2
1,5 (1.2)
4
2ª fase: otimização(3)
8
Modelos de Transporte
 Antes de entendermos os 3 principais métodos para a 
geração de soluções iniciais básicas e viáveis, precisamos 
observar qual característica particular em tais modelos nos 
permite a definição de métodos mais simples;
 Todo sistema de equações oriundo de um problema de 
transporte possui a seguinte característica:
 O sistema possui 𝑚 × 𝑛 variáveis;
 O sistema possui 𝑚 + 𝑛 equações;
 Dadas 𝑚 + 𝑛 − 1 equações, a remanescente pode ser 
escrita como uma combinação linear das demais 
(linearmente dependente). E
N
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
9
Modelos de Transporte
 Dadas 𝑚 + 𝑛 − 1 equações, a remanescente pode ser escrita 
como uma combinação linear das demais (linearmente 
dependente).
 Qual é o impacto disso para o problema em si?
 Tentem lembrar da definição de Simplex:
 Um simplex N-dimensional é um poliedro cujos N+1 vértices são 
independentes afins (formam vetores linearmente 
independentes – vulgo não-colineares).
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
v2
v1
v3
Simplex! No ℝ2
10
Modelos de Transporte
 Normalmente, nos nossos modelos tradicionais, a nossa base 
seria do tamanho do número 𝑚+ 𝑛 de restrições (equações 
linearmente independentes - considerando que já inserimos as 
folgas da forma canonizada);
 No caso de modelos de transporte, o que acontece é que a base 
aqui é composta somente por 𝑚+ 𝑛 − 1 variáveis, pois assim é 
suprimida a dependência linear entre as restrições:
 Na prática, isso significa que toda solução básica viável de 
problemas de transporte possui 𝑚 + 𝑛 − 1 variáveis com valor 
maior ou igual a zero (variáveis básicas) e todas as demais são 
nulas (variáveis não-básicas) EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
11
Modelos de Transporte
 Exemplo: dependência linear em modelos de transporte
 Uma empresa têxtil fabrica blusas contando com duas 
fábricas, uma em San Diego, outra em Seattle. A empresa 
atende ao público através de 3 revendedoras, localizadas 
em New York, Chicago e Topeka. 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
3
4
5
1
2
Seattle
San-Diego
New -York
Chicago
Topeka
Plantas
Distância de envio
OfertasMercados
New York Chicago Topeka
Seattle 2.5 1.7 1.8 350
San Diego 2.5 1.8 1.4 650
Demandas 325 400 275
12
Modelos de Transporte
 Formulação explícita:
 Tentem escrever cada uma das equações em função das 
demais...
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 2,5𝑥13 +1,7𝑥14 +1,8𝑥15 +2,5𝑥23 +1,8𝑥24 +1,4𝑥25
𝑠. 𝑎: 𝑥13 +𝑥14 +𝑥15 = 350 (1)
𝑥23 +𝑥24 +𝑥25 = 650 (2)
𝑥13 +𝑥23 = 325 (3)
𝑥14 +𝑥24 = 400 (4)
𝑥15 +𝑥25 = 275 (5)
𝑥13, 𝑥14, 𝑥15, 𝑥23, 𝑥24, 𝑥25 ≥ 0
13
Modelos de Transporte
 Formulação explícita:
 Tentem escrever cada uma das equações em função das 
demais...
 (1) = (3) + (4) + (5) −(2);
 (2) = (3) + (4) + (5) − (1);
 (3) = (1) + (2) − (4) − (5);
 ... Como isso é possível?
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 2,5𝑥13 +1,7𝑥14 +1,8𝑥15 +2,5𝑥23 +1,8𝑥24 +1,4𝑥25
𝑠. 𝑎: 𝑥13 +𝑥14 +𝑥15 = 350 (1)
𝑥23 +𝑥24 +𝑥25 = 650 (2)
𝑥13 +𝑥23 = 325 (3)
𝑥14 +𝑥24 = 400 (4)
𝑥15 +𝑥25 = 275 (5)
𝑥13, 𝑥14, 𝑥15, 𝑥23, 𝑥24, 𝑥25 ≥ 0
14
Modelos de Transporte
 Formulação explícita:
 A prova se baseia no fato de que toda variável aparece pelo 
menos em um par de restrições... Então, tirando uma 
restrição, é sempre possível “representar” a variável com 
alguma combinação linear entre as demais...
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = 2,5𝑥13 +1,7𝑥14 +1,8𝑥15 2,5𝑥23 +1,8𝑥24 +1,4𝑥25
𝑠. 𝑎: 𝑥13 +𝑥14 +𝑥15 = 350 (1)
𝑥23 +𝑥24 +𝑥25 = 650 (2)
𝑥13 +𝑥23 = 325 (3)
𝑥14 +𝑥24 = 400 (4)
𝑥15 +𝑥25 = 275 (5)
𝑥13, 𝑥14, 𝑥15, 𝑥23, 𝑥24, 𝑥25 ≥ 0
15
Modelos de Transporte - Solução Inicial
 Baseados nesse fato exposto anteriormente, 3 métodos de 
obtenção de soluções iniciais foram desenvolvidos;
 Método do Canto Noroeste;
 Método do Menor Custo;
 Método de Vogel;
 Em geral, o Método de Vogel apresenta melhores resultados 
para soluções iniciais;
 No entanto, os dois primeiros são mais simples de 
implementar e podem gerar soluções eventualmente tão 
boas quanto.
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
16
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 O método inicia alocando-se o máximo fluxo possível na 
variável 𝑥11 - daí vem o “canto noroeste”;
 Cada célula é preenchida com o valor máximo possível para o 
fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra 
variável da linha (ou da coluna) assumirá valor maior que 
zero;
 Deve-se seguir para o preenchimento da célula vizinha da 
outra coluna (ou linha):
 Definição: 𝑥𝑖𝑗 e 𝑥𝑘𝑙 serão chamados vizinhos se, e 
somente se, 𝑖 = 𝑘 ou 𝑗 = 𝑙
 O processo é concluído quando todas as demandas são 
atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
17
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 1º: atribuir a 𝑥11 o máximo fluxo possível 
(min 𝑎1, 𝑏1 = min 350,325 = 325)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350
2,5 1,8 1,4
650
325 400 275
Seattle
San Diego
New York Chicago Topeka
18
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 1º: atribuir a 𝑥11 o máximo fluxo possível 
(min 𝑎1, 𝑏1 = min 350,325 = 325)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 25
325
2,5 1,8 1,4
650
325
0
400 275
Seattle
San Diego
New York Chicago Topeka
Nenhum outro fluxo será alocado
nesta coluna
19
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 2º: atribuir a 𝑥12 (vizinhos: 𝑥12 e 𝑥21) o máximo fluxo 
possível (min 𝑎1, 𝑏2 = min 25,400 = 25)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 25
325
2,5 1,8 1,4
650
325
0
400 275
Seattle
San Diego
New York Chicago Topeka
Vizinhos!
20
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 2º: atribuir a 𝑥12 (vizinhos: 𝑥12 e 𝑥21) o máximo fluxo 
possível (min 𝑎1, 𝑏2 = min 25,400 = 25)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
Nenhum outro fluxo será alocado
nesta linha
2,5 1,7 1,8
350 25 0
325 25
2,5 1,8 1,4
650
325
0
400
375
275
Seattle
San Diego
New York Chicago Topeka
21
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 3º: atribuir a 𝑥22 (vizinhos: 𝑥22 e 𝑥13) o máximo fluxo 
possível (min 𝑎2, 𝑏2 = min 375,650 = 375)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 25 0
325 25
2,5 1,8 1,4
650
325
0
400
375
275
Seattle
San Diego
New York Chicago Topeka
22
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 3º: atribuir a 𝑥22 (vizinhos: 𝑥22 e 𝑥13) o máximo fluxo 
possível (min 𝑎2, 𝑏2 = min 375,650 = 375)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 25 0
325 25
2,5 1,8 1,4
650 275
375
325
0
400
375
0
275
Seattle
San Diego
New York Chicago Topeka
23
Solução Inicial - Canto Noroeste
 Método do Canto Noroeste
 Exemplo:
 4º: completar a última célula com o valor 
remanescente
 Custo Total = 325 × 2,5 + 25 × 1,7 + 375 × 1,8 +
275 × 1,4 = 1915
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 25 0
325 25
2,5 1,8 1,4
650 275 0
375 275
325
0
400
375
0
275
0
Seattle
San Diego
New York Chicago Topeka
24
Solução Inicial - Canto Noroeste
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o método do 
canto noroeste para o problema de transporte 
representado no tableau abaixo:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
12 7 9 20
25
0 14 16 18
5
5 15 15 10 25
Solução Inicial - Canto Noroeste
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o método do 
canto noroeste para o problema de transporte 
representado no tableau abaixo:
 Solução:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
5 10
12 7 9 20
25
5 15 5
0 14 16 18
5
5
5 15 15 10 26
Solução Inicial - Menor Custo
 Método do Menor Custo
 O método inicia alocando-se o máximo fluxo possível na 
variável 𝑥𝑖𝑗 de menor custo unitário de transporte 𝑐𝑖𝑗;
 A célula é preenchida com o valor máximo possível para o 
fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra 
variável da linha (ou da coluna) assumirá valor maior que 
zero;
 Deve-se seguir para o preenchimento da próxima célula de 
menor custo 𝑐𝑖𝑗 ainda não descartada;
 O processo é concluído quando todas as demandas são 
atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
27
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 1º: atribuir a 𝑥23 (menor 𝑐𝑖𝑗) o máximo fluxo possível 
(min 𝑎2, 𝑏3 = min 650,275 = 275
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350
2,5 1,8 1,4
650
325 400 275
Seattle
San Diego
New York Chicago Topeka
28
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 1º: atribuir a 𝑥23 (menor 𝑐𝑖𝑗) o máximo fluxo possível 
(min 𝑎2, 𝑏3 = min 650,275 = 275
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350
2,5 1,8 1,4
650 375
275
325 400 275
0
Seattle
San Diego
New York Chicago Topeka
29
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 2º: atribuir a 𝑥12 (próximo menor 𝑐𝑖𝑗) o máximo fluxo 
possível (min 𝑎1, 𝑏2 = min 350,400 = 350
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350
2,5 1,8 1,4
650 375
275
325 400 275
0Seattle
San Diego
New York Chicago Topeka
30
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 2º: atribuir a 𝑥12 (próximo menor 𝑐𝑖𝑗) o máximo fluxo 
possível (min 𝑎1, 𝑏2 = min 350,400 = 350
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0
350
2,5 1,8 1,4
650 375
275
325 400
50
275
0
Seattle
San Diego
New York Chicago Topeka
31
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 3º: atribuir a 𝑥22 (próximo menor 𝑐𝑖𝑗) o máximo fluxo 
possível (min 𝑎2, 𝑏2 = min 50,375 = 50
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0
350
2,5 1,8 1,4
650 375
275
325 400
50
275
0
Seattle
San Diego
New York Chicago Topeka
32
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 3º: atribuir a 𝑥22 (próximo menor 𝑐𝑖𝑗) o máximo fluxo 
possível (min 𝑎2, 𝑏2 = min 50,375 = 50
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0
350
2,5 1,8 1,4
650 375 325
50 275
325 400
50
0
275
0
Seattle
San Diego
New York Chicago Topeka
33
Solução Inicial - Menor Custo
 Método do Menor Custo
 Exemplo:
 4º: completar a última célula com o valor 
remanescente
 Custo Total = 350 × 1,7 + 325 × 2,5 + 50 × 1,8 +
275 × 1,4 = 1882,5(≈ 17,3%𝑚𝑒𝑛𝑜𝑟)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0
350
2,5 1,8 1,4
650 375 325 0
325 50 275
325
0
400
50
0
275
0
Seattle
San Diego
New York Chicago Topeka
34
Solução Inicial - Menor Custo
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o método do 
menor custo para o problema de transporte 
representado no tableau abaixo:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
12 7 9 20
25
0 14 16 18
5
5 15 15 10 35
Solução Inicial - Menor Custo
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o método do 
menor custo para o problema de transporte 
representado no tableau abaixo:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
0 15 0
12 7 9 20
25
15 10
0 14 16 18
5
5
5 15 15 10 36
Solução Inicial - Método de Vogel
 Também conhecido como Método de Aproximação de 
Vogel.
 Usualmente, o método provê soluções bem próximas ao 
ótimo, ou mesmo ótimas.
 O método busca contornar duas falhas dos métodos 
anteriores:
 O método do canto noroeste ser “cego” com relação aos 
custos;
 O método do menor enxergar os custos de forma míope 
(ou seja, enxergar somente o custo imediatamente 
seguinte);
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
37
Solução Inicial - Método de Vogel
 Método de Vogel
 O método inicia calculando a penalidade atual para cada linha e 
coluna
 Definição: Penalidade = menor custo subtraído o segundo 
menor custo em cada linha e coluna;
 Seleciona-se a linha ou coluna com maior penalidade atual
 A célula com menor custo na coluna (ou linha) selecionada é 
preenchida com o valor máximo possível para o fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra variável 
da linha (ou da coluna) assumirá valor maior que zero;
 Deve-se então atualizar os as penalidades atuais 
considerando somente as variáveis em linhas e colunas ainda 
disponíveis;
 O processo é concluído quando todas as demandas são atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
38
Solução Inicial - Método de Vogel
 Condições particulares do método de Vogel:
 Nos casos em que ambas a linha e a coluna são satisfeitas 
simultaneamente, escolher arbitrariamente uma a ser 
cancelada. A outra não deve mais ser considerada no 
cálculo de futuras penalidades;
 Se somente uma linha (ou coluna) com valor de oferta 
(ou demanda) restar não cancelada, determinar as 
variáveis básicas usando o método do menor custo;
 Se somente uma linha (ou coluna) com valor de oferta 
nulo (ou demanda) restar não cancelada, determinar as 
variáveis básicas nulas usando o método do menor 
custo;
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
39
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 1º: calcular as penalidades para as linhas e colunas e 
escolher a linha ou coluna com maior penalidade
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350
2,5 1,8 1,4
650
325 400 275
Seattle
San Diego
New York Chicago Topeka
40
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 1º: calcular as penalidades para as linhas e colunas e 
escolher a linha ou coluna com maior penalidade
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0,1
2,5 1,8 1,4
650 0,4
325 400 275
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
Em caso de empate, 
a decisão é arbitrária. 41
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 2º: na linha 𝑖 = 2 selecionada (arbitrariamente) 
atribuir a 𝑥23 (menor 𝑐2𝑗) o fluxo máximo 
min 𝑎2, 𝑏3 = min 650,275 = 275
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0,1
2,5 1,8 1,4
650 0,4
325 400 275
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
42
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 2º: na linha 𝑖 = 2 selecionada (arbitrariamente) 
atribuir a 𝑥23 (menor 𝑐2𝑗) o fluxo máximo 
min 𝑎2, 𝑏3 = min 650,275 = 275
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0,1
2,5 1,8 1,4
650 375 0,4
275
325 400 275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
43
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 3º: Recalcular as penalidades e escolher uma 
nova linha ou coluna com maior penalidade
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0,1 0,8
2,5 1,8 1,4
650 375 0,4 0,7
275
325 400 275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
44
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 4º: na linha 𝑖 = 1, atribuir a 𝑥12 (menor 𝑐1𝑗) o 
máximo fluxo min 𝑎1, 𝑏2 = min 350,400 =
350
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0,1 0,8
2,5 1,8 1,4
650 375 0,4 0,7
275
325 400 275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
45
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 4º: na linha 𝑖 = 1, atribuir a 𝑥12 (menor 𝑐1𝑗) o 
máximo fluxo min 𝑎1, 𝑏2 = min 350,400 =
350
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8
350 0 0,1 0,8
350
2,5 1,8 1,4
650 375 0,4 0,7
275
325 400
50
275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
46
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 5º: como só temos uma penalidade válida, 
escolher a linha 𝑖 = 2 e atribuir a 𝑥22 o máximo 
fluxo min 𝑎2, 𝑏2 = min 375,50 = 50
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
2,5 1,7 1,8350 0 0,1 0,8
350
2,5 1,8 1,4
650 375 325 0,4 0,7
50 275
325 400
50
0
275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
47
Solução Inicial - Método de Vogel
 Método de Vogel
 Exemplo:
 5º: completar a última célula com o valor 
remanescente
 Custo Total = 350 × 1,7 + 325 × 2,5 + 50 × 1,8 +
275 × 1,4 = 1882,5(𝑖𝑔𝑢𝑎𝑙)
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I2,5 1,7 1,8
350 0 0,1 0,8
350
2,5 1,8 1,4
650 375 325 0,4 0,7
325 50 275
325
0
400
50
0
275
0
0 0,1 0,4
Seattle
San Diego
New York Chicago Topeka
48
Solução Inicial - Método de Vogel
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o Método de 
Vogel para o problema de transporte representado no 
tableau abaixo:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
12 7 9 20
25
0 14 16 18
5
5 15 15 10 49
Solução Inicial - Método de Vogel
 Para fixar o método...
 Exercício:
 Proponha uma solução inicial utilizando o Método de 
Vogel para o problema de transporte representado no 
tableau abaixo:
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
10 0 20 11
15
5 10
12 7 9 20
25
10 15
0 14 16 18
5
5 0
5 15 15 10 50
Relembrando o que vimos até aqui...
 A modelagem de problemas através de modelos de 
transporte se dá em três etapas:
1. Montagem do tableau de transporte e balanceamento 
da instância;
2. Geração de uma solução inicial factível;
3. Otimização;
 Para gerar soluções iniciais conhecemos 3 métodos
 Método do canto noroeste;
 Método do menor custo;
 Método de Vogel; EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
51
Relembrando o que vimos até aqui...
 Método do Canto Noroeste
 O método inicia alocando-se o máximo fluxo possível na 
variável 𝑥11 - daí vem o “canto noroeste”;
 Cada célula é preenchida com o valor máximo possível para o 
fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra 
variável da linha (ou da coluna) assumirá valor maior que 
zero;
 Deve-se seguir para o preenchimento da célula vizinha da 
outra coluna (ou linha):
 Definição: 𝑥𝑖𝑗 e 𝑥𝑘𝑙 serão chamados vizinhos se, e 
somente se, 𝑖 = 𝑘 ou 𝑗 = 𝑙
 O processo é concluído quando todas as demandas são 
atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
52
Relembrando o que vimos até aqui...
 Método do Menor Custo
 O método inicia alocando-se o máximo fluxo possível na 
variável 𝑥𝑖𝑗 de menor custo unitário de transporte 𝑐𝑖𝑗;
 A célula é preenchida com o valor máximo possível para o 
fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra 
variável da linha (ou da coluna) assumirá valor maior que 
zero;
 Deve-se seguir para o preenchimento da próxima célula de 
menor custo 𝑐𝑖𝑗 ainda não descartada;
 O processo é concluído quando todas as demandas são 
atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
53
Relembrando o que vimos até aqui...
 Método de Vogel
 O método inicia calculando a penalidade atual para cada linha e 
coluna
 Penalidade = menor custo subtraído o segundo menor custo 
em cada linha e coluna;
 Seleciona-se a linha ou coluna com maior penalidade atual
 A célula com menor custo na coluna (ou linha) selecionada é 
preenchida com o valor máximo possível para o fluxo:
 𝑥𝑖𝑗 = min(𝑎𝑖 , 𝑏𝑗)
 Ao ser esgotada a oferta (ou demanda), nenhuma outra variável 
da linha (ou da coluna) assumirá valor maior que zero;
 Deve-se então atualizar os as penalidades atuais 
considerando somente as variáveis em linhas e colunas ainda 
disponíveis;
 O processo é concluído quando todas as demandas são atendidas; 
EN
G
1
5
0
2
 -
Pe
sq
u
is
a 
O
p
er
ac
io
n
al
 I
54
Até a próxima e 
aproveitem o fim de 
semana!
Prof. Rafael Martinelli
martinelli@puc-rio.br 
Departamento de Engenharia Industrial - PUC-Rio