Problema de corte de valores

Específicamente, es un problema de programación lineal con números enteros.que representa cuántas veces será utilizado cada patrón.es el costo (a menudo los residuos) del patrónMuchas variaciones son posibles, incluyendo uno en el que el objetivo no es reducir al mínimo los desechos, si no maximizar el valor total de los artículos producidos, permitiendo que cada orden tenga un valor diferente.Un enfoque alternativo utiliza generación-retrasada de columnas.Este método resuelve el problema del corte de valores comenzando con unos pocos patrones.El método de generación de columnas retardada puede ser mucho más eficiente que el enfoque original, en particular como el tamaño del problema crece.[2]​[3]​ Gilmore y Gomory demostraron que este enfoque garantiza la convergencia a la solución óptima (fraccionada), sin necesidad de enumerar todos los posibles patrones de antemano.Una limitación del método original de Gilmore y Gomory es que no maneja integralidad, por lo que la solución puede contener fracciones, por ejemplo, un patrón particular se debe producir 3,67 veces.El problema de corte de valores es a menudo degenerado, en que son posibles varias soluciones con el mismo residuos.Esta degeneración se debe a que es posible mover los elementos alrededor, creando nuevos patrones, sin afectar a los residuos.Los siguientes 13 artículos deben ser cortados: Hay 308 patrones posibles para este pequeño ejemplo.[9]​ Una forma es la dimensionalidad del corte: el ejemplo anterior ilustra un problema unidimensional (1D); otras aplicaciones industriales de 1D se producen al cortar los tubos, cables y barras de acero.No se conocen muchas aplicaciones tridimensionales (3D) que implican el corte; sin embargo, el estrechamente relacionados problema de empaquetamiento 3D tiene muchas aplicaciones industriales, tales como el empaquetamiento de objetos en los contenedores de transporte (ver por ejemplo contenerización - el relacionado Empaquetamiento de esferas problema que ha sido estudiado desde el siglo XVII (Conjetura de Keplerr )).El problema relacionado de determinar, para el caso unidimensional, el mejor tamaño de master que se reunirá dada la demanda se conoce como el problema variedad.