Probleme de împachetare

Sfere sau cercuri împachetate lejer (sus) și mai dens (jos)

În matematică problemele de împachetare sunt o clasă de probleme de optimizare care tratează împachetarea unor obiecte împreună în containere. Scopul este fie de a le împacheta într-un singur container cu o densitate cât mai mare, fie de a împacheta toate obiectele folosind cât mai puține containere. Multe dintre aceste probleme pot fi legate de chestiuni de ambalare, depozitare și transport din viața reală. Fiecare problemă de împachetare are o problemă de acoperire duală, care tratează câte dintre aceleași obiecte sunt necesare pentru a acoperi complet fiecare regiune a containerului, unde obiectelor li se permite să se suprapună.

În problema bin packing^⁠(d) se dă:

• Un container, de obicei o regiune convexă bidimensională sau tridimensională, posibil de mărime infinită. Pot fi date mai multe containere, în funcție de problemă.
• Un set de obiecte, dintre care unele sau toate trebuie împachetate într-unul sau mai multe containere. Setul poate conține diferite obiecte cu dimensiunile specificate sau un singur obiect cu o dimensiune fixă care poate fi utilizat în mod repetat.

De obicei împachetarea trebuie să fie fără suprapuneri între obiecte sau să treacă dincolo de pereții containerului. În unele variante scopul este de a găsi configurația care se împachetează într-un singur container cu densitatea de împachetare maximă. Mai frecvent, scopul este de a împacheta toate obiectele în cât mai puține containere.^[1] În unele variante, suprapunerea obiectelor între ele și/sau depățirea limitelor containerului sunt permise, dar trebuie reduse la minimum.

Împachetare într-un spațiu infinit

Multe dintre aceste probleme, atunci când dimensiunea containerului este mărită în toate direcțiile, devin echivalente cu problema împachetării obiectelor cât mai dens posibil în spațiul euclidian infinit. Această problemă este relevantă pentru o serie de discipline științifice și i s-a acordat o atenție semnificativă. Conjectura Kepler^⁠(d) a postulat o soluție optimă pentru împachetarea sferelor^⁠(d) cu sute de ani înainte să fie corect demonstrată matematic de către Thomas Callister Hales. Multe alte forme au fost în atenție, inclusiv pentru elipsoizi,^[2] poliedre platonice și arhimedice^[3] cuprinzînd împachetarea tetraedrelor,^[4][5] tripoduri (reuniuni de cuburi de-a lungul a trei axe pozitive),^[6] și grupuri de câte două sfere inegale.^[7]

Împachetarea hexagonală a cercurilor

Împachetarea hexagonală a cercurilor dintr-un plan euclidian

Aceste probleme sunt distincte din punct de vedere matematic de ideile din teorema împachetării cercurilor^⁠(d). Problema aferentă cercurilor se ocupă de împachetarea cercurilor, posibil de diferite dimensiuni, pe o suprafață, de exemplu planul sau o sferă.

Omologul cercului din alte dimensiuni nu poate fi niciodată împachetat cu eficiență completă în dimensiuni mai mari decât 1 (într-un spațiu unidimensional analogul cercului este doar două puncte). Adică, va exista întotdeauna spațiu neocupat dacă se împachetează doar cercuri. Cel mai eficient mod de a împacheta cercuri, împachetarea hexagonală, are o eficiență de aproximativ 91 %.^[8]

Împachetarea sferelor în spații din dimensiuni superioare

În spațiul tridimensional structurile de împachetare compactă a sferelor^⁠(d) oferă cea mai bună rețea de împachetare a sferelor și se crede că este cea mai bună dintre toate împachetările. Cu împachetări „simple” ale sferelor în spații tridimensionale („simple” fiind definit cu atenție) există nouă împachetări posibile.^[9] De asemenea, rețeaua E8^⁠(d) 8-dimensională și rețeaua Leech^⁠(d) 24-dimensională s-au dovedit a fi optime în spațiul lor dimensional real respectiv.

Împachetarea poliedrelor platonice în spațiul tridimensional

Cuburile pot fi aranjate cu ușurință pentru a umple complet spațiul tridimensional, cea mai naturală împachetare fiind fagurele cubic. Niciun alt poliedru platonic nu poate umple spațiul singur, dar există unele rezultate parțiale. Tetraedrul poate atinge o împachetare de cel puțin 85 %. Unul dintre cele mai bune împachetări ale dodecaedrelor regulate se bazează pe rețeaua cubică centrată pe fețe.

Tetraedrele și octaedrele pot umple împreună spațiul într-un aranjament cunoscut drept fagure tetraedric-octaedric.

Corp	Densitatea optimă a rețelei de împachetare
icosaedru	0,836357...[10]
dodecaedru	(5 + √5)/8 = 0,904508...[10]
octaedru	18/19 = 0,947368...[11]

Simulările care combină metodele locale de îmbunătățire cu împachetări aleatorii sugerează că rețelele de împachetare ale icosaedrelor, dodecaedrelor și octaedrelor sunt optime în clasa mai largă a tuturor împachetărilor.^[3]

Împachetarea în containere tridimensionale

Diferiți cuboizi într-un cuboid

Să se determine numărul minim de containere cuboide care sunt necesare pentru a împacheta un anumit set de elemente cuboide. Cuboidele dreptunghice care urmează să fie împachetate pot fi rotite cu 90° pe fiecare axă.

Sfere într-o bilă euclidiană

Problema găsirii celei mai mici bile astfel încât k bile unitate disjuncte deschise să fie împachetate în ea are un răspuns simplu și complet în spațiul euclidian n-dimensional dacă ${\displaystyle k\leq n+1}$ și într-un spațiu Hilbert infinit dimensional fără restricții. Merită descris în detaliu aici, pentru a da un exemplu din problema generală. În acest caz, fie o configurație de k perechi de bile tangente. Se plasează centrele în vârfurile ${\displaystyle a_{1},\dots ,a_{k}}$ ale unui simplex regulat (k−1)-dimensional cu latura 2; acest lucru este ușor de realizat pornind de la o bază ortonormată. Un mic calcul arată că distanța fiecărui vârf de la baricentru este ${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$. Mai mult, orice alt punct al spațiului are în mod necesar o distanță mai mare față de cel puțin unul dintre vârfurile k. În termeni de includere a bilelor, k bile unitate deschise centrate în ${\displaystyle a_{1},\,\dots \,,\,a_{k}}$ sunt incluse într-o bilă cu raza ${\textstyle r_{k}:=1+{\sqrt {2\left(1-{\frac {1}{k}}\right)}}}$, ceea ce este minim pentru această configurație.

Pentru a arăta că această configurație este optimă, fie ${\displaystyle x_{1},\,\dots \,,\,x_{k}}$ centrele a k bile unitate deschise disjuncte conținute într-o bilă cu raza r cu centrul în punctul ${\displaystyle x_{0}}$. Se consideră aplicația din mulțimea finită ${\displaystyle \{x_{1},\,\dots \,,\,x_{k}\}}$ în ${\displaystyle \{a_{1},\,\dots \,,\,a_{k}\}}$ luând ${\displaystyle x_{j}}$ în ${\displaystyle a_{j}}$ corespunzătoare pentru fiecare ${\displaystyle 1\leq j\leq k}$. Deoarece pentru toate ${\displaystyle 1\leq i<j\leq k}$, ${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$ această aplicație este 1-Lipschitz^⁠(d) și prin teorema Kirszbraun se extinde la o aplicație 1-Lipschitz care este definită global; în special, există un punct ${\displaystyle a_{0}}$ astfel încât pentru orice ${\displaystyle 1\leq j\leq k}$ unul are ${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$, astfel încât, de asemenea, ${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$. Aceasta arată că există k bile unitate deschise disjuncte într-o bilă cu raza r dacă și numai dacă ${\displaystyle r\geq r_{k}}$. Se observă că într-un spațiu Hilbert cu dimensiuni infinite acest lucru implică faptul că există infinit de multe bile unitate deschise disjuncte în interiorul unei bile cu raza r dacă și numai dacă ${\displaystyle r\geq 1+{\sqrt {2}}}$. De exemplu, bilele unitate centrate în ${\displaystyle {\sqrt {2}}e_{j}}$, unde ${\displaystyle \{e_{j}\}_{j}}$ este o bază ortonormată, sunt disjuncte și incluse într-o bilă cu rază ${\displaystyle 1+{\sqrt {2}}}$ centrată în origine. Mai mult, pentru ${\displaystyle r<1+{\sqrt {2}}}$, numărul maxim de bile unitate deschise disjuncte în interiorul unei bile cu raza r este ${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$.

Sfere într-un cuboid

Să se determine numărul de obiecte sferice cu diametrul dat d care pot fi împachetate într-un cuboid de dimensiunea ${\displaystyle a\times b\times c}$.

Sfere identice într-un cilindru

Să se determine înălțimea minimă h a unui cilindru cu raza dată R în care se vor împacheta n sfere identice cu raza r(< R).^[12] Pentru o rază mică R sferele se aranjează în structuri ordonate, în coloane.

Poliedre în sfere

Să se determine raza minimă R în care se vor împacheta n poliedre identice de o formă dată, cu volumul o unitate.^[13]

Împachetări în containere bidimensionale

Împachetarea optimă a 10 cercuri într-un cerc

Au fost studiate multe variante de probleme de împachetare în spații bidimensionale.

Împachetarea cercurilor

Articol principal: Împachetarea cercurilor.

Fiind date n cercuri unitate, se cere împachetarea lor în cel mai mic container. Au fost studiate mai multe tipuri de containere:

• Împachetarea cercurilor într-un cerc: strâns legată de împrăștierea punctelor într-un cerc unitate cu obiectivul de a găsi cea mai mare separare minimă, d_n, între puncte. Soluțiile optime au fost demonstrate pentru n ≤ 13 și n = 19.

Împachetarea optimă a 15 cercuri într-un pătrat

• Împachetarea cercurilor într-un pătrat: strâns legată de împrăștierea punctelor într-un pătrat unitate cu obiectivul de a găsi cea mai mare separare minimă, d_n, între puncte. Pentru a converti între aceste două formulări ale problemei, latura pătrată pentru cercurile unitate va fi ${\displaystyle L=2+2/d_{n}}$. S-au demonstrat soluții optime pentru n ≤ 30.
• Împachetarea cercurilor într-un triunghi dreptunghic isoscel: estimări bune sunt cunoscute pentru n < 300.
• Împachetarea cercurilor într-un triunghi echilateral: se cunosc soluții optime pentru n < 13 și există conjecturi până la n < 28.^[14]

Împachetarea pătratelor

Fiind date n pătrate unitate, se cere împachetarea lor în cel mai mic container de diferite tipuri:

Împachetarea optimă a 10 pătrate într-un pătrat

• Împachetarea pătratelor într-un pătrat: au fost demonstrate soluții optime pentru n 1–10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100 și orice pătrat întreg. Spațiul irosit este asimptotic O(a^7/11).
• Împachetarea pătratelor într-un cerc: sunt cunoscute soluții bune pentru n ≤ 35.

Împachetarea dreptunghiurilor

• Împachetarea dreptunghiurilor identice într-un dreptunghi: problema împachetării mai multor copii ale unui singur dreptunghi de dimensiune (l,w), permițând rotația de 90°, într-un dreptunghi mai mare de dimensiune (L,W ) are unele aplicații precum încărcarea cutiilor pe paleți sau la depozitare. De exemplu, este posibilă împachetarea a 147 de dreptunghiuri de dimensiuni (137, 95) într-un dreptunghi de dimensiuni (1600, 1230).
• Împachetarea diferitelor dreptunghiuri într-un dreptunghi: problema împachetării mai multor dreptunghiuri de diferite lungimi și lățimi într-un dreptunghi de arie minimă (dar fără pereți la lungimea sau lățimea dreptunghiului care le cuprinde) are o aplicație importantă în combinarea imaginilor într-o singură imagine mai mare. O pagină web care încarcă o singură imagine mai mare este redată adesea mai rapid în browser decât aceeași pagină care încarcă mai multe imagini mici, din cauza supraîncărcării implicate de solicitarea fiecărei imagini de la serverul web. Problema este în general NP-completă, dar există algoritmi rapizi pentru rezolvare în cazul numerelor mici.

Domenii înrudite

În problemele de pavări sau teselări nu trebuie să existe goluri, nici suprapuneri. Multe dintre puzzle-urile de acest tip cer împachetarea dreptunghiurilor sau poliominourilor într-un dreptunghi mai mare sau altă formă asemănătoare pătratului.

Există teoreme importante pentru pavarea dreptunghiurilor (și cuboizilor) cu dreptunghiuri (cuboizi) fără spații sau suprapuneri:

Un dreptunghi a × b poate fi împachetat în 1 × n benzi dacă și numai dacă n divide a sau b.^[15][16]

Teorema lui de Bruijn: într-o casetă se pot împacheta obiecte în formă de paralelipiped dreptunghic armonic a × a b × a b c dacă caseta are dimensiunile a p × a b q × a b c r cu p, q, r numere naturale (adică, caseta este un multiplu al obiectului.)^[15]

Studiul pavărilor cu poliominouri se referă în mare măsură la două clase de probleme: să se paveze un dreptunghi cu dale congruente și să se împacheteze câte unul din fiecare n-mino într-un dreptunghi.

Un puzzle clasic de al doilea tip este aranjarea tuturor celor douăsprezece pentominouri în dreptunghiuri de 3×20, 4×15, 5×12 sau 6×10.

Împachetarea obiectelor neregulate

Împachetarea obiectelor neregulate este o problemă care nu se pretează bine la soluții complete. Totuși, aplicabilitatea în științele mediului este destul de importantă. De exemplu, particulele de sol de formă neregulată se împachetează diferit pe măsură ce dimensiunile și formele variază, ceea ce duce la rezultate importante pentru ca speciile de plante să-și adapteze rădăcinile și să permită mișcarea apei în sol.^[17]

Problema de a decide dacă un anumit set de poligoane se poate încadra într-un container pătrat dat s-a dovedit a fi completă pentru teoria existențială a numerelor reale^⁠(d).^[18]

Note

1. en Lodi, A., Martello, S., Monaci, M. (2002). „Two-dimensional packing problems: A survey”. European Journal of Operational Research. Elsevier. 141 (2): 241–252. doi:10.1016/s0377-2217(02)00123-6. Mentenanță CS1: Utilizează parametrul autori (link)
2. en Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). „Unusually Dense Crystal Packings of Ellipsoids”. Physical Review Letters. 92 (25): 255506. arXiv:cond-mat/0403286 . Bibcode:2004PhRvL..92y5506D. doi:10.1103/PhysRevLett.92.255506. PMID 15245027. 
3. ^ en Torquato, S.; Jiao, Y. (2009). „Dense packings of the Platonic and Archimedean solids”. Nature. 460 (7257): 876–879. arXiv:0908.4107 . Bibcode:2009Natur.460..876T. doi:10.1038/nature08239. ISSN 0028-0836. PMID 19675649. 
4. en Haji-Akbari, A.; Engel, M.; Keys, A. S.; Zheng, X.; Petschek, R. G.; Palffy-Muhoray, P.; Glotzer, S. C. (2009). „Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra”. Nature. 462 (7274): 773–777. arXiv:1012.5138 . Bibcode:2009Natur.462..773H. doi:10.1038/nature08641. PMID 20010683. 
5. en Chen, E. R.; Engel, M.; Glotzer, S. C. (2010). „Dense Crystalline Dimer Packings of Regular Tetrahedra”. Discrete & Computational Geometry. 44 (2): 253–280. arXiv:1001.0586 . Bibcode:2010arXiv1001.0586C. doi:10.1007/s00454-010-9273-0 . 
6. en Stein, Sherman K. (martie 1995), „Packing tripods”, Mathematical entertainments, The Mathematical Intelligencer, 17 (2): 37–39, doi:10.1007/bf03024896 . Reprinted in Gale, David (1998), Gale, David, ed., Tracking the Automatic ANT, Springer-Verlag, pp. 131–136, doi:10.1007/978-1-4612-2192-0, ISBN 0-387-98272-8, MR 1661863 
7. en Hudson, T. S.; Harrowell, P. (2011). „Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures”. Journal of Physics: Condensed Matter. 23 (19): 194103. Bibcode:2011JPCM...23s4103H. doi:10.1088/0953-8984/23/19/194103. PMID 21525553. 
8. en „Circle Packing”. 
9. en Smalley, I.J. (1963). „Simple regular sphere packings in three dimensions”. Mathematics Magazine. 36 (5): 295–299. doi:10.2307/2688954. JSTOR 2688954. 
10. ^ en Betke, Ulrich; Henk, Martin (2000). „Densest lattice packings of 3-polytopes”. Computational Geometry. 16 (3): 157–186. arXiv:math/9909172 . doi:10.1016/S0925-7721(00)00007-9 . MR 1765181. 
11. de Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904)
12. en Stoyan, Y. G.; Yaskov, G. N. (2010). „Packing identical spheres into a cylinder”. International Transactions in Operational Research. 17: 51–70. doi:10.1111/j.1475-3995.2009.00733.x. 
13. en Teich, E.G.; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, S.C. (2016). „Clusters of Polyhedra in Spherical Confinement”. Proc. Natl. Acad. Sci. U.S.A. 113 (6): E669–E678. Bibcode:2016PNAS..113E.669T. doi:10.1073/pnas.1524875113 . PMC 4760782 . PMID 26811458. 
14. en Melissen, J. (1995). „Packing 16, 17 or 18 circles in an equilateral triangle”. Discrete Mathematics. 145 (1–3): 333–342. doi:10.1016/0012-365X(95)90139-C. 
15. ^ en Honsberger, Ross (1976). Mathematical Gems II. The Mathematical Association of America. p. 67. ISBN 0-88385-302-7. 
16. en Klarner, David A.; Hautus, M.L.J (1971). „Uniformly coloured stained glass windows”. Proceedings of the London Mathematical Society. 3. 23 (4): 613–628. doi:10.1112/plms/s3-23.4.613. 
17. en C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC
18. en Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), Framework for ${\displaystyle \exists \mathbb {R} }$-Completeness of Two-Dimensional Packing Problems, arXiv:2004.07558  

Bibliografie

• en Eric W. Weisstein, Klarner's Theorem la MathWorld.
• en Eric W. Weisstein, de Bruijn's Theorem la MathWorld.

Legături externe

• Materiale media legate de probleme de împachetare la Wikimedia Commons
• en Optimizing Three-Dimensional Bin Packing
• en API for 3D bin packing
• en 3D Boxes and Cylinders packing with telescoping

Many puzzle books as well as mathematical journals contain articles on packing problems.

• en Links to various MathWorld articles on packing
• en MathWorld notes on packing squares.
• en Erich's Packing Center
• en www.packomania.com A site with tables, graphs, calculators, references, etc.
• en "Box Packing" by Ed Pegg, Jr., the Wolfram Demonstrations Project, 2007.
• en Best known packings of equal circles in a circle, up to 1100
• en Circle packing challenge problem in Python