Algoritmos proyectivos de separación para problemas de programación lineal entera

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 un...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Rodes, Federico
Otros Autores: Zabala, Paula Lorena, Méndez Díaz, Isabel
Formato: Tesis Libro
Lenguaje:Español
Publicado: Octubre de 2011
Acceso en línea:Registro en la Biblioteca Digital
PDF
Handle
Aporte de:Registro referencial: Solicitar el recurso aquí
Biblioteca Central Dr. Luis F. Leloir (FCEN) de Universidad de Buenos Aires
LEADER 06110nam a22003257a 4500
003 AR-BaUEN
005 20251204134520.0
008 251006s2011 ag ad||f|m||| 000 0|spa|d
040 |a AR-BaUEN  |b spa  |c AR-BaUEN 
041 0 |b spa 
044 |a ag 
084 |a MAT 000775 
100 1 |a Rodes, Federico 
245 1 0 |a Algoritmos proyectivos de separación para problemas de programación lineal entera 
260 |c Octubre de 2011 
300 |a 61 p. :   |b il., gráfs. 
502 |b Licenciado en Ciencias Matemáticas  |c Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales  |d 2011-12-29 
506 |2 openaire  |e Autorización del autor  |f info:eu-repo/semantics/openAccess 
518 |o Fecha de publicación en la Biblioteca Digital FCEN-UBA 
520 3 |a 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.  |l spa 
540 |2 cc  |f https://creativecommons.org/licenses/by-nc-sa/2.5/ar 
700 1 |a Zabala, Paula Lorena 
700 1 |a Méndez Díaz, Isabel 
856 4 |q application/pdf  |u https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nMAT000775_Rodes  |y Registro en la Biblioteca Digital 
856 4 |q application/pdf  |u https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000775_Rodes.pdf  |y PDF 
856 4 |q application/pdf  |u https://hdl.handle.net/20.500.12110/seminario_nMAT000775_Rodes  |y Handle 
931 |a DM 
961 |b seminario  |c PE  |e ND  |a seminario_nMAT000775_Rodes 
962 |a info:eu-repo/semantics/bachelorThesis  |a info:ar-repo/semantics/tesis de grado  |b info:eu-repo/semantics/publishedVersion 
999 |c 108451 

Ejemplares similares