Un caso especial del problema de asignación cuadrática: el GAP-arbol

• Autores: Enric Benavent López
• Directores de la Tesis: Marco A. López Cerdá (dir. tes.)
• Lectura: En la Universitat de València ( España ) en 1982
• Idioma: español
• Tribunal Calificador de la Tesis: Marco A. López Cerdá (presid.) , Segundo Gutiérrez Cabria (secret.) , Francisco José Cano Sevilla (voc.) , Ramiro Melendreras Gimeno (voc.) , Rafael Infante Macías (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.