Um modelo para resolução de problema de alocação com restrição estocática

UM MODELO PARA RESOLUÇÃO DE PROBLEMA DE ALOCAÇÃO COM RESTRIÇÃO ESTOCÁTICA

Resumo
Dentre os problemas de otimização combinatória, o Problema Quadrático de Alocação (PQA) é um dos mais difíceis no que diz respeito à complexidade computacional. Ele pertence a classe de problemas NP-Hard, juntamente com os Problemas do Caixeiro Viajante, do Isomorfismo em Grafos, e do Particionamento, que por sua vez, podem também ser formulados como Problema Quadrático de Alocação. Pela sua alta complexidade muitos métodos heurísticos têm sido desenvolvidos para tentar resolver PQA aproximadamente. Este trabalho busca a resolução de problemas de layout de instalações e localização com congestão estocástica no sistema de circulação de tráfego, tentando minimizar a distância, o tempo e principalmente o custo de um sistema de circulação de pedestres ou mesmo o trabalho e circulação de pessoas em uma sala, utilizando para isso um modelo com quatro somátorias e três restrições e um método de solução heurístico.
Palavras-Chaves: Problemas de Otimização, Problema Quadrático de Alocação, Heurístico. 1. Introdução Inicialmente formulado em um contexto econômico por Koopmans & Beckmann [KB57], o Problema Quadrático de Alocação (PQA) foi apresentado como a alocação de n facilidades indissociáveis a n localidades com o objetivo de minimizar custos dessa alocação, ou seja, consiste em encontrar uma alocação de custo mínimo dos objetos aos locais, sendo os custos obtidos pela soma dos produtos distância-fluxo. Desde a sua primeira formulação, o PQA tem atraído a atenção de pesquisadores em todo o mundo, não apenas pela sua importância prática e teórica, mas principalmente pela sua complexidade. Trata-se de um dos mais difíceis problemas de otimização combinatória, pertencente à classe NP-hard. Os estudos sobre métodos de resolução do PQA basicamente se dividem em dois grupos: algoritmos exatos ou ótimos, e algoritmos heurísticos ou sub-ótimos. Em ambas as estratégias de estudo