Registro:
| Documento: | Tesis de Grado |
| Título: | Una variación del problema de ordenamiento lineal |
| Autor: | Curcio, Brian Luis |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2013 |
| Fecha en portada: | 2013 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel |
| Director Asistente: | Zabala, Paula Lorena |
| Jurado: | Delle Donne, Diego Andrés; Figueira, Santiago Daniel |
| Idioma: | Español |
| Palabras clave: | OPTIMIZACION COMBINATORIA; ORDENAMIENTO LINEAL; PROGRAMACION LINEAL ENTERA; ESTUDIO POLIEDRALBRANCH AND CUT |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000711_Curcio |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000711_Curcio.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000711_Curcio |
| Ubicación: | Dep.COM 000711 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Curcio, Brian Luis. (2013). Una variación del problema de ordenamiento lineal. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000711_Curcio |
Resumen:
El objetivo de esta tesis es desarrollar un algoritmo exacto para una variante del problema de ordenamiento lineal basado en un modelo de programación lineal entera. El problema de ordenamiento lineal es un problema clásico de optimización combinatoria estudiado desde hace más de 50 años. Los diversos escenarios reales que provienen de situaciones surgidas en variados campos de la industria y otros sectores, han dado origen a distintas variaciones de este problema. La gran cantidad de aplicaciones que poseen los problemas de esta familia hacen que los mismos no solo tengan interés teórico, sino también, una gran importancia práctica. La versión del problema abordada en este trabajo consiste en encontrar un orden total de elementos de manera que se minimice la suma de las penalidades entre pares de ellos, donde la penalidad se define como el producto entre la distancia a la que se encuentran los dos elementos y un costo asociado a ellos. Este problema recibe el nombre de Problema de Ordenamiento Lineal con Penalidades POLP. POLP pertenece a la clase de problemas NP-Difícil. Para estos problemas no se conocen algoritmos que encuentren la solución en tiempo polinomial. Como muchos de los problemas de Optimización Combinatoria, POLP puede ser modelado mediante formulaciones de programación lineal entera o entera mixta. Los algoritmos Branch-and-Cut son una de las herramientas más efectivas que se conoce para resolver un modelo de programación lineal entera. Especialmente las implementaciones basadas en combinatoria poliedral han permitido incrementar el tamaño de las instancias resueltas. En el transcurso del trabajo se analizan diversas formulaciones de programación lineal entera que permiten modelar el problema. Luego de seleccionar la más prometedora según ciertos criterios, se realiza un estudio poliedral para determinar características de la cápsula convexa del conjunto de soluciones factibles. En base a estas familias de desigualdades válidas, se desarrolló e implementó un algoritmo Branch-and-Cut para resolver el problema. También se consideraron factores decisivos en la eficiencia de este tipo de algoritmos, como la incorporación de heurísticas iniciales y primales, distintas estrategias de selección de variable de branching, y esquemas de recorrido del árbol de Branch-and-Bound. Finalmente se muestran resultados experimentales sobre instancias de prueba que permiten evaluar la eficiencia del algoritmo desarrollado.
Citación:
---------- APA ----------
Curcio, Brian Luis. (2013). Una variación del problema de ordenamiento lineal. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000711_Curcio
---------- CHICAGO ----------
Curcio, Brian Luis. "Una variación del problema de ordenamiento lineal". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2013.https://hdl.handle.net/20.500.12110/seminario_nCOM000711_Curcio
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000711_Curcio.pdf
Distrubución geográfica
