RT info:eu-repo/semantics/bachelorThesis
T1 Relajación y heurística Lagrangiana. Aplicación a un problema de optimización combinatoria
A1 Fernández Serna, Elena
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Optimización
K1 Programación entera
K1 Relajación y Heurística Lagrangiana
AB La optimización combinatoria es un campo de las matemáticas en el que se trabajacon un problema modelizado de modo que el objetivo que se tiene es minimizaro maximizar una función. Las variables de ese problema están sujetas a una serie derestricciones que nos complican su resolución, entre las que se encuentran las restriccionesde variables enteras.Realizaremos una pequeña introducción a los problemas de optimización relajados,cuyo nombre proviene de ser más ¨permisivos" con las restricciones, profundizandoconcretamente en la denominada relajación Lagrangiana. Gracias a las característicasde la función Lagrangiana, es posible emplear el algoritmo subgradiente parabuscar un óptimo de esta función iteración tras iteración. Detallaremos los pasos yparámetros necesarios para este método, describiendo detalladamente una de las reglasmás famosas, la de Held-Wolfe-Crowder.Se presentarán técnicas heurísticas con las que podremos obtener soluciones para laprimera iteración del algoritmo, además de su posible mejora con una determinadafrecuencia. La técnica de combinar la relajación y la heurítica Lagrangiana nospermitirá obtener simultáneamente buenas cotas inferiores y superiores del óptimo delproblema original.Por último, se ha procedido a aplicar todo lo recogido en la memoria para la resoluciónde un problema de optimización combinatoria en particular, el problema de cubrimientomáximo. Para ello se ha empleado el programa informático de Xpress IVE y sepresentan los resultados y conclusiones obtenidas del análisis de un conjunto de datos.
YR 2021
FD 2021
LK https://uvadoc.uva.es/handle/10324/50578
UL https://uvadoc.uva.es/handle/10324/50578
LA spa
DS UVaDOC
RD 19-abr-2024