PO TRANSPORTES

Prévia do material em texto

PESQUISA OPERACIONAL 
APLICADA AOS TRANSPORTES
CURSO DE ENGENHARIA DE PRODUÇÃO - UFPI
Prof. Dr. Francisco 
Pinheiro
Prof. Airton CarneiroProf. Francisco Pinheiro
PROBLEMAS DE TRANSPORTES
A estruturação do problema de transportes é uma
aplicação interessante de programação linear. A Pesquisa
Operacional estuda esses problemas com o objetivo de
minimizar custos de transporte.
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
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
Exemplo: A LCL Bicicletas 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
consumidor de forma a minimizar os custos de transporte.
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Existem 9 variáveis de decisão para expressar a
quantidade transportada em cada uma das possíveis
vias.
 xij = Quantidade de bicicleta transportada da fábrica i
para o centro consumidor j.





-
-
-
=
HorizonteBelo3
PauloSão2
Rio1
i





-
-
-
=
Manaus3
Salvador2
Recife1
j
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
RIO
SP
BH
REC
SAL
MAN
x12
x13
x21
x22
x23
x31
x32
x33
Centro Consumidor
Fábrica REC SAL MAN
Rio x11 x12 x13
SP x21 x22 x23
BH x31 x32 x33
x11
Função Objetivo:
Min 25x11+ 20x12+ 30x13+ 30x21+
25x22+ 25x23+ 20x31+ 15x32+ 23x33
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
1000
2000
2000
1500
1500
2000
332313
322212
312111
333231
232221
131211
=
=
=
=
=
=
xxx
xxx
xxx
xxx
xxx
xxx
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
Restrições:
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Para solucionar o problema de transporte costuma-se
representar seus dados conforme segue no Quadro a seguir.
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Exemplo: Uma empresa tem 3 fábricas e 3 depósitos para
distribuição de seus produtos (CD – Centros de distribuição).
Os custos de transporte e capacidades são dados nas tabelas
abaixo. O objetivo é minimizar o custo de transporte das
unidades fabris aos CD, conhecendo os custos de transporte.
Custos de transporte
Fábrica
Depósitos
1 2 3
1 8 15 3
2 5 10 9
3 6 12 10
Capacidade de 
produção
Fábrica Produção
1 120
2 80
3 80
Capacidade de 
armazenagem
CD Capacidade
1 150
2 70
3 60
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Fábrica
1
2
3
1
2
3 
x11
x12
x13
x21
x22
x23
x31
x32
x33
Depósitos
Produções
Capacidades
120
80
80
150
70
60
Total = 280 Total = 280Problema Balanceado 
8
15
3
5
10
9
6
12
10
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Produção
x11 + x12 + x13 = 120
x21 + x22 + x23 = 80
x31 + x32 + x33 = 80
Capacidade
x11 + x21 + x31 = 150
x12 + x22 + x32 = 70
x13 + x23 + x33 = 60
Custo
8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = FO
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
1
2
3
1
2
3 
x11
x12
x13
x21
x22
x23
x31
x32
x33
120
80
80
150
70
60
Total = 280 Total = 280
8
15
3
5
10
9
6
12
10
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60
280/280
Balanceado
8
15
3
5
10
9
6
12
10
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60 280
120
30 50
20 60
Método do Canto Noroeste
Custo
8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = FO = 2690
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
0
0
0
0
Prof. Airton CarneiroProf. Francisco Pinheiro
Método do Menor Custo
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70
0 70
0
0 0
10
50
Custo
8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = FO = 2060
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Método de Voguel
8
15
3
5
10
9
6
12
10
80
80
120
150 70 60
8 - 3 = 5 9 - 5 = 4 10 - 6 = 4
6 - 5 = 1
12 - 10 = 2
9 - 3 = 6
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Método de Voguel
8
15
3
5
10
9
6
12
10
80
80
120
150 70 60
8 - 3 = 5 9 - 5 = 4 10 - 6 = 4
6 - 5 = 1
12 - 10 = 2
9 - 3 = 680
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Método de Voguel
8
15
3
5
10
9
6
12
10
80
80
120
150 70 60
15 - 8 = 7 10 - 5 = 5 12 - 6 = 6
6 - 5 = 1
12 - 10 = 2
9 - 3 = 680
70 50
70 10
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70 50
70 10
X11=70; x22=70; x31=80; x13=50; x23=10
FO = 8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = 1920
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método de Voguel
0
00
0
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
PROBLEMA!!!!!! COMO PROVAR QUE ESTA É A 
MELHOR SOLUÇÃO???
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70
70
10
50
Método do 
Menor 
Custo, 
FO=2060
X11= +8 – 6 + 12 – 15 = -1
X22= +10 – 12 + 6 – 5 = -1
X32= +9 – 3 + 15 – 12 + 6 – 5 = 10
X33= +10 – 12 + 15 - 3 = 10
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70
70
10
50+1
+1
-1
-1
50
20
0
60
FO = 50*8 + 70*5 + 20*15 + 60*12 + 80*3 = 2010
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
20
70
60
50
FO = 2010
X13= +6 – 12 + 15 – 8 = +1
X22= +10 – 15 + 8 – 5 = -2
X32= +9 – 3 + 8 – 5 = 9
X33= +10 – 3 + 15 - 12 = 10
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
20
7060
50
+1
+1-1
-1
20
5070
0
FO = 70*8 + 50*5 + 20*10 + 60*12 + 80*3 = 1970
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
50
60
70
20
FO = 1970
X13= +6 – 12 + 10 – 5 = -1
X21= +15 – 8 + 5 – 10 = +2
X32= +9 – 3 + 8 – 5 = 9
X33= +10 – 3 + 8 – 5 +10 -12 = 8
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
50
60
70
20
FO = 1970
-1
+1
+1
-1
50
70 10
FO = 70*8 + 50*6 + 70*10 + 00*12 + 80*3 = 1920
0
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Método do Steping-Stone
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70
FO = 1920
50
70 10
X12= +5 – 6 + 12 – 10 = +2
X21= +15 – 12 + 6 – 8 = +10
X32= +9 – 3 + 8 – 6 +12 – 10 = +10
X33= +10 – 3 + 8 – 6 = +9
Sem negativos! 
Solução Ótima
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
80
70 50
70 10
X11=70; x22=70; x31=80; x31=50; x23=10
FO = 8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = 1920
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Voguel/ Confirmado por Steping Stone
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
80
80
120
150 70 60
280/280
Balanceado
8
15
3
5
10
9
6
12
10
Quando os valores não representam custos, mas sim, os ganhos unitários devido à
venda de mercadorias compradas nas origens e comercializadas nos destinos. Deste
modo o objetivo será maximizar o retorno proveniente das vendas.
O caso da maximização em transportes (método do
complemento)
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
80
80
120
150 70 60
280/280
Balanceado
8
15
3
5
10
9
6
12
10
Pega-se o maior valor (15), e cada
cada célular será dada por 15 menos o
valor atual
X11 15 – 8 = 7
X1215 – 5 = 10
X1315 – 6 = 9
X2115 – 15 = 0
80
80
120
150 70 60
280/280
Balanceado
7
0
12
10
5
6
9
3
5
X22 15 – 10 = 5
X2315 – 12 = 3
X3115 – 3 = 12
X3215 – 9 = 6
X3315 – 10 = 5
Aplicando os valores, a nova tabela
será formada:
Seguindo agora pelo método de Vogel,
teremos:
Prof. Airton CarneiroProf. Francisco Pinheiro
Método de Voguel
7
0
2
10
5
6
9
3
5
80
80
120
150 70 60
2-0 = 2 6 - 5 = 1 5 - 3 = 2
9 - 7 = 2
3 - 0 = 3
5 - 2 = 3
80
70 50
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
Método de Voguel
7
0
2
10
5
6
9
3
5
80
80
120
150 70 60
7-2 = 5 10 - 6 = 4 9 - 5 = 4
9 - 7 = 2
3 - 0 = 3
5 - 2 = 3
80
70
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
10
5070
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60 280
7
0
2
10
5
6
9
3
5
70
70 50
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
10
80
X11= +7 – 9 + 5 – 2 = +1
X22= +5 – 10 + 9 – 5 + 2 – 0 = +1
X23= +3 – 5 + 2 – 0 = 0
X32= +6-10 + 9 – 5 = 0
Como todos os valores são positivos, estamos diante da
solução ótima, ou seja: x12 =70, x13=50, x21=80,
x31=70 e x33=10
Prof. Airton CarneiroProf. Francisco Pinheiro
80
80
120
150 70 60 280
8
15
3
5
10
9
6
12
10
70
70 50
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
10
80
Sabendo o valor ótimo do fluxo, precisamos calcular o retorno, para isso, insere-se na tabela
os valores originais de retorno:
X12=70; x31=50; x21=80; x31=70; x33=10
FO = 8x11 + 5x12 + 6x13 +15x21 + 10x22 + 12x23 + 3x31 + 9x32 + 10x33 = 2160
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
COMPLICADORES
 Problema não Balanceado ( seja na oferta ou
na demanda)
Deve-se criar um destino/origem fictícia para
absorver o desequilíbrio a custo zero de transporte
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
COMPLICADORES
 Usos de Sistema de Transporte (quando houver
recursos com múltiplas origens e mais de um
destino)
 - Fornecimento de água – Rios e cidades
 - Rede de transmissão de dados – Origem e Demanda
 - Grão nas fazendas e sistemas de silos de armazenagem
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 1: Três usinas de geração de energia elétrica com
capacidades de 25, 40 e 30 milhões de kWh fornecem
eletricidade a três cidades. As demandas máximas das três
cidades são estimadas em 30, 35 e 25 milhões de kwh, Os
preços por milhão de kwh nas três cidades é dado na Tabela A.
Durante o mês de agosto há um aumento de 20% na demanda
em cada uma das três cidades, que pode ser satisfeito com a
compra de fornecimento de eletricidade de uma outra rede, a
uma taxa mais elevada, por R$ 1.000 por milhão de kWh.
Contudo, a rede não está ligada à Cidade 3. A empresa
fornecedora deseja determinar o plano mais econômico para a
distribuição e compra de energia adicional.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
(a) Formule a questão como um problema de transporte.
(b) Determine um plano de distribuição ótimo para a empresa
fornecedora.
(c) Determine o custo da energia adicional comprada por cada
uma das três cidades.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 2: Resolva o Exemplo 2 considerando que há uma 
perda de 10% na transmissão de energia em toda a rede. 
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 3: Três refinarias com capacidades diárias de 6,5 e 8 milhões
de galões, respectivamente, abastecem três áreas de distribuição cujas
demandas diárias são 4,8 e 7 milhões de galões, respectivamente, A
gasolina é transportada para as três áreas de distribuição por meio de
uma rede de tubulações, O custo de transporte é 10 centavos por
1.000 galões por milha de tubulação. A Tabela B dá as distâncias entre
as refinarias e as áreas de distribuição. A Refinaria 1 não está
conectada à área de distribuição 3.
(a) Formule o problema de transporte associado.
(b) Determine a programação ótima de expedição na rede.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 4: No Exemplo 3, suponha que a capacidade da Refinaria
3 seja Apenas 6 milhões de galões e que a área de distribuição 1
deva receber toda a sua demanda. Ademais, quaisquer fatias nas
áreas 2 e 3 sofrerão uma multa de 500 centavos.
(a) Formule a questão como um problema de transporte.
(b) Determine a programação ótima de expedição.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 5: No Exemplo 3, suponha que a demanda diária na área
3 caia para 4 milhões de galões. A produção excedente nas
refinarias 1 e 2 é desviada para outras áreas de distribuição por
caminhão-tanque.
O custo de transporte por 100 galões é R$1,50 da Refinaria 1 e R$
2,20 da Refinaria 2. A Refinaria 3 pode destinar seu excedente de
produção para outros processos químicosdentro da fabrica.
(a) Formule a questão como um problema de transporte.
(b) Determine a programação ótima de expedição.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 6: Três pomares fornecem caixas de laranjas a quatro varejistas.
As demandas diárias dos quatro varejistas são 150, 150, 400 e 100
caixas, respectivamente. As quantidades fornecidas pelos três pomares são
determinadas pela mão-de-obra normal disponível e são estimadas em
150, 200 e 250 caixas por dia. Contudo, os pomares l e 2 indicaram que
poderiam fornecer mais caixas, se necessário, usando horas extras. O
Pomar 3 não oferece essa opção. Os custos de transporte por caixa dos
pomares ate os varejistas são dados na Tabela C.
(a) Formule a questão como um problema de transporte.
(b) Resolva o problema.
(c) Quantas caixas os pomares 1 e 2 devem fornecer usando horas extras?
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
 Exemplo 7: Três centrais de distribuição enviam carros para cinco
revendedoras. O custo de expedição é baseado nas distancias entre as
origens e os destinos e independe de a carreta fazer a viagem com
cargas parciais ou completas. A tabela D resume as distancias entre as
centrais de distribuição e as revendedoras, junto com as quantidades
fornecidas e as demandas, ambas mensais, dadas em números de
carros. Uma carga completa corresponde a 18 carros. O custo de
transporte por milha por carreta é R$ 25.
(a) Formule o problema de transporte associado.
(b) Determine a programação ótima de expedição.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
É um caso especial do modelo de transportes onde cada
origem tem uma unidade disponível e cada destino necessita também
de uma unidade. É o caso de escalar vendedores para regiões de
vendas, máquinas para diversos locais, dentre outras.
No modelo de designação, o número de origens deve ser
igual ao número de destinos devido a sua característica. Caso isso
não ocorra, devemos construir origens ou destinos auxiliares, com custo
de transferência zero.
O PROBLEMA DA DESIGNAÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Descrição do Algoritmo
a) Subtrair de cada linha seu menor valor. Em seguida fazer o mesmo
com as colunas. Cada linha e cada coluna deverá então apresentar
pelo menos um elemento nulo (zero).
b) Designar origens para destinos nas células em que aparece o
elemento nulo. Dar preferência a linhas ou colunas que tenham
apenas um zero disponível. Cada designação efetuada invalida os
outros zeros na linha e na coluna da célula designada. Se a
designação for completa, o problema está resolvido. Se não realizar
o “cobrimento”, conforme os passos a seguir:
O PROBLEMA DA DESIGNAÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Descrição do Algoritmo
c) Cobrir os zeros da tabela com o menor número de linhas possível,
fazendo da seguinte maneira:
 Marcar as linhas sem designação.
 Marcar as colunas com zeros nas linhas marcadas.
 Marcar as linhas com designação nas colunas marcadas.
 Voltar a marcar as colunas com zeros nas linhas marcadas até que
não seja possível marcar novas linhas ou colunas.
 Riscar as linhas não marcadas e as colunas marcadas.
O PROBLEMA DA DESIGNAÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
d) Subtrair o menor valor dentre os números não cobertos, de todos
os elementos da tabela. A reposição necessária nas linhas e colunas
com zeros para impedir o aparecimento de custos negativos na
tabela, resulta o quadro em que:
Os elementos não cobertos ficam diminuídos deste número;
Os elementos no cruzamento de coberturas (riscados duas vezes)
ficam aumentados desse número;
Outros elementos permanecem iguais.
e) Retornar ao item b.
O PROBLEMA DA DESIGNAÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Exemplo: O quadro a seguir representa os custos de transporte de
uma máquina dos locais de depósito para as fábricas onde deverão
ser instaladas. Designar uma máquina para cada fábrica com o
menor custo possível no programa:
1º:subtrair o menor número de cada linha
10
12
10
12
10 -10 12 -10 15 -10 16 -10
14 -12 12 -12 13 -12 18 -12
14 -12 12 -12 13 -12 15 -12
10 -10 16 -10 19 -10 15 -10
0 2 5 6
2 0 1 6
2 0 1 3
0 6 9 5
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
2º:subtrair o menor número de cada coluna
0 -0 2 -0 5 - 1 6 - 3
2 - 0 0 - 0 1 -1 6 - 3
2 - 0 0 - 0 1 -1 3 - 3
0 -0 6 -0 9 -1 5 - 3
0 2 5 6
2 0 1 6
2 0 1 3
0 6 9 5
0 0 1 3
0 2 4 3
2 0 0 3
2 0 0 0
0 6 8 2
Designar nos zeros de linhas ou colunas
(prefira linhas ou colunas com apenas um
zero)
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
A designação não se completou devido à origem 3 e ao destino 3. Realizar então o
cobrimento.
0 2 4 3
2 0 0 3
2 0 0 0
0 6 8 2
Cobrir com o menor número de linhas, os
zeros da tabela.
a) Nº não riscados: Escolhe o menor e
subtraí-lo de todos os não riscados. O
menor é o 2.
b) Nº riscados uma vez: Mantém os
mesmos números.
c) Nº riscados duas vezes: soma-se ao
número que foi subtraído. 2.
0 2-2 4-2 3-2
2+2 0 0 3
2+2 0 0 0
0 6-2 8-2 2-2
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
A nova tabela fica:
0 0 2 1
2 0 0 3
4 0 0 0
0 4 6 0
Fazendo a designação
Assim, temos que:
O D1 manda para o F1
O D2 manda para o F2
O D3 manda para o F4
O D4 manda para o F3
Dessa forma, o custo será dado por:
10 + 12 + 15 + 13 = 50
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
O caso da maximização
Caso a tabela de transferência traga retornos que devem ser
maximizados, o modelo deve ser substituído por outro de minimização.
Isso pode ser feito multiplicando a função objetivo por (-1), ou
transformando o quadro num quadro de perdas (complemento em
relação a um valor fixo).
Exemplo: O quadro a seguir representa as eficiências de quatro
vendedores, testados em quatro regiões. Os potenciais de vendas nas
regiões são conhecidos. Designar um vendedor para cada região para
maximizar o valor total das vendas.
O PROBLEMA DA DESIGNAÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
70 60 80 90
70 80 70 90
70 80 70 80
60 90 60 70
Capacidade de cada vendedor de atingir o potencial da região em %
Potencial de vendas em milhares de R$
F1 = 100
F2 = 80
F3 = 60
F4 = 90
Exemplo: O quadro a seguir representa as eficiências de quatro
vendedores, testados em quatro regiões. Os potenciais de vendas nas
regiões são conhecidos.Designar um vendedor para cada região para
maximizar o valor total das vendas.
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
70 60 80 90
70 80 70 90
70 80 70 80
60 90 60 70
Capacidade de cada vendedor de atingir o potencial da região em %
Potencial de vendas em milhares de R$
F1 = 100
F2 = 80
F3 = 60
F4 = 90
70 48 48 81
70 64 42 81
70 64 42 72
60 72 36 63
Quadro de vendas ou retornos (% x Potencial
de Vendas)
11 33 33 0
11 17 39 0
11 17 39 9
21 9 45 18
Quadro de perdas: subtrair de 81
81-70 81-48 81-48 81-81
81-70 81-64 81-42 81-81
81-70 81-64 81-42 81-72
81-60 81-72 81-36 81-63
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
Subtrair o menor de cada linha
Subtrair o menor de cada coluna
11 33 33 0
11 17 39 0
11 17 39 9
21 9 45 18
11-0 33-0 33-0 0-0
11-0 17-0 39-0 0-0
11-9 17-9 39-9 9-9
21-9 9-9 45-9 18-9
11 33 33 0
11 17 39 0
2 8 30 0
12 0 36 9
0
0
9
9
11-2 33-0 33-30 0-0
11-2 17-0 39-30 0-0
2-2 8-0 30-30 0-0
12-2 0-0 36-30 9-0
2 0 30 0
9 33 3 0
9 17 9 0
0 8 0 0
10 0 6 9
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
9 33 3 0
9 17 9 0
0 8 0 0
10 0 6 9
Designar nos zeros de linhas ou colunas
(prefira linhas ou colunas com apenas um
zero)
A designação não se completou devido à origem D2 e ao destino F3. Realizar então o
cobrimento. Cobrir com o menor número de linhas, os zeros da
tabela.
a) Nº não riscados: Escolhe o menor e subtraí-
lo de todos os não riscados. O menor é o 3.
b) Nº riscados uma vez: Mantém os mesmos
números.
c) Nº riscados duas vezes: soma-se ao número
que foi subtraído =3.
9 33 3 0
9 17 9 0
0 8 0 0
10 0 6 9
Prof. Airton CarneiroProf. Francisco Pinheiro
PESQUISA OPERACIONAL APLICADA AOS TRANSPORTES
9-3 33-3 3-3 0
9-3 17-3 9-3 0
0 8 0 0+3
10 0 6 9+3
6 30 0 0
6 14 6 0
0 8 0 3
10 0 6 12
Assim, temos que:
O D1 manda para o F3
O D2 manda para o F4
O D3 manda para o F2
O D4 manda para o F1
Dessa forma, o retorno de vendas será dado por:
Total de vendas = 48 + 81 + 72 + 70 = 271
70 48 48 81
70 64 42 81
70 64 42 72
60 72 36 63