Problemas de embalaje

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

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

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 problemas de embalaje , almacenamiento y transporte de la vida real . Cada problema de embalaje tiene un problema de cobertura dual , que pregunta cuántos objetos iguales se necesitan para cubrir completamente cada región del contenedor, donde se permite que los objetos se superpongan.

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

• Un contenedor , generalmente una región convexa bidimensional o tridimensional , posiblemente de tamaño infinito. Se pueden dar varios contenedores según el problema.
• 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 único objeto de una dimensión fija que se puede utilizar repetidamente.

Por lo general, el embalaje debe realizarse sin superposiciones entre la mercancía y otras mercancías o las paredes del contenedor. En algunas variantes, el objetivo es encontrar la configuración que empaquete un solo contenedor con la máxima densidad de embalaje . 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.

Empacar en el espacio infinito

Muchos de estos problemas, cuando se aumenta el tamaño del contenedor en todas direcciones, se vuelven equivalentes al problema de empaquetar objetos lo más densamente posible en el espacio euclidiano infinito . Este problema es relevante para varias disciplinas científicas y ha recibido mucha atención. 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] 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 esferas desiguales. dímeros. ^[7]

Embalaje 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 empaquetado circular . El problema de empaquetamiento de círculos relacionado se ocupa 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 que uno (en un universo unidimensional, el círculo análogo son solo dos puntos). Es decir, siempre habrá espacio no utilizado si la gente sólo hace 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

