TRABALHO PESQUISA OPERACIONAL PESQUISA OPERACIONAL

PESQUISA OPERACIONAL

TEMA : CAXEIRO VIAJANTE E MÉTODO DE BUSCA

Nome: Rodrigo Marinho Leite da Silva RA: B154DE-0 Turma : EP7P13

Universidade Paulista
Campus Marquês SP
2014
Professora : ANTONIO BRENO DE ALLELUIA

CAIXEIRO-VIAJANTE

* Origem termo Caixeiro-Viajante.

É uma profissão antiga,onde um vendedor realizava suas vendas fora da cidade que produzia.
Antigamente, quando não havia a facilidade do transporte entre cidades, os caixeiros-viajantes eram a única forma de transportar produtos entre diferentes regiões fora das grandes cidades.

* O que é Caixeiro-Viajante em Pesquisa Operacional ?

É um método do Caixeiro Viajante (PCV) que visa determinar a menor e a melhor rota para percorrer uma série de cidades/destinos(visitando cada uma pelo menos uma vez), retornando assim a sua cidade de origem. Visando a necessidade do ponto de origem em realizar entregas em diversas cidades/destinos, buscando minimizar o percurso percorrido e o custo operacional do transporte.
Sua idéia inicial consiste em encontrar uma rota em que se passe pelo menos uma vez em cada destino,até retornar ao ponto de origem.
* Aplicação do método Caixeiro-Viajante

- A imagem corresponde a ilustração do método,sendo que : as cidades( destinos) são os vertices,e as estradas definem as arestas.

Métodos de solução Basicamente existem 2 formas de solucionar o PCV,são elas :
1° Métodos exatos
2° Métodos Heurísticos

Características do MÉTODO EXATO :
Analisa-se todas as alternativas possíveis.
O embaraço dele é fatorial.
Por ser fatorial,os método de resolução '' Branch-and-bound'' é mais usado.

Características do MÉTODO HEURÍSTICO :
Com base em heurística é possível encontrar soluções aproximadas,isto é,não são soluções exatas mas fornecem um resultado satisfatório em tempo hábil.
Os métodos exatos não retornam solução alguma para um número de cidades maior do que 14 ou 15.

MÉTODO DE