El problema del K-centro en RN con normas LPB estrictas

• Autores: Lázaro Cánovas Martínez
• Directores de la Tesis: Blas Pelegrín Pelegrín (dir. tes.)
• Lectura: En la Universidad de Murcia ( España ) en 1995
• Idioma: español
• Tribunal Calificador de la Tesis: Procopio Zoroa Terol (presid.) , José Andrés Moreno Pérez (secret.) , Rafael Infante Macías (voc.) , Miguel Sánchez García (voc.) , José María Ruiz Gómez (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • SE PLANTEA EL PROBLEMA DE ENCONTRAR UN CONJUNTO C DE K PUNTOS EN IRN, TAL QUE LA DISTANCIA MAXIMA ENTRE C Y CADA ELEMENTO DE UN CONJUNTO FINITO DADO A SEA MINIMA, APLICACIONES PUEDEN ENCONTRARSE EN LOCALIZACION DE SERVICIOS DE EMERGENCIA, CENTROS DE TRANSMISION MULTIONDA Y CLASIFICACION DE DATOS. SE ESTUDIA EL PROBLEMA CUANDO LA DISTANCIA VIENE MEDIDA POR UNA NORMA LPB CON 1<P<INFINITO, B=(B1,..., BN), BJ 0, J=L,...,N.

    PARA K=1, SE OBTIENEN ALGORITMOS PRIMALES Y DUALES BASADOS RESPECTIVAMENTE EN EL METODO DE DIRECCIONES FACTIBLES Y EN LA DETERMINACION DE UNA SOLUCION OPTIMA MEDIANTE N+1 PUNTOS DEL CONJUNTO A. PARA K L, SE DEMUESTRA QUE EL PROBLEMA ES EQUIVALENTE A UN PROBLEMA DE OPTIMIZACION DISCRETA, Y SE PRESENTA UN ALGORITMO EXACTO PARA SU RESOLUCION, QUE SOLO ES VIABLE PARA A<IR2 Y M<100, DEBIDO A LA NP-DUREZA DEL PROBLEMA.

    PARA LA OBTENCION DE SOLUCIONES EN IRN Y M 100, SE PRESENTAN ALGORITMOS HEURISTICOS, BASADOS EN UNA NUEVA REGLA DE ASIGNACION DE LOS PUNTOS DE A A LOS CENTROS DE C, Y SE ESTUDIAN SUS PROPIEDADES. SE REALIZAN ESTUDIOS COMPUTACIONALES PARA N=2, 4, 6, 8 Y 10 Y M=500T, T=L,...,10 QUE PERMITEN COMPARAR LOS DIFERENTES ALGORITMOS PROPUESTOS, Y ESTABLECER CONCLUSIONES EN CUANTO A SU TIEMPO DE COMPUTACION Y CALIDAD DE LA SOLUCION OBTENIDA. PARA K=L, SE OBTIENEN BUENOS RESULTADOS EN TIEMPOS DE COMPUTACION INFERIORES A 15 SEG.

    EN TODOS LOS CASOS. PARA K L, LOS ALGORITMOS OBTENIDOS SE EJECUTAN CON MENORES TIEMPOS DE COMPUTACION Y PROPORCIONAN MEJORES VALORES OBJETIVO QUE CUANDO SE ASIGNAN LOS PUNTOS A LOS CENTROS MAS CERCANOS, SIENDO LOS TIEMPOS DE COMPUTACION INFERIORES A 10 SEG. EN TODOS LOS CASOS.