OPTIMIZACION

UNIVERSIDAD AUTONOMA DE NUEVO LEON

FACULTAD DE INGENIERIA MECANICA Y ELECTRICA

TEMAS SELECTOS DE OPTIMIZACION

SINTESIS TEMATICA 1

CUTTING STOCK PROBLEM

MAESTRA: MARTINEZ SALAZAR IRIS ABRIL

SALON: 4111 HORA: M3-M6 JUEVES

• Integrantes del equipo en clase:

Nombre Matricula

Luis Enrique Segovia Valdez 1503989

INDICE

Introduccion…………………………………………………………………………………………………………………………………..3

Descripción del problema. …………………………………………………………………………………………………………….4

Descripción gráfica del problema……………………………………………………………………………………………………5

Formulación matemática del problema………………………………………………………………………………………….6

Aplicaciones del problema en casos reales.…………………………………………………………………………………….7

Antecedentes del problema……………………………………………………………………………………………………………9

Métodos de solución al problema…………………………………………………………………………………………………10

Conclusiones…………………………………………………………………………………………………………………………………11

Referencias…………………………………………………………………………………………………………………………………..12

INTRODUCCION

El problema de corte de valores es un problema NP-completo optimización, esencialmente se reduce al problema de la mochila. Específicamente, es un problema de programación lineal con números enteros. Surge de muchas aplicaciones en la industria. Imagine que usted trabaja en una fábrica de papel y tiene un número de rollos de papel de ancho fijo a la espera de ser cortado, pero diferentes clientes quieren diferentes números de rollos de distintos tipos de anchos. ¿Cómo se van a cortar los rollos de manera que minimiza los residuos (cantidad de sobras)?

DESCRIPCIÓN DEL PROBLEMA

CUTTING STOCK PROBLEM.

El problema de corte de valores fue formulada por primera vez por Kantorovich en 1939.11 En 1951 antes de que se dispusiera de los ordenadores, L. V. Kantorovich y VA Zalgaller sugerieron12 resolver el problema de la utilización económica de material en la etapa de corte con la ayuda de la programación lineal. La técnica propuesta más tarde se llamó el método de generación de columnas.

es un problema NP-completo optimización , el cual consiste en encontrar el minimo numero de rollos o unidades de materia prima, que se necesitan para obtener un conjunto de artiulos de diferentes tamanos .

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. Esto da lugar a toda una colección de problemas afines que se ocupan de algún otro criterio, como el siguiente:

El problema de recuento mínimo de patrones: para encontrar una solución de la cantidad mínima de patrones entre las soluciones de desecho mínimo. Este es un problema muy difícil, incluso cuando se conoce los residuos.6 7 Hay una conjeturas que cualquier instancia unidimensional de restricciones de igualdad con n órdenes tiene al menos una solución mínima de residuos con no más n+ 1 patrones. No se conoce tampoco cota superior del numero de patrones, ejemplos con n + 5 son conocidos.

El problema de apilamiento mínimo: esto se refiere a la secuencia de los patrones a fin de no tener demasiadas órdenes parcialmente terminados en cualquier momento. Este era un problema abierto hasta 2007, cuando se publicó un algoritmo eficiente basado en programación dinámica.8

El problema del cambio mínimo del numero de cuchillo (para problema unidimensional): esto se refiere permutación de los patrones a fin de minimizar el número de veces que las cuchillas de corte longitudinal tienen que ser movido. Este es un caso especial del generalizado problema del viajante.

DESCRIPCIÓN GRÁFICA DEL PROBLEMA

Una máquina de papel puede producir un número ilimitado de rollos maestros (jumbo), cada uno mide 5600 mm de ancho. Los siguientes 13 artículos deben ser cortados

Solución:

Hay 308 patrones posibles para este pequeño ejemplo. La respuesta óptima requiere 73 rollos maestros y tiene 0,401% de residuos; se puede demostrar computacionalmente que en este caso el número mínimo de patrones con este nivel de residuos es 10. También se puede calcular que existen 19 diferentes soluciones, cada una con 10 patrones y una pérdida de 0,401%, de las que una solución se muestra a continuación:

FORMULACIÓN MATEMÁTICA DEL PROBLEMA

Datos del problema

- Xi: representa cuántas veces será utilizado cada patrón.

- Aij: es el numero de veces que la orden j aparece en el patron i.

- Ci: es el costo(a menudo los residuos) del patron i.

- m: numero de ordenes a realiazar.

La formulación estándar para el problema de corte de valores (pero no la única) comienza con una lista de m órdenes, cada una requiriere q_j, j = 1,\ldots,m piezas. A continuación se construye una lista de todas las combinaciones posibles de los recortes (a menudo llamados "patrones")

La naturaleza precisa de la cantidad de restricciones puede llevar a características matemáticas diferentes.

...