aula 7 Problema de Transporte

Prévia do material em texto

Problema de Transporte 
Fabiana Gomes dos Passos 
Referências 
 
 
 
 
• ANDRADE, Eduardo Leopoldino de. 
Introdução à pesquisa operacional: métodos e 
modelos para análise de decisões. 3. ed. Rio 
de Janeiro: LTC, 2004.192 p. 
 
• LACHTERMACHER, Gerson. Pesquisa 
operacional na tomada de decisões. 2. ed. 
rev. e atual. Rio de Janeiro: Elsevier, 2004. 
384 p. 
 
 
Roteiro da aula 
 
• Problemas de Transporte 
– Definição de Problemas de Transporte 
– Algoritmo para Resolução de Problemas de Transporte 
– Método do Canto Noroeste 
– Método do Menor Custo 
– Método de Aproximação de Vogel 
– Exemplo de Aplicação 
– Exercícios de Fixação 
 
 
 
Problema de Transporte 
• O problema de transporte é uma classe especial de problema 
de programação linear que trata do envio de uma mercadoria 
de origens (por exemplo, fábricas) para destinos (por 
exemplo, depósitos); 
 
• O objetivo é determinar a programação de expedição que 
minimize o custo total de expedição e, ao mesmo tempo, 
satisfaça os limites de fornecimento e demanda; 
 
• A aplicação do problema de transporte pode ser estendida a 
outras áreas de operações, entre elas controle de estoque, 
programação de empregos e designação de pessoal. 
Problema de Transporte 
 
• É um problema de grande aplicação prática, tendo sido 
estudado por vários investigadores, embora tenha sido 
Dantzig o primeiro a estabelecer a sua formulação em PL e a 
propor um método sistemático de resolução além de ser o 
criador do método simplex. (DANTZIG, 1953 – 1963), 
(CANAVARRO, 2005). 
 
• O Método de Transporte resolve esta classe de problemas de 
programação linear de uma maneira mais eficiente do que o 
Simplex tradicional; 
 
 
 
Problema de Transporte 
 
• Porém, o Método de Transporte foi especialmente utilizado 
antes da era da microcomputação, ou seja, nos primórdios da 
Pesquisa Operacional, para aperfeiçoar cálculos feitos a mão; 
 
• Atualmente, com a existência de diversos sistemas 
automatizados de resolução de Problemas de programação 
Linear , eles também são utilizados para resolver Problemas 
de Transporte; 
 
Definição do Problema de Transporte 
• O problema geral é representado pela rede na figura a seguir: 
 
 
 
 
 
 
• Há m origens e n destinos, cada um representado por um nó. 
Os arcos representam as rotas que ligam as origens aos 
destinos. O arco (i, j), que liga a origem i ao destino j, nos dá 
duas informações: 
– O custo de transporte por unidade cij 
– A quantidade enviada, xij 
 
1 
2 
1 
n m 
2 
a1 
a2 
am 
b1 
b2 
bn 
Origens c11:x11 Destinos 
Unidades de 
suprimento 
Unidades de 
demanda 
Definição do Problema de Transporte 
• O problema geral é representado pela rede na figura a seguir: 
 
 
 
 
 
 
• A quantidade de suprimento na origem i é ai e a quantidade 
de demanda no destino j é bj. 
• O objetivo do problema é determinar as incógnitas xij que 
minimizarão o custo total de transporte e, ao mesmo tempo, 
satisfarão todas as restrições de suprimento e demanda. 
 
1 
2 
1 
n m 
2 
a1 
a2 
am 
b1 
b2 
bn 
Origens c11:x11 Destinos 
Unidades de 
suprimento 
Unidades de 
demanda 
Definição do Problema de Transporte 
 
• O Problema de Transporte básico é aquele em que queremos 
determinar, dentre as diversas maneiras de distribuição de um 
produto, a que resultará no menor custo de transporte entre 
as fábricas e os centros de distribuição; 
 
• Por se tratar de um problema de programação linear, 
devemos fazer a hipótese de que o custo unitário de 
transporte de cada fábrica para cada destino é constante, 
independentemente da quantidade transportada. 
 
 
 
 
Definição do Problema de Transporte 
 
• Matematicamente, queremos a minimização do custo total de 
transporte, a qual é dada por: 
 
 Min Z = 
Onde: 
 
 
 
 m 
 n 
 
 

 
