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

  1. Benavent López, Enric
unter der Leitung von:
  1. Marco A. López Cerdá Doktorvater/Doktormutter

Universität der Verteidigung: Universitat de València

Jahr der Verteidigung: 1982

Gericht:
  1. Marco A. López Cerdá Präsident/in
  2. Segundo Gutiérrez Cabria Sekretär/in
  3. Francisco José Cano Sevilla Vocal
  4. Ramiro Melendreras Gimeno Vocal
  5. Rafael Infante Macías Vocal

Art: Dissertation

Teseo: 7167 DIALNET

Zusammenfassung

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.