En tres dimensiones, las estructuras compactas ofrecen el mejor empaquetamiento reticular de esferas y se cree que son el óptimo de todos los empaquetamientos. Con empaquetaduras esféricas "simples" en tres dimensiones (definiéndose cuidadosamente "simples") hay nueve empaquetaduras posibles definibles. ^{[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.

Empaques de sólidos platónicos en tres dimensiones.

Los cubos se pueden organizar fácilmente para llenar completamente el espacio tridimensional; el embalaje más natural es el panal cúbico . Ningún otro sólido platónico puede revestir el espacio por sí solo, pero se conocen algunos resultados preliminares. Los tetraedros pueden alcanzar 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

Diferentes cuboides en un cuboide

Determine la cantidad mínima de contenedores cuboides (contenedores) que se requieren para empacar un conjunto determinado de cuboides de artículos. Los cuboides rectangulares 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 k bolas unitarias abiertas disjuntas puedan empaquetarse en su interior tiene una respuesta simple y completa en un 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 . La gente coloca los centros en los vértices de un simplex de dimensión regular con arista 2; esto se logra fácilmente partiendo de una base ortonormal . Un pequeño cálculo muestra que la distancia de cada vértice al baricentro es . Además, cualquier otro punto del espacio necesariamente tiene una distancia mayor de al menos uno de los k vértices. En términos de inclusiones de bolas, las k bolas unitarias abiertas centradas en se incluyen 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 . Considere el mapa del conjunto finito y tome el correspondiente para cada uno . Dado que para todos , este mapa es 1- Lipschitz y según el teorema de Kirszbraun se extiende a un mapa de 1-Lipschitz que está definido globalmente; en particular, existe un punto tal que para todo uno tiene , de modo que también . Esto muestra que hay k bolas abiertas unitarias disjuntas en una bola de radio r si y solo si . 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 r si y solo si . Por ejemplo, las bolas unitarias centradas en , donde es una base ortonormal, son disjuntas y están 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 empaquetará 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

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

Embalaje en contenedores bidimensionales

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

Se han estudiado muchas variantes de problemas de empaquetamiento bidimensionales.

Embalaje de círculos

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

• Empacar 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 separación mínima más grande, d _n , entre puntos. Se han demostrado soluciones óptimas para n ≤ 13 y n = 19 .
• Empaquetar círculos en un cuadrado : estrechamente relacionado con los puntos de dispersión en un cuadrado unitario con el objetivo de encontrar la separación mínima más grande, d _n , entre puntos. Para convertir entre estas dos formulaciones del problema, el lado del cuadrado de los círculos unitarios será . ${\displaystyle L=2+2/d_{n}}$

  

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

  Se han probado soluciones óptimas para n ≤ 30 .
• Empacar círculos en un rectángulo
• Círculos de embalaje en un triángulo rectángulo isósceles : se conocen buenas estimaciones para n <300 .
• Círculos empaquetados 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 cuadrados unitarios y deben 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 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 ( un ^7/11 ) .
• Empacar cuadrados en un círculo : Se conocen buenas soluciones para n ≤ 35 .

  

  El embalaje óptimo de 10 cuadrados en un cuadrado.

Embalaje de rectángulos

• Empacar 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, la estiba de pasta de madera . 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 al combinar imágenes en una sola imagen más grande. . Una página web que carga una sola imagen más grande a menudo se muestra 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 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 mosaico o teselación , 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 similar a un cuadrado.

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

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

Teorema de 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 poliomino se refiere en gran medida a dos clases de problemas: mosaico de 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.

Embalaje de objetos irregulares.

El embalaje de objetos irregulares es un problema que no se adapta bien a soluciones de forma cerrada; sin embargo, la aplicabilidad a la ciencia ambiental práctica es bastante importante. Por ejemplo, las partículas del 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]

Ver también

• Problema de embalaje del contenedor
• Empaquetado cerrado de esferas iguales.
• rompecabezas de conway
• Problema de cobertura
• Problema de corte de stock
• embalaje elipsoide
• problema del numero de besos
• problema de mochila
• Paquete cerrado aleatorio
• Establecer embalaje
• Rompecabezas Slothouber-Graatsma
• Problema de embalaje de tiras
• embalaje tetraédrico
• Tetris

Notas

1. Lodi, A.; Martello, S.; Monaci, M. (2002). "Problemas de embalaje bidimensional: una encuesta". Revista europea de investigación operativa . Elsevier. 141 (2): 241–252. doi :10.1016/s0377-2217(02)00123-6.
2. Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). "Empaquetaduras de elipsoides de cristal inusualmente densos". Cartas de revisión física . 92 (25): 255506. arXiv : cond-mat/0403286 . Código Bib : 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 de Arquímedes". Naturaleza . 460 (7257): 876–879. arXiv : 0908.4107 . Código Bib :2009Natur.460..876T. doi : 10.1038/naturaleza08239. ISSN  0028-0836. PMID  19675649. S2CID  52819935.
4. Haji-Akbari, A.; Engel, M.; Claves, COMO; Zheng, X.; Petschek, RG; Palffy-Muhoray, P.; Glotzer, Carolina del Sur (2009). "Fases desordenadas, cuasicristalinas y cristalinas de tetraedros densamente empaquetados". Naturaleza . 462 (7274): 773–777. arXiv : 1012.5138 . Código Bib :2009Natur.462..773H. doi : 10.1038/naturaleza08641. PMID  20010683. S2CID  4412674.
5. Chen, emergencias; Engel, M.; Glotzer, Carolina del Sur (2010). "Empaquetaduras de dímeros cristalinos densos de tetraedros regulares". Geometría discreta y computacional . 44 (2): 253–280. arXiv : 1001.0586 . Código Bib : 2010arXiv1001.0586C. doi : 10.1007/s00454-010-9273-0 . S2CID  18523116.
6. Stein, Sherman K. (marzo de 1995), "Empacar 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, señor  1661863
7. Hudson, TS; Harrowell, P. (2011). "Búsquedas estructurales utilizando conjuntos isopointales como generadores: empaquetamientos más densos para mezclas binarias de esferas duras". Revista de Física: Materia Condensada . 23 (19): 194103. Código bibliográfico : 2011JPCM...23s4103H. doi :10.1088/0953-8984/23/19/194103. PMID  21525553. S2CID  25505460.
8. "Embalaje circular".
9. Smalley, IJ (1963). "Empaquetaduras de esferas regulares simples en tres dimensiones". Revista Matemáticas . 36 (5): 295–299. doi :10.2307/2688954. JSTOR  2688954.
10. Betke, Ulrich; Henk, Martín (2000). "Empaquetamientos de celosía más densos de 3 politopos". Geometría Computacional . 16 (3): 157–186. arXiv : matemáticas/9909172 . doi : 10.1016/S0925-7721(00)00007-9 . SEÑOR  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). "Empacar esferas idénticas en un cilindro". Transacciones Internacionales en Investigación Operativa . 17 : 51–70. doi :10.1111/j.1475-3995.2009.00733.x.
13. Teich, por ejemplo; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, Carolina del Sur (2016). "Grupos de poliedros en confinamiento esférico". Proc. Nacional. Acad. Ciencia. EE.UU . 113 (6): E669-E678. Código Bib : 2016PNAS..113E.669T. doi : 10.1073/pnas.1524875113 . PMC 4760782 . PMID  26811458. 
14. Melissen, J. (1995). "Empacar 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 . La Asociación Matemática de América . pag. 67.ISBN​ 0-88385-302-7.
16. Klarner, DA ; Hautus, MLJ (1971). "Vidrieras de colores uniformes". Actas de la Sociedad Matemática de Londres . 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. editores 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 integridad de problemas de embalaje bidimensionales , 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 de contenedores tridimensionales

Muchos libros de acertijos y revistas de matemáticas contienen artículos sobre problemas de embalaje.

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

• Problema del desafío del embalaje circular en Python