ALGORITMO GRASP

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
FACULTAD DE CIENCIAS MATEMÁTICAS
E.A.P. DE INVESTIGACIÓN OPERATIVA

Un estudio algorítmico del problema de corte y
empaquetado 2D

TESIS
para optar el Título Profesional de Licenciado en Investigación Operativa

AUTOR
Rosa Sumactika Delgadillo Avila

Lima – Perú
2007

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

RosaSumactika Delgadillo Avila

Tesis presentada 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 RivasPresidente

______________________________

Mg. Luis Alberto Oré Luján
Miembro

_______________________________
Mg. Esther Berger Vidal
Miembro Asesor

Lima – Perú
Marzo, 2007

2

A todas las personas que hacen

Investigación de

Operaciones.
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 haberme bendecido 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 larealización de este trabajo y por
su apoyo.
A los profesores 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

INDICEINTRODUCCIÓN
Relevancia del Problema
Objetivo

1
4
5

CAPÍTULO I
Conceptos 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 deEmpaquetado
1.7 Problemas de Corte por Guillotina
1.8 Problemas de Corte No-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

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

CAPÍTULO II
Métodos Exactos
2.1 Método Simplex
2.2 Método deGeneració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 Informado Algoritmo AAO*

38
39
40
43
47
49

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 BFD3.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.6 Algoritmo 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

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

CAPÍTULO IV
MetaHeurísticas
4.1 GRASP

77

10

4.2 Búsqueda Tabú
4.3 Templado Simulado
4.4 Algoritmos Genéticos.

83
89
94

CAPÍTULO V
Conclusiones y Perspectivas Futuras
5.1 Conclusiones
5.2 Perspectivas

100
102

BIBLIOGRAFÍA

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....