Resumen:
En esta tesis nos concentraremos en los Problemas de Programación Lineal Entera (PPLE) y, en especial, en los métodos exactos utilizados para su resolución. Los PPLE son problemas de optimización con las siguientes características distintivas: la función que se pretende maximizar (o minimizar) es una función lineal; el dominio sobre el que se debe trabajar queda determinado por la intersección de un conjunto de desigualdades lineales; y, por último, al menos una de las variables en juego debe estar obligada a adquirir valores enteros. El interés por estudiar estas estructuras surge como consecuencia del gran número de situaciones reales que permiten representar. Típicamente, los modelos de programación lineal entera son utilizados para describir procesos industriales y actividades del sector servicios con el fin de minimizar los costos de producción y logística. En cuanto a los métodos de resolución, hasta el momento no se conoce ningún algoritmo eficiente –de tiempo polinomial– que permita hallar la solución óptima para cualquier instancia. Es decir, los PPLE pertenecen a la clase NP-Hard [12]. Por dicho motivo, desde el surgimiento de esta rama de la matemática en la década del 50, se han ensayado distintas estrategias para abordar este tipo de problemas. Podemos agruparlas en tres categorías: métodos exactos, métodos aproximados y métodos heurísticos. Los métodos exactos son procedimientos que garantizan la obtención del óptimo. Si bien la pertenencia a la clase NP-Hard indica que el tiempo requerido para encontrar la solución óptima puede resultar prohibitivo, los algoritmos exactos no son dejados de lado. La posibilidad de resolver en forma exacta instancias cada vez más grandes aumenta debido al desarrollo de mejores algoritmos y a la aparición de nuevas tecnologías. Los métodos aproximados permiten encontrar una solución factible del problema (es decir, una solución que satisfaga el conjunto de restricciones lineales, aunque no sea la mejor) y, al mismo tiempo, estimar la brecha entre esa solución y la solución óptima (certificado de optimalidad). Consumen menos recursos que los algoritmos exactos. Los métodos heurísticos son procedimientos que permiten hallar una solución factible del problema, pero son incapaces de determinar cuán cerca está esa solución de la solución óptima. Utilizan la menor cantidad de recursos y suelen ser una muy buena alternativa para instancias donde los algoritmos exactos no son adecuados. Dentro de la primera familia de métodos, las técnicas Branch-and-Bound y Branch-and-Cut –basadas en la teoría poliedral– han demostrado ser una de las mejores herramientas para tratar este tipo de problemas. Una de las características más destacables de estos algoritmos es su flexibilidad, la cual les permite adaptarse a las distintas formulaciones y, de esa manera, explotar características propias de cada problema (ver, por ejemplo: Problema del Viajante [1], Ruteo de Vehículos [14] y Orden Lineal [17]). En un contexto más general, podemos destacar a los solvers CPLEX [20], XPRESS-MP [9] y GuroBi [16] como algunos de los paquetes académico-comerciales que ofrecen las mejores implementaciones de las técnicas anteriormente citadas. En esta tesis propondremos un nuevo método exacto que, utilizando proyecciones para determinar la solución óptima, pueda ser aplicado sobre cualquier PPLE. Si bien la actual implementación del método puede considerarse un prototipo sobre el cual hay espacio para introducir muchas mejoras, los resultados computacionales, comparados con aquellos obtenidos con paquetes académico-comerciales, son altamente satisfactorios. La experiencia computacional nos demuestra que la propuesta es válida y que aporta una nueva visión dentro de la clase de métodos exactos. El trabajo está organizado de la siguiente manera: en el capítulo 1 introducimos los conceptos básicos de la programación lineal entera y describimos los principales algoritmos usados para su resolución; en el capítulo 2 presentamos dos casos particulares de problemas de programación lineal entera: el Problema de la Mochila No Acotado (UKP) y el Problema de la Mochila Multidimensional (MKP); en el capítulo 3 motivamos el uso de proyecciones para determinar soluciones enteras y proponemos nuestro algoritmo; el comportamiento del algoritmo es analizado para los problemas UKP y MKP en los capítulos 4 y 5 respectivamente; finalmente, en el capítulo 6 formulamos nuestras conclusiones y futuras líneas de trabajo.
Citación:
---------- APA ----------
Rodes, Federico. (2011). Algoritmos proyectivos de separación para problemas de programación lineal entera. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000775_Rodes
---------- CHICAGO ----------
Rodes, Federico. "Algoritmos proyectivos de separación para problemas de programación lineal entera". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/seminario_nMAT000775_Rodes
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000775_Rodes.pdf
Distrubución geográfica