m
i
n
j
ijij xc
1 1
ijc
ijx
É a quantidade de itens transportados da fábrica i para o 
destino j (vaiáveis de decisão); 
É o custo de unidade de transporte da fábrica i para o destino j 
(constantes); 
É o número de fábricas; 
É o número de destinos (centros de consumidores). 
Definição do Problema de Transporte 
 
• As restrições deste tipo de problema são: 
 
– as fábricas não podem produzir mais do que suas capacidades 
instaladas, e 
– os centros consumidores não desejam receber volumes acima de suas 
demandas. 
 
 
 
 
 
Definição do Problema de Transporte 
 
• Para que estas restrições seja implementadas: o montante 
ofertado (somatório das capacidades das fábricas) deve ser 
igualado ao total demandado (somatório das demandas dos 
centros consumidores ). 
 
• Para operacionalizar estas restrições de igualdade, as 
seguintes regras devem ser seguidas: 
 
 
 
 
 
 
Definição do Problema de Transporte 
 
• No caso de Oferta maior que a Demanda devemos introduzir 
um destino fantasma (dummy) que tenha os custos de 
transporte unitários de todas as fábricas para este destino 
iguais a zero. A demanda deste centro consumidor deve ser 
igual à diferença entre o total ofertado e o total demandado; 
 
• No caso de Demanda maior que Oferta devemos introduzir 
uma fonte de oferta fantasma (dummy) que tenha os custos 
de transporte unitários para todos os destinos iguais a zero e 
uma capacidade igual à diferença entre o total demandado e 
o total ofertado. 
 
 
Definição do Problema de Transporte 
• Inserindo uma demanda ou uma oferta fantasma, garantimos 
que todas as restrições do problema serão dadas por 
igualdades; 
• Em outras palavras, o total fabricado será virtualmente igual à 
demanda dos centros consumidores e vice-versa. 
• Matematicamente, estas restrições serão representadas pelas 
equações a seguir: 
 
 
 
 
 
 



n
j
iij fx
1
(para i = 1, 2, ..., m) restrições das 
capacidades das fábricas 
O somatório das quantidades enviadas de cada fábrica para 
os n destinos deve ser igual ao total ofertado por aquela 
fábrica (fi) 
Definição do Problema de Transporte 
 
 
 
 
 
 
 
• Somando-se todos os lados de todas as restrições, teremos: 
 
j
m
i
ij dx 
1
(j = 1, 2, ..., n) restrições dos centros 
consumidores 
O somatório das quantidades recebidas por centro consumidor 
das m fábricas deve ser igual ao total demandado por aquele 
destino (dj). 

 

m
i
i
m
i
n
j
ij fx
11 1
e 

 

n
j
j
n
j
m
i
ij dx
11 1
Definição do Problema de Transporte 
• Como os lados esquerdos das duas equações acima 
representam o somatório dos custos de todos os itens 
transportados das fábricas para os destinos, podemos concluir 
que os lados direitos das equações também devem ser iguais, 
isto é: 
 
 
 
• Esta última igualdade é condição necessária e suficiente para 
que qualquer problema de transporte tenha solução ótima 
quando modelado utilizando variáveis dummy (oferta ou 
demanda fantasma). 
 
 



n
j
j
m
i
i df
11
Definição do Problema de Transporte 
• Conforme vimos, a inserção de variáveis do tipo dummy não é 
obrigatória, porém facilitam a interpretação do resultado da 
otimização. 
• Quando existe um desequilíbrio entre oferta e demanda, 
podemos ter as seguintes ações e interpretações para as 
variáveis dummy:Capacidade > Demanda Demanda > capacidade 
Ação: busca de novos centros 
consumidores 
Ação: criação de nova fábrica 
Interpretação: capacidade 
ociosa das fábricas 
Interpretação: demanda não 
atendida 
Exemplo 
• A MG Auto tem três fábricas: uma em Los Angeles, uma em 
Detroit e outra em Nova Orleans, e duas grandes centrais de 
distribuição: uma em Denver e outra em Miami. As 
capacidades das três fábricas para o próximo trimestre são 
1000, 1500 e 1200 carros. As demandas trimestrais nas duas 
centrais de distribuição são 2300 e 1400 carros. O mapa de 
distâncias entre as fábricas e as centrais de distribuição é 
dado na tabela a seguir: 
 
 
 
 
 
