Otimização Combinatória

A Otimização Combinatória é uma sub-área da Pesquisa Operacional que lida com problemas de otimização em conjuntos de soluções finitos, como, por exemplo, problemas de decisão de sequência, programação, agendamento, itinerários, entre outros.

Problemas Clássicos

Problema da Mochila

Imagine que você seja contemplado com um cruzeiro marítimo com tudo pago e direito a um acompanhante. Nesse cruzeiro só tem gente da alta sociedade como políticos, jogadores de futebol, médicos, cientistas, engenheiros, entre outros. Em alto mar o navio começa a afundar. Só existe um barco salva-vidas, que, no entanto, tem um limite de peso. Portanto não podemos colocar todas as pessoas no barco.

Supondo que cada pessoa tem um peso e um grau de importância. E agora? Quem deverá ser salvo? Esse problema é conhecido como o Problema da Mochila. Nesse caso a mochila é o barco salva-vidas.

Para n pessoas há 2n soluções possíveis. Exemplo: Para 50 pessoas há 1015 soluções para serem testadas. Se tivéssemos um computador que realizasse uma avaliação em 10-8 segundos, ele gastaria cerca de 130 dias para encontrar a melhor solução enumerando todas as possíveis soluções. Conclusão: O barco afundaria antes mesmo que fosse tomada a decisão dos escolhidos.

Um excursionista planeja fazer uma viagem acampando. Há 5 itens que ele deseja levar consigo, mas estes, juntos, excedem o limite de 60 quilos que ele supõe ser capaz de carregar. Para ajudar a si próprio no processo de seleção, ele atribui valores, por ordem crescente de importância a cada um dos itens conforme a tabela a seguir:

Problema da Partição de Números

O problema de partição de números consiste em: dado um conjunto de N números, o objetivo é subdividi-lo em dois subconjuntos (chamados de partições) de tal forma que, a diferença entre os valores das somas dos números dessas duas partições seja a menor possível. Por exemplo, considere o seguinte conjunto com quatro números (23, 20, 56, 48). As partições (20,56) e (23,48) consistem no particionamento ótimo para este conjunto e, seu valor é 5. Apesar da simplicidade do enunciado, este é um problema de otimização combinatória que pertence a classe NP-difícil. Observe que, para um conjunto com n números têm-se 2n possíveis maneiras de subdividi-lo em duas partições.

Problema do Caixeiro Viajante (PCV)

Dado um conjunto de cidades e uma matriz de distâncias entre elas.

PCV consiste em encontrar uma rota tal que esta:


Considerando PCV simétrico, para n cidades há (n-1)!/2 rotas possíveis. Para n = 20 cidades, há 1016 rotas possíveis. Um computador que avalia uma rota em 10−8 segundos gastaria cerca de 19 anos para encontrar a melhor solução por enumeração completa.

Download de instâncias do PCV: Clique aqui.

Métodos de Resolução

Programação Matemática

Características Básicas:

Exemplos: Branch-and-Bound, Planos de Corte, Enumeração Implícita.

Métodos Heurísticos

Características Básicas:

Exemplos: GRASP, ILS, Simulated Annealing, Algoritmos Genéticos.





© copyright 2018 | Duca Siqueira

E-mail: duca_siqueira@hotmail.com