Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.udec.cl/jspui/handle/11594/11075
Título : | Una matheurística para la resolución del Set Union Knapsack Problem. |
Autor : | Contreras Bolton, Carlos Emilio; profesor guía Cañete Saavedra, Alex Javier |
Fecha de publicación : | 2022 |
Editorial : | Universidad de Concepción. |
Resumen : | El Set Union Knapsack Problem (SUKP) es una generalización del problema de la mochila (KP) clásica, donde el objetivo es seleccionar desde un conjunto de ítems que aportan beneficio, aquellos que maximizan este último, sujeto a una restricción de capacidad. En el caso del SUKP, estos ítems se forman por elementos que son los que ocupan capacidad. Esta característica convierte al SUKP en un problema de complejidad mayor al KP clásico, esto último sumado a las múltiples aplicaciones en sistemas de producción, finanzas, bases de datos, entre otras, otorgan gran relevancia a la investigación de este problema. En este trabajo se presenta una matheurística para la resolución del SUKP, que utiliza soluciones parciales creada mediante muestreo aleatorio, generando instancias reducidas que luego son resultas mediante CPLEX y/o MSBTS, algoritmo del estado del arte dedicado a resolver el SUKP. Se realiza una revisión de la literatura del estado del arte de los métodos para resolver el SUKP. Se reportan resultados computacionales sobre 30 instancias ejecutadas, siendo estos resultados comparados con otros algoritmos del estado del arte. Los resultados muestran un buen desempeño del algoritmo propuesto, muchas veces cercano a los métodos de vanguardia,destacando una brecha de rendimiento menor al 0.5% en el mejor valor encontrado para la función objetivo. |
Descripción : | Memoria de Título presentada para optar al título profesional de Ingeniero Civil Industrial. |
URI : | http://repositorio.udec.cl/jspui/handle/11594/11075 |
Aparece en las colecciones: | Ingeniería Industrial - Tesis Pregrado |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Cañete Saavedra_Alex Tesis.pdf | 578,26 kB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons