Problemas de embalaje

Problemas que intentan encontrar la forma más eficiente de empaquetar objetos en contenedores.

Esferas o círculos agrupados de forma suelta (arriba) y más densa (abajo)

Los problemas de empaquetado son una clase de problemas de optimización en matemáticas que implican intentar empacar objetos juntos en contenedores. El objetivo es empacar un solo contenedor lo más densamente posible o empacar todos los objetos usando la menor cantidad de contenedores posible. Muchos de estos problemas pueden estar relacionados con problemas de empaquetado , almacenamiento y transporte de la vida real . Cada problema de empaquetado tiene un problema de doble cobertura , que pregunta cuántos objetos iguales se requieren para cubrir por completo cada región del contenedor, donde se permite que los objetos se superpongan.

En un problema de empaquetado de contenedores , a las personas se les da:

• Un contenedor , generalmente una región convexa bidimensional o tridimensional , posiblemente de tamaño infinito. Se pueden proporcionar múltiples contenedores según el problema.
• Conjunto de objetos , algunos de los cuales o todos ellos deben empaquetarse en uno o más contenedores. El conjunto puede contener distintos objetos con tamaños especificados o un único objeto de una dimensión fija que puede usarse repetidamente.

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

Embalaje en 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 tan densamente como sea posible en el 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 empaquetar esferas cientos de años antes de que Thomas Callister Hales demostrara que era correcta . Muchas otras formas han recibido atención, incluidos los elipsoides, ^{[2] los sólidos} platónicos y arquimedianos ^[3] incluidos los tetraedros , ^{[4] [5]} los trípodes (uniones de cubos a lo largo de tres rayos positivos paralelos al eje), ^[6] y los dímeros de esferas desiguales. ^[7]

Empaquetamiento 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 de empaquetamiento de círculos . El problema de empaquetamiento de círculos relacionado trata del empaquetamiento de círculos , posiblemente de diferentes tamaños, sobre una superficie, por ejemplo, el plano o una esfera .

Los equivalentes de un círculo en otras dimensiones nunca pueden empaquetarse con total eficiencia en dimensiones mayores que una (en un universo unidimensional, el análogo del círculo son solo dos puntos). Es decir, siempre habrá espacio sin usar si la gente solo empaqueta círculos. La forma más eficiente de empaquetar círculos, el empaquetamiento hexagonal , produce aproximadamente un 91% de eficiencia. ^[8]

Empaquetaduras de esferas en dimensiones superiores

En tres dimensiones, las estructuras compactas ofrecen el mejor empaquetamiento reticular de esferas y se cree que es el óptimo de todos los empaquetamientos. Con empaquetamientos de esferas "simples" en tres dimensiones (el término "simple" se define con cuidado) hay nueve empaquetamientos definibles posibles. ^{[9] También se ha demostrado que la} red E8 de 8 dimensiones y la red Leech de 24 dimensiones son óptimas en sus respectivos espacios dimensionales reales.

Empaquetamientos de sólidos platónicos en tres dimensiones

Los cubos se pueden organizar fácilmente para llenar por completo el espacio tridimensional, siendo el empaquetamiento más natural el de panal cúbico . Ningún otro sólido platónico puede rellenar el espacio por sí solo, pero se conocen algunos resultados preliminares. Los tetraedros pueden lograr un empaquetamiento de al menos el 85%. Uno de los mejores empaquetamientos de dodecaedros regulares se basa en la red cúbica centrada en las caras (FCC) antes mencionada.

Los tetraedros y octaedros juntos pueden llenar todo el espacio en una disposición conocida como panal tetraédrico-octaédrico .

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

Embalaje en contenedores tridimensionales

Empaquetado de nueve tricubos L en un cubo

Diferentes cuboides en un cuboide

