Ordena��es parciais nos conjuntos das solu��es dos problemas de aloca��o
linear e quadr�tico
Pesquisa Operacional, 23 (2):
265-284 (2003)Abstract
O Problema Quadr�tico de Aloca��o, PQA, pode ser abordado atrav�s
de uma relaxa��o na forma do Problema de Aloca��o Linear, PAL. Introduzimos
um poset (conjunto parcialmente ordenado) no conjunto das solu��es
lineares que nos permite comparar tamb�m os custos das solu��es do
problema quadr�tico, sem o conhecimento pr�vio das matrizes que definem
seus exemplares. Constru�mos um algoritmo polinomial capaz de determinar
pares de permuta��es livremente compar�veis, conceito apresentado
neste trabalho. Provamos um teorema que garante que os custos associados
a tais permuta��es preservam a ordem dada pelo n�mero de invers�es
das mesmas. Associando solu��es do problema a permuta��es, testes
emp�ricos s�o apresentados, visando a valida��o do n�mero de invers�es
como um par�metro de refer�ncia para a qualidade das solu��es. Este
trabalho � uma extens�o do artigo RA01 publicado nos anais do XXXIII
SBPO, em CD-ROM, 1277-1287, Sobrapo, ILTC, 2001.