caixeiro viajante
Neste trabalho estamos relatando e descrevendo sobre a importância da Otimização De Sistemas de Transporte através de uma grande pesquisa onde cada trabalho defenderá as teses e objetivos de maneira eficiente . Visando conhecer a fundo como desenvolve os métodos de trabalho tais como :
• Caixeiro Viajante
• Caminho Mínimo
• Fluxo Máximo
• Analise da Teoria das Filas .
Exemplos :vamos deixar claro os termos pesquisados exemplificando os mesmos .
O Problema do Caixeiro Viajante
O problema do caixeiro-viajante (PCV), travelling salesman problem (TSP) (em inglês) , é um problema de otimização que, apesar de parecer modesto é, na realidade, muito investigado por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros (Applegate et al., cop. 2006, p. 1).
O problema pertence à categoria NP-Completo que o remete para um campo de complexidade exponencial, isto é, o esforço computacional necessário para a sua resolução cresce exponencialmente com o tamanho do problema. Assim, dado que é difícil, se não impossível, determinar a solução óptima desta classe de problemas, os métodos de resolução passam pelasheurísticas e afins que, do ponto de vista matemático, não asseguram a obtenção de uma solução óptima (Cunha, 2002).
Figura 1. Problema do caixeiro-viajante.
O problema do caixeiro-viajante (representado na Figura 1) consiste naprocura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial (Nilsson, 1982).
Formulação combinatória
Dado um conjunto de n cidades ci e uma matriz de distâncias , onde , , , a tarefa passa por encontrar a permutação que faça com que a função objectivo (distância do circuito) , onde
,
atinja o seu mínimo.
Caminho Mínimo
Na teoria de grafos, o problema do caminho mínimo consiste na minimização do custo de travessia de um grafo entre