Problema de empaquetado

Esferas o círculos empaquetados sueltos (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 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:

• '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.​ En algunas variantes, la superposición (de objetos entre sí y/o con el límite del contenedor) está permitida, pero debe minimizarse.

Empaquetado 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,​ 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.​

Empaquetado 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 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.​

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.​ 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.

Empaquetaduras 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. 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 + ${\sqrt {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.​

Embalaje en contenedores tridimensionales

Diferentes cuboides en un cuboide

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.

Esferas en una bola euclidiana

El problema de encontrar la bola más pequeña tal que $k$ bolas separadas de la unidad abierta se pueden empaquetar dentro tiene una respuesta simple y completa en $n$-dimensiones del espacio euclídeo si $\scriptstyle k\leq n+1$, 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 $k$ hay disponibles bolas unitarias tangentes por pares. Coloca los centros en los vértices $a_{1},..,a_{k}$ de un regular $\scriptstyle (k-1)$ 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 $\scriptstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}$. Además, cualquier otro punto del espacio tiene necesariamente una mayor distancia de al menos uno de los $\scriptstyle k$ vértices. En términos de inclusiones de bolas, las $\scriptstyle k$ bolas unitarias abiertas centradas en $\scriptstyle k$ bolas unitarias abiertas centradas en $\scriptstyle a_{1},..,a_{k}$ están incluidos en una bola de radio $\scriptstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}$, que es mínimo para esta configuración.

Para demostrar que esta configuración es óptima, sea $\scriptstyle x_{1},...,x_{k}$ los centros de $\scriptstyle k$ bolas unitarias abiertas disjuntas contenidas en una bola de radio $\scriptstyle r$ centrado en un punto $\scriptstyle x_{0}$. Considere el mapa del conjunto finito $\scriptstyle \{x_{1},..x_{k}\}$ en $\scriptstyle \{a_{1},..a_{k}\}$ tomando $\scriptstyle x_{j}$ en el correspondiente $\scriptstyle a_{j}$ para cada $\scriptstyle 1\leq j\leq k$. Ya que para todos $\scriptstyle 1\leq i<j\leq k$, $\scriptstyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|$ 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 $\scriptstyle a_{0}$ tal que para todos $\scriptstyle 1\leq j\leq k$ uno tiene $\scriptstyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|$, para que también $\scriptstyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r$. Esto muestra que hay $\scriptstyle k$ unidad disjunta bolas abiertas en una bola de radio $\scriptstyle r$ si y solo si $\scriptstyle r\geq r_{k}$. 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 $\scriptstyle r$ si y solo si $\scriptstyle r\geq 1+{\sqrt {2}}$. Por ejemplo, las bolas unitarias centradas en $\scriptstyle {\sqrt {2}}e_{j}$, dónde $\scriptstyle \{e_{j}\}_{j}$ es una base ortonormal, son disjuntos y se incluyen en una bola de radio $\scriptstyle 1+{\sqrt {2}}$ centrado en el origen. Además, para $\scriptstyle r<1+{\sqrt {2}}$, el número máximo de bolas unitarias abiertas disjuntas dentro de una bola de radio r es $\scriptstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }$.

Esferas en un cuboide

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.

Esferas idénticas en un cilindro

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.

Poliedros en esferas

Determinar el radio mínimo R que empacará n poliedros de volumen unitario idénticos de una forma dada.​

Empaquetado en contenedores bidimensionales

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

Se han estudiado muchas variantes de problemas de empaquetamiento bidimensional.

Empaquetado de círculos

Dados n círculos unitarios, se debe empacarlos en el recipiente más pequeño posible. Se han estudiado varios tipos de envases:

• Círculos empacados 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 empacados 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 empacados en un triángulo rectángulo isósceles: se conocen buenas estimaciones para n<300.
• Círculos empacados en un triángulo equilátero: se conocen soluciones óptimas para n<13, y hay conjeturas disponibles para n<28.​

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

Empaquetado de cuadrados

Dados n cuadrados unitarios, se 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(a^7/11).
• Empaquetar cuadrados en un círculo: se conocen buenas soluciones para n hasta 35.

  

  El empaque ó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 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).
• 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 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 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:

• Un rectángulo de a × b puede ser embalado con 1 × n tiras si y sólo si n divide a o n divide b.​​
• 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).​

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.

Empaquetado de objetos irregulares

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.​

Véase también

• Set packing
• Rompecabezas de Slothouber-Graatsma
• Rompecabezas de Conway
• Tetris
• Problema de cobertura (combinatoria)
• Problema de la mochila
• Problema de corte de valores
• Número de osculación
• Empaquetamiento compacto
• Empaquetamiento aleatorio

Fuentes

• Weisstein, Eric W. «Klarner's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «de Bruijn's Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

Enlaces externos

• Wikimedia Commons alberga una categoría multimedia sobre Problema de empaquetado.

En inglés:

• Optimización del embalaje de contenedores tridimensionales Archivado el 3 de marzo de 2019 en Wayback Machine.
• API para empaquetado 3D
• Erich's Packing Center
• www.packomania.com
• "Box Packing" por Ed Pegg, Jr., Wolfram Demonstrations Project, 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

• Datos: Q3851477
• Multimedia: Packing problems / Q3851477