Pesquisa operacional

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2193 palavras )
  • Download(s) : 0
  • Publicado : 30 de setembro de 2012
Ler documento completo
Amostra do texto
Introdução aos Conceitos de Problemas de Transporte e Roteamento de Veículos
Alexandre da Costa1

1

Acadêmico do Curso de Matemática - Centro de Ciências Exatas e Tecnológicas da Universidade Estadual do Oeste do Paraná Caixa Postal 711 - 85819-110 - Cascavel - PR - Brasil
alex2dc@hotmail.com

Resumo. Este trabalho aborda os problemas de transporte e de roteamento de veículos naperspectiva de levar ao conhecimento, de quem venha a se interessar pelo assunto, as dificuldades que se encontra e as estratégias abordadas para se modelar problema como esses. Problemas de roteamento de veículos pertencem a uma classe particular dos problemas de transporte e a programação linear não é capaz de lhes oferecer, sozinha, resultados eficazes. Utiliza-se, então de métodos heurísticos para seobter uma solução otimizada. Além disso, o tratamento dado a cada tipo de problema, por mais semelhantes que estes possam ser, é bastante diversificado, variando não apenas nos algoritmos utilizados, mas também no tipo de tratamento dado às particularidades próprias de cada um [BODIN, 1983].

Palavras Chaves. Problemas de Transporte, Roteamento de Veículos, Programação
Linear, NP-hard.

1.Problemas de Transporte
Geralmente os problemas de transporte requerem uma otimização de seus processos com objetivo de minimizar os gastos. Procura-se assim encontrar a forma mais econômica de distribuir um bem disponível em certa quantidade, não necessariamente em um mesmo local, para outros locais onde se exige determinada quantidade desse bem. O Problema do Transporte é muito usado em exemplos deProblemas de PL por sua grande aplicação prática e por ser alvo de estudado de vários investigadores, embora tenha sido George Dantzig o primeiro a estabelecer a sua formulação como modelo de PL e a propor um método sistemático de resolução, conhecido como método simplex. [CANAVARRO, 2005] Alguns problemas desse tipo, devido as suas estruturas particulares, podem ser resolvidos com métodosderivados do simplex e com maior eficiência

[CANAVARRO, 2005]. Já problemas de roteirização (ou roteamento) necessitam de métodos mais complexos abordando, além de programação linear, conceitos como os de grafos e heurísticas particulares. Problemas de transporte são amplamente estudados pela Investigação Operacional, ciência que surgiu em 1947 e veio com o objetivo de resolver com maior eficiênciaproblemas envolvendo administração nas organizações, distribuição ótima de recursos, etc.. Essa ciência se vale da Programação Linear como uma de suas ferramenta mais poderosas para tratar de problemas como os de transporte.

2. Problemas de Transporte e Programação Linear
Problemas de Programação Linear (PL) pertencem a uma categoria especial de problemas de Programação Matemática (PM)1 , onde afunção objetivo e as restrições podem ser representadas por funções lineares. A aplicação da Programação Linear visa estabelecer um plano otimizado que representa a melhor solução entre todas as soluções possíveis do problema [C. JORDÁN, 2002]. Sendo assim um problema de transporte pode ser formalizado em termos de PL: ∙ enviar um bem que encontra-se alocado em origens (depósitos) nas quantidades> 0 com = 1, 2, . . . , e é requerido em destinos (Pontos de demanda) nas quantidades > 0 com = 1, 2, . . . , ∙ O produto deve ser enviado diretamente para os destinos, esgotando as disponibilidades em cada origem e satisfazendo os requerimentos em cada destino; ∙ Cada percurso entre origem e destino tem um determinado custo de transporte; ∙ O problema tem por objetivo a minimização do custo totalenvolvido na distribuição desse produto, sabendo os custos unitários de transporte de cada origem para cada destino. Minimizar : =
=1 =1

Sujeito a: =
=1

= 1, 2, . . . ,

=
=1

= 1, 2, . . . ,

Com: ∙ ∙ ∙ ∙
1

: número de unidades a transportar da origem i para o destino j; :custo do transporte de uma unidade da origem i para o destino j; : quantidade disponível na origem i; :...
tracking img