Un caso especial del problema de asignación cuadráticael GAP-arbol

Abstract

SE EXAMINA UN CASO PARTICULAR DEL PROBLEMA DE ASIGNACION CUADRATICA QUE SE DENOMINA EL QAP-ARBOL, ESTE PROBLEMA SE FORMULA COMO UN PROBLEMA DE PROGRAMACION LINEAL ENTERA. UTILIZANDO ESTA FORMULACION Y CIERTAS RESTRICCIONES ADICIONALES SE CONSTRUYEN CINCO RELACIONES LAGRANGIANAS DISTINTAS A LAS QUE SE APLICA EL METODO DEL SUBGRADIENTE PARA OBTENER UNA COTA INFERIOR AL QAP-ARBOL. EL ESTUDIO DE UNA DE ESTAS RELAJACIONES NOS HA LLEVADO A LA ELABORACION DE UN METODO PARA CALCULAR LAS VARIABLES DUALES OPTIMAS DEL PROBLEMA DE LA ARBORESCENCIA DE MINIMO COSTE ASI COMO A LA DEMOSTRACION DE QUE ESTE PROBLEMA CUMPLE LA PROPIEDAD DE INTEGRALIDAD. FINALMENTE UTILIZANDO LA MEJOR DE LAS COTAS INFERIORES OBTENIDAS SE HAN APLICADO LOS METODOS DE BRANCH AND BOUND PARA RESOLVER EL QAP-ARBOL. SE INCLUYE UN ESTUDIO COMPUTACIONAL DE LOS RESULTADOS OBTENIDOS.