Modelos enteros para el problema de empaquetamiento de círculos en un contenedor rectangular. - Zamarrón Castro, Ruth Lizeth (2014)
Título de Estudio: MODELOS ENTEROS PARA EL PROBLEMA DE EMPAQUETAMIENTO DE CIRCULOS EN UN CONTENEDOR RECTANGULAR OBJETIVOS Y METODOS DE ESTUDIO: El objetivo general de este trabajo consiste en desarrollar e implementar un modelo de optimización lineal entera para el problema de empaquetamiento de círculos en un contenedor rectangular. La formulación de un problema es de suma importancia para encontrar su solución, por tal motivo, en el presente trabajo se estudian cuatro formulaciones equivalentes para el problema de empaquetamiento de círculos en un contenedor rectangular y se busca aprovechar la estructura del mismo con el propósito de comparar la calidad de las diversas formulaciones. Se busca encontrar una solución similar a lo existente en la literatura que depende de la cantidad de círculos a empaquetar, y otro de los objetivos que se espera es obtener un mejor tiempo para la solución del problema. Para esto, se desarrolla un modelo lineal entero binario para encontrar la solución y no un modelo basado en variables continúas que es lo que se hace comúnmente en la literatura para resolver el empaquetamiento de círculos. Se encuentra una mejor solución que proporciona la solución factible para el problema, y se estudia además el tiempo en el que se encuentran dichas soluciones. Se utiliza una formulación que cumple con todas las características del problema de empaquetamiento, una segunda formulación que cuenta con las restricciones de intersección, una tercera formulación que es compacta ya que elimina las restricciones que se duplican en la restricción de intersección y una última formulación que es compacta y utiliza las restricciones de intersección. CONTRIBUCIONES Y CONCLUSIONES: Se comparan numéricamente las diferentes soluciones que se encuentran, dependiendo de la cantidad de círculos que se empaquetaron, el tiempo en el que se resuelven las formulaciones, así como con las obtenidas en la literatura. En la mayoría de los trabajos que tratan el problema de empaquetamiento son modelos no lineales, en donde las variables continuas son las coordenadas de los centros de los círculos que se procura empaquetar. Sin embargo, en la experimentación encontramos que con un modelo lineal binario: a) se pueden encontrar los mismos resultados, o la misma cantidad de círculos a empaquetar en el contenedor rectangular. b) el tiempo para encontrar la solución es el mismo o menor dependiendo del caso. Algunos de los resultados de este trabajo se han presentado en congresos o foros nacionales e internacionales como: • Segundo Congreso de la Sociedad Mexicana de Investigación de Operaciones/ Quinto Taller Iberoamericano de Investigación de Operaciones (TLAIO), Acapulco, México, noviembre 2013. • Ciclo de Seminarios de la Universidad Estadual Paulista campus S. J. do Rio Preto, S.P. Brasil, Agosto 2013. • Semana Cultural de la FIME, UANL, San Nicolás de los Garza, Nuevo León, México, Octubre 2013. • XXIII Escuela Nacional de Optimización y Análisis Numérico (ENOAN), Saltillo Coahuila, México, Abril 2013. • Seminario de Investigación del Posgrado en Ingeniería en Sistemas, UANL, Abril 2013.