Els problemes d'empaquetat són una classe de problemes d'optimisació en matemàtiques que impliquen intentar empaquetar objectes en contenidors. L'objectiu és empaquetar un sol contenidor lo més densament possible o empaquetar tots els objectes usant la menor cantitat de contenidors possible. Molts d'estos problemes poden estar relacionats en qüestions reals d'embalage, almagasenament i transport. Cada problema de empaque té un problema de doble cobertura, que pregunta quànts dels mateixos objectes es requerixen per a cobrir completament cada regió del contenidor, a on els objectes poden superpondre's.

Problema d'empaquetat
Esferes o círculs empaquetats solts (dalt) i més densament (avall).

En un problema d'embalage en contenidors, es proporciona:

  • 'contenidors' (generalment una sola regió convexa bidimensional o tridimensional, o un espai infinit)
  • Un conjunt de 'objectes' alguns o tots els quals deuen empaquetar-se en un o més contenidors. El conjunt pot contindre diferents objectes en els seus tamanys especificats, o un sol objecte d'una dimensió fixa que es pot utilisar repetidament.

Per lo general, l'embalage no deu tindre superposicions entre les mercaderies i atres mercaderies o les parets del contenidor. En algunes variants, l'objectiu és trobar la configuració que empaqueta un sol contenidor en la màxima densitat. Més comunament, l'objectiu és empaquetar tots els objectes en la menor cantitat de contenidors possible.[1] En algunes variants, la superposició (d'objectes entre sí i/o en el llímit del contenidor) està permesa, pero deu minimisar-se.

Empaquetat en un espai infinit

Molts d'estos problemes, quan el tamany del contenidor aumenta en totes les direccions, es tornen equivalents al problema d'empaquetar objectes lo més densament possible en un espai euclidiano infinit. Este problema és rellevant per a vàries disciplines científiques i ha rebut una atenció significativa. La conjectura de Kepler va postular una solució òptima per a empacar esferes centenars d'anys ans que Thomas Callister Hales demostrara que era correcta. Moltes atres formes han rebut atenció, inclosos elipsoide,[2] sòlits platònics i de Arquímedes[3] inclosos els tetraedres,[4][5] trípodes (unions de gavetes a lo llarc de tres rajos paralels a l'eix positiu),[6] i dímers d'esferes desiguals.[7]

Empaquetat hexagonal de círculs

 
El empaquetamiento hexagonal de círculs en un pla euclidiano bidimensional.

Estos problemes són matemàticament distints de les idees del teorema de l'empaquetamiento de círculs. El problema d'empaquetamiento de círculs tracta d'empaquetar círculs, possiblement de diferents tamanys, en una superfície, per eixemple el pla o una esfera.

Les contraparts d'un círcul en atres dimensions mai poden empaquetar-se en total eficiència en dimensions majors a un (en un univers unidimensional, el círcul anàlec són solament dos punts). És dir, sempre hi haurà espai no utilisat si solament està empacando círculs. La forma més eficient d'empaquetar círculs, el empaque hexagonal, produïx aproximadament un 91 % d'eficiència.[8]

Empaquetaduras d'esferes en dimensions superiors

Artícul principal → Empaquetamiento d'esferes.


En tres dimensions, les estructures compactes oferixen el millor empaque de celosía d'esferes i es creu que és l'òptim de tots els empaques. En empaquetaduras esfèriques 'simples' en tres dimensions (definint-se cuidadosadament 'simple') hi ha nou empaquetaduras definibles possibles.[9] La celosía E8 de 8 dimensions i la celosía Leech de 24 dimensions també han demostrat ser òptimes en el seu respectiu espai dimensional real.

Empaquetaduras de sòlits platònics en tres dimensions

Les gavetes es poden organisar fàcilment per a omplir completament l'espai tridimensional, sent el empaque més natural el panal cúbic. Cap atre sòlit platònic pot enlosar l'espai per sí solament, pero es coneixen alguns resultats preliminars. L'empaquetat en tetraedres pot conseguir un empacado d'a lo manco el 85 %. Un dels millors empaques de dodecaedres regulars es basa en la celosía cúbica centrada en la cara (FCC) abans mencionada.

El tetraedre i l'octaedre junts poden omplir tot l'espai en una disposició coneguda com panal tetraèdric-octaèdric.

Sòlit Densitat òptima d'un empaque de celosía
icosaedre 0.836357...[10]
dodecaedre (5 + 5)/8 = 0.904508...[10]
octaedre 18/19 = 0.947368...[11]

Les simulacions que combinen métodos de millora local en empaques aleatoris sugerixen que els empaques de celosía per a icosaedres, dodecaedres i octaedres són òptims en la classe més àmplia de tots els empaques.[3]

Embalage en contenidors tridimensionals

Diferents cuboides en un cuboide

Determinar la cantitat mínima de contenidors cuboides (contenidors) que es requerixen per a empacar un conjunt donat d'artículs cuboides (rectànguls tridimensionals). Els cuboides rectangulars que es van a empaquetar es poden girar 90 graus en cada eix.

Esferes en una bola euclidiana

El problema de trobar la bola més chicoteta tal que k boles separades de l'unitat oberta es poden empaquetar dins té una resposta simple i completa en n-dimensions del espai euclídeo si k≤n+1, i en un espai de Hilbert de dimensió infinita sense restriccions. Val la pena descriure-ho en detalle ací per a donar una idea del problema general. En este cas, en una configuració de k hi ha disponibles boles unitàries tangentes per parells. Coloca els centres en els vèrtiços a1,..,ak d'un regular (k−1) simplex dimensional en vora 2; açò es realisa fàcilment partint d'una base ortonormal. Un chicotet càlcul mostra que la distància de cada vèrtiç des del baricentre és 2(1−1k). Ademés, qualsevol atre punt de l'espai té necessàriament una major distància de a lo manco un dels k vèrtiços. En térmens d'inclusions de boles, les k boles unitàries obertes centrades en k boles unitàries obertes centrades en a1,..,ak estan inclosos en una bola de radi rk:=1+2(1−1k), que és mínim per a esta configuració.

Per a demostrar que esta configuració és òptima, siga x1,...,xk els centres de k boles unitàries obertes disjuntas contingudes en una bola de radi r centrat en un punt x0. Considere el mapa del conjunt finit {x1,..xk} en {a1,..ak} prenent xj en el corresponent aj per a cada 1≤j≤k. Ya que para tots 1≤i<j≤k, ‖ai−aj‖=2≤‖xi−xj‖ este mapa és 1-Lipschitz i pel teorema de Kirszbraun s'estén a un mapa 1-Lipschitz que està definit globalment; en particular, existix un punt a0 tal que para tots 1≤j≤k un té ‖a0−aj‖≤‖x0−xj‖, per a que també rk≤1+‖a0−aj‖≤1+‖x0−xj‖≤r. Açò mostra que hi ha k unitat disjunta boles obertes en una bola de radi r si i solament si r≥rk. Observe que en un espai de Hilbert de dimensió infinita açò implica que hi ha infinites boles unitàries obertes disjuntas dins d'una bola de radi r si i solament si r≥1+2. Per eixemple, les boles unitàries centrades en 2ej, on {ej}j és una base ortonormal, són disjuntos i s'inclouen en una bola de radi 1+2 centrat en l'orige. Ademés, per a r<1+2, el número màxim de boles unitàries obertes disjuntas dins d'una bola de ràdio r és ⌊22−(r−1)2⌋.

Esferes en un cuboide

Determinar la cantitat d'objectes esfèrics de diàmetro d ya que es poden empaquetar en un cuboide de tamany a×b×c.

Esferes idèntiques en un cilindre

Determinar l'altura mínima h d'un cilindre en un radi R ya que empacará n esferes idèntiques de ràdio r (< R.[12] Per a un radi chicotet R, les esferes s'organisen en estructures ordenades, cridades estructures columnars.

Poliedres en esferes

Determinar el radi mínim R que empacará n poliedres de volum unitari idèntics d'una forma donada.[13]


Referències

  1. ↑ Lodi, Andrea; Martello, Silvano; Monaci, Michele(2002-09-01).«Two-dimensional packing problems: A survey».European Journal of Operational Research.141(2): 241–252.ISSN 0377-2217.doi:10.1016/S0377-2217(02)00123-6.Consultat el 2021-02-16.(en en)
  2. ↑ Donev, Aleksandar; Stillinger, Frank H.; Chaikin, P. M.; Torquato, Salvatore(2004-06-23).«Unusually Donen-se Crystal Packings of Ellipsoids».Physical Review Letters.92(25): 255506.doi:10.1103/PhysRevLett.92.255506.Consultat el 2021-02-16.
  3. ↑ 3,0 3,1 Torquato, S.; Jiao, Y.(2009-08).«Donen-se packings of the Platonic and Archimedean solids».Nature.460(7257): 876–879.ISSN 1476-4687.doi:10.1038/nature08239.Consultat el 2021-02-16.(en en)
  4. ↑ Haji-Akbari, Amir; Engel, Michael; Keys, Aaron S.; Zheng, Xiaoyu(2009-12).«Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra».Nature.462(7274): 773–777.ISSN 1476-4687.doi:10.1038/nature08641.Consultat el 2021-02-16.(en en)
  5. ↑ Chen, Elizabeth R.; Engel, Michael; Glotzer, Sharon C.(2010-09-01).«Donen-se Crystalline Dimer Packings of Regular Tetrahedra».Discrete & Computational Geometry.44(2): 253–280.ISSN 1432-0444.doi:10.1007/s00454-010-9273-0.Consultat el 2021-02-16.(en en)
  6. ↑ (1998).«Tracking the Automatic ANT».doi:10.1007/978-1-4612-2192-0.Consultat el 2021-02-16.(en en-gb)
  7. ↑ Hudson, Toby S; Harrowell, Peter(2011-04-27).«Structural searches using isopointal sets as generators: densest packings for binary hard sphere mixtures».Journal of Physics: Condensed Matter.23(19): 194103.ISSN 0953-8984.doi:10.1088/0953-8984/23/19/194103.Consultat el 2021-02-16.(en en)
  8. ↑ Weisstein, Eric W.. «Circle Packing» (en en). mathworld.wolfram.com. Consultat el 2021-02-16.
  9. ↑ Smalley, Ian(1963-11-01).«Simple Regular Sphere Packings in Three Dimensions».Mathematics Magazine.36(5): 295–299.ISSN 0025-570X.doi:10.1080/0025570X.1963.11975458.Consultat el 2021-02-16.
  10. ↑ 10,0 10,1 (2000-07-01).«Densest lattice packings of 3-polytopes».Computational Geometry.16(3): 157–186.ISSN 0925-7721.doi:10.1016/S0925-7721(00)00007-9.Consultat el 2021-02-16.(en en)
  11. ↑ Minkowski, H. Dichteste gitterfo¨rmige Lagerung kongruenter Ko¨rper. Nachr. Akad. Wiss. Go¨ttingen Math. Phys. KI. II 311–355 (1904).
  12. ↑ Stoyan, Yu G.; Yaskov, G. N.(2010).«Packing identical spheres into a cylinder».International Transactions in Operational Research.17(1): 51–70.ISSN 1475-3995.doi:10.1111/j.1475-3995.2009.00733.x.Consultat el 2021-02-16.(en en)
  13. ↑ Teich, Erin G.; Anders, Greg van; Klotsa, Daphne; Dshemuchadse, Julia(2016-02-09).«Clusters of polyhedra in spherical confinement».Proceedings of the National Academy of Sciences.113(6): E669–E678.ISSN 0027-8424.doi:10.1073/pnas.1524875113.Consultat el 2021-02-16.(en en)