Pesquisa OperacionalI_04_Livrotexto

Prévia do material em texto

formador autor José RobeRto Dale luche
pesquisa operacional i
PROBLEMAS DE 
TRANSPORTE
pesquisa operacional i
PROBLEMAS DE TRANSPORTE
4
Neste módulo são discutidos assuntos relacionados a 
problemas de transporte de bens. O modelo e os algo-
ritmos foram desenvolvidos para resolverem problemas 
onde se tem uma determinada quantidade m de origens 
(fontes) e uma quantidade n de destinos, tal como ilus-
trado na Figura 1.
fontes destinos
Porém, na literatura, encontram-se aplicações que não 
estão relacionadas ao transporte de mercadorias. As si-
tuações que envolvam a decisão de escolha de “proce-
dência” e “destino” podem se beneficiar do modelo geral 
de transportes como base e depois implementar as par-
ticularidades, se necessário.
Figura 1. 
Ilustração de 
um problema de 
transportes.
Fonte: adaptado de 
<www.ingenieria 
industrialonline.com>.
http://www.ingenieriaindustrialonline.com
http://www.ingenieriaindustrialonline.com
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 3
A seção 1 trata da formulação matemática, já na seção 2 são apresenta-
dos alguns métodos de construção de uma solução inicial. Em 3 é apresen-
tado o problema da solução degenerada, enquanto que na seção 4 é apre-
sentado o método de otimização de stepping stone. Por último, na seção 5, 
é apresentado um problema especial de transporte com transbordo.
1. Formulação matemática e aplicações
O problema consiste em minimizar o custo total do transporte de um bem 
único a partir de “m” origens com oferta “oi” (i = 1 a m) para “n” destinos 
com procura “pj” (j = 1 a n). Neste problema, independente da quantidade 
a ser transportada de uma origem para certo destino, o valor unitário de 
transporte não se altera. Essa situação e outras diversas que acontecem 
no mundo real poderão ser tratadas com a inclusão de novas regras na 
formulação do modelo clássico que é apresentado a seguir.
Índices
 → m: quantidade de origens;
 → n: quantidade de destinos;
 → i : origem [1..m];
 → j : destino [1..n].
Parâmetros 
 → Cij: custo unitário de transporte da origem i ao destino j.
 → fi: quantidade disponível na origem i;
 → di: quantidade demandada pelo destino j.
Variáveis Xij: quantidade transportada da origem i ao destino j.
	 	 	
m
i	=	1
∑
n
j	=	1
∑ 	cij xij 
sujeito a:
	 	 	
n
j	=	1
∑ 	xij	 =	 fi ∀i 
	 	 	
m
i	=	1
∑ 	xij	 =	 dj ∀j 
	 	 	 xij	 ≥	 0 ∀i,	j 
(1)
(2)
(3)
(4)
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 4
Em (1), tem-se a função objetivo que procura minimizar o custo total de 
transporte. Nas equações de (2), encontram-se as restrições que deter-
minam que tudo que for transportado a partir de uma origem, deve ser 
exatamente igual a disponibilidade desta. Já em (3), tudo que for transpor-
tado para um destino deve ser exatamente igual a sua demanda. Em (4) 
encontram-se as restrições quanto ao domínio das variáveis.
A combinação de (2) e (3) leva ao entendimento de que o problema está 
balanceado, ou seja, total transportado = disponibilidade total = demanda 
total, tal como representado em (5).
m
i	=	1
∑ 	fi	 =	
n
j	=	1
∑ 	dj
Esta última igualdade é condição necessária para que qualquer problema 
de transporte tenha solução ótima quando modelado utilizando variáveis 
dummy (fictícia).
Como nem todo o problema, principalmente no mundo real, terá a dis-
ponibilidade total = a demanda total, será necessário criar uma linha ou 
coluna de variáveis dummy (fictícias) com custo de transporte = 0. Se a dis-
ponibilidade total for maior que a demanda total, então será preciso criar 
uma coluna (demanda) com a diferença entre a quantidade demandada e 
a disponibilidade, caso contrário deve-se criar uma linha com esta mesma 
diferença, sempre positiva.
ExEmplos
Oferta maior que a demanda: é adicionado um destino fictício com cus-
tos de transporte nulo de todas as origens para este destino. A demanda 
deste destino fictício deve ser igual à diferença entre o total ofertado e o 
total demandado.
D1 D2 disponibilidade
O1 c11 c12 10
O2 c21 c22 15
demanda 8 12 25/20
Como o problema não se encontra balanceado, é preciso adicionar uma 
coluna de variáveis dummy:
D1 D2 dummy disponibilidade
O1 c11 c12 0 10
O2 c21 c22 0 15
demanda 8 10 5 25/25
(5)
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 5
Problema 1: Transporte de Tratores
Existem duas associações de agricultores em certa Região do Estado. Es-
sas duas associações possuem, a Associação A com 15 e a Associação 
B com 13 tratores. Três fazendas têm demanda desse tipo de veículo, a 
Fazenda 1 por exemplo, tem demanda de 12 unidades, a Fazenda B de 
14 e a Fazenda C de apenas 7. Os tratores devem ser transportados às 
fazendas e no quadro a seguir encontram-se os custos para o transporte 
por unidade do veículo.
origem
destino
disponibilidade
D1 D2 D3
O1 $140 $60 $110 15
O2 $70 $90 $120 13
demanda 12 14 7 33/28
Este problema também não se encontra balanceado, e será preciso adi-
cionar uma linha de variáveis dummy:
origem
destino
disponibilidade
D1 D2 D3
O1 $140 $60 $110 15
O2 $70 $90 $120 13
dummy $0 $0 $0 5
demanda 12 14 7 33/33
O código do modelo de transportes para este problema no software LIN-
DO terá a seguinte forma:
min 140x11 + 60x12 + 110x13 + 70x21 + 90x22 + 120x23
st
x11 + x12 + x13 = 15
x21 + x22 + x23 = 13
x31 + x32 + x33 = 5
x11 + x21 + x31 = 12
x12 + x22 + x32 = 14
x13 + x23 + x33 = 7
end
gin 9
Resultado
lp optimum found at step 6
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 6
objective value = 1910.00000
variable value
 x12 14
 x13 1
 x21 12
 x23 1
 x33 5
Problema 2: Montadoras e empresa de autopeças
Uma companhia fabricante de discos de freio para automotores possui 
duas unidades de fabricação e expedição no país. Acreditando no poten-
cial da companhia, seu diretor acertou contratos com quatro montado-
ras diferentes. Os contratos também possuem características diferentes 
devido à filosofia de trabalho de cada montadora. Assim, o contrato com 
a montadora A prevê uma multa de R$5,00 para cada disco de freio não 
entregue na data especificada, as montadoras B e C não cobram multa, 
porém, a montadora D é um contrato novo e de apenas um mês para 
experiência, sendo assim, esta companhia irá garantir o atendimento da 
montadora D. As capacidades semanais de cada unidade e a demanda 
das montadoras para o produto são:
unidade capacidade semanal montadora demanda semanal
1 150 A 100
2 100 B 80
C 70
D 50
total 250 total 300
Como já se sabe que não será possível atender a demanda total, o diretor 
precisa elaborar um plano de transporte que minimize o custo total com 
multas e transporte. Os custos unitários de transporte entre as unidades 
e montadoras são conhecidos e são apresentados juntamente com o qua-
dro que já conta com a linha de variáveis de fornecimento fictícias.
destino
disponibilidade
m1 m2 m3 m4
unidade 1 20 23 37 25 150
unidade 2 23 35 30 33 100
dummy 5 0 0 999 50
demanda 100 80 70 50 300/300
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 7
O código do modelo de transportes para este problema no software LIN-
DO terá a seguinte forma:
min 20x11 + 23x12 + 37x13 + 25x14 + 23x21 + 35x22 + 30x23 + 33x24 + 5x31 + 999x34 
st
x11 + x12 + x13 + x14 = 150
x21 + x22 + x23 + x24 = 100
x31 + x32 + x33 + x34 = 50
x11 + x21 + x31 + x41 = 100
x12 + x22 + x32 + x42 = 80
x13 + x23 + x33 + x43 = 70
x14 + x24 + x34 + x44 = 50
end
gin 16
Resultado com o software LINDO:
no. iterations = 10
objective function value
1) 5930
variable value 
 x11 20
 x12 80
 x14 50
 x21 80
 x23 20 
 x33 50
2. métodos de construção de uma solução inicial
Nesta seção, são apresentados três métodos para a construção de uma 
solução inicial para o problema de transportes, a qualidade da solução ini-
cial influencia na facilidade (número de iterações), que um algoritmo de 
otimização precisará realizar para encontrar a solução ótima do problema.
2.1. Método do canto noroeste
Nestemétodo, cada atribuição deve ser realizada na célula de variável 
que seja o canto a Noroeste (canto esquerdo superior) entre as variá-
veis que possam receber algum valor. A primeira atribuição sempre será 
realizada na variável X11, que receberá o mínimo entre a capacidade de 
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 8
fornecimento da origem 1 e a demanda do destino 1. Então, elimine a 
linha ou coluna já atendida e escolha a variável que agora será o canto 
Noroeste, essa variável será adjacente à anterior.
método: canto noroeste
disponibilidade
D1 D2 D3
Origem 1 12
140
3
60
–
110
15
X11 X12 X13
Origem 2 –
70
11
90
2
120
13
X21 X22 X23
Dummy –
0
–
0
5
0
5
X31 X32 X33
Demanda 12 14 7  
As variáveis básicas são: X11, X12, X22, X23, X33, que satifaz a regra quanto ao 
número de variáveis básicas necessárias: m + n - 1 = 3 + 3 - 1 = 5.
Função objetivo:
Minimizar	Z	 =	 12×140	+	3×60	+	11×90	+	2×120	 =	 3090
Validando as Restrições:
1ª linha : 12 + 3 + 0 = 15
2ª linha : 0 + 11 + 2 = 13
3ª linha : 0 + 0 + 5 = 5
1ª coluna : 12 + 0 + 0 = 12
2ª coluna : 3 + 11 + 0 = 14
3ª coluna : 0 + 2 + 5 = 7
2.2. Método do MíniMo custo
Bastante simples também, a cada atribuição deve-se atribuir a maior quan-
tidade possível, respeitando as restrições de linha e coluna até que todas 
as restrições tenham sido satisfeitas. Por haver alguma inteligência no mé-
todo, espera-se que em média os resultados sejam melhores do que utili-
zando o método do canto Noroeste, o que acontece no exemplo utilizado:
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 9
método: canto noroeste
disponibilidade
D1 D2 D3
Origem 1 –
140
14
60
1
110
15
X11 X12 X13
Origem 2 7
70
–
90
6
120
13
X21 X22 X23
Dummy 5
0
–
0
–
0
5
X31 X32 X33
Demanda 12 14 7  
Como o mínimo custo na matriz é zero e este se repete na mesma linha, 
a escolha de por qual variável entre X31, X32 e X33 iniciará a atribuição será 
arbitrária e assim, pode-se encontrar diferentes soluções.
Min	Z	=	14×60	+	110	+	7×70	+	6×120	=	2160
2.3. Método de aproxiMação de Vogel
Dentre os três métodos apresentados, Vogel deve atingir, em média, os 
melhores resultados. É um método melhor pensado para o problema, 
pois se preocupa em identificar a linha ou coluna que têm a maior dife-
rença entre os menores custos, procurando evitar que seja necessário 
pagar tal diferença. O algoritmo funciona da seguinte maneira, até que a 
solução esteja completa faça:
 → Para cada linha e coluna calcule a diferença (penalidade) entre os 
dois menores custos, se iguais, a penalidade é zero;
 → Na linha ou coluna com a maior penalidade (escolha arbitrária no 
caso de empate), atribua a maior quantidade possível na célula de 
menor custo.
Para o quadro abaixo, considere que em cada linha da ‘Penalidade’ ocor-
reu uma decisão de atribuição.
método: vogel
disponibilidade penalidade
D1 D2 D3
O1 –
140
14
60
1
110
15
110 - 60 = 50
110 - 60 = 50
110 - 60 = 50X11 X12 X13
O2 12
70
–
90
1
120
13
90 - 70 = 20
90 - 70 = 20
120 - 90 = 30X21 X22 X23
Dummy –
0
–
0
5
0
5 0 - 0 = 0
X31 X32 X33
Demanda 12 14 7  
Penalidade 70 - 0 = 70140 - 70 = 70
60 - 0 = 60
90 - 60 = 30
110 - 0 = 110
120 - 110 = 10
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 10
O valor da Função objetivo foi o melhor encontrado nas três soluções 
apresentadas: 
Min	Z	=	14×60	+	110	+	12×70	+	120	=	1910
3. solução degenerada
Um problema que pode ocorrer ao montar uma solução é esta não apre-
sentar o número esperado de variáveis básicas, ou seja, vb < m+n-1. Nes-
ses casos, se faz necessário transformar (m+n-1)-vb variáveis nulas em 
variáveis básicas com valor zero até satisfazer o número de variáveis bási-
cas necessárias, o que levará a uma solução degenerada, tal como no caso 
apresentado a seguir.
ExEmplo
Construir uma solução para o problema de transportes a seguir utilizando 
o método do canto Noroeste (canto esquerdo).
destinos
capacidade
D1 D2
origem 1 25 20 2000
origem 2 30 25 1000
origem 3 20 15 1500
demanda 2000 2000
Resposta:
Como o problema não está balanceado deve-se adicionar uma coluna de 
variáveis fictícias com custo de transporte = 0.
método: canto noroeste
d1 d2 dummy
origem 1 2000
140
–
60
–
0
2000
X11 X12 X13
origem 2 0
70
1000
90
–
0
1000
X21 X22 X23
origem 3 –
0
1000
0
500
0
1500
X31 X32 X33
2000 2000 500  
Repare que logo na primeira atribuição, a restrição da linha e a restrição 
da coluna foram satisfeitas, implicando que as variáveis X12, X13, X21 e X22 
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 11
recebessem valores nulos e, portanto, permanecessem fora da base 
e assim, a solução contou com apenas 4 variáveis básicas, mas m + n 
- 1 = 5. Nesses casos, uma das variáveis adjacentes a X11, seja na linha 
(X12), ou na coluna (X21), precisará receber o valor zero e ser considerada 
básica, passando a ter uma solução degenerada. Com essa solução o 
problema poderá ser resolvido normalmente pelo método de stepping 
stone apresentado na próxima seção.
4. método de otimização
Na seção 2 foram vistos três diferentes métodos de construção de uma 
solução para um problema de transporte. Nesta seção será apresentado 
o método de stepping stone, um método de otimização simples e rápido 
que depende de uma solução inicial dada por um método de construção 
qualquer.
No método de stepping stone são investigadas as (m*n)-(m + n - 1) variá-
veis não básicas na tentativa de identificar uma solução adjacente melhor. 
Para cada vnb deverá existir apenas um ‘caminho fechado’. Cada ‘caminho 
fechado’ terá apenas uma vnb associada, que é aquela que está sendo 
investigado se poderá gerar alguma contribuição, que em caso afirmativo, 
se transformaria em uma vb para a saída de outra variável da base. Um 
caminho fechado é aquele que permitirá a troca de variáveis na base sem 
que alguma restrição do problema seja violada.
O algoritmo tem como critério de parada a constatação de que não há 
uma solução adjacente melhor, ou seja, nenhuma vnb é capaz de melho-
rar a solução atual. Para saber se uma vnb melhorará a solução atual, no 
‘caminho fechado’ atribua 1 para a vnb, note que as duas restrições, linha 
e coluna serão violadas. Agora, siga o ‘caminho fechado’ da vnb subtrain-
do 1 e somando 1 até terminar o caminho com uma subtração. Calcule 
então a influência que essa alteração causaria na solução.
Faça isso para cada vnb e ao final, verifique se há algum ‘caminho fe-
chado’ que a soma dos custos tenha dado negativo, o que significaria que 
existe uma solução melhor que a atual. Poderá acontecer de mais de um 
‘caminho fechado’ oferecer melhoria, porém, deve ser escolhido aquele 
que tiver o maior valor negativo, sua variável então entrará na base, en-
quanto que a variável que sairá, será aquela com menor quantidade den-
tre as que sofrem subtração. Assim, a nova solução terá a vnb entrando 
na base exatamente com a quantidade da variável que está saindo. Note 
que dessa forma mantêm-se a integridade de todas as restrições.
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 12
método: canto noroeste
disponibilidade
D1 D2 dummy
origem 1 12
140
3
60
–
110
15
X11 X12 X13
origem 2 –
70
11
90
2
120
13
X21 X22 X23
dummy –
0
–
0
5
0
5
X31 X32 X33
demanda 12 14 7  
cálculo do benefício do caminho fechado das vnbs
X13 → X23 → X22 → X12 = + 20
+ 110 - 120 + 90 - 60
X31 → X11 → X12 → X22 → X23 → X33 = - 50
+ 0 - 140 + 60 - 90 + 120 - 0
 X21 → X11 → X12 → X22 = - 100
