minimização

Série Pesquisa Operacional – Problema do Caixeiro Viajante

Na semana passada vimos uma introdução e a definição do que é a pesquisa operacional. Hoje conheceremos um pouco mais sobre o Problema do Caixeiro Viajante (Traveling Salesman Problem).

Na definição padrão do problema, imagine que você tem uma lista de cidades para visitar, e que você conhece a distância entre cada par de cidades. Você precisa visitar todas as cidades, sem passar pela mesma cidade duas vezes, viajando o menor tempo possível.

Este problema é muito importante para a logística, pois ajuda a definir as melhores rotas possíveis, mas do ponto de vista teórico é muito mais amplo que isto.

Em empresas de transportes e entregas, o termo milk run é usado para descrever o trajeto que passa por todas as estações para coletas de produtos, para depois entregá-los num ponto específico. O milk run, ou corrida do leite, seria passar por várias fazendas coletando leite e depois entregar o grande volume coletado numa empresa de laticínio. Este assunto foi tratado recentemente no blog Universo da Logística.

Este mesmo problema do caixeiro viajante é usado para otimizar a fabricação de microchips, obtendo os caminhos mais curtos para os circuitos integrados, a otimização de padrões de corte em chapas e placas, economizando material quando obtém o melhor aproveitamento possível, além de economizar o uso e troca das facas ou lasers que fazem o corte, e em uma versão levemente modificada ele ajuda a fazer o sequenciamento do DNA. Um problema típico com algumas centenas de pontos (cidades) pode levar muitas horas para ser resolvido, pois as combinações possíveis crescem muito rapidamente.

Série Pesquisa Operacional – uma visão geral (ATUALIZADO)

equações pesquisa operacional - Logística DescomplicadaA Pesquisa Operacional (PO) é a área que analisa formas de modelar os sistemas do mundo real em termos matemáticos, para identificar mais claramente as relações entre diferentes elementos com o objetivo de melhorar ou otimizar seu desempenho. Ela faz uso de modelos matemáticos, estatísticos e de algoritmos para identificar pontos de melhoria e ajudar na tomada de decisões empresariais.

Esta área está intimamente ligada à logística, pois muitos sistemas produtivos, industriais e gerenciais podem fazer uso das técnicas de Pesquisa Operacional para alcançar um desempenho superior. De fato, muitos softwares utilizados por empresas têm complexos algoritmos por trás, para determinar a melhor quantidade de produtos para se manter em estoques, os melhores volumes de produção (e seu agendamento), fazer roteamento de veículos, dentre outros.

A Pesquisa Operacional normalmente busca encontrar o valor máximo (de lucro, performance, aproveitamento) ou mínimo (de risco, de custo). É importante ressaltar que do ponto de vista da PO, quando se fala em máximo ou mínimo está implícito que não existe nenhuma outra solução melhor, ou seja, a solução encontrada é provada matematicamente como sendo a melhor de todas as soluções possíveis. Esta solução é chamada de ótima e o sistema é dito otimizado.