Euristica

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
FACULTAD DE CIENCIAS MATEMATICAS

UN ESTUDIO ALGORÍTMICO DEL PROBLEMA DE CORTE Y EMPAQUETADO 2D

TESIS PARA OPTAR EL TÍTULO PROFESIONAL DE LICENCIADO EN INVESTIGACIÓN OPERATIVA

Rosa Sumactika Delgadillo Avila

Lima - Perú Marzo, 2007

1

UN ESTUDIO ALGORÍTMICO DEL PROBLEMA DE CORTE Y EMPAQUETADO 2D

Rosa Sumactika Delgadillo Avila

Tesispresentada a consideración del Cuerpo Docente de la Escuela de Investigación Operativa de la Facultad de Ciencias Matemáticas, de la Universidad Nacional Mayor de San Marcos, como parte de los requisitos para optar el Título de Licenciado en Investigación Operativa.

Aprobada por:

________________________________

Dra. María del Pilar Álvarez Rivas
Presidente______________________________

Mg. Luis Alberto Oré Luján
Miembro

_______________________________ Mg. Esther Berger Vidal Miembro Asesor

Lima – Perú Marzo, 2007

2

A todas las personas que hacen Operaciones.

Investigación de

A mi esposo e hijos, a mis padres y hermanos, por las horas de estímulo y amor incondicional que me han dado y me dan.

4

AGRADECIMIENTOS Agradezco a Dios por habermebendecido abundantemente en toda mi vida, por haberme capacitado intelectualmente para este trabajo, por haberme mostrado que en él encuentro vida. A mis padres porque siempre me incentivaron para alcanzar mis metas. A mi esposo porque en él me siento estimulada, a mis hijos por el amor que me dan. A la profesora Esther Berger por confiar en mí para la realización de este trabajo y por su apoyo. A losprofesores María Álvarez y Luis Oré por su participación como jurados. A todos los profesores de la Facultad de Matemáticas que aportaron en mi formación académica. También a los distintos autores de los libros y artículos que he leído, que contribuyeron en mi conocimiento del tema y que forman parte de este trabajo.

5

INDICE
INTRODUCCIÓN Relevancia del Problema Objetivo CAPÍTULO IConceptos y Notaciones Preliminares 1.1 Estructura de un Problema de Corte 1.2 Estructura de un Problema de Empaquetado 1.3 Dualidad del Problema de Corte y el Problema de Empaquetado 1.4 Definición del Problema de Corte en una Dimensión 1.5 Definición del Problema de Corte en dos Dimensiones 1.6 Definición del Problema de Empaquetado 1.7 Problemas de Corte por Guillotina 1.8 Problemas de CorteNo-Guillotina 1.9 Relación con otros Problemas de Optimización 1.9.1 Problema de la Mochila 1.9.2 Problema de Programación de Tareas Independientes 1.10 Clasificación del Problema de Corte y Empaquetado CAPÍTULO II Métodos Exactos 2.1 Método Simplex 2.2 Método de Generación de Columnas 2.3 Método Programación Dinámica 2.4 Método de Ramificación y Acotación 2.5 Método Enumerativo de Wang 2.6 Método InformadoAlgoritmo AAO* CAPÍTULO III Métodos Heurísticos 3.1 Heurísticas para el Problema de Empaquetado 1D 3.1.1 Heurística NF 3.1.2 Heurística FF 3.1.3 Heurística BF 3.1.4 Heurística NFD 3.1.5 Heurística FFD 3.1.6 Heurística BFD 3.2 Heurísticas para el Problema de Empaquetado 2D 3.2.1 Algoritmo FBSOG 3.2.2 Algoritmo FFFOG 3.2.3 Algoritmo FBSRG y FFFRG 3.2.4 Algoritmo FCRG 3.2.5 Algoritmo KPOG 3.2.6Algoritmo KPRG 3.2.7 Algoritmo ADOF 3.2.8 Algoritmo TPRF 3.2.9 Algoritmo FFD-CUT-2DRG 3.2.10 Algoritmo BFD-CUT-2DRG CAPÍTULO IV Meta Heurísticas 4.1 GRASP 1 4 5

7 10 12 13 15 17 20 23 24 24 26 27

38 39 40 43 47 49

53 53 54 55 55 56 56 58 58 59 60 62 62 63 65 68 70 74

77

10

4.2 Búsqueda Tabú 4.3 Templado Simulado 4.4 Algoritmos Genéticos. CAPÍTULO V Conclusiones y PerspectivasFuturas 5.1 Conclusiones 5.2 Perspectivas BIBLIOGRAFÍA

83 89 94

100 102 103

11

LISTA DE FIGURAS Y TABLAS

Fig. 1.1 Fig. 1.2 Fig. 1.3 Fig. 1.4 Fig. 1.5 Fig. 1.6 Fig. 1.7 Fig. 1.8 Fig. 1.9 Fig. 1.10 Fig. 1.11 Fig. 1.12 Fig. 1.13 Fig. 2.1 Fig. 2.2 Fig. 2.3 Fig. 2.4 Fig. 3.1

Estructura general del problema de corte 1D. Estructura general del problema de corte 2D. Estructura general del...