+ 70 - 140 + 60 - 90
X32 → X22 → X23 → X33 = + 30
+ 0 - 90 + 120 - 0
Perceba que mais de um caminho fechado deu valor negativo, mas como 
comentado anteriormente, deve ser escolhida a vnb X21 para entrar na 
base por ter o caminho de maior valor negativo (maior contribuição). A 
decisão de quanto alocar em X21 depende apenas da variável que sairá da 
base, neste caso, a variável X22 tem uma unidade a menos sendo transpor-
tada que X11, logo, ela sairá da basee X21 receberá 11, devendo-se atualizar 
essa quantidade para todas as variáveis pertencentes ao caminho obten-
do o quadro a seguir.
método: stepping stone
disponibilidade
D1 D2 D3
origem 1 1
140
14
60
–
110
15
X11 X12 X13
origem 2 11
70
–
90
2
120
13
X21 X22 X23
dummy –
0
–
0
5
0
5
X31 X32 X33
demanda 12 14 7  
Deve-se calcular novamente os caminhos fechados.
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 13
cálculo do benefício do caminho fechado das vnbs
X13 → X23 → X21 → X11 = - 80
+ 110 - 120 + 70 - 140
X32 → X33 → X23 → X21 → X11 → X12 = + 130
+ 0 - 0 + 120 - 70 + 140 - 60
 X22 → X21 → X11 → X12 = + 100
+ 90 - 70 + 140 - 60
X31 → X21 → X23 → X33 = + 50
+ 0 - 70 + 120 - 0
Entra X13 e sai X11, o quadro deve ser atualizado:
método: stepping stone
disponibilidade
D1 D2 D3
origem 1 –
140
14
60
1
110
15
X11 X12 X13
origem 2 12
70
–
90
1
120
13
X21 X22 X23
dummy –
0
–
0
5
0
5
X31 X32 X33
demanda 12 14 7  
Deve-se calcular novamente os caminhos fechados.
cálculo do benefício do caminho fechado das vnbs
X11 → X13 → X23 → X21 = + 80
+ 110 - 110 + 120 - 70
X31 → X21 → X23 → X33 = + 50
+ 0 - 70 + 120 - 0
 X22 → X12 → X13 → X23 = + 20
+ 90 - 60 + 110 - 120
X32 → X33 → X13 → X12 = + 50
+ 0 - 0 + 110 - 60
Finalmente, o critério de parada foi satisfeito e a solução ótima (S*) foi 
encontrada com:
Min	Z	=	14×60	+	110	+	12×70	+	120	=	1910.
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 14
5. o problema de transporte com transbordo
Problemas de Transbordo possuem uma característica mais geral em rela-
ção ao problema clássico de transportes. Neste problema, nós de transbor-
do são aqueles que enviam e recebem mercadorias, podendo ser ao mes-
mo tempo nós de fornecimento (por exemplo, fabricação) ou de demanda. 
armazéns clientesfábricas
Neste tipo de problema, procura-se diminuir o custo total de transporte 
ao despachar mercadorias com a utilização de nós intermediários antes 
de chegar ao seu destino final. Nesta seção, um problema de transbordo 
será convertido e resolvido como um problema de transporte clássico. 
Para isso, é preciso dividir todo nó de transbordo em dois: um de origem 
e outro de destino, tal como ilustrado na Figura 3.
dois nósi
oi
di
xij
xii
xji
Esses novos nós devem ter as seguintes quantidades associadas:
 → Nó de demanda: quantidade máxima da mercadoria que poderá 
