Tareas de embalaje
Los problemas de empaquetamiento son una clase de problemas de optimización en matemáticas que intentan empaquetar objetos en contenedores. El objetivo de empacar es empacar un solo contenedor lo más apretado posible o empacar todos los objetos usando la menor cantidad de contenedores posible. Muchas de estas tareas pueden relacionarse con problemas de embalaje , almacenamiento y transporte de la vida real. Cada problema de empaque tiene un problema de doble cobertura que pregunta cuántos artículos se necesitan para cubrir completamente todas las áreas del contenedor, mientras que los artículos pueden superponerse.
El problema de empaque especifica:
- "contenedores" (generalmente una sola región convexa 2D o 3D o una región infinita)
- un conjunto de "objetos", algunos o todos los cuales deben ser empaquetados en uno o más contenedores. Un conjunto puede contener varios objetos con tamaños dados, o un solo objeto de tamaños fijos que se pueden usar varias veces.
Por lo general, en un paquete, los objetos no deben cruzarse y los objetos no deben cruzar las paredes del contenedor. En algunas realizaciones, el objetivo es encontrar una configuración que empaque un contenedor con la máxima densidad. De forma más general, el objetivo es empaquetar todos los objetos en el menor número posible de contenedores [1] . En algunas realizaciones, se permite la superposición (de objetos uno encima de otro y/o en los límites del contenedor), pero esta superposición debe minimizarse.
Embalaje de espacio infinito
Muchos de estos problemas, si el tamaño del contenedor aumenta en todas las direcciones, se vuelven equivalentes a los problemas de empaquetar objetos lo más densamente posible en un espacio euclidiano infinito . Este problema pertenece a varias disciplinas científicas y recibe una atención significativa. La conjetura de Kepler postuló una solución óptima para empaquetar bolas cientos de años antes de que Thomas Hales la probara . Otras formas han recibido atención, incluidos los elipsoides [2] , los sólidos platónicos y de Arquímedes [3] , incluidos los tetraedros [4] [5] y los dímeros de varias esferas [6] .
Empaquetamiento hexagonal de círculos
Estos problemas son matemáticamente diferentes de las ideas del teorema de empaquetamiento circular . Un problema de empaquetamiento de círculos relacionado se ocupa del empaquetamiento de círculos, posiblemente de varios tamaños, sobre una superficie, como un plano o una esfera.
Los análogos de un círculo en otras dimensiones no pueden empaquetarse con eficiencia absoluta en dimensiones mayores que 1 (en un espacio unidimensional, el análogo de un círculo son solo dos puntos). Así, siempre habrá espacio desocupado al empacar exclusivamente en círculos. La forma más eficiente de empaquetar círculos, el empaque hexagonal , tiene una eficiencia de alrededor del 91 % [7] .
Empaquetamiento de esferas en dimensiones superiores
En el espacio 3D, una red centrada en las caras proporciona un empaquetado óptimo de esferas. Se demuestra que la red E8 de 8 dimensiones y la red Leach de 24 dimensiones son óptimas en los espacios correspondientes.
Empaquetamiento de sólidos platónicos en tres dimensiones
Los cubos se pueden colocar fácilmente en el espacio 3D para que llenen completamente el espacio. El empaque más natural son los panales cúbicos . Ningún otro poliedro regular puede llenar el espacio por completo, pero se conocen algunos resultados. Un tetraedro puede dar al menos un 85% de empaquetamiento. Uno de los mejores empaques de dodecaedros regulares se basa en la red cúbica centrada en las caras antes mencionada.
Los tetraedros y los octaedros juntos pueden llenar todo el espacio en una configuración conocida como mosaico tetraédrico-octaédrico .
| Cuerpo | Densidad de empaquetamiento de celosía óptima |
|---|---|
| icosaedro | 0.836357… [8] |
| dodecaedros | [ocho] |
| octaedros | 18/19 = 0,947368… [9] |
El modelado que combina métodos de mejora local con empaques generados aleatoriamente sugiere que los empaques de celosía para el icosaedro, el dodecaedro y el octaedro también son óptimos en una clase más amplia de todos los empaques [3] .
Embalaje en contenedores 3D
Esferas en una esfera euclidiana
El problema de encontrar la bola más pequeña en la que se pueden empaquetar bolas unitarias abiertas sin superponerse tiene una respuesta simple y completa en el espacio euclidiano bidimensional si , y en el espacio de Hilbert de dimensión infinita - sin restricciones. Tiene sentido describirlo aquí para mostrar el problema general. En este caso, es posible la configuración de bolas unitarias que se tocan por pares. Colocamos los centros en los vértices de un símplex dimensional regular con borde 2. Esto es fácil de hacer, comenzando con una base ortonormal. Cálculos sencillos muestran que la distancia desde cualquier vértice al centro de gravedad es . Además, cualquier otro punto del espacio tiene una distancia mayor a por lo menos uno de los vértices. En términos de inclusión de bolas, las bolas unitarias abiertas centradas en los puntos , caen en una bola de radio , que es mínimo para tal configuración.
Para mostrar que tal configuración es óptima, supongamos que son los centros de bolas unitarias abiertas que no se intersecan ubicados en una bola con radio centrado en . Considere un mapeo de un conjunto finito que se mapea para todos . Dado que para todo , , este mapeo es 1-Lipschitz y, por el teorema de Kirschbrown , se extiende a un mapeo 1-Lipschitz globalmente definido. En particular, existe un punto tal que para todo lo que tenemos , y por lo tanto . Esto muestra que hay bolas abiertas unitarias que no se intersecan en una bola de radio si y solo si . Tenga en cuenta que en el caso de un espacio de Hilbert de dimensión infinita, esto implica la existencia de un número infinito de bolas abiertas unitarias que no se intersecan dentro de una bola de radio si y solo si . Por ejemplo, las bolas unitarias centradas en , donde es una base ortonormal, no se intersecan y están contenidas en una bola de radio centrada en el origen. Además, para el número máximo de bolas unitarias abiertas que no se cruzan dentro de una bola de radio r es igual a .
Esferas en un paralelepípedo
El problema determina el número de objetos esféricos de un diámetro dado d que se pueden empaquetar en un paralelepípedo de tamaño a × b × c .
Esferas idénticas en un cilindro
El problema determina la altura mínima h de un cilindro de radio R dado, en el que se empaquetan n bolas idénticas de radio r (< R ) [10] .
Embalaje en contenedores 2D
Círculos de embalaje
Círculos dentro de un círculoEmpacando n círculos unitarios en el círculo más pequeño posible . El problema está estrechamente relacionado con la distribución de puntos en el círculo unitario para lograr la mayor distancia mínima d n entre puntos.
Se han probado soluciones óptimas para n ≤13 y para n =19.
Círculos en un cuadradoEmpacando n círculos unitarios en un cuadrado lo más pequeño posible . El problema está íntimamente relacionado con la distribución de puntos en el cuadrado unitario para lograr la mayor distancia mínima d n entre puntos [11] . Para transformar estas dos formulaciones del problema, el tamaño del cuadrado de los círculos unitarios será L=2+2/d n .
Se han probado soluciones óptimas para n ≤30 [12] .
Círculos en un triángulo rectángulo isóscelesEmpacando n círculos unitarios en el triángulo rectángulo isósceles más pequeño posible . Se conocen buenas aproximaciones para n <300 [13] .
Círculos en un triángulo equiláteroEmpacando n círculos unitarios en el triángulo regular más pequeño posible . Las soluciones óptimas se conocen para n <13 y se formulan hipótesis para n <28 [14] .
Plazas de embalaje
Cuadrados dentro de un cuadradoEmpacando n cuadrados unitarios en el cuadrado más pequeño posible .
Se han probado soluciones óptimas para n =1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100 y cualquier cuadrado completo [15] .
El espacio vacío es asintóticamente O ( a 7/11 ) [16] .
Cuadrados en un círculoEmpacando n cuadrados en el círculo más pequeño posible.
Soluciones mínimas: [17]
| Número de cuadrados | Radio del círculo |
|---|---|
| una | 0.707… |
| 2 | 1.118… |
| 3 | 1.288… |
| cuatro | 1.414… |
| 5 | 1.581… |
| 6 | 1.688… |
| 7 | 1.802… |
| ocho | 1.978… |
| 9 | 2.077… |
| diez | 2.121… |
| once | 2.214… |
| 12 | 2.236… |
Rectángulos de embalaje
Rectángulos idénticos en un rectánguloEl problema de empaquetar múltiples copias de un solo rectángulo de tamaño ( l , w ) con permiso de rotación de 90° en un rectángulo más grande de tamaño ( L , W ) tiene varias aplicaciones, como paletizar cajas y apilar aglomerado.
Por ejemplo, puede empaquetar 147 rectángulos de 137x95 en un rectángulo de 1600x1230 [18] .
Varios rectángulos dentro de un rectánguloEl problema de empaquetar rectángulos con diferentes anchos y alturas en un rectángulo de área mínima (pero sin limitar el ancho y la altura de dicho rectángulo) tiene una aplicación importante para ensamblar imágenes en una imagen grande. Una página web que carga una imagen grande a menudo se muestra más rápido en los navegadores que una que carga muchas imágenes pequeñas porque cada imagen debe solicitarse al servidor.
Un ejemplo de un algoritmo rápido que empaqueta rectángulos de varias alturas y anchos en un rectángulo de área mínima está aquí .
Tareas relacionadas
No debe haber lagunas ni superposiciones en los problemas de mosaico . Muchos rompecabezas de este tipo utilizan el empaquetamiento de rectángulos o poliominós en un rectángulo más grande u otra forma cercana a un cuadrado.
Hay un teorema importante sobre la colocación de rectángulos (y cuboides ) en rectángulos (cuboides) sin espacios ni superposiciones:
Un rectángulo a × b se puede empaquetar en una cinta de 1 × n si y solo si n es divisible por a o n es divisible por b [19] [20] Teorema de De Bruijn : una caja rectangular 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.) [19]El estudio de las teselaciones de poliominós se ocupa principalmente de dos clases de problemas: teselar un rectángulo con teselas congruentes y teselar un rectángulo con un conjunto de teselas de n -poliominós.
El rompecabezas clásico del segundo tipo consiste en colocar las doce fichas de pentomino en rectángulos de 3x20, 4x15 , 5x12 o 6x10.
Empaquetado de objeto incorrecto
Embalar objetos irregulares es un problema que difícilmente puede resolverse de forma cerrada (analítica). Sin embargo, en la ciencia del mundo circundante, la tarea es muy importante. Por ejemplo, las partículas irregulares del suelo se empaquetan de manera diferente cuando cambia el tamaño y la forma de las partículas, lo que tiene consecuencias significativas para las plantas en términos de formación de raíces y la capacidad de mover el agua en el suelo. [21]
Véase también
- Juegos de embalaje
- Problema de embalaje del contenedor
- El rompecabezas de Slotober - Graatsma
- Rompecabezas de Conway
- tetris
- Tareas de cobertura
- El problema de la mochila
- Empaquetamiento tetraédrico
- Tarea de corte
- número de contacto
- Empaque denso de esferas iguales
- Empaquetamiento denso aleatorio
Notas
- ↑ Lodi, Martello, Monaci, 2002 , pág. 241–252.
- ↑ Donev, Stillinger, Chaikin, Torquato, 2004 .
- ↑ 1 2 Torquato, Jiao, 2009 , pág. 876–879.
- ↑ Haji-Akbari, Engel, Keys, Zheng et al., 2009 , p. 773–777.
- ↑ Chen, Engel, Glotzer, 2010 , pág. 253–280.
- ↑ Hudson, Harrowell, 2011 , pág. 194103.
- ↑ Empaque circular - de Wolfram MathWorld . Consultado el 9 de junio de 2016. Archivado desde el original el 4 de agosto de 2016.
- ↑ 12Betke , Henk, 2000 .
- ↑ Minkowski, 1904 .
- ↑ Stoyan, Yaskov, 2010 , pág. 51–70.
- ↑ Croft, Falconer, Guy, 1991 , pág. 108–110.
- ↑ Specht, 2010 .
- ↑ Specht, 2011 .
- ↑ Melissen, 1995 , pág. 333–342.
- ↑ Friedman, 2005 .
- ↑ Erdős, Graham, 1975 , p. 119–123.
- ↑ Cuadrados en círculos (enlace descendente) . Consultado el 9 de junio de 2016. Archivado desde el original el 14 de septiembre de 2017.
- ↑ Birgin, Lobato, Morabito, 2010 , p. 306–320.
- ↑ 1 2 Honsberger, 1976 , pág. 67.
- ↑ Klarner, Hautus, 1971 , pág. 613–628.
- ↑ 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 Archivado el 8 de junio de 2013 en Wayback Machine . Washington DC.
Literatura
- S. Torcuato, Y. Jiao. Empaquetamientos densos de los sólidos platónicos y de Arquímedes // Naturaleza. - 2009. - T. 460 , núm. 7257 . — S. 876–879 . — ISSN 0028-0836 . -doi : 10.1038/ naturaleza08239 . — . -arXiv : 0908.4107 . _ —PMID 19675649 .
- Hallard T. Croft, Kenneth J. Falconer, Richard K. Guy. Problemas no resueltos en Geometría. - Nueva York: Springer-Verlag, 1991. - S. 108-110. — ISBN 0-387-97506-3 .
- J. Melissen. Empaquetar 16, 17 o 18 círculos en un triángulo equilátero // Matemáticas discretas. - 1995. - T. 145 . — Pág. 333–342 . - doi : 10.1016/0012-365X(95)90139-C .
- YG Stoyan, GN Yaskov. Empaquetando esferas idénticas en un cilindro // Transacciones internacionales en investigación operativa. - 2010. - T. 17 . — S. 51–70 . -doi : 10.1111/ j.1475-3995.2009.00733.x .
- Eckard Specht. Los empaquetamientos más conocidos de círculos iguales en un cuadrado (20 de mayo de 2010). Recuperado: 25 de mayo de 2010.
- P. Erdős, R. L. Graham. Sobre empaquetar cuadrados con cuadrados iguales // Journal of Combinatorial Theory, Serie A. - 1975. - T. 19 . — S. 119–123 . - doi : 10.1016/0097-3165(75)90099-0 .
- A. Lodi, S. Martello, M. Monaci. Problemas de empaquetamiento bidimensional: una encuesta // European Journal of Operational Research. - Elsevier, 2002. - T. 141 . — S. 241–252 . - doi : 10.1016/s0377-2217(02)00123-6 .
- A. Donev, F. Stillinger, P. Chaikin, S. Torquato. Empaques cristalinos inusualmente densos de elipsoides // Cartas de revisión física. - 2004. - T. 92 , núm. 25 . -doi : 10.1103 / PhysRevLett.92.255506 . - . -arXiv : cond - mat/0403286 .
- A. Haji-Akbari, M. Engel, AS Keys, X. Zheng, RG Petschek, P. Palffy-Muhoray, SC Glotzer. Fases desordenadas, cuasicristalinas y cristalinas de tetraedros densamente empaquetados // Naturaleza. - 2009. - T. 462 , núm. 7274 . — S. 773–777 . -doi : 10.1038/ naturaleza08641 . — . -arXiv : 1012.5138 . _ —PMID 20010683 .
- E. R. Chen, M. Engel, S. C. Glotzer. Empaques de dímeros cristalinos densos de tetraedros regulares // Geometría discreta y computacional. - 2010. - T. 44 , núm. 2 . — S. 253–280 . -doi : 10.1007/ s00454-010-9273-0 .
- TS Hudson, P. Harrowell. Búsquedas estructurales utilizando conjuntos isopuntuales como generadores: Empaquetamientos más densos para mezclas binarias de esferas duras // Journal of Physics: Condensed Matter. - 2011. - T. 23 , núm. 19 _ - S. 194103 . -doi : 10.1088 / 0953-8984/23/19/194103 .
- E.G. Birgin, R.D. Lobato, R. Morabito. Un enfoque de partición recursivo efectivo para empaquetar rectángulos idénticos en un rectángulo // Journal of the Operational Research Society. - 2010. - T. 61 . — S. 306–320 . -doi : 10.1057 / jors.2008.141 .
- Ross Honsberger. Gemas Matemáticas II. - La Asociación Matemática de América , 1976. - ISBN 0-88385-302-7 .
- DA Klarner, MLJ Hautus. Vidrieras de colores uniformes // Actas de la Sociedad Matemática de Londres. - 1971. - T. 23 . -doi : 10.1112 / plms/s3-23.4.613 .
- Eckard Specht. Los empaques más conocidos de círculos iguales en un triángulo rectángulo isósceles (11 de marzo de 2011). Consultado: 1 de mayo de 2011.
- U. Betke, M. Henk. Empaquetamientos de red más densos de 3 politopos // Comput. Geom.. - 2000. - T. 16 . — S. 157–186 .
- H. Minkowski. Dichteste gitterförmige Lagerung kongruenter Körper // Nachr. Akád. sabio Matemáticas de Gotinga. física KI. II. - 1904. - S. 311-355 .
- Eric Friedman. Cuadrados de unidades de embalaje en cuadrados: una encuesta y nuevos resultados // The Electronic Journal of Combinatorics. - 2005. - T.DS7 . Archivado desde el original el 27 de julio de 2009.
Enlaces
- Weisstein, Eric W. Klarner's Theorem (inglés) en el sitio web de Wolfram MathWorld .
- Weisstein, Eric W. de Bruijn's Theorem (inglés) en el sitio web de Wolfram MathWorld .
- API para empaquetar contenedores 3D
- Embalaje de cajas y cilindros 3D con nesting
- Empaquetar rectángulos 2D en una tabla ortogonal
Muchos libros de acertijos, así como revistas de matemáticas, tienen artículos sobre paquetes.
- Enlaces a varios artículos de MathWorld sobre paquetes
- Notas de MathWorld sobre cuadrados de embalaje.
- Centro de embalaje de Erich Archivado el 14 de marzo de 2010 en Wayback Machine .
- www.packomania.com Sitio con tablas, gráficos, cálculos, enlaces, etc.
- "Box Packing" de Ed Pegg, Jr., Wolfram Demonstrations Project , 2007.
- Los packs más famosos de círculos idénticos en un círculo, unos 1100
- Problema de desafío de empaquetado de círculos en Python
| Tareas de embalaje | |
|---|---|
| círculos de embalaje |
|
| Embalaje de globos |
|
| Otros paquetes | |
| Rompecabezas | |