Pesquisa operacional problema de transporte

Problema de Transporte
Prof. Gustavo Peixoto Silva
Departamento de Computação
Univ. Federal de Ouro Preto
8 modelos

Problema de Transporte
Rede bipartida onde um conjunto contém nós de oferta e o outro contém os nós de demanda. Os arcos ligam os nós de oferta diretamente aos nós de demanda.

Problema de Transporte
{10} 1
4 {-20}
{15} 2
5 {-20}
{15} 3 nós de oferta nós de demanda M11.1 Problema de Transporte (Hamdy A. Taha Cap. 5)
Temos três fábricas e dois centros de distribuição. As capacidades das fábricas para o próximo trimestre são: 1.000, 1.500 e 1.200 veículos. As demandas nas centrais de distribuição são de: 2.300 e 1.400 veículos. Os custos de transporte por veículo entre as fábricas e os CDs são apresentados na tabela abaixo.
C1

C2

F1

80

215

F2

100

108

F3

102

68

Formular um de PL para atender à demanda de veículos nos centros distribuidores com o menor custo de transporte.
Existem algoritmos específicos para resolver problemas deste tipo...

M11.2 Problema de Transporte
O Problema de Transporte parte da hipótese de que oferta e demanda são equilibradas, ou seja, iguais. Caso isso não ocorra devemos “corrigir” o desequilíbrio antes de aplicar os algoritmos específicos para o problema.Considere o problema anterior com as seguintes características: C1

C2

Oferta

F1

80

215

1.000

F2

100

108

1.500

F3

102

68

1.500

Demanda

2.300

1.400

Como o total da oferta difere do total da demanda, como devemos proceder para termos um problema equilibrado?

Problema de Transporte Desbalanceado – transformação da rede
A soma da oferta com a demanda diferem.
Acrescentar um nó artificial no “lado” (oferta/demanda) com menor valor e ligar este nós aos nós do outro lado com arco de custo zero e u = ∞.

l
{10}

{10}

i

l

{-10}

{-10}

{10}

j

m

{-10}

{-10}

{10}

k

n

{-10}

i m {10}

{-10}

j n As