Aula 9 - Caixeiro Viajante

Prévia do material em texto

Nome do Professor
PESQUISA OPERACIONAL II
Professor: Douglas Pinheiro
Nome do Professor
PROBLEMA DO CAIXEIRO VIAJANTE: 
COBERTURA DOS NÓS
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema do Caixeiro Viajante
Visitar todas as cidades, sem repetir, com a menor distância
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema do Mochileiro Econômico
Visitar todas as cidades, gastando o mínimo possível
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Rota Simplificado
Fazer todas as entregas com menor consumo de combustível
Nome do Professor
PROBLEMA DA COBERTURA DOS NÓS
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Cobertura dos Nós
• Problema: visitar todos os nós cobrindo a menor distância possível
• Posso ir de qualquer nó para qualquer nós
• Não posso revisitar nós, mas tenho que partir e voltar ao mesmo nó inicial 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Cobertura dos Nós
• Começando de 1, possibilidades:
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Cobertura dos Nós
• Começando de 1, possibilidades:
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Cobertura dos Nós
• Minimizar a distancia percorrida 
• Modelo Completo 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Problema da Cobertura dos Nós
Considerações importantes 
Ø Solução “garantida”...
Para grafos totalmente conectados 
Ø Para grafos não totalmente conectados... 
Não há garantia de solução 
Ø Para problemas limitados (20 cidades ou mais) 
Método Simplex muito lento! 
Ø Para problemas grandes...
Muitas vezes não é possível descobrir a solução ótima!
Ø Solução ótima independente do ponto de início!
Começamos sempre no ponto “1”
Nome do Professor
MÉTODO DA CIDADE MAIS PROXIMA
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Método com Complexidade O(n2) 
Ø Passos
1. Dentre os nós não visitados, encontre o vizinho mais próximo
2. Siga até ele 
3. Se ainda houver nós não visitados, volte para 1 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Basta Tabela de Distâncias (ou a calcular) 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Começando do nó 1, para onde vamos? 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø A partir do 4, para onde vamos? 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø E depois do 2, para onde?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Finalmente, depois do 3 ... 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Exercício
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Método do Vizinho mais Próximo
Ø Exemplo mais Completo
Nome do Professor
MÉTODO DA INSERÇÃO DE MENOR ENCARGO
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Encontrar o par de cidades de menos custo para fechar um ciclo
Ø Passos 
1. Para cada ligação, calcular o custo de inserir cada nó na mesma 
2. Inserir o nó que ampliar menos o custo 
3. Se ainda houver nós não visitados, volte para 1 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Basta Tabela de Distâncias (ou a calcular) 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Qual o par inicial?
Ø Escolha de circuito inicial?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Qual o par inicial?
Ø Qual e onde adicionar?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Qual o par inicial?
Ø Qual e onde adicionar?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Qual o par inicial?
Ø Sequencia Final
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Menor Encargo
Ø Exercício
Nome do Professor
MÉTODO DA INSERÇÃO DE MAIOR AFASTAMENTO
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Encontrar o par de cidades: de maior custo
Ø Passos 
1. Verificar a distância de todos os nós do caminho para todos os nós que ainda não estão 
no caminho 
2. Para cada nó fora do caminho, anotar a menor distância 
3. Escolher para entrar na solução o nó que tem a “maior ‘menor distância’” 
4. Procurar o ponto de inserção: aquele que causa o menor incremento de custo 
5. Se ainda houver nós não visitados, volte para 1 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Basta Tabela de Distâncias (ou a calcular) 
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Qual o par inicial?
Ø Escolha de circuito inicial?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Procurar qual nó entar
Ø Onde entrar?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Procurar qual nó entar
Ø Onde entrar?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Pesquisa Operacional II
Inserção de Maior Afastamento
Ø Procurar qual nó entar
Ø Onde entrar?
Pesquisa Operacional II Professor: Douglas Pinheiro Email: pinheiro.douglas@estacio.br
Dúvidas?