Comparação do desempenho de metaheurísticas aplicadas ao Problema Quadrático de Alocação utilizando instâncias originais e isomorfas
Nome: RICARDO DE MAGALHÃES SIMÕES
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 13/11/2006
Banca:
Nome |
Papel |
|---|---|
| MARIA CRISTINA RANGEL | Orientador |
| NAIR MARIA MAIA DE ABREU | Orientador |
Resumo: Qual a melhor localização de uma determinada clínica em um hospital? Qual o melhor desenho para uma placa de circuito de computador? Estas perguntas abordam dois temas distintos, mas a solução para ambas pode ser obtida seguindo um princípio: disponibilização de recursos. Estes problemas, e muitos outros, possuem uma característica comum, que é a associação de um recurso (sala ou circuito integrado) com o melhor local para se disponibilizá-lo para que outros possam utilizá-lo. Tais problemas são modelados utilizando-se um modelo de Otimização Combinatória. Em especial, esses problemas fazem parte de uma classe definida como: Problema Quadrático de Alocação. Existem vários problemas do cotidiano que podem ser formulados como um PQA, por exemplo: análise de reações químicas, sistemas de decisão de alocação de uma nova instalação (posto policial, supermercado, fábrica, escola), arqueologia, entre outros. Trata-se de um dos mais difíceis problemas de otimização combinatória: instâncias contendo 30 recursos não podem, em geral, ser resolvidas exatamente em um tempo computacional aceitável. Este projeto irá apresentar o Problema Quadrático de Alocação segundo os aspectos de formulação, aplicação e resolução. Serão definidas as famílias de instâncias do PQA e os problemas isomorfos. E também será abordado a ordenação da instância como estratégia para resolução, e serão mostrado os resultados obtidos nos testes realizados com instâncias ordenadas e a conclusão deste trabalho.
