Ordenações parciais nos conjuntos das soluções dos problemas de alocação linear e quadrático

Pesquisa Operacional

Maria Cristina Rangel²  Nair Maria Maia De Abreu¹ 

[1] ,Universidade Federal do Espírito Santo Departamento de Informática - CT Vitória ES

关键词: ordenação parcial;    problema quadrático de alocação;    problema de alocação linear;    partial ordination;    quadratic assignment problem;    linear assignment problem;   

DOI  :  10.1590/S0101-74382003000200002

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License