El Problema de Corte de Rollos (conocido también por «Cutting Stock Problem») es una de las aplicaciones clásicas de la Programación Entera que consiste en determinar cómo cortar un rollo de papel en dimensiones más pequeñas, de modo de satisfacer las demandas u ordenes de los clientes y al mismo tiempo minimizar la pérdida de material.
En este contexto, el Problema de Corte de Rollos se puede extender fácilmente a otra serie de aplicaciones prácticas como la industria textil, muebles, acero, etc, donde se dispone de un insumo que se debe cortar para poder utilizarlo como materia prima o venderlo directamente a los clientes y en donde en dicho proceso se incurre necesariamente en una pérdida de material.
A continuación presentaremos un ejemplo del problema de corte de rollos de papel, donde se dispone de rollos de 100[cm], 80[cm] y 55[cm] y los clientes demandan rollos más pequeños de 45[cm], 30[cm] y 18[cm]. Notar que dependiendo el esquema o patrón de corte a utilizar existe una pérdida de papel (en [cm]) asociada. Por ejemplo, el esquema de corte 1 representado en la imagen a continuación considera cortar un rollo de 100[cm] en 2 rollos más pequeños con una pérdida de 10[cm].
Al resumir las posibles combinaciones de cortes para los rollos se identifican 15 patrones. Adicionalmente los clientes demandan 150[u], 200[u] y 175[u] de los rollos de 45[cm], 30[cm] y 18[cm], respectivamente.
Para el problema anterior consideremos el siguiente modelo de Programación Entera:
1. Variables de Decisión:
Xi: Número de Rollos cortados bajo el esquema o patrón de corte i (con i=1,…,15 que representa las distintas combinaciones posibles)
2. Función Objetivo:
Minimizar la pérdida de material total que esta dada por la ponderación de la pérdida en centímetros asociada a cada esquema de corte por la cantidad de veces que se utiliza el esquema respectivo.
Minimizar 10X1+7X2+X3+10X4+4X5+16X6+10X7+5X8+17X9+2X10+14X11
+8X12+10X13+7X14+X15
La notación anterior se puede expresar de forma equivalente y compacta definir el conjunto de parámetros Pi que indica la pérdida en centímetros asociada al patrón de corte i. La función objetivo en este caso sería:
3. Restricciones:
Se debe satisfacer la demanda de rollos de 45[cm], 30[cm] y 18[cm]. En este contexto las restricciones son:
- Rollos de 45[cm]: 2X1+X2+X3+X8+X9+X13>=150
- Rollos de 30[cm]: X2+3X4+2X5+X6+X8+2X10+X11+X14>=200
- Rollos de 18[cm]: X2+3X3+2X5+3X6+5X7+X9+X10+2X11+4X12+X14+3X15>=175
Por ejemplo en el caso de los rollos de 45[cm] se puede satisfacer la demanda de 150[u] sólo con el esquema de corte 1, 2, 3, 8, 9 y 13. En el lado izquierdo de la respectiva restricción se pondera la variable por la cantidad de rollos de la dimensión requerida obtenidos al utilizar el esquema de corte seleccionado.
Finalmente definimos condiciones de no negatividad e integralidad para las variables de decisión: Xi>=0 Enteros. Para i=1,…,15. En este tipo de aplicaciones es natural requerir un número entero para el valor que adopten las variables de decisión dada la naturaleza del problema formulado.