O PROBLEMA DO TRANSPORTE

Prévia do material em texto

O PROBLEMA DO
TRANSPORTE
Prof.: Michele Lana Mourão
Nesta unidade vamos abordar o problema dos transportes
que também pode ser resolvido utilizando o método simplex,
porém existe uma maneira mais simples que será o foco
desta unidade o algoritmo do transporte.
O QUE IREMOS APRENDER?
• MÉTODO DO CANTO NOROESTE;
• MÉTODO DE APROXIMAÇÃO DE VOGEL.
TÓPICOS ABORDADOS
O problema de transporte simples pode ser descrito como
sendo concernente ao transporte de um único produto de várias
origens, onde é fabricado, para muitos destinos, onde é
consumido. Cada origem tem uma capacidade de produção
limitada e cada destino tem uma demanda conhecida.
O PROBLEMA DO TRANSPORTE
O único fator que varia é o custo de distribuição, que depende principalmente da
distância entre cada origem i, e cada destino j. Objetiva-se minimizar o custo
total de transporte, respeitando as restrições de ofertas e demandas do produto.
O PROBLEMA DO TRANSPORTE
• Primeiro é preciso verificar se os sistemas estão equilibrados;
• Escolhemos uma cédula para começar.
MÉTODO DO CANTO NOROESTE
Calcular a solução inicial do quadro de transportes, pelo canto noroeste.
EXEMPLO 1
D1 D2 D3
01 12 9 8 10
02 13 12 6 20
03 7 9 5 10
04 3 2 8 15
8 30 17
Passo 1: para cada linha e coluna, calcular a penalidade que corresponde
à diferença entre os dois menores custos unitários de transporte na
respectiva linha (e coluna).
Passo 2: escolher a linha ou coluna de maior penalidade. Em caso de
empate, escolher qualquer uma delas, aleatoriamente
MÉTODO DE VOGEL
Passo 3: aloque a maior quantidade possível de produto, de forma que a
soma das células correspondentes na mesma linha e na mesma coluna
não ultrapasse a capacidade de fornecimento total e de demanda total,
respectivamente.
Passo 4: bloqueie as células correspondentes à mesma linha ou coluna
que atingiu o limite máximo de fornecimento ou demanda, enquanto restar
mais de uma célula não alocada e não bloqueada, volte ao passo 1, caso
contrário, vá para o passo 5.
Passo 5: aloque a essa última célula a capacidade ou demanda
remanescente.
Vamos resolver utilizando o método Vogel.
EXEMPLO 2
D1 D2 D3 CAPACIDADE PENALIDADE
01 12 9 8 10
02 13 12 6 20
03 7 9 5 10
04 3 2 8 15
DEMANDA 8 30 17
PENALIDADE