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

  1. Benavent López, Enric
Supervised by:
  1. Marco A. López Cerdá Director

Defence university: Universitat de València

Year of defence: 1982

Committee:
  1. Marco A. López Cerdá Chair
  2. Segundo Gutiérrez Cabria Secretary
  3. Francisco José Cano Sevilla Committee member
  4. Ramiro Melendreras Gimeno Committee member
  5. Rafael Infante Macías Committee member

Type: Thesis

Teseo: 7167 DIALNET

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.