Los problemas de empaque 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 de embalaje , almacenamiento y transporte de la vida real . 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 se permite que los objetos se superpongan.
En un problema de embalaje en un contenedor , se le 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.
Embalaje 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 ejes positivos-rayos paralelos), [6] y esferas desiguales. dímeros. [7]
Embalaje hexagonal de círculos
Estos problemas son matemáticamente distintos de las ideas del teorema del empaquetamiento de círculos . El relacionada embalaje círculo ofertas de problemas con los círculos de embalaje, 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
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 sus respectivos espacios dimensionales reales.
Envases 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. Tetrahedra puede lograr un empaquetamiento 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 empaquetamiento de celosía |
---|---|
icosaedro | 0,836357 ... [10] |
dodecaedro | (5 + √ 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
Determine el número mínimo de contenedores cuboides (contenedores) que se requieren para empacar un conjunto dado de cuboides de artículos (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 Las bolas separadas de la unidad abierta se pueden empaquetar en su interior tiene una respuesta simple y completa en -espacio euclidiano dimensional 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, una configuración deHay disponibles bolas unitarias tangentes por pares. Coloca los centros en los vértices de un regular 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. Además, cualquier otro punto del espacio tiene necesariamente una mayor distancia de al menos uno de losvértices. En términos de inclusiones de bolas, la bolas unitarias abiertas centradas en están incluidos en una bola de radio , que es mínimo para esta configuración.
Para demostrar que esta configuración es óptima, dejemos ser los centros de bolas unitarias abiertas disjuntas contenidas en una bola de radio centrado en un punto . Considere el mapa del conjunto finito dentro tomando en el correspondiente para cada . Ya que para todos, 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 tal que para todos uno tiene , para que también . Esto muestra que hay unidad disjunta bolas abiertas en una bola de radio 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 si y solo si . Por ejemplo, las bolas unitarias centradas en, dónde es una base ortonormal, son disjuntos y se incluyen en una bola de radio centrado en el origen. Además, para, el número máximo de bolas unitarias abiertas disjuntas dentro de una bola de radio r es .
Esferas en un cuboide
Determine 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
Determine 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
Determine el radio mínimo R que empacará n poliedros de volumen unitario idénticos de una forma dada. [13]
Embalaje en contenedores bidimensionales
Se han estudiado muchas variantes de problemas de empaquetamiento bidimensional. Consulte las páginas vinculadas para obtener más información.
Embalaje de círculos
Se le dan n círculos unitarios y debe empacarlos en el recipiente más pequeño posible. Se han estudiado varios tipos de envases:
- Círculos de empaque 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 de empaque 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 de empaque en un triángulo rectángulo isósceles : se conocen buenas estimaciones para n <300.
- Círculos de empaque en un triángulo equilátero : se conocen soluciones óptimas para n <13, y hay conjeturas disponibles para n <28. [14]
Embalaje de cuadrados
Se le dan n cuadrados unitarios y 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 ( un 7/11 ).
- Empaquetar cuadrados en un círculo : se conocen buenas soluciones para n hasta 35.
Embalaje 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).
- 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 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 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 cuadrada.
Existen teoremas importantes sobre el mosaico de rectángulos (y cuboides) en rectángulos (cuboides) sin espacios ni superposiciones:
- Una un × b rectángulo puede ser embalado con 1 × n tiras si y sólo si n divide una 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 poliomino 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.
Embalaje de objetos irregulares
El embalaje 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 formas, lo que lleva a 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 puede caber en un contenedor cuadrado dado es completo para la teoría existencial de los reales . [18]
Ver también
- Establecer embalaje
- Problema de embalaje del contenedor
- Rompecabezas de Slothouber-Graatsma
- Rompecabezas de Conway
- Tetris
- Cubriendo el problema
- Problema de la mochila
- Empaquetadura de tetraedro
- Empaquetadura elipsoide
- Problema de stock de corte
- Problema de número de besos
- Empaquetado cerrado de esferas iguales
- Paquete cerrado aleatorio
- Problema de empaque de bandas
Notas
- ^ 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 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Donev, A .; Stillinger, F .; Chaikin, P .; Torquato, S. (2004). "Empaquetaduras de cristal inusualmente densas de elipsoides". Cartas de revisión física . 92 (25): 255506. arXiv : cond-mat / 0403286 . Código Bibliográfico : 2004PhRvL..92y5506D . doi : 10.1103 / PhysRevLett.92.255506 . PMID 15245027 . S2CID 7982407 .
- ^ a b Torquato, S .; Jiao, Y. (agosto de 2009). "Empaquetaduras densas de los sólidos platónicos y de Arquímedes". Naturaleza . 460 (7257): 876–879. arXiv : 0908.4107 . Código bibliográfico : 2009Natur.460..876T . doi : 10.1038 / nature08239 . ISSN 0028-0836 . PMID 19675649 . S2CID 52819935 .
- ^ Haji-Akbari, A .; Engel, M .; Llaves, AS; 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 Bibliográfico : 2009Natur.462..773H . doi : 10.1038 / nature08641 . PMID 20010683 . S2CID 4412674 .
- ^ Chen, ER; Engel, M .; Glotzer, Carolina del Sur (2010). "Embalajes 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 .
- ^ Stein, Sherman K. (marzo de 1995), "Packing tripods", Mathematical Entertainment, 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, MR 1661863
- ^ Hudson, TS; Harrowell, P. (2011). "Búsquedas estructurales utilizando conjuntos isopointales como generadores: empaquetaduras más densas para mezclas de esferas duras binarias". 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 .
- ^ "Embalaje circular" .
- ^ Smalley, IJ (1963). "Empaquetaduras simples de esferas regulares en tres dimensiones". Revista de Matemáticas . 36 (5): 295–299. doi : 10.2307 / 2688954 . JSTOR 2688954 .
- ^ a b Betke, Ulrich; Henk, Martin (2000). "Empaquetaduras de celosía más densas 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 .
- ^ Minkowski, H. Dichteste gitterfo¨rmige Lagerung kongruenter Ko¨rper. Nachr. Akad. Wiss. Go¨ttingen Math. Phys. KI. II 311–355 (1904).
- ^ Stoyan, YG; Yaskov, GN (2010). "Empaquetando esferas idénticas en un cilindro". Transacciones internacionales en investigación operativa . 17 : 51–70. doi : 10.1111 / j.1475-3995.2009.00733.x .
- ^ Teich, EG; van Anders, G .; Klotsa, D .; Dshemuchadse, J .; Glotzer, Carolina del Sur (2016). "Racimos de poliedros en confinamiento esférico" . Proc. Natl. Acad. Sci. USA . 113 (6): E669 – E678. Código bibliográfico : 2016PNAS..113E.669T . doi : 10.1073 / pnas.1524875113 . PMC 4760782 . PMID 26811458 .
- ^ Melissen, J. (1995). "Empaquetando 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 .
- ^ a b Honsberger, Ross (1976). Gemas matemáticas II . La Asociación Matemática de América . pag. 67. ISBN 0-88385-302-7.
- ^ 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 .
- ^ C.Michael Hogan. 2010. Factor abiótico . Enciclopedia de la Tierra. eds Emily Monosson y C. Cleveland. Consejo Nacional de Ciencia y Medio Ambiente . Washington DC
- ^ Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), Marco para-Completidad de problemas de empaque bidimensional , arXiv : 2004.07558.
Referencias
- Weisstein, Eric W. "Teorema de Klarner" . MathWorld .
- Weisstein, Eric W. "Teorema de Bruijn" . MathWorld .
enlaces externos
- Optimización del embalaje de contenedores tridimensionales
- API para embalaje de contenedores 3D
- Embalaje de cajas y cilindros 3D con telescópico
Muchos libros de acertijos y revistas de matemáticas contienen artículos sobre problemas de empaque.
- Enlaces a varios artículos de MathWorld sobre empaque
- MathWorld notas 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. , el Proyecto de demostraciones de Wolfram , 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