Aplicación de métodos de optimización en la solución de un problema de la industria editorial

Abstract

En la industria editorial, se deben crear los negativos de los documentos y las planchas donde se van a colocar dichos negativos para que luego sean enviadas a imprimir. Analizando los costos de imprimir documentos se notó que el costo de crear un negativo es muy elevado en comparación con el costo de imprimir todas las copias necesarias para satisfacer una cierta demanda. Por otro lado, se observó que en muchas ocasiones no se utilizaba todo el espacio disponible en cada una de las planchas o que si todo el espacio era utilizado muchas veces se imprimían copias de más, las cuales representan un desperdicio o un gasto innecesario para la industria. Como consecuencia de esto, surge el siguiente problema: suponga que una determinada industria debe imprimir en gráficos, cierta cantidad de copias para cada uno de ellos (no necesariamente la misma cantidad para todos), y se tiene una cantidad, no prefijada, de planchas del mismo tamaño, en las cuales se deben colocar primero los negativos de los dibujos para luego enviarlos a imprimir. Lo que se quiere es utilizar la menor cantidad de planchas de tal forma que minimice la cantidad de copias de cada gráfico que no se utilizarán y además el espacio no utilizado en cada plancha. En el año 2007, se llevó a cabo un proyecto de investigación para resolver el problema de la industria editorial, desarrollando algoritmos basados en heurísticas, cuyos resultados obtenidos dan una solución al problema de una dimensión, únicamente. Esta investigación tuvo como objetivo principal desarrollar e implementar algoritmos basados en programación lineal que determinen la solución del problema de la industria editorial, utilizando el método de generación de columnas. Se implementaron algoritmos que permiten obtener una solución al problema en una y en dos dimensiones. Con estos algoritmos se lograron mejores resultados que los obtenidos en el 2007, por otro lado, con la solución dada en esta investigación se consigue un menor número de copias sobrantes, lo cual significa disminución en los costos de impresión.

In the publishing industry negatives have to be created to print documents as well as the plates where the negatives are going to be placed. By weighting the cost of printing documents it was noted that the cost of creating a negative is higher compared to the cost of printing all the copies required to meet a certain demand. Furthermore, it was observed that all the available space on each plate was not fully used or, if all the space was used more copies were printed, which represent a waste or expense unnecessary for the industry. As a result, the following problem arises: suppose a particular industry prints n graphics, a certain amount of copies for each (not necessarily the same quantity for each one), and where the size of the plates are all the same. The negatives of the pictures are prepared first and then sent to print. The goal is to use the least amount of plates in a way that minimizes the number of copies of each graph that are not used and also the unused space on each plate. A research project was conducted in 2007 to solve the problem of the publishing industry. In that project, algorithms were developed based on heuristics. The results obtained gave a solution only to the one dimensional problem. Based on the method of column generation this research aims mainly developing and implementing algorithms based on linear programming to determine the solution of the publishing industry problem. Algorithms were implemented that can provide a solution to the problem in one and two dimensions. These algorithms showed better results than those obtain in 2007, also the solution propose in this investigation was able to use less number of waste copies, which is most cost efficient for the publishing industry.