Problemasdetransporte

Disponível somente no TrabalhosFeitos
  • Páginas : 14 (3303 palavras )
  • Download(s) : 0
  • Publicado : 7 de maio de 2012
Ler documento completo
Amostra do texto
PESQUISA OPERACIONAL - Profa. Vânia Gayer

PROBLEMAS DE TRANSPORTE


INTRODUÇÃO:
O Problema de transporte é de forma geral o problema de determinar o carregamento de uma rede de transporte que liga várias fontes a vários destinos, de forma que o custo total do transporte seja mínimo. É encontrado em empresas que têm unidades produtoras em algumas cidades e depósitos em outras. Umavariação desta situação é o caso em que o produto não vai direto da fonte para o destino, mas passa por outras fontes e outros destinos antes de chegar ao destino final. É o modelo de transportes com transbordo.

HISTÓRICO:
Em 1975, os professores Leonid Kantarovich (URSS) e Tjalling C. Koopmans (USA) receberam o prêmio Nobel de Ciências Econômicas por suas contribuições para a teoria da alocaçãoótima de recursos. Estes professores investigaram uma grande variedade de problemas de otimização. É interessante notar que ambos estão associados a vários dos primeiros trabalhos descrevendo problemas de fluxo em redes. Em 1939, Kantarovich discutiu uma classe de modelos de otimização com exemplos específicos. A ideia de cada exemplo era a busca da mais alta produção possível com uma utilização ótimados recursos existentes. Um destes exemplos envolveu a distribuição de transporte de carga entre diferentes rotas de uma rede de modo a satisfazer as necessidades e restrições de capacidade nas rotas enquanto otimizava o gasto de combustível. A discussão deu-se na URSS e não foi conhecida pelo ocidente antes de 1950. Enquanto isso, nos EUA, trabalhando independente, Koopmans formulou o mesmoproblema. Devido a isso, o problema de transporte é frequentemente chamado de Problema de transporte de Kantarovich-Koopmans. Em 1956, Alex Orben propôs uma generalização do modelo de transporte no qual pontos de transcarregamento eram alocados. A formulação é conhecida hoje como um problema de transporte com transbordo.

1. O PROBLEMA CLÁSSICO DE TRANSPORTES
A modelagem de um problema clássico detransportes com m fontes e n destinos pode ser assim expressa:
Min

s.a. para i=1,..,m

para j=1,..,n

onde:
cij é o custo de transportar uma unidade da fonte i para o destino j
xij é a quantidade (un) que deve ser transportada da fonte i para o destino j
ai é a capacidade da fonte i
bj é a capacidade de absorção do destino j

EXEMPLO 1:

Suponha um problema de 2 fontes e 3destinos, onde a capacidade das fontes sejam respectivamente 15 e 25 e a capacidade de absorção pelos destinos sejam 20, 10 e 10, respectivamente. Os custos de transportar uma unidade da fonte 1 para o destino 1 seja 10, da fonte 1 para o destino 2 seja 3 e da fonte 1 para o destino 3 seja 5. Analogamente, suponha que os custos de transporte da fonte 2 para os destinos 1, 2 e 3 sejam 12, 7 e 9,respectivamente.

Para facilitar o entendimento, podemos fazer um esquema utilizando nós e arcos, de tal forma que teremos 2 nós fontes e 3 nós destinos e 6 arcos que correspondem as rotas que ligam as fontes aos destinos.

25
15
10
10
20

Note que no problema clássico, existe a suposição que

a soma das capacidades das fontes é igual a capacidade de absorção dos destinos:

a1+a2=b1+b2+b3=40

Para fazermos a modelagem do problema acima precisamos perceber que o objetivo é transportar todas as unidades das fontes para os destinos ao menor custo possível. Desse modo precisamos encontrar o valor das variáveis do problema que minimizam este custo, ou seja, quanto deverá ser transportado da fonte i para o destino j. As variáveis deste problema são:

x11, x12, x13, x21, x22 ex23

Sabendo que os custos unitários de transporte da fonte i para o destino j são:

c11=10, c12=3, c13=5,
c21=12, c22=7, c23=9

A função objetivo é expressa por:

Min 10x11 + 3x12+ 5x13 + 12x21+ 7x22 + 9x23

Em relação às restrições do problema, note que todas as unidades armazenadas nas fontes devem ser transportadas, sendo estas capacidades definidas por a1= 15 e a2=25, temos...
tracking img