Csomagolási feladatok

A csomagolási problémák  az optimalizálási problémák egy osztálya a matematikában , amelyek az objektumokat konténerekbe próbálják csomagolni. A csomagolás célja vagy egyetlen edény minél szorosabb becsomagolása, vagy az összes tárgy becsomagolása a lehető legkevesebb konténer felhasználásával. E feladatok közül sok a valós csomagolási , raktározási és szállítási problémákhoz kapcsolódhat. Minden csomagolási problémának van egy kettős lefedettségi problémája , amely azt kérdezi, hány darab kell ahhoz, hogy teljesen lefedje a tartály összes területét, miközben a tételek átfedhetik egymást.

A csomagolási probléma a következőket írja le:

• "tárolók" (általában egyetlen 2D vagy 3D konvex régió vagy végtelen terület)
• "tárgyak" halmaza, amelyek egy részét vagy mindegyikét egy vagy több tartályba kell csomagolni. Egy készlet tartalmazhat különböző, adott méretű objektumokat, vagy egyetlen rögzített méretű objektumot, amely többször használható.

Jellemzően egy csomagban a tárgyak nem metszhetik egymást, és a tárgyak nem keresztezhetik a konténer falát. Egyes kiviteli alakoknál a cél egy olyan konfiguráció megtalálása, amely egy tartályt maximális sűrűséggel csomagol. Általánosabban fogalmazva, a cél az, hogy az összes objektumot a lehető legkevesebb konténerbe csomagolják [1] . Egyes kiviteli alakoknál az átfedés (az egymás tetején és/vagy a tartály határain lévő objektumok) megengedett, de ezt az átfedést minimálisra kell csökkenteni.

Infinite Space Packing

E problémák közül sok, ha a tartály mérete minden irányban növekszik, egyenértékűvé válik az objektumok lehető legsűrűbben történő becsomagolásával a végtelen euklideszi térben . Ez a probléma számos tudományághoz tartozik, és jelentős figyelmet kap. Kepler sejtése optimális megoldást feltételezett a golyók becsomagolására több száz évvel azelőtt, hogy ezt Thomas Hales bebizonyította volna . Más alakzatokra is felfigyeltek, köztük ellipszoidokra [2] , platóni és arkhimédeszi szilárd testekre [3] , köztük tetraéderekre [4] [5] és különböző gömbök dimereire [ 6] .

Körök hatszögletű tömörítése

Ezek a problémák matematikailag eltérnek a körcsomagolási tétel elképzeléseitől . Egy ehhez kapcsolódó körtömítési probléma az esetlegesen különböző méretű körök felületre, például síkra vagy gömbre való pakolásával foglalkozik .

A kör más dimenziójú analógjai nem pakolhatók abszolút hatékonysággal 1-nél nagyobb méretekben (egydimenziós térben a kör analógja mindössze két pont). Így mindig lesz szabad hely, ha kizárólag körbe pakolunk. A körök tömörítésének leghatékonyabb módja, a hatszögletű tömörítés körülbelül 91%-os hatékonyságú [7] .

Gömbcsomagolás nagyobb méretekben

A 3D-s térben az arc- központú rács a gömbök optimális tömörítését adja. Bebizonyosodott, hogy a 8-dimenziós E8 és a 24-dimenziós Leach-rács optimális a megfelelő terekben.

Platóni szilárd anyagok csomagolása három dimenzióban

A kockák könnyen elhelyezhetők a 3D térben, így teljesen kitöltik a teret. A legtermészetesebb csomagolás a köbös méhsejt . Egyetlen más szabályos poliéder sem tudja teljesen kitölteni a teret, de néhány eredmény ismert. Egy tetraéder legalább 85%-os töltetet adhat. Az egyik legjobb szabályos dodekaéder töltet a fent említett arcközpontú köbös rácson alapul.

A tetraéderek és az oktaéderek együtt képesek kitölteni az egész teret a tetraéder-oktaéder burkolatként ismert konfigurációban .

Test	Optimális rácsos tömörítési sűrűség
ikozaéder	0,836357… [8]
dodekaéderek	[nyolc]
oktaéderek	19/18 = 0,947368… [9]

A lokális fejlesztési módszereket véletlenszerűen generált pakolással kombináló modellezés azt sugallja, hogy az ikozaéder, a dodekaéder és az oktaéder rácsos tömítései is optimálisak az összes tömörítés szélesebb osztályában [3] .

Csomagolás 3D konténerekbe

Gömbök egy euklideszi gömbben

Arra a problémára, hogy megtaláljuk azt a legkisebb golyót, amelybe a nyitott egységnyi golyókat átfedés nélkül lehet pakolni, egyszerű és teljes válasz van a -dimenziós euklideszi térben, ha , és a végtelen dimenziós Hilbert-térben - korlátozás nélkül. Érdemes itt leírni az általános probléma bemutatása érdekében. Ebben az esetben páronként összeérő egységgolyók konfigurációja lehetséges. A középpontokat egy szabályos dimenziójú szimplex 2-es élű csúcsaiba helyezzük. Ez ortonormális alapból indulva könnyen megtehető. Az egyszerű számítások azt mutatják, hogy bármely csúcs és a súlypont távolsága . Ezenkívül a tér bármely más pontja nagyobb távolságra van legalább az egyik csúcstól. Ami a golyókat illeti, a pontokon középre helyezett nyitott egységgolyók egy sugarú golyóba esnek , ami minimális egy ilyen konfigurációnál.

Annak bizonyítására, hogy egy ilyen konfiguráció optimális, tegyük fel, hogy  azok a nem metsző, nyitott egységgolyók középpontjai, amelyek egy olyan gömbben helyezkednek el, amelynek sugara középpontja . Tekintsünk egy véges halmazból a mindenre leképezést . Mivel minden , esetén ez a leképezés 1-Lipschitz , és a Kirschbrown-tétel szerint egy globálisan meghatározott 1-Lipschitz-leképezésre is kiterjed. Konkrétan létezik olyan pont , hogy mindenre , amink van , és így . Ez azt mutatja, hogy akkor és csak akkor vannak nem metsző egységnyi nyitott golyók egy sugarú golyóban . Vegyük észre, hogy egy végtelen dimenziós Hilbert-tér esetén ez végtelen számú, nem metsző egységnyi nyitott golyó létezését jelenti egy sugarú gömbön belül, akkor és csak akkor, ha . Például a középpontban lévő egységgömbök , ahol  egy ortonormális alap, nem metszik egymást, és egy sugarú golyóban vannak, amelynek középpontja az origóban van. Ezenkívül egy r sugarú golyón belül a nem metsző nyitott egységgolyók maximális száma esetén egyenlő .

Gömbök téglatestben

A feladat meghatározza, hogy egy a  ×  b  ×  c méretű téglatestbe hány adott d átmérőjű gömb alakú objektum csomagolható .

Azonos gömbök egy hengerben

A feladat meghatározza egy adott R sugarú henger minimális h magasságát, amelybe n egyforma r sugarú (< R ) golyó van becsomagolva [10] .

Csomagolás 2D konténerekbe

Csomagolási körök