Um Mapeamento das Soluções do Problema Quadrático de Alocação no Universo das Soluções do Problema de Alocação Linear
Nome: LEANDRO COLOMBI RESENDO
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 28/06/2004
Banca:
Nome |
Papel |
|---|---|
| ARLINDO GOMES DE ALVARENGA | Examinador Interno |
| MARIA CRISTINA RANGEL | Orientador |
| NAIR MARIA MAIA DE ABREU | Examinador Externo |
Resumo: O Problema Quadrático de Alocação foi estudado utilizando uma abordagem algébrica através de uma relaxação, o Problema de Alocação Linear. A utilização dessa abrodagem se deve ao fato de existir na literatura o Teroema das Inversões demostrado por Rangel. M.C., que associa o custo de uma solução quadrática ao número de inversões de sua correspondente linerar. Descobrir quais soluções lineares são viáveis para o Problema Quadrático de Alocação é uma tarefa extremamente difícil dados que o número de soluções lineares é bem maior que o das quadráticas. Neste trabalho construímos uma mariz que armazena informações de soluções lineares capazes de gerar soluções quadráticas. Combinando esse mapeamento com o Teorema das Inversões apresentamos um algoritmo construtivo que gera soluções gera soluções quadráticas de boa qualidade. Propomos uma versão paralela do referido algoritmo.
