Apostila Pesquisa operacional

Prévia do material em texto

14/08/2017
1
11
Professor – Paulo Amorim
Disciplina: Pesquisa Operacional
Pesquisa Operacional
A PO como ciência aplica-se a:
A PO surgiu no início da Segunda Guerra Mundial com
fins bélicos, especificamente no dimensionamento do número
de navios mercantes dos aliados, que formavam comboios e
atravessavam o atlântico escoltados por navios de guerra,
como o objetivo de prevenir dos ataques dos torpedos dos
submarinos alemães.
Aplicada também para estudar de forma sistemática e
racional os processos envolvidos na realização de uma
atividade produtiva, com ênfase na otimização, minimização de
esforços e maximização de resultados.
2
14/08/2017
2
Pesquisa Operacional
A PO como ciência aplica-se a:
Pessoas (organização e gerência, relações de
trabalho, economia, decisões individuais, pesquisa do
mercado, etc);
Máquinas (eficiência e produtividade,
organização de fluxos em fábricas, métodos de
controle de qualidade, organização de mudanças
tecnológicas, etc);
Movimento (transporte, estoque, distribuição,
manipulação, comunicação, localização, etc.)
3
Programação linear
Modelagem de um problema de programação 
linear:
Programação Linear é uma ferramenta para 
solução de problemas de otimização, utilizada em 
diversos segmentos da atividade produtiva. Na 
modelagem de problemas, devem ser estabelecidas:
• As variáveis do problema: aquilo que se pode 
controlar e que se deseja saber o quanto vale;
• A função objetivo: se quer maximizar ou minimizar 
determinado objetivo, expresso em função das 
variáveis do problema;
• As restrições: limitam as combinações da variáveis.
4
14/08/2017
3
Modelagem de um Problema de Transporte
Exemplo 1:
Certa empresa fabrica dois produtos P1 e P2.
O lucro unitário do produto P1 é de 1000 u.m. e o lucro
unitário de P2 é 1800 u.m.. A empresa precisa de 20
horas para fabricar uma unidade de P1 e de 30 hs para
fabricar uma unidade de P2.
O tempo anual de produção disponível para isso é de
1200 hs. A demanda máxima esperada para cada
produto é de 40 unid. anuais para P1 e 30 unid. anuais
para P2.
Qual é o plano de produção para que a empresa
maximize seu lucro nesses itens?
Construa o modelo de programação linear para esse
caso. 5
Solução:
a) Quais as variáveis de decisão?
• x1 quantidade anual a produzir de P1
• x2 quantidade anual a produzir de P2
b) Qual o objetivo?
O objetivo é maximizar o lucro, que pode ser calculado:
Lucro total: L= 1000x1 + 1800x2
c) Quais as restrições?
• Disponibilidade de horas (1200 hs): 20 x1 + 30x2 ≤ 1200
• Demanda P1 (40 unid): x1 ≤ 40
• Demanda P2 (30 unid): x2 ≤ 30
6
Modelagem de um Problema de Transporte
14/08/2017
4
Modelagem de um Problema de Transporte
Solução:
Resumo do modelo : Max Z = 1000x1 + 1800x2
Sujeito a:
20 x1 + 30x2 ≤ 1200
x1 ≤ 40
x2 ≤ 30
x1, x2 ≥ 0
7
Modelagem de um Problema de Transporte
Exemplo 2:
Para uma boa alimentação, o corpo necessita de vitaminas e
proteínas. A necessidade mínima de vitaminas é de 32 unid. por
dia e a de proteínas de 36 unid. por dia.
Uma pessoa tem disponível carne e ovos para se alimentar.
Cada unid. de carne contém 4 unid. de vitaminas e 6 unid. de
proteínas. Cada unid. de ovo contém 8 unid. de vitaminas e 6
unid. de proteínas.
Qual a quantidade diária de carne e ovos que deve ser
consumida para suprir as necessidades de vitaminas e
proteínas com o menor custo possível?
Cada unid. de carne custa 3 u.m. e cada unid. de ovo custa 2,5
u.m.
8
14/08/2017
5
Modelagem de um Problema de Transporte
a) Quais as variáveis de decisão?
• x1 quantidade diária de carne
• x2 quantidade diária de ovos
b) qual o objetivo? Menor custo possível
Min Z = 3x1 + 2,5x2
c) quais as restrições
• Mín. vitamina (32unid /dia): 4x1 + 8x2 ≥ 32
• Mín. proteína (36unid /dia): 6x1 + 6x2 ≥ 36
Solução:
Resumo do modelo : Min Z = 3x1 + 2,5x2
Sujeito a:
4x1 + 8x2 ≥ 32
6x1 + 6x2 ≥ 36
x1, x2 ≥ 0
9
Modelagem de um Problema de Transporte
Exemplo 3:
A Votram fabrica soldados e trens de madeira.
Cada soldado é vendido por $27 e utiliza $10 de matéria-prima e
$14 de mão-de-obra. 2 h de acabamento e 1 h de carpintaria
são demandadas para produção de um soldado.
Cada trem é vendido por $21 e utiliza $9 de matéria-prima e $10
de mão-de-obra. 1 h de acabamento e 1 h de carpintaria são
demandadas para produção de um trem.
A Votram não tem problemas no fornecimento de matéria-prima,
mas só pode contar com 100 h de acabamento e 80 h de
carpintaria.
A demanda semanal de trens é ilimitada, mas no máximo 40
soldados são comprados a cada semana.
10
14/08/2017
6
Modelagem de um Problema de Transporte
A Votram deseja maximizar seus ganhos semanais.
Formule um modelo matemático a ser utilizado nessa
otimização.
Variáveis de decisão- A Votran deve decidir sobre:
x1 = núm. de soldados produzidos a cada semana
x2 = núm. de trens produzidos a cada semana
Função objetivo- A função a ser maximizada (ou minimizada) 
é a função objetivo.
A Votram deseja maximizar seus ganhos semanais:
Ganho = venda de soldados + venda de trens.
= ($/soldado).(soldados/sem) + ($/trem). (trem/sem)
= 27x1 + 21x2
11
Modelagem de um Problema de Transporte
Custo matéria-prima: 10x1 + 9x2
Custo mão-de-obra: 14x1 + 10x2
O que a Votram deseja maximizar é:
(27x1 + 21x2) - (10x1 + 9x2) - (14x1 + 10x2) = 3x1 + 2x2
Usaremos a variável z para designar o valor assumido pela 
função objetivo.
Assim:
Max z = 3x1 + 2x2
12
14/08/2017
7
Modelagem de um Problema de Transporte
Restrições
• Restrição 1= 100 h de acabamento / semana.
• Restrição 2= 80 h de carpintaria / semana
• Restrição 3=não mais que 40 soldados/ semana (demanda).
2x1 + x2 ≤ 100 Restrição de horas de acabamento
x1 + x2 ≤ 80 Restrição de horas de carpintaria
x1 ≤ 40 Restrição de demanda
13
Modelagem de um Problema de Transporte
Combinando a função objetivo e as restrições, chega-se a 
formulação matemática do problema da Votram:
Max z = 3x1 + 2x2
Sujeito a:
2x1 + x2 ≤ 100 Restrição de horas de acabamento
x1 + x2 ≤ 80 Restrição de horas de carpintaria
x1 ≤ 40 Restrição de demanda
x1, x2 ≥ 0 Restrição de sinal (não negatividade)
14
14/08/2017
8
Modelagem de um Problema de Transporte
Exemplo 4:
Um agricultor deseja cultivar duas variedades de cereais, A e B,
em uma área restrita a um hectare (1 hectare= 100 ares), sendo
que cada are cultivado pelo cereal A produz 8 sacas, enquanto
cada are cultivado pelo cereal B produz 10 sacas. Para o
plantio, cada are cultivado pelo cereal do tipo A precisa de 3
homens-hora de trabalho, e o cultivado do cereal B precisa de 2
homens-hora, sendo que se dispõe de até 240 homens-hora de
trabalho para o cultivo.
O custo da mão de obra é de 200 u.m. (Unid. Monetárias) por
homem-hora. A demanda máxima é limitada pelo mercado
consumidor a 480 sacas do cereal tipo A, vendido a 150 u.m.
por saca, e 800 sacas do cereal tipo B, vendido a 120 u.m. por
saca.
15
Modelagem de um Problema de Transporte
O agricultor deseja planejar a sua produção de forma a maximizar
o lucro
a) Quais as variáveis de decisão
x1= Quantidade de ares cultivados pelo sereal A
x2= Quantidade de ares cultivados pelo sereal B
Quantidade de ares a serem cultivados por cada variedade de
cereal de forma a maximizar os lucros
b) Função objetivo: Max Lucro Z= receita – custo
Receita
A(x1)= 8 sacas x 150u.m. (para cada are cultivado)
B(x2)= 10 sacas x 120u.m. (para cada are cultivado)
Receita= 1.200x1 + 1.200x2
16
14/08/2017
9
Modelagem de um Problema de Transporte
b) Função objetivo: Max Lucro Z=receita – custo
Custo
A(x1)= 3 homens-hora x 200u.m.
B(x2)= 2 homens-hora x 200u.m.
Custo= 600x1 + 400x2
Max Z= 600x1 + 800x2
c) Restrições
x1 + x2 ≤ 100 (Ares disponíveis)
3x1 +2x2 ≤ 240 (Homens-hora)
8x1 ≤ 480 = x1 ≤ 60 (Demanda do tipo A)
10x2 ≤ 800 = x2 ≤ 80 (Demanda do tipo B)
17
Modelagem de um Problema de Transporte
Solução: Modelo matemático
Max Z= 600x1 + 800x2
Sujeito as restrições:
x1 + x2 ≤ 100
3x1 + 2x2 ≤ 240
x1 ≤ 60
x2 ≤ 80
x1, x2 ≥ 0
18
14/08/2017
10
19
É talvez o mais representativo dos Problemas de
Programação Linear, apresentando uma vasta
aplicação prática por meio de um método sistemático
de resolução.
O problema (geral) de transporte consiste em:
determinar a forma mais econômica (ou mais lucrativa)
de enviar um bem disponível em quantidades limitadas
de determinados locais para outros.
Como qualquer problema de PL, este pode ser
resolvido pelo método do simplex, entretanto, por
possuir uma estrutura particular, permite-se a utilização
de métodos que, embora derivados do simplex, são
bem mais eficientes.
O Problema do Transporte
19
20
O modelo dos transportes visa minimizar o custo
total do transporte necessário para abastecer n
centros consumidores (destinos), a partir de m centros
fornecedores (origens), podendo ser esquematizado,.
A determinação do melhor plano de transporte de
bens, desde as instalações de produção até os
mercados consumidores, constitui-se entre os muitos
problemas que enfrenta um administrador
O Problema do Transporte
20
14/08/2017
11
21
As quantidades a serem transportadas não podem
exceder a capacidade das instalações de produção e
devem satisfazer a demanda dos clientes, sendo que,
com frequência, o melhor programa minimiza os custos
totais de transporte.
Para tanto, precisa-se das seguintes informações
para desenvolver o modelo de transportes:
• A demanda dos clientes;
• A capacidade das fábricas;
• Os custos de transporte da fábrica até o cliente.
O Problema do Transporte
21
22
Representação geral do problema de transporte:
O transporte em cada uma das rotas, indicadas pelas
setas, deve ser planejado de modo a se obter o mínimo
custo total de transporte
O Problema do Transporte
22
14/08/2017
12
23
O Problema do Transporte
Esquema do problema de transporte:
Em que,
cij : custo unitário de transporte da origem i para o destino j;
ai : quantidade disponível na origem i;
bj : quantidade requerida no destino j;
xij : quantidade a ser transportada da origem i para o destino j.
São as incógnitas do problema. 23
24
O Problema de Transportes consiste em determinar as
quantidades de um determinado produto que deverão ser
tranportadas de m origens para n destinos, dadas as restrições
de oferta máxima ( i O ) associadas a cada origem
e as restrições de demanda ( j D ) associadas a cada destino.
Formalmente, pode ser equacionado como:
O Problema do Transporte
24
14/08/2017
13
25
Possíveis Aplicações:
O Problema de transporte pode surgir em diversas situações.
• Transporte de alimentos de indústrias aos mercados
consumidores;
• Transporte de pedras de centros de mineração para depósitos
ao longo de uma rodovia em construção;
• Designação de tarefas a máquinas;
• Transporte de produção agrícola do campo até armazéns.
O Problema do Transporte
25
26
Exemplo 1 - Transporte de Bebidas
Uma indústria de bebidas possui:
• Dois centros de produção (m = 2), Araraquara e São José dos 
Campos
• Três mercados consumidores (n = 3), São Paulo, Belo
Horizonte e Rio de Janeiro.
Sejam:
• xij a quantidade do produto (uma unidade pode ser um
engradado contendo dezenas de garrafas) a ser enviada do
centro de produção i ao mercado consumidor j.
• cij o custo unitário do transporte de uma unidade de produto 
do centro de produção i ao mercado consumidor j.
O Problema do Transporte
26
14/08/2017
14
27
Exemplo 1 - Transporte de Bebidas
Os custos são dados na tabela abaixo:
O Problema do Transporte
27
28
Exemplo 1 - Transporte de Bebidas
O modelo matemático para este problema é dado por:
Minimizar f (x11, ..., x23) = 4x11 +2x12 +5x13 +11x21 +7x22 +4x23
sujeito a:
x11 + x12 + x13 ≤ 800
x21 + x22 + x23 ≤ 1000
x11 + x21 ≥ 500
x12 + x22 = 400
x13 + x23 = 900
x11 ...x23 = 0
O Problema do Transporte
28
14/08/2017
15
29
Exemplo 2 - Transporte de rochas
Os custos de transporte de cada jazida aos depósitos são 
dados na seguinte tabela:
xij é a quantidade (m3) transportada de rochas da jazida i para 
o deposito j.
O Problema do Transporte
29
30
Exemplo 2 - Transporte de rochas
O modelo matemático deste problema é dados por:
Minimizar
f (x11, ..., x43) = 30x11 + 13x12 + 21x13 + 12x21 + 40x22 + 26x23 + 
27x31 + 15x32 + 35x33 + 37x41 + 25x42 + 19x43
sujeito a:
x11 + x12 + x13 ≤ 433
x21 + x22 + x23 ≤ 215
x31 + x32 + x33 ≤ 782
x41 + x42 + x43 ≤ 300
x11 + x21 + x31 + x41 = 697
x12 + x22 + x32 + x42 = 421
x13 + x23 + x33 + x43 = 612
x11 ...x43 ≥ 0
O Problema do Transporte
30
14/08/2017
16
O Problema do Transporte
Exemplo 3:
Uma fábrica produz um determinado produto e o distribui através de 3
fornecedores para 4 consumidores. A disponibilidade deste produto no
fornecedor 1 é de 30, no 2 é de 50 e no 3 é de 40 unidades. A
necessidade de cada consumidor é de, respectivamente, 40, 30, 20 e
30 unidades. O custo unitário para transportar este produto de um
fornecedor para um consumidor é dado pela seguinte tabela (numa
certa unidade monetária).
Modele matematicamente o problema de modo que a quantidade a
ser transportada de um fornecedor para um consumidor tenha um
custo de transporte o mínimo possível.
31
O Problema do Transporte
Exemplo 3:
Min Z = 10x11 + 12x12 + 5x13 + 8x14 + 25x21 + 7x22 +14x23 +
30x24 + 15x31 + 20x32 + 6x33+ 40x34
S.a. x11 + x12 + x13 + x14 ≤ 30
x21 + x22 + x23 + x24 ≤ 50
x31 + x32 + x33 + x34 ≤ 40
x11 + x21 + x31 =40
x12 + x22 + x32 = 30
x13 + x23 + x33 = 20
x14 + x24 + x34 = 30
xij ≥ 0, i = 1, 2 e 3 e j = 1, 2, 3 e 4.
32
14/08/2017
17
33
Modelos de Transporte
Método de Transporte com Transbordo
Em alguns problemas de transporte, para se fazer o
deslocamento, podem-se usar localidades intermediárias (ou de
transbordo), ou seja, localidades que não são nem centros
produtores nem mercados consumidores dos produtos. Essas
localidades intermediárias podem representar, por exemplo,
depósitos ou centros de distribuição. Tais problemas são
denominados de problemas de transbordo. O que é
transportado de cada localidade intermediária aos mercados
consumidores não pode ultrapassar a quantidade de produto
que chega dos centros produtores a esses locais.
34
Modelos de Transporte
Método de Transporte com Transbordo
A quantidade transportada de cada localidade intermediária
aos mercados consumidores é igual à quantidade de produto
que chega dos centros produtores a esses locais de transbordo.
Na figura mostra uma situação em que um centro de distribuição
j recebe produtos de dois centros e abastece três mercados
consumidores. Assim, deve-se adicionar ao modelo de
transporte as restrições para toda localidade
intermediária j que represente um centro de distribuição.
14/08/2017
18
35
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 1
Considere uma Companhia distribuidora de bebidas supondo que ela dispõe
de dois depósitos para abastecer os mercados consumidores. Para evitar
ambigüidade, enumera-se cada localidade distintamente – os centros de
produção: Araraquara(1), S. J. dos Campos(2); os depósitos: Campinas(3),
Barra Mansa(4);e os mercados consumidores: São Paulo(5), Belo
Horizonte(6) e Rio de Janeiro(7). Suponha que os mercados sejam
abastecidos somente a partir dos depósitos. Os custos unitários de se
transportar uma unidade do produto de cada centro de produção para cada
depósito e de cada depósito para cada mercado consumidor são dados nas
tabelas (1) e (2) a seguir. Represente o modelo matemático do problema.
36
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 1
14/08/2017
19
37
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 1
Min Z = x13 + 3x14 + x23 + 2x24 + x35 +3x36 + 3x37 + 3x45 + 4x46 + x47
S.a. x13 + x14 ≤ 800
X23 + x24 ≤ 1000
x35 + x45 = 500
x36 + x46 = 400
x37 + x47 = 900
x13 + x23 = x35 + x36 + x37
x14 + x24 = x45 + x46 + x47
x13, x14, x23, x24,x35, x36, x37, x45, x46, x47 ≥ 0
38
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 2
Suponha que, para a construção de uma rodovia, não estejam disponíveis na região
jazidas de rochas adequadas à obtenção de pedra britada. Faz-se necessário, portanto,
o transporte desse material de jazidas mais próximas para alguns pontos convenientes
preestabelecidos ao longo do caminho onde será implantada a estrada ao menor custo.
Na figura a seguir estão apresentados todos os caminhos possíveis que ligam cada
pedreira aos pontos de depósito e na tabela a seguir mostra os dados do problema de
transporte de agregados. Represente o modelo matemático do problema.
Pedreiras fornecedoras de pedra britada: P1, P2, P3
e P4; pontos convenientes para depósito de material:
D1, D2 e D3; trajeto da rodovia R.
14/08/2017
20
39
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 3
Considere uma companhia distribuidora de bebidas que tem os centros de
produção e suponha que ela dispõe de dois depósitos para abastecer os
mercados consumidores. Para evitar ambigüidade, enumera-se cada
localidade distintamente – os centros de produção: Fab(1), Fab(2), Fab(3) e
Fab(4) ; os depósitos: CD(1), CD(2); e os mercados consumidores:
Cliente(1), Cliente(2) e Cliente(3). Suponha que os mercados sejam
abastecidos somente a partir dos depósitos. Os custos unitários de se
transportar uma unidade do produto de cada centro de produção para cada
depósito e de cada depósito para cada mercado consumidor ao menor custo
possível são apresentados na tabela a seguir. Represente o modelo
matemático do problema.
Tabela 1: Custos unitários de transporte de uma unidade do produto de cada
centro de produção para cada depósito.
40
Modelos de Transporte
Método de Transporte com Transbordo – Exercício 3
14/08/2017
21
41
Modelos de Transporte
41
42
Modelos de Transporte
42
14/08/2017
22
43
Modelos de Transporte
43
Regra do Canto Noroeste
8
15 10
109
44
Modelos de Transporte
44
Método de Aproximação de Vogel
14/08/2017
23
45
Modelos de Transporte
45
Método de Aproximação de Vogel
46
Modelos de Transporte
46
Método de Aproximação de Vogel
14/08/2017
24
47
Modelos de Transporte
47
Penalidade 
por Coluna
6070150
803
802
1201
Penalidade por Linha321
15
3
58
12
6
10
10
9
Penalidade 
por Coluna
6070150
803
802
1201
Penalidade por Linha321
5
8 - 3 = 5
10 - 12 = 2
10 - 6 = 49 - 5 = 4
6 - 5 = 1
9 - 3 = 6
7 65
1
270
5070
80
10
Método de Aproximação de Vogel
Custo Total
Oferta
Demanda
48
Modelos de Transporte
Equilíbrio entre a oferta total e a demanda total
No caso da demanda total maior que a oferta total, adiciona-se
uma origem fictícia de modo a igualar oferta e demanda. No
caso de ter sido acrescentado uma oferta fictícia, esta
representará a falta de produto no mercado, e os transportes
realizados a partir desta origem serão interpretados como uma
demanda não atendida.
No caso da oferta total ser maior, deverá ser acrescentado um
destino fictício. Neste caso, quando for acrescentado uma
demanda fictícia, os transportes realizados para este destino
serão interpretados como um excesso de oferta não
transportado.
14/08/2017
25
49
Modelos de Transporte
Equilíbrio entre a oferta total e a demanda total
No caso abaixo a oferta (290) é maior que a demanda (270),
dessa forma foi necessário acrescentar um depósito fictício,
com isso, os transportes realizados para este destino serão
interpretados como um excesso de oferta não transportado.
50
Modelos de Transporte
50
Exercício 1:
Uma companhia faz esquis em 3 fábricas através do mundo. As 
fábricas suprem 4 depósitos que distribuem os esquis 
diretamente às lojas. O problema é achar quantos pares de 
esquis devem ser transportados de cada fábrica para os vários 
depósitos para minimizar o custo total 
a) Ache a solução inicial pelo método do Canto Noroeste 
b) Ache a solução inicial pelo método de Vogel 
14/08/2017
26
51
Modelos de Transporte
Exercício 2:
Uma companhia locadora de automóveis se defronta com um 
problema de alocação resultante dos contratos de locação que 
permitem que os automóveis sejam devolvidos em localidades 
outras que aquelas onde foram originalmente alugados. 
Atualmente há 2 agências de locação com, respectivamente, 15 
e 13 carros excedentes e 4 outras agências necessitando de 9, 
6, 7 e 9 carros, respectivamente. Os custos unitários de 
transporte entre as locadoras são os apresentados no quadro 
abaixo. Determine um plano de transporte ótimo que minimize o 
custo de transporte. 
52
Modelos de Transporte
Exercício 2:
a)Identifique as restrições do problema
b)Declare o objetivo
c)Com base no método de Vogel, ache o custo total de 
transporte
14/08/2017
27
53
Modelos de Transporte
Exercício 3:
O Expresso Rápido Faxina é uma empresa de transporte com 
quatro grandes terminais localizados em Curitiba, Cascavel, 
Londrina e Campo Mourão. Os pneus utilizados pela frota dessa 
empresa são padronizados. A empresa fez uma tomada de 
preços em três grandes revendedores de pneus e obteve as 
seguintes cotações: 
Se o objetivo da empresa Expresso Rápido Faxina é minimizar o 
custo total de aquisição dos pneus, quanto ela deverá comprar 
de cada revendedor? Ache a solução inicial pelo método de 
Vogel. Calcule o custo total.
54
Modelos de Transporte
Exercício 3:
a) Identifique as restrições do problema
b)Declare o objetivo
14/08/2017
28
55
Modelos de Transporte
Exercício 4:
56
Modelos de Transporte
Exercício 4:
a)Identifique as restrições do problema
b)Declare o objetivo
c)Com base no método de Vogel, determine a solução inicial e 
ache o custo total de transporte
14/08/2017
29
57
Modelos de Transporte
Exercício 5:
Inglaterra, Franca e Espanha são produtores de trigo, cevada e aveia, existe
uma demanda que requer que 50 milhoes de hectares de terra sejam
dedicados a produção de trigo, 24 milhões de hectares para cevada e 30
milhões de hectares para aveia. As quantidades totais de terra (em milhões de
hectares) disponíveis para esses propósitos na Inglaterra, França e Espanha
são consecutivamente 28, 44 e 32.
Para Inglaterra, França e Espanha, considere respectivamente os valores
apresentados de cada item abaixo:
- Número de horas de trabalho para produzir um hectare de trigo: 45hs; 32,5hs;
40hs.
- Número de horas de trabalho para produzir um hectare de aveia: 30hs; 25hs;
40hs.
- Número de horas de trabalho para produzir um hectare de cevada: 37,5hs;
30hs; 30hs.
- Custo de mão de obra por hora para a produção de trigo $3,00; $2,40; $3,30.
58
Modelos de TransporteExercício 5:
- Custo de mão de obra por hora para a produção de cevada
$2,70; $3,00; $2,80.
- Custo de mão de obra por hora para a produção de aveia $2,30;
$2,50; $2,10.
Solucione o problema alocando as áreas necessárias em cada
país de modo a atender a demanda por alimento e minimizar o
custo total.
a) Monte uma tabela com as informações de demanda, 
disponibilidade e custos.
b) Declare o objetivo.
c) Identifique as restrições do problema.
d) Com base no método de Vogel, determine a solução inicial e 
ache o custo total de transporte.
14/08/2017
30
Modelos de Transporte
Método stepping-stone
Modelos de Transporte
Método stepping-stone
14/08/2017
31
Modelos de Transporte
Método stepping-stone
Modelos de Transporte
Método stepping-stone
14/08/2017
32
Modelos de Transporte
Método stepping-stone
64
Modelos de Transporte
Exercício:
A partir da solução inicial do exercício 5, ache a solução ótima
pelo método Stepping-stone.
14/08/2017
33
65
Modelos de Transporte
Exercício:
Determinada empresa pretende transportar um certo produto, que é fabricado nas 
suas 3 fábricas, para 3 centros de distribuição. A capacidade de produção por dia de 
cada fábrica é a que consta na última coluna da tabela em baixo. A última linha da 
tabela dá-nos as necessidades máximas de cada centro de distribuição. Os custos de 
transporte, por unidade de produto, das fábricas para cada centro encontram-se 
mencionados na mesma tabela. 
Pretende-se determinar a solução mais econômica para transportar o produto das 
fábricas para os centros de distribuição. Uma das soluções é a que consta no quadro 
seguinte: 
66
Modelos de Transporte
Exercício: 
a) Verifique, e justifique, se a solução apresentada é ou não é ótima. 
b) Se não for ótima, a partir da solução dada, determine a solução ótima. 
c) Interprete os resultados obtidos e diga qual o custo total de transporte. 
14/08/2017
34
67
Modelos de Transporte
Exercício: 
Uma empresa tem 3 fábricas e 4 clientes, referentes a um determinado produto, e 
conhece-se os dados abaixo:
. 
Fábrica
Capacidade 
de produção Cliente
Demanda
mensal
F1 85 C1 100
F2 90 C2 80
F3 65 C3 20
C4 40
Total 240 Total 240
Local de Locais de Venda
Fabricação C1 C2 C3 C4
F1 43 57 33 60
F2 30 49 25 47
F3 44 58 33 64
custos de transporte ($/unidade
. 
Encontrar o programa de distribuição que proporcione lucro máximo. Aplique o 
Stepping Stone. Inicialize o algoritmo pelo médoto de Vogel.