chegar até ele, possivelmente seja a quantidade total de fornecimen-
to no sistema;
 → Nó de fornecimento: da quantidade no nó de demanda deve ser 
subtraída a demanda original (como destino final neste nó) se houver.
ExEmplo
O Governo de um país pobre vive o surto de uma doença nova e precisa 
adquirir vacinas para imunizar pessoas de uma determinada faixa-etária, 
sexo e condição de vulnerabilidade. Esse governo é responsável por fazer 
Figura 2. 
Ilustração de 
um problema de 
transportes com 
transbordo.
Fonte: adaptado 
de <www.ingenieria 
industrialonline.com>.
Figura 3. 
Representação da 
divisão de um nó 
de transbordo em 
um de origem e 
outro de demanda.
http://www.ingenieriaindustrialonline.com
http://www.ingenieriaindustrialonline.com
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 15
chegarem 400 caixas de vacinas à região Norte do país e 520 caixas na 
região Sul. A ONU está ajudando o país por meio de um doador anônimo, 
que pagará a aquisição das vacinas, porém, o custo de transporte das cai-
xas será arcado pelo Governo daquele país.
Devido à dificuldade de encontrar matéria-prima para a produção, não 
há muitas opções de fornecedores da vacina pronta, os mercados encon-
trados foram: Japão com capacidade de produzir 220 vacinas, Brasil 300 e 
E.U.A 400. Portanto, o Governo está se deparando com duas dificuldades, 
a saber: a. não haverá vacinas suficientes para todos e b. o custo de trans-
porte direto daqueles países é extremamente alto em alguns casos, o que 
faria com que, mesmo não tendo que arcar com o custo de aquisição das 
vacinas, o valor a ser gasto no transporte de todas as vacinas superaria o 
orçamento disponível. 
Para ajudar aquele país, você, estudante de pesquisa operacional em 
uma renomada universidade do Brasil, resolveu fazer um estudo para 
diminuir o custo do transporte e descobriu primeiro que: existe a pos-
sibilidade de fazer a baldeação das vacinas utilizando o porto de Cuba e 
o depósito de vacinas da Bélgica, que, devido a acordos comerciais, fará 
diminuir os custos de maneira suficiente para caber no orçamento do 
Governo do país demandante. Assim, você chegou aos seguintes custos 
de transporte: 
custo do transporte por 
caixa de vacinas em us$
capacidade
*cuba *bélgica região norte
região 
sul
brasil 40 45 - - 300
japão 55 30 - - 220
e.u.a. - 35 - - 400
*cuba 0 25 30 40 ?
*bélgica 25 0 40 35 ?
demanda ? ? 400 520
Então, você apresentou o seguinte desenvolvimento:
Rede do problema:
Brasil
E.U.A.
Japão
Cuba
Bélgica
Norte
Sul
25
40
55
30
35
45
30
35
40
40
Tabela 2. 
Custo de transporte 
por caixa de 100 
unidades da vacina.
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 16
Resolução:
Onde não há possibilidade de transporte, atribui-se o M (um custo grande 
o suficiente para inviabilizar a atribuição na variável). Tanto Cuba como 
Bélgica, pode receber a quantidade total de fornecimento (920 caixas).
cuba bélgica norte sul capacidade
brasil 40 45 M M 300
japão 55 30 M M 220
e.u.a. M 35 M M 400
cuba 0 25 30 40 920
bélgica 25 0 40 35 920
demanda 920 920 400 520
Deve-se atribuir um valor ao M (custo alto onde não há transporte), um 
valor suficiente é 999.
cuba bélgica norte sul capacidade
brasil 40 45 999 999 300
japão 55 30 999 999 220
e.u.a. 999 35 999 999 400
cuba 0 25 30 40 920
bélgica 25 0 40 35 920
demanda 920 920 400 520
Construção de uma solução básica inicial pelo método de aproximação 
de Vogel.
método: vogel
disponibilidade
cuba bélgica norte sul
brasil –
40
300
45
–
999
–
999
300
X11 X12 X13 X14
japão –
55
220
30
–
999
–
999
220
X21 X22 X23 X24
E.U.A. –
999
400
35
–
999
–
999
400
X31 X32 X33 X34
cuba 920
0
–
25
–
30
–
40
920
X41 X42 X43 X44
bélgica –
25
–
0
400
40
520
35
920
X51 X52 X53 X54
demanda 920 920 400 520  
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 17
Aplicando o método de stepping stone:
método: stepping stone
disponibilidade
cuba bélgica norte sul
brasil 300
40
–
45
–
999
–
999
300
X11 X12 X13 X14
japão –
55
220
30
–
999
–
999
220
X21 X22 X23 X24
E.U.A. –
999
400
35
–
999
–
999
400
X31 X32 X33 X34
cuba 620
0
–
25
300
30
–
40
920
X41 X42 X43 X44
bélgica –
25
300
0
100
40
520
35
920
X51 X52 X53 X54
demanda 920 920 400 520  
 → Ponto de fornecimento {Brasil, Japão e E.U.A};
 → Ponto de demanda {Norte e Sul};
 → Recebimento e Repasse {Cuba e Bélgica}.
Portanto, o governo daquele país gastará US$ 63.800,00 no transporte 
das vacinas.
Código no software LINDO:
min 40x11 + 45x12 + 999x13 + 999x14 + 55x21 + 30x22 + 999x23 + 999x24 + 
999x31 + 35x32 + 999x33 + 999x34 + 25x42 + 30x43 + 40x44 + 25x51 + 40x53 
+ 35x54
st
x11 + x12 + x13 + x14 = 300
x21 + x22 + x23 + x24 = 220
x31 + x32 + x33 + x34 = 400
x41 + x42 + x43 + x44 = 920
x51 + x52 + x53 + x54 = 920
x11 + x21 + x31 + x41 + x51 = 920
x12 + x22 + x32 + x42 + x52 = 920
x13 + x23 + x33 + x43 + x53 = 400
x14 + x24 + x34 + x44 + x54 = 520
end
gin 20
Agora com a Região Norte como nó de destino e de transbordo:
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 18
custo do transporte por 
caixa de vacinas em us$
capacidade
*cuba *bélgica região norte
região 
sul
brasil 40 45 M M 300
japão 55 30 M M 220
e.u.a. M 35 M M 400
*cuba 0 25 30 40 920
*bélgica 25 0 40 35 920
r. norte M M 0 5 920-400
demanda 920 920 920 520
Rede do problema:
Brasil
E.U.A.
Japão
Cuba
Bélgica
Norte
Sul
25
40
55
30
35
45
30
35
40
40
5
Construção de uma solução pelo método de Vogel.
método: vogel
disponibilidade
cuba bélgicanorte sul
brasil –
40
300
45
–
999
–
999
300
X11 X12 X13 X14
japão –
55
220
30
–
999
–
999
220
X21 X22 X23 X24
E.U.A. –
999
400
35
–
999
–
999
400
X31 X32 X33 X34
cuba 920
0
–
25
–
30
–
40
920
X41 X42 X43 X44
bélgica –
25
–
0
400
40
520
35
920
X51 X52 X53 X54
norte –
0
–
25
920
30
–
35
520
X41 X42 X43 X54
demanda 920 920 400 520  
Pesquisa Operacional I / Aulas 13–16 Problemas de Transporte 19
REFERÊNCIAs
BELFIORI, P. PAULO, L.� Pesquisa Operacional 
Para Cursos de Engenharia. Editora Cam-
pus Elsevier, Edição: 1, 2012.
COLIN, E.C. �Pesquisa Operacional - 170 apli-
cações. Editora LTC, Edição 1, 2007.
CAIXETA-FILHO, J.V. �Pesquisa Operacional. 
2.ed. Atlas, 2004.
GOLDBARG, M.C.; LUNA, H.P.� Otimização com-
binatória e programação linear. 2.ed. El-
sevier, 2005.
MARINS, FERNANDO AUGUSTO SILVA. �Introdução 
à Pesquisa Operacional. Cultura acadêmi-
ca, 2011.