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.
En un problema de embalaje en contenedores, se proporciona:
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. En algunas variantes, la superposición (de objetos entre sí y/o con el límite del contenedor) está permitida, pero debe minimizarse.
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, sólidos platónicos y de Arquímedes incluidos los tetraedros, trípodes (uniones de cubos a lo largo de tres rayos paralelos al eje positivo), y dímeros de esferas desiguales.
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.
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. 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.
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... |
dodecaedro | (5 + )/8 = 0.904508... |
octaedro | 18/19 = 0.947368... |
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.
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.
El problema de encontrar la bola más pequeña tal que bolas separadas de la unidad abierta se pueden empaquetar dentro tiene una respuesta simple y completa en -dimensiones del espacio euclídeo 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, en una configuración de hay 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 los vértices. En términos de inclusiones de bolas, las bolas unitarias abiertas centradas en 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, sea los centros de bolas unitarias abiertas disjuntas contenidas en una bola de radio centrado en un punto . Considere el mapa del conjunto finito en 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 .
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.
Determinar la altura mínima h de un cilindro con un radio R dado que empacará n esferas idénticas de radio r (< R. Para un radio pequeño R, las esferas se organizan en estructuras ordenadas, llamadas estructuras columnares.
Determinar el radio mínimo R que empacará n poliedros de volumen unitario idénticos de una forma dada.
Se han estudiado muchas variantes de problemas de empaquetamiento bidimensional.
Dados n círculos unitarios, se debe empacarlos en el recipiente más pequeño posible. Se han estudiado varios tipos de envases:
Dados n cuadrados unitarios, se debe empacarlos en el contenedor más pequeño posible, donde el tipo de contenedor varía:
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:
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.
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.
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.
En inglés:
This article uses material from the Wikipedia Español article Problema de empaquetado, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). El contenido está disponible bajo la licencia CC BY-SA 4.0, salvo que se indique lo contrario. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Español (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.