Problema de empaquetado

Los problemas de empaquetado son una clase de problemas de optimización en matemáticas que implican intentar empaquetar objetos en contenedores. El objetivo es empaquetar un solo contenedor lo más densamente posible o empaquetar todos los objetos usando la menor cantidad de contenedores posible. Muchos de estos problemas pueden estar relacionados con cuestiones reales de embalaje, almacenamiento y transporte. Cada problema de empaque tiene un problema de doble cobertura, que pregunta cuántos de los mismos objetos se requieren para cubrir completamente cada región del contenedor, donde los objetos pueden superponerse.

Esferas o círculos empaquetados sueltos (arriba) y más densamente (abajo)

En un problema de embalaje en contenedores, se proporciona:

• 'contenedores' (generalmente una sola región convexa bidimensional o tridimensional, o un espacio infinito)
• Un conjunto de 'objetos' algunos o todos los cuales deben empaquetarse en uno o más contenedores. El conjunto puede contener diferentes objetos con sus tamaños especificados, o un solo objeto de una dimensión fija que se puede utilizar repetidamente.

Por lo general, el embalaje no debe tener superposiciones entre las mercancías y otras mercancías o las paredes del contenedor. En algunas variantes, el objetivo es encontrar la configuración que empaqueta un solo contenedor con la máxima densidad. Más comúnmente, el objetivo es empaquetar todos los objetos en la menor cantidad de contenedores posible.^[1]​ En algunas variantes, la superposición (de objetos entre sí y/o con el límite del contenedor) está permitida, pero debe minimizarse.

Empaquetado en un espacio infinito

Muchos de estos problemas, cuando el tamaño del contenedor aumenta en todas las direcciones, se vuelven equivalentes al problema de empaquetar objetos lo más densamente posible en un espacio euclidiano infinito. Este problema es relevante para varias disciplinas científicas y ha recibido una atención significativa. La conjetura de Kepler postuló una solución óptima para empacar esferas cientos de años antes de que Thomas Callister Hales demostrara que era correcta. Muchas otras formas han recibido atención, incluidos elipsoides,^[2]​ sólidos platónicos y de Arquímedes^[3]​ incluidos los tetraedros,^[4]​^[5]​ trípodes (uniones de cubos a lo largo de tres rayos paralelos al eje positivo),^[6]​ y dímeros de esferas desiguales.^[7]​

Empaquetado hexagonal de círculos

 

El empaquetamiento hexagonal de círculos en un plano euclidiano bidimensional.

Estos problemas son matemáticamente distintos de las ideas del teorema del empaquetamiento de círculos. El problema de empaquetamiento de círculos trata de empaquetar círculos, posiblemente de diferentes tamaños, en una superficie, por ejemplo el plano o una esfera.

Las contrapartes de un círculo en otras dimensiones nunca pueden empaquetarse con total eficiencia en dimensiones mayores a uno (en un universo unidimensional, el círculo análogo son solo dos puntos). Es decir, siempre habrá espacio no utilizado si solo está empacando círculos. La forma más eficiente de empaquetar círculos, el empaque hexagonal , produce aproximadamente un 91% de eficiencia.^[8]​

Empaquetaduras de esferas en dimensiones superiores

Artículo principal: Empaquetamiento de esferas

En tres dimensiones, las estructuras compactas ofrecen el mejor empaque de celosía de esferas y se cree que es el óptimo de todos los empaques. Con empaquetaduras esféricas 'simples' en tres dimensiones (definiéndose cuidadosamente 'simple') hay nueve empaquetaduras definibles posibles.^[9]​ La celosía E8 de 8 dimensiones y la celosía Leech de 24 dimensiones también han demostrado ser óptimas en su respectivo espacio dimensional real.

Empaquetaduras de sólidos platónicos en tres dimensiones

Los cubos se pueden organizar fácilmente para llenar completamente el espacio tridimensional, siendo el empaque más natural el panal cúbico. Ningún otro sólido platónico puede enlosar el espacio por sí solo, pero se conocen algunos resultados preliminares. El empaquetado en tetraedros puede lograr un empacado de al menos el 85%. Uno de los mejores empaques de dodecaedros regulares se basa en la celosía cúbica centrada en la cara (FCC) antes mencionada.

El tetraedro y el octaedro juntos pueden llenar todo el espacio en una disposición conocida como panal tetraédrico-octaédrico.

Sólido	Densidad óptima de un empaque de celosía
icosaedro	0.836357...^[10]​
dodecaedro	(5 + ${\displaystyle {\sqrt {5}}}$ )/8 = 0.904508...^[10]​
octaedro	18/19 = 0.947368...^[11]​

Las simulaciones que combinan métodos de mejora local con empaques aleatorios sugieren que los empaques de celosía para icosaedros, dodecaedros y octaedros son óptimos en la clase más amplia de todos los empaques.^[3]​

Embalaje en contenedores tridimensionales

Diferentes cuboides en un cuboide

Determinar la cantidad mínima de contenedores cuboides (contenedores) que se requieren para empacar un conjunto dado de artículos cuboides (rectángulos tridimensionales). Los cuboides rectangulares que se van a empaquetar se pueden girar 90 grados en cada eje.

Esferas en una bola euclidiana

El problema de encontrar la bola más pequeña tal que ${\displaystyle k}$  bolas separadas de la unidad abierta se pueden empaquetar dentro tiene una respuesta simple y completa en ${\displaystyle n}$ -dimensiones del espacio euclídeo si ${\displaystyle \scriptstyle k\leq n+1}$ , y en un espacio de Hilbert de dimensión infinita sin restricciones. Vale la pena describirlo en detalle aquí para dar una idea del problema general. En este caso, en una configuración de ${\displaystyle k}$  hay disponibles bolas unitarias tangentes por pares. Coloca los centros en los vértices ${\displaystyle a_{1},..,a_{k}}$  de un regular ${\displaystyle \scriptstyle (k-1)}$  simplex dimensional con borde 2; esto se realiza fácilmente partiendo de una base ortonormal. Un pequeño cálculo muestra que la distancia de cada vértice desde el baricentro es ${\displaystyle \scriptstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ . Además, cualquier otro punto del espacio tiene necesariamente una mayor distancia de al menos uno de los ${\displaystyle \scriptstyle k}$  vértices. En términos de inclusiones de bolas, las ${\displaystyle \scriptstyle k}$  bolas unitarias abiertas centradas en ${\displaystyle \scriptstyle k}$  bolas unitarias abiertas centradas en ${\displaystyle \scriptstyle a_{1},..,a_{k}}$  están incluidos en una bola de radio ${\displaystyle \scriptstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ , que es mínimo para esta configuración.

Para demostrar que esta configuración es óptima, sea ${\displaystyle \scriptstyle x_{1},...,x_{k}}$  los centros de ${\displaystyle \scriptstyle k}$  bolas unitarias abiertas disjuntas contenidas en una bola de radio ${\displaystyle \scriptstyle r}$  centrado en un punto ${\displaystyle \scriptstyle x_{0}}$ . Considere el mapa del conjunto finito ${\displaystyle \scriptstyle \{x_{1},..x_{k}\}}$  en ${\displaystyle \scriptstyle \{a_{1},..a_{k}\}}$  tomando ${\displaystyle \scriptstyle x_{j}}$  en el correspondiente ${\displaystyle \scriptstyle a_{j}}$  para cada ${\displaystyle \scriptstyle 1\leq j\leq k}$ . Ya que para todos ${\displaystyle \scriptstyle 1\leq i<j\leq k}$ , ${\displaystyle \scriptstyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$  este mapa es 1-Lipschitz y por el teorema de Kirszbraun se extiende a un mapa 1-Lipschitz que está definido globalmente; en particular, existe un punto ${\displaystyle \scriptstyle a_{0}}$  tal que para todos ${\displaystyle \scriptstyle 1\leq j\leq k}$  uno tiene ${\displaystyle \scriptstyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$ , para que también ${\displaystyle \scriptstyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$ . Esto muestra que hay ${\displaystyle \scriptstyle k}$  unidad disjunta bolas abiertas en una bola de radio ${\displaystyle \scriptstyle r}$  si y solo si ${\displaystyle \scriptstyle r\geq r_{k}}$ . Observe que en un espacio de Hilbert de dimensión infinita esto implica que hay infinitas bolas unitarias abiertas disjuntas dentro de una bola de radio ${\displaystyle \scriptstyle r}$  si y solo si ${\displaystyle \scriptstyle r\geq 1+{\sqrt {2}}}$ . Por ejemplo, las bolas unitarias centradas en ${\displaystyle \scriptstyle {\sqrt {2}}e_{j}}$ , dónde ${\displaystyle \scriptstyle \{e_{j}\}_{j}}$  es una base ortonormal, son disjuntos y se incluyen en una bola de radio ${\displaystyle \scriptstyle 1+{\sqrt {2}}}$  centrado en el origen. Además, para ${\displaystyle \scriptstyle r<1+{\sqrt {2}}}$ , el número máximo de bolas unitarias abiertas disjuntas dentro de una bola de radio r es ${\displaystyle \scriptstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$ .

Esferas en un cuboide

Determinar la cantidad de objetos esféricos de diámetro d dado que se pueden empaquetar en un cuboide de tamaño a×b×c.

Esferas idénticas en un cilindro

Determinar la altura mínima h de un cilindro con un radio R dado que empacará n esferas idénticas de radio r (< R.^[12]​ Para un radio pequeño R, las esferas se organizan en estructuras ordenadas, llamadas estructuras columnares.

Poliedros en esferas

Determinar el radio mínimo R que empacará n poliedros de volumen unitario idénticos de una forma dada.^[13]​

Empaquetado en contenedores bidimensionales

 

El empaque óptimo de 10 círculos en un círculo.

Se han estudiado muchas variantes de problemas de empaquetamiento bidimensional.

Empaquetado de círculos

Dados n círculos unitarios, se debe empacarlos en el recipiente más pequeño posible. Se han estudiado varios tipos de envases:

• Círculos empacados en un círculo: estrechamente relacionado con los puntos de dispersión en un círculo unitario con el objetivo de encontrar la mayor separación mínima, d_n, entre puntos. Se han probado soluciones óptimas para n ≤13 y  n =19.
• Círculos empacados en un cuadrado: estrechamente relacionado con los puntos de dispersión en un cuadrado unitario con el objetivo de encontrar la mayor separación mínima, d _n , entre puntos. Para convertir entre estas dos formulaciones del problema, el lado cuadrado de los círculos unitarios será L= 2+2/d_n. Se han probado soluciones óptimas para n  ≤ 30.
• Círculos empacados en un triángulo rectángulo isósceles: se conocen buenas estimaciones para n <300.
• Círculos empacados en un triángulo equilátero: se conocen soluciones óptimas para n <13, y hay conjeturas disponibles para n<28.^[14]​
   

  El empaque óptimo de 15 círculos en un cuadrado.

Empaquetado de cuadrados

Dados n cuadrados unitarios, se debe empacarlos en el contenedor más pequeño posible, donde el tipo de contenedor varía:

• Empaquetar cuadrados en un cuadrado: Se han demostrado soluciones óptimas para n  = 1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100 y cualquier número entero cuadrado. El espacio desperdiciado es asintóticamente O(a^7/11).
• Empaquetar cuadrados en un círculo: se conocen buenas soluciones para n hasta 35.
   

  El empaque óptimo de 10 cuadrados en un cuadrado.

Empaquetado de rectángulos

• Empaquetado de rectángulos idénticos en un rectángulo: el problema de empaquetar múltiples instancias de un solo rectángulo de tamaño (l,w), permitiendo una rotación de 90°, en un rectángulo más grande de tamaño (L,W) tiene algunas aplicaciones como la carga de cajas sobre palés y, en concreto, estiba de celulosa. Por ejemplo, es posible empaquetar 147 rectángulos de tamaño (137,95) en un rectángulo de tamaño (1600,1230).
• Empaquetar diferentes rectángulos en un rectángulo: el problema de empaquetar múltiples rectángulos de diferentes anchos y alturas en un rectángulo circundante de área mínima (pero sin límites en el ancho o alto del rectángulo circundante) tiene una aplicación importante en la combinación de imágenes en una sola imagen más grande . Una página web que carga una sola imagen más grande a menudo se procesa más rápido en el navegador que la misma página que carga varias imágenes pequeñas, debido a la sobrecarga que implica solicitar cada imagen del servidor web. El problema es NP-completo en general, pero existen algoritmos rápidos para resolver instancias pequeñas.

Campos relacionados

En los problemas de mosaico o teselado, no debe haber espacios ni superposiciones. Muchos de los acertijos de este tipo implican empaquetar rectángulos o poliominós en un rectángulo más grande u otra forma cuadrada.

Existen teoremas importantes sobre el mosaico de rectángulos (y cuboides) en rectángulos (cuboides) sin espacios ni superposiciones:

• Un rectángulo de a × b puede ser embalado con 1 × n tiras si y sólo si n divide a o n divide b.^[15]​^[16]​
• Teorema de Bruijn: Una caja se puede empaquetar con un ladrillo armónico a × ab × abc si la caja tiene dimensiones ap × abq × abcr para algunos números naturales p, q, r (es decir, la caja es un múltiplo del ladrillo)^[15]​

El estudio de los mosaicos de poliominó se refiere en gran medida a dos clases de problemas: enlosar un rectángulo con mosaicos congruentes y empaquetar uno de cada n -omino en un rectángulo.

Un rompecabezas clásico del segundo tipo consiste en organizar los doce pentominós en rectángulos de tamaño 3×20, 4×15, 5×12 o 6×10.

Empaquetado de objetos irregulares

El empaquetado de objetos irregulares es un problema que no se presta bien a soluciones de forma cerrada; sin embargo, la aplicabilidad a la ciencia ambiental práctica es bastante importante. Por ejemplo, las partículas de suelo de forma irregular se empaquetan de manera diferente a medida que varían los tamaños y las formas, lo que genera resultados importantes para que las especies de plantas adapten las formaciones de raíces y permitan el movimiento del agua en el suelo.^[17]​

Se ha demostrado que el problema de decidir si un conjunto dado de polígonos cabe en un contenedor cuadrado dado es completo para la teoría existencial de los reales.^[18]​

Véase también

• Set packing
• Rompecabezas de Slothouber-Graatsma
• Rompecabezas de Conway
• Tetris
• Problema de cobertura (combinatoria)
• Problema de la mochila
• Problema de corte de valores
• Número de osculación
• Empaquetamiento compacto
• Empaquetamiento aleatorio

Referencias

1. Lodi, Andrea; Martello, Silvano; Monaci, Michele (1 de septiembre de 2002). «Two-dimensional packing problems: A survey». European Journal of Operational Research (en inglés) 141 (2): 241-252. ISSN 0377-2217. doi:10.1016/S0377-2217(02)00123-6. Consultado el 16 de febrero de 2021. 
2. Donev, Aleksandar; Stillinger, Frank H.; Chaikin, P. M.; Torquato, Salvatore (23 de junio de 2004). «Unusually Dense Crystal Packings of Ellipsoids». Physical Review Letters 92 (25): 255506. doi:10.1103/PhysRevLett.92.255506. Consultado el 16 de febrero de 2021. 
3. Torquato, S.; Jiao, Y. (2009-08). «Dense packings of the Platonic and Archimedean solids». Nature (en inglés) 460 (7257): 876-879. ISSN 1476-4687. doi:10.1038/nature08239. Consultado el 16 de febrero de 2021. 
4. Haji-Akbari, Amir; Engel, Michael; Keys, Aaron S.; Zheng, Xiaoyu; Petschek, Rolfe G.; Palffy-Muhoray, Peter; Glotzer, Sharon C. (2009-12). «Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra». Nature (en inglés) 462 (7274): 773-777. ISSN 1476-4687. doi:10.1038/nature08641. Consultado el 16 de febrero de 2021. 
5. Chen, Elizabeth R.; Engel, Michael; Glotzer, Sharon C. (1 de septiembre de 2010). «Dense Crystalline Dimer Packings of Regular Tetrahedra». Discrete & Computational Geometry (en inglés) 44 (2): 253-280. ISSN 1432-0444. doi:10.1007/s00454-010-9273-0. Consultado el 16 de febrero de 2021. 
6. Gale, David, ed. (1998). Tracking the Automatic ANT (en inglés británico). doi:10.1007/978-1-4612-2192-0. Consultado el 16 de febrero de 2021. 
7. Hudson, Toby S; Harrowell, Peter (27 de abril de 2011). «Structural searches using isopointal sets as generators: densest packings for binary hard sphere mixtures». Journal of Physics: Condensed Matter (en inglés) 23 (19): 194103. ISSN 0953-8984. doi:10.1088/0953-8984/23/19/194103. Consultado el 16 de febrero de 2021. 
8. Weisstein, Eric W. «Circle Packing». mathworld.wolfram.com (en inglés). Consultado el 16 de febrero de 2021. 
9. Smalley, Ian (1 de noviembre de 1963). «Simple Regular Sphere Packings in Three Dimensions». Mathematics Magazine 36 (5): 295-299. ISSN 0025-570X. doi:10.1080/0025570X.1963.11975458. Consultado el 16 de febrero de 2021. 
10. «Densest lattice packings of 3-polytopes». Computational Geometry (en inglés) 16 (3): 157-186. 1 de julio de 2000. ISSN 0925-7721. doi:10.1016/S0925-7721(00)00007-9. Consultado el 16 de febrero de 2021. 
11. Minkowski, H. Dichteste gitterfo¨rmige Lagerung kongruenter Ko¨rper. Nachr. Akad. Wiss. Go¨ttingen Math. Phys. KI. II 311–355 (1904).
12. Stoyan, Yu G.; Yaskov, G. N. (2010). «Packing identical spheres into a cylinder». International Transactions in Operational Research (en inglés) 17 (1): 51-70. ISSN 1475-3995. doi:10.1111/j.1475-3995.2009.00733.x. Consultado el 16 de febrero de 2021. 
13. Teich, Erin G.; Anders, Greg van; Klotsa, Daphne; Dshemuchadse, Julia; Glotzer, Sharon C. (9 de febrero de 2016). «Clusters of polyhedra in spherical confinement». Proceedings of the National Academy of Sciences (en inglés) 113 (6): E669-E678. ISSN 0027-8424. PMID 26811458. doi:10.1073/pnas.1524875113. Consultado el 16 de febrero de 2021. 
14. Melissen, J. B. M.; Schuur, P. C. (13 de octubre de 1995). «Packing 16, 17 or 18 circles in an equilateral triangle». Discrete Mathematics (en inglés) 145 (1): 333-342. ISSN 0012-365X. doi:10.1016/0012-365X(95)90139-C. Consultado el 16 de febrero de 2021. 
15. Honsberger, Ross (<©1976>). Mathematical gems. Mathematical Association of America. ISBN 0-88385-300-0. OCLC 3017331. Consultado el 16 de febrero de 2021. 
16. Klarner, D. A.; Hautus, M. L. J. (1971). «Uniformly Coloured Stained Glass Windows». Proceedings of the London Mathematical Society (en inglés). s3-23 (4): 613-628. ISSN 1460-244X. doi:10.1112/plms/s3-23.4.613. Consultado el 16 de febrero de 2021. 
17. C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC
18. Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), Framework for ${\displaystyle \exists \mathbb {R} }$ -Completeness of Two-Dimensional Packing Problems, arXiv:2004.07558 ..

Fuentes

• Weisstein, Eric W. «Klarner's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «de Bruijn's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

Enlaces externos

•   Wikimedia Commons alberga una categoría multimedia sobre Problema de empaquetado.

En inglés:

• Optimización del embalaje de contenedores tridimensionales
• API para empaquetado 3D
• Erich's Packing Center
• www.packomania.com
• "Box Packing" por Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.
• Empaquetaduras más conocidas de círculos iguales en un círculo, hasta 1100
• Problema de desafío de empaquetado de círculos en Python