Determinar la cantidad mínima de contenedores cuboides (bins) que se requieren para embalar un conjunto determinado de cuboides de artículos. Los cuboides rectangulares que se van a embalar 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 k bolas unitarias abiertas disjuntas puedan empaquetarse dentro de ella tiene una respuesta simple y completa en el espacio euclidiano de n dimensiones si , 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, está disponible una configuración de k bolas unitarias tangentes por pares . Las personas colocan los centros en los vértices de un símplex de dimensión regular con arista 2; esto se realiza fácilmente comenzando desde una base ortonormal . Un pequeño cálculo muestra que la distancia de cada vértice desde el baricentro es . Además, cualquier otro punto del espacio necesariamente tiene una distancia mayor desde al menos uno de los k vértices. En términos de inclusiones de bolas, las k bolas unitarias abiertas centradas en están incluidas en una bola de radio , que es mínimo para esta configuración. ${\displaystyle k\leq n+1}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\displaystyle (k-1)}$ ${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$

Para demostrar que esta configuración es óptima, sean los centros de k bolas unitarias abiertas disjuntas contenidas en una bola de radio r centrada en un punto . Considérese la función del conjunto finito en tomando en cuenta el correspondiente para cada . Puesto que para todo , esta función es 1- Lipschitz y por el teorema de Kirszbraun se extiende a una función 1-Lipschitz que está definida globalmente; en particular, existe un punto tal que para todo se tiene , de modo que también . Esto demuestra que hay k bolas unitarias abiertas disjuntas en una bola de radio r si y solo si . Nótese 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 r si y solo si . Por ejemplo, las bolas unitarias centradas en , donde es una base ortonormal, son disjuntas e incluidas en una bola de radio centrada en el origen. Además, para , el número máximo de bolas unitarias abiertas disjuntas dentro de una bola de radio r es . ${\displaystyle x_{1},\dots ,x_{k}}$ ${\displaystyle x_{0}}$ ${\displaystyle \{x_{1},\dots ,x_{k}\}}$ ${\displaystyle \{a_{1},\dots ,a_{k}\}}$ ${\displaystyle x_{j}}$ ${\displaystyle a_{j}}$ ${\displaystyle 1\leq j\leq k}$ ${\displaystyle 1\leq i<j\leq k}$ ${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$ ${\displaystyle a_{0}}$ ${\displaystyle 1\leq j\leq k}$ ${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$ ${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$ ${\displaystyle r\geq r_{k}}$ ${\displaystyle r\geq 1+{\sqrt {2}}}$ ${\displaystyle {\sqrt {2}}e_{j}}$ ${\displaystyle \{e_{j}\}_{j}}$ ${\displaystyle 1+{\sqrt {2}}}$ ${\displaystyle r<1+{\sqrt {2}}}$ ${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$

Esferas en un cuboide

La gente determina la cantidad de objetos esféricos de un diámetro dado d que se pueden empaquetar en un cuboide de tamaño . ${\displaystyle a\times b\times c}$

Esferas idénticas en un cilindro

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

Poliedros en esferas

La gente determina el radio mínimo R que permitirá empaquetar n poliedros idénticos de volumen unitario de una forma dada. ^[13]

Embalaje en contenedores bidimensionales

El empaquetamiento óptimo de 10 círculos en un círculo

Se han estudiado muchas variantes de problemas de empaquetamiento bidimensional.

Empaquetado de círculos

A las personas se les dan n círculos unitarios y deben colocarlos en el recipiente más pequeño posible. Se han estudiado varios tipos de recipientes:

• Empaquetamiento de círculos en un círculo : estrechamente relacionado con la dispersión de puntos en un círculo unitario con el objetivo de encontrar la mayor separación mínima, d _n , entre puntos. Se han demostrado soluciones óptimas para n ≤ 13 y n = 19 .
• Empaquetamiento de círculos en un cuadrado : estrechamente relacionado con la distribución de puntos 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á . ${\displaystyle L=2+2/d_{n}}$

  

  El empaquetamiento óptimo de 15 círculos en un cuadrado

  Se han demostrado soluciones óptimas para n ≤ 30 .
• Empaquetar círculos en un rectángulo
• Círculos de empaquetamiento en un triángulo rectángulo isósceles : se conocen buenas estimaciones para n < 300 .
• Empaquetamiento de círculos en un triángulo equilátero : se conocen soluciones óptimas para n < 13 y hay conjeturas disponibles para n < 28. [ ^14]

Embalaje de cuadrados

A las personas se les dan n unidades cuadradas y tienen que empaquetarlas en el contenedor más pequeño posible, donde el tipo de contenedor varía:

• Empaquetamiento de cuadrados en un cuadrado : Se han demostrado soluciones óptimas para n de 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 y cualquier entero cuadrado . El espacio desperdiciado es asintóticamente O ( a ^3/5 ) .
• Empaquetamiento de cuadrados en un círculo : Se conocen buenas soluciones para n ≤ 35 .

  

  El empaquetamiento ó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 único 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 en palés y, específicamente, el almacenamiento de pulpa de madera . Por ejemplo, es posible empaquetar 147 rectángulos de tamaño (137,95) en un rectángulo de tamaño (1600,1230).
• Empaquetado de diferentes rectángulos en un rectángulo : el problema de empaquetar múltiples rectángulos de diferentes anchos y alturas en un rectángulo envolvente de área mínima (pero sin límites en el ancho o la altura del rectángulo envolvente) 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 múltiples imágenes pequeñas, debido a la sobrecarga que implica solicitar cada imagen al 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 teselación o mosaico , no debe haber espacios vacíos ni superposiciones. Muchos de los acertijos de este tipo implican agrupar rectángulos o poliominós en un rectángulo más grande u otra forma similar a un cuadrado.

Existen teoremas importantes sobre la colocación de rectángulos (y cuboides) en rectángulos (cuboides) sin espacios ni superposiciones:

Un rectángulo a × b se puede rellenar con tiras de 1 × n si y solo si n divide a a o n divide a b . ^{[15] [16]}

Teorema de De Bruijn : Una caja puede llenarse 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 teselados de poliominós se ocupa en gran medida de dos clases de problemas: teselar un rectángulo con teselas congruentes y empaquetar uno de cada n -ominó en un rectángulo.

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

Embalaje de objetos irregulares

El empaquetamiento de objetos irregulares es un problema que no se presta bien a soluciones de forma cerrada; sin embargo, su 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 vegetales adapten las formaciones de las 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 puede caber en un contenedor cuadrado dado es completo para la teoría existencial de los reales . ^[18]

Véase también

• Problema de embalaje del contenedor
• Empaquetamiento compacto de esferas iguales
• Rompecabezas de Conway
• Problema de cobertura
• Problema de corte de stock
• Empaquetamiento de elipsoides
• Problema del número del beso
• Problema de la mochila
• Paquete cerrado aleatorio
• Conjunto de embalaje
• Rompecabezas de Slothouber-Graatsma
• Problema de empaquetamiento de tiras
• Empaquetamiento tetraédrico
• Tetris

Notas

1. Lodi, A.; Martello, S.; Monaci, M. (2002). "Problemas de empaquetamiento bidimensional: una encuesta". Revista Europea de Investigación Operativa . 141 (2). Elsevier: 241–252. doi :10.1016/s0377-2217(02)00123-6.
2. Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). "Empaquetamientos cristalinos inusualmente densos de elipsoides". Physical Review Letters . 92 (25): 255506. arXiv : cond-mat/0403286 . Código Bibliográfico :2004PhRvL..92y5506D. doi :10.1103/PhysRevLett.92.255506. PMID  15245027. S2CID  7982407.
3. Torquato, S.; Jiao, Y. (agosto de 2009). "Empaquetamientos densos de los sólidos platónicos y arquimedianos". Nature . 460 (7257): 876–879. arXiv : 0908.4107 . Bibcode :2009Natur.460..876T. doi :10.1038/nature08239. ISSN  0028-0836. PMID  19675649. S2CID  52819935.
4. Haji-Akbari, A.; Engel, M.; Keys, AS; Zheng, X.; Petschek, RG; Palffy-Muhoray, P.; Glotzer, SC (2009). "Fases desordenadas, cuasicristalinas y cristalinas de tetraedros densamente empaquetados". Nature . 462 (7274): 773–777. arXiv : 1012.5138 . Bibcode :2009Natur.462..773H. doi :10.1038/nature08641. PMID  20010683. S2CID  4412674.
5. Chen, ER; Engel, M.; Glotzer, SC (2010). "Empaquetamientos densos de dímeros cristalinos de tetraedros regulares". Geometría discreta y computacional . 44 (2): 253–280. arXiv : 1001.0586 . Código Bibliográfico :2010arXiv1001.0586C. doi : 10.1007/s00454-010-9273-0 . S2CID  18523116.
6. Stein, Sherman K. (marzo de 1995), "Empaquetado de trípodes", Entretenimientos matemáticos, The Mathematical Intelligencer , 17 (2): 37–39, doi :10.1007/bf03024896, S2CID  124703268. Reimpreso en Gale, David (1998), Gale, David (ed.), Tracking the Automatic ANT , Springer-Verlag, págs. 131-136, doi :10.1007/978-1-4612-2192-0, ISBN 0-387-98272-8, Sr.  1661863
7. Hudson, TS; Harrowell, P. (2011). "Búsquedas estructurales utilizando conjuntos isopuntuales como generadores: empaquetamientos más densos para mezclas binarias de esferas duras". Journal of Physics: Condensed Matter . 23 (19): 194103. Bibcode :2011JPCM...23s4103H. doi :10.1088/0953-8984/23/19/194103. PMID  21525553. S2CID  25505460.
8. "Embalaje circular".
9. Smalley, IJ (1963). "Empaquetamientos esféricos regulares simples en tres dimensiones". Revista de Matemáticas . 36 (5): 295–299. doi :10.2307/2688954. JSTOR  2688954.
10. Betke, Ulrich; Henk, Martin (2000). "Empaquetamientos reticulares más densos de 3-politopos". Geometría computacional . 16 (3): 157–186. arXiv : math/9909172 . doi : 10.1016/S0925-7721(00)00007-9 . MR  1765181. S2CID  12118403.
11. Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akád. Wiss. Matemáticas de Gotinga. Física. KI. II 311–355 (1904).
12. Stoyan, YG; Yaskov, GN (2010). "Empaquetado de esferas idénticas en un cilindro". International Transactions in Operational Research . 17 : 51–70. doi :10.1111/j.1475-3995.2009.00733.x.
13. Teich, EG; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, SC (2016). "Cúmulos de poliedros en confinamiento esférico". Proc. Natl. Sci. USA . 113 (6): E669–E678. Bibcode :2016PNAS..113E.669T. doi : 10.1073/pnas.1524875113 . PMC 4760782 . PMID  26811458. 
14. Melissen, J. (1995). "Empaquetado de 16, 17 o 18 círculos en un triángulo equilátero". Matemáticas discretas . 145 (1–3): 333–342. doi : 10.1016/0012-365X(95)90139-C .
15. Honsberger, Ross (1976). Gemas matemáticas II . Asociación Matemática de Estados Unidos . pág. 67. ISBN 0-88385-302-7.
16. Klarner, DA ; Hautus, MLJ (1971). "Vidrieras de colores uniformes". Actas de la London Mathematical Society . 3. 23 (4): 613–628. doi :10.1112/plms/s3-23.4.613.
17. C. Michael Hogan. 2010. Factor abiótico. Enciclopedia de la Tierra. eds. Emily Monosson y C. Cleveland. Consejo Nacional para la Ciencia y el Medio Ambiente. Washington DC.
18. Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), Marco para la completitud de problemas de empaquetamiento bidimensional , arXiv : 2004.07558 ${\displaystyle \exists \mathbb {R} }$.

Referencias

• Weisstein, Eric W. "Teorema de Klarner". MundoMatemático .
• Weisstein, Eric W. "Teorema de de Bruijn". MundoMatemático .

Enlaces externos

• Optimización del embalaje tridimensional de contenedores

Muchos libros de acertijos, así como revistas matemáticas, contienen artículos sobre problemas de empaquetado.

• Enlaces a varios artículos de MathWorld sobre embalaje
• Notas de MathWorld sobre el empaquetado de cuadrados.
• Centro de embalaje de Erich
• www.packomania.com Un sitio con tablas, gráficos, calculadoras, referencias, etc.
• "Box Packing" de Ed Pegg, Jr. , Proyecto de Demostraciones Wolfram , 2007.
• Empaquetamientos más conocidos de círculos iguales en un círculo, hasta 1100

• Problema de desafío de empaquetamiento circular en Python