Denver Miami 
Los Angeles 1000 2690 
Detroit 1250 1350 
Nova Orleans 1275 850 
Exemplo 
• A empresa transportadora encarregada do transporte dos 
carros cobra 8 centavos por milha por carro. Os custos de 
transporte por carro nas diferentes rotas, arredondados para 
o valor mais próximo, são dados na tabela a seguir (Custos ($) 
de transporte por carro): 
 
 
 
 
 
 
Denver Miami 
Los Angeles 80 215 
Detroit 100 108 
Nova Orleans 102 68 
Exemplo 
 
• Tabela do modelo de transporte da MG: 
 
 
 
 
 
Modelo de transporte da 
MG 
Centrais de distribuição 
Fábricas Denver Miami Suprimento 
Los Angeles x11 x12 1.000 
Detroit X21 x22 1.500 
Nova Orlens X31 x32 1.200 
Demanda 2.300 1.400 3.700 
80 
100 
102 68 
215 
108 
 Exemplo 
 
 
 
 
 
 
• A formulação do problema de PL da questão é dada por: 
Minimização z = 80 X11 + 215 X12 + 100 X21 + 108 X22 + 102 X31 +68X32 
Sujeita a X11 + X12 = 1.000 
 X21 + X22 = 1.500 
 X31 + X32 = 1.200 
 X11 + X21 + X31 = 2.300 
 X12 + X22 + X32 = 1.400 
 Xij ≥ 0; i = 1, 2,3; j = 1,2 
Modelo de transporte da 
MG 
Centrais de distribuição 
Fábricas Denver Miami Suprimento 
Los Angeles x11 x12 1.000 
Detroit X21 x22 1.500 
Nova Orlens X31 x32 1.200 
Demanda 2.300 1.400 3.700 
80 
100 
102 68 
215 
108 
 Exemplo 
• Todas essas restrições são equações porque o suprimento total 
das três origens é igual à demanda total dos dois destinos, 
equivalente a 3.700 carros. 
• O problema de PL pode ser resolvido pelo método simplex, 
porém, com a estrutura especial das restrições podemos 
resolver o problema com mais facilidade usando a tabela 
simplex para o problema de transporte mostrada na tabela 
abaixo: 
 
 
 
 
 
Modelo de transporte da 
MG 
Centrais de distribuição 
Fábricas Denver Miami Suprimento 
Los Angeles x11 x12 1.000 
Detroit X21 x22 1.500 
Nova Orlens X31 x32 1.200 
Demanda 2.300 1.400 3.700 
80 
100 
102 68 
215 
108 
Exemplo 
 
• Solução ótima para o modelo da MG Auto: 
 
 
 
 
 
 
 
 
• O custo mínimo do transporte associado é calculado como 
1.000*$80 + 1.300*$100 + 200*$108 + 1.200*$68 = 
$ 313.200,00 
 
 
1 
2 
3 
1 
2 
Los Angeles 
Detroit 
Nova Orlens 
Denver 
Miami 
1.000 
1.500 
1.200 
2.300 
1.400 
Exemplo 
 
• Balanceamento do problema de transporte. O algoritmo de 
transporte é baseado na premissa de que o problema é 
balanceado, o que significa que a demanda total é igual ao 
fornecimento total. 
 
• Se o problema não for balanceado, sempre podemos 
adicionar uma origem fictícia ou destino fictício para restaurar 
o equilíbrio. Conhecido também como: variáveis dummy. 
 
 
 
 
 
 
Exemplo 1 
• No modelo de transporte da MG , suponha que a capacidade 
da fábrica de Detroit seja 1.300 carros (em vez de 1.500) e o 
suprimento total (3.500 carros) é menor do que a demanda 
total (3.700 carros), o que significa que parte da demanda em 
Denver a Miami não será satisfeita : 
 
 
 
 
 
 
• 
 
 
 
Modelo de transporte da 
MG 
Centrais de distribuição 
Fábricas Denver Miami Suprimento 
Los Angeles x11 x12 1.000 
Detroit X21 x22 1.300 
Nova Orlens X31 x32 1.200 
Demanda 2.300 1.400 
80 
100 
102 68 
215 
108 
Exemplo 1 
• Como a demanda ultrapassa o fornecimento, uma origem (fábrica) 
fictícia com uma capacidade de 200 carros é adicionado para 
equilibrar o problema de transporte. O custo unitário de transporte 
da fábrica fictícia para os dois destinos é zero porque a fábrica não 
existe : 
• : 
 
 
 
 
 
 
 
 
• O custo mínimo do transporte associado é calculado como 
1.000*$80 + 1.300*$100 + 1.200*$68 + 200*$0 = 291.600,00 
 
1 
2 
3 
1 
2 
Los Angeles 
Detroit 
Nova Orlens 
Denver 
Miami 
1.000 
1.300 
1.200 
2.300 
1.400 
4 
Fábrica Fictícia 
200 
Exemplo 1 
• No modelo de transporte da MG, suponha que o 
fornecimento ultrapassa a demanda. Podendo ser 
demonstrado ao se considerar que a demanda em Denver é 
apenas 1.900 carros: 
 
 
 
 
 
 
• 
 
 
 
Modelo de transporte da 
MG 
Centrais de distribuição 
Fábricas Denver Miami Suprimento 
Los Angeles x11 x12 1.000 
Detroit X21 x22 1.500 
Nova Orlens X31 x32 1.200 
Demanda 1.900 1.400 
80 
100 
102 68 
215 
108 
Exemplo 1 
• Como o fornecimento ultrapassa a demanda, uma central de 
distribuição fictícia deverá ser adicionado para receber o 
suprimento excedente. O custo unitário de transporte da central de 
distribuição fictícia para os dois destinos é zero porque a central 
não existe : 
 
 
 
 
 
 
 
 
 
• O custo mínimo do transporte associado é calculado como 
1.000*$80 + 900*$100 + 200*$108 + 1200*$68 + 400*$0,0 = 
273.200,00 
1 
2 
3 
1 
2 
Los Angeles 
Detroit 
Nova Orlens 
Denver 
Miami 
1.000 
1500 
1.200 
1.900 
1.400 
3 400 
Central de Distribuição Fictícia 
Exemplo 2 
Uns dos principais produtos da firma Lactosal é o leite. 
 
Os pacotes de leites são empacotados 
 em 3 fábricas 
 e depois são distribuídos de caminhão 
 para 4 armazéns 
 
Conhecendo os custos de transporte,a procura prevista para 
cada armazém e as capacidades de produção de cada fábrica, 
pretende-se: 
 
OTIMIZAR O PROGRAMA DE DISTRIBUIÇÃO DIÁRIO DO LEITE. 
Exemplo 2 
• Os dados dos custos de uma carga de leite para cada 
combinação fábrica-armazém e das ofertas (produção) e 
procuras, em cargas de caminhão/dia, são os seguintes: 
 
 
 
 
 
 
 
 
 
 
24 cargas 
diárias de leite 
devem ser 
produzidas e 
distribuídas 
Custo por carga de 
caminhão 
Armazéns 
Fábricas 1 2 3 4 Oferta 
1 1 2 3 4 6 
2 4 3 2 4 8 
3 0 2 2 1 10 
Procura 4 7 6 7 24 
Exemplo 2 
 
 
 
 
 
 
 
 
 
 
Custo por carga de 
camião
Armazéns
1012203
7
4
4
4
4
4
1
1
7
3
2
2
6
2
3
3
Procura
82
61
OfertaFábricas
Custo por carga de 
camião
Armazéns
1012203
7
4
4
4
4
4
1
1
7
3
2
2
6
2
3
3
Procura
82
61
OfertaFábricas
Destino
Origem
1 2 3 4 1 2 3 4 Oferta
11
22
33
66
88
1010
Procura 44 77 6 6 77 2424 ==2424
11 22 44
44 33 44
xx11 11 xx12 12 
xx1414
xx21 21 xx22 22 xx2424
33
xx13 13 
22
xx23 23 
00 22 11
xx31 31 xx32 32 xx3434
22
xx33 33 
Destino
Origem
Destino
Origem
1 2 3 4 1 2 3 4 Oferta
11
22
33
66
88
1010
Procura 44 77 6 6 77 2424 ==2424
1111 2222 4444
4444 3333 4444
xx11 11 xx12 12 
xx1414
xx21 21 xx22 22 xx2424
3333
xx13 13 
2222
xx23 23 
0000 2222 1111
xx31 31 xx32 32 xx3434
2222
xx33 33 
Para o exemplo 2 a oferta total é igual à 
procura total 
Exemplo 2 
 
 
 
 
 
 
 
 
 
 
Destino
Origem
1 2 3 4 1 2 3 4 Oferta
11
22
33
66
88
1010
Procura 44 77 6 6 77 2424 ==2424
11 22 44
44 33 44
xx11 11 xx12 12 
xx1414
xx21 21 xx22 22 xx2424
33
xx13 13 
22
xx23 23 
00 22 11
xx31 31 xx32 32 xx3434
22
xx33 33 
Destino
Origem
Destino
Origem
1 2 3 4 1 2 3 4 Oferta
11
22
33
66
88
1010
Procura 44 77 6 6 77 2424 ==2424
1111 2222 4444
4444 3333 4444
xx11 11 xx12 12 
xx1414
xx21 21 xx22 22 xx2424
3333
xx13 13 
2222
xx23 23 
0000 2222 1111
xx31 31 xx32 32 xx3434
2222
xx33 33 
Para o exemplo 2 
a oferta total é 
igual à procura 
total 
A formulação do problema de PL da questão é dada por: 
Minimização z = 1X11 + 2X12 + 3X13 +...+ 2X33 + 1X34 
Sujeita a X11 + X12 + X13 + X14 = 6 
 X21 + X22 + X23 +X24 = 8 
 X31 + X32 + X33 +X34 = 10 
 X11 + X21 + X31 = 4 
 X12 + X22 + X32 = 7 
 X13 + X23 + X33 = 6 
 X14 + X24 + X34 = 7 
 Xij ≥ 0; i = 1,2,3; j = 1,2,3,4 
 
Exercício de Fixação 
Algoritmo para resolução do Problema 
de Transporte 
 
• Como o problema de transporte é apenas um tipo especial de 
problema de programação linear, ele poderia ser resolvido 
aplicando o método simplex exatamente como vimos 
anteriormente. 
 
• Para tanto, teríamos que acrescentar variáveis artificiais e 
usando o método “das duas fases ou método do M grande” 
para proceder as iterações do método simplex. 
 
 
 
 
 
 
Algoritmo para resolução do Problema 
de Transporte 
 
• Entretanto, veremos na aula de hoje como explorar esta 
estrutura especial para obtermos um método muito mais 
eficiente o qual chamaremos método simplex para o 
problema de transporte. 
 
• Cabe observar que outros tipos de estruturas especiais 
podem ser exploradas de forma a obter algoritmos eficientes 
(como problema de designação). 
 
 
 
 
 
 
Propriedades do Problema de 
Transporte 
 
• Teorema I: O problema de transporte tem sempre solução 
ótima (finita). 
 
• Teorema II: Qualquer solução básica admissível do problema 
de transporte tem no máximo (m+n-1) variáveis positivas. 
 
• Teorema III: A matriz da base de qualquer SBF do problema 
de transporte é triangular. 
 
• Teorema IV: Se fij e dij com i = 1,2,...,m e j = 1,2,...,n, são 
inteiros, então qualquer solução básica admissível tem apenas 
valores inteiros. 
 
 
A SBF verifica o 
critério de 
otimalidade? 
Obtenção de uma SBF 
inicial 
FIM !!! 
a solução é 
ótima 
Mover-se para uma SBF 
"melhor" 
Sim 
Não 
Algoritmo para a resolução do Problema de 
Transporte 
Passo 1: Obtenção de uma SBF inicial 
 
• Qualquer SBF do problema de transporte tem no máximo 
m+n-1 variáveis básicas 
 
Qualquer restrição de oferta é igual à soma das restrições de 
demanda menos a soma das outras restrições de oferta e, 
cada restrição de demanda também é igual a soma das 
restrições de oferta menos a soma das outras restições de 
demanda. 
• Assim vamos contruir uma SBF inicial selecionando m+n–1 
variáveis, uma de cada vez e, posteriormente, vamos atribuir 
valores a essas variáveis. 
• Diversos métodos foram propostos para obteção de uma SBF 
inicial, vejamos a seguir alguns deles. 
 
 
Passo 1: Obtenção de uma SBF inicial 
 
• Diversos métodos foram propostos para obteção de uma SBF 
inicial, dentre eles se destacam: 
 
– Método do Canto Noroeste. 
– Método do Menor Custo ou Mínimo da Matriz de Custos 
– Método de aproximação de Vogel 
 
 
 
 
 
 
 
 
Passo 1: Obtenção de uma SBF Inicial 
Método do Canto Noroeste 
 A variável básica escolhida é, em cada quadro, a variável 
situada no canto superior esquerdo (por isso o nome do 
canto do NW (NorthWest). 
 A primeira variável básica escolhida será sempre x11, depois 
que tenha sido traçada a coluna 1 ou a linha 1, 
será escolhida como variável básica x12 ou x21 
respectivamente, e assim sucessivamente até terem sido 
traçadas todas as linhas e todas as colunas, com cuidado de 
não violar as restrições de produção e capacidade. 
 Este método é de aplicação muito fácil, mas tem como 
grande inconveniente o fato de não considerar os custos na 
identificação da SBF inicial. 
 
 4 7 6 7 
1 2 4 
4 3 4 
3 
2 
0 2 1 2 
6 
8 
10 
4 2 
5 3 
7 3 
1º. x11 =min (4,6 )= 4 
2 
2º. x12 =min (7,2 )= 2 
3º. x22 =min (5,8 )= 5 
5 
4º. x23=min (6,3 )= 3 
3 
3 
7 
5º. x33=min (3,10 )= 3 
6º. x34=min (7,7 )= 7 
SBF inicial: X0 = ( 4 , 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7 ) ; z
0
 = 42 
Exemplo - Método do Canto NoroestePasso 1: Obtenção de uma SBF Inicial 
Método do Menor Custo 
 
1. A variável básica escolhida é a variável que corresponde ao 
menor custo unitário (em caso de empate a escolha é 
arbitrária) e aloque à mesma o máximo possível de unidades. 
 
2. “Elimine” a linha ou coluna já completamente atendida e 
caminhe para o “próximo” mínimo custo. 
 
3. Termine quando todas as linhas e colunas forem atendidas. 
 
 
Passo 1: Obtenção de uma SBF Inicial 
Método do Menor Custo 
 
 A primeira variável básica escolhida será sempre a de menor 
custo, depois será escolhida como variável básica a de 
menor custo no quadro resultante relativo ao que foi 
traçado, e assim sucessivamente, até terem sido traçadas 
todas as linhas e todas as colunas. 
 
 Este método, em princípio, fornece soluções iniciais mais 
próximas da solução ótima que o método anterior, já que são 
considerados os custos na identificação da SBF inicial. 
 
 
 4 7 6 7 
1 2 4 
4 3 4 
3 
2 
0 2 1 2 
6 
8 
10 
4 6 
1 6 
6 
 1 
1º: min (cij )= c31= 0 
  x31 =min (4,10)= 4 
1 
2º: min (cij) =c34= 1  
x34 = min ( 7, 6 )= 6 
3º: min (ci) = c12=c23= 2 
  x12 = min ( 7, 6 ) = 6 
1 
4º: min (cij) =c23= 2 
  x23= min ( 6, 8 ) = 6 
2 1 
6 
5º: min (cij)= c22= 3  
x22= min ( 2, 1 ) = 1 
6º: min (cij) =c24= 4  
x24=min (1, 1 ) =1 
SBF inicial: X0 = ( 0 , 6, 0, 0, 0, 1, 6, 1, 4,0, 0,6) ; z = 37 
Exemplo - Método do Menor Custo 
Passo 1: Obtenção de uma SBF Inicial. 
Método de Vogel 
1. Calcule os valores das penalidades de cada uma das linhas e 
colunas subtraindo o menor valor de Cij do segundo menor 
valor de Cij naquela linha ou coluna (penalidade = “infração” 
por não escolher a célula de custo mínimo); 
 
1. Escolha a linha ou coluna com maior valor de penalidade ( se 
houver empate, escolha arbitrariamente) e aloque o máximo 
possível de unidades à célula de menor Cij daquela linha ou 
coluna (assim as maiores penalidades são evitadas); 
Passo 1: Obtenção de uma SBF Inicial. 
Método de Vogel 
 
3. “Elimine” a linha ou coluna já completamente atendida e 
retorne ao passo “a”, recalculando os valores das 
penalidades; 
4. Termine quando “sobrar” apenas uma linha ou coluna, 
balanceando-a. 
 
 Este método identifica uma SBF inicial, em geral, melhor do 
que as obtidas pelos métodos anteriores. 
 
 
 1 0 0 3 
1 2 4 
4 3 4 
3 
0 2 1 2 
2 
3 7 
1º: acrescentar uma linha 
e uma coluna, com as 
diferenças entre os dois 
menores custos, em 
coluna e em linha 
respectivamente. 
2º: Selecionar a maior 
das diferenças: max 
(diferenças) = 3 , coluna 
4. 
3º: Selecionar o menor 
dos custos para esta 
coluna: 
 min (cij: j=4)= c34= 1 
 x34= min ( 7, 10 ) = 7 
Iteração 1: x34= 7 
 4 7 6 7 
1 
1 
1 
máximo 
10 
8 
6 
mínimo 
Exemplo - Método de Vogel (Quadro 1) 
1 2 3 4 
4 3 4 2 
 3 
8 
6 
 4 7 6 
 
0 2 1 2 
7 
1 
3 
1º: calcular as novas 
diferenças relativas 
apenas aos elementos 
não traçados 
2º: Selecionar a maior 
das diferenças: 
max (diferenças) = 2 e 
corresponde à linha 3. 
3º: Selecionar o menor 
dos custos para esta 
linha: 
 min (cij: i=3)= c31= 0 
 x31= min ( 4, 3 ) = 3 
Iteração 2: x31= 3 
máximo 
 
1 0 0 
1 
1 
2 
mínimo 
Exemplo - Método de Vogel (Quadro 2) 
1 2 3 
4 3 4 2 
 
8 
6 
 4 7 6 
0 2 1 2 
3 
4 
7 
1 
 
1 
1º: calcular as novas 
 diferenças relativas 
 apenas aos 
elementos não traçados 
2º: Selecionar a maior 
 das diferenças : 
 max (diferenças) = 3 
 e corresponde à coluna 
1. 
3º: Selecionar o menor 
 dos custos para esta 
 coluna: 
 min (cij: j=1) = c11= 1 
 x11= min ( 1, 6 ) = 1 
Iteração 3: x11= 1 
 
3 1 1 
1 
1 
mínimo 
5 
máximo 
Exemplo - Método de Vogel (Quadro 3) 
 
8 
6 5 
 4 7 6 
7 
 
1 
3 
4 3 4 2 
0 2 1 2 
3 
2 4 
1 
1 
 
1 1 
5 
1º: calcular as novas 
diferenças relativas 
apenas aos elementos 
não traçados: todas são 
iguais a 1, pelo que 
pode ser escolhida 
qualquer delas . 
2º: Selecionar a coluna 
2 
e o menor dos seus 
custos : 
 min (cij: j=2) = c12= 2 
 x12= min ( 7,5 ) = 5 
Iteração 4: x12= 5 
1 
1 
mínimo 
2 
Exemplo - Método de Vogel (Quadro 4) 
As células restantes 
podem ser 
preenchidas 
imediatamente: 
x22= 2 
x23= 6 
 
8 
 2 6 
7 
 
3 
4 3 4 2 
0 2 1 2 
3 
2 4 
1 
1 
 
 5 
2 6 
SBF inicial: X0 = ( 1 , 5, 0, 0, 0, 2, 6, 0, 3,0, 0,7) ; z = 36 
Exemplo - Método de Vogel (Quadro 5) 
 z0 = 36 X0 = ( 1 , 5, 0, 0, 
 0, 2, 6, 0, 
 3, 0, 0, 7) 
X0 = ( 4 , 2, 0, 0, 
 0, 5, 3, 0, 
 0, 0, 3, 7) 
X0 = ( 0 , 5, 1, 0, 
 0, 2, 6, 0, 
 4, 0, 0, 6) 
 z0 = 42 
 z0 = 37 
mais fácil 
menos fácil 
"pior" SBF 
"melhor" 
SBF 
Método SBF inicial f.o. 
Canto do NW 
 
Mínimo de custos 
 
Voguel 
Passo 1: Obtenção de uma SBF Inicial. 
Exemplo 
Exercício de Fixação 
Referências 
 
 
 
 
• ANDRADE, Eduardo Leopoldino de. 
Introdução à pesquisa operacional: métodos e 
modelos para análise de decisões. 3. ed. Rio 
de Janeiro: LTC, 2004.192 p. 
 
• LACHTERMACHER, Gerson. Pesquisa 
operacional na tomada de decisões. 2. ed. 
rev. e atual. Rio de Janeiro: Elsevier, 2004. 
384 p.