Balicí úkoly

Problémy s balením  jsou třídou optimalizačních problémů v matematice , které se pokoušejí zabalit objekty do kontejnerů. Cílem balení je buď zabalit jeden kontejner co nejtěsněji, nebo zabalit všechny předměty do co nejmenšího počtu kontejnerů. Mnoho z těchto úkolů se může týkat skutečných problémů s balením , skladováním a dopravou. Každý problém s balením má problém dvojího pokrytí , který se ptá, kolik položek je potřeba k úplnému pokrytí všech oblastí kontejneru, přičemž položky se mohou překrývat.

Problém s balením specifikuje:

• "kontejnery" (obvykle jedna 2D nebo 3D konvexní oblast nebo nekonečná oblast)
• soubor „předmětů“, z nichž některé nebo všechny musí být zabaleny v jedné nebo více nádobách. Sada může obsahovat různé objekty s danými velikostmi nebo jeden objekt pevných velikostí, který lze použít vícekrát.

V balíku by se objekty obvykle neměly protínat a objekty by neměly křížit stěny kontejneru. V některých provedeních je cílem nalézt konfiguraci, která zabalí jednu nádobu při maximální hustotě. Obecněji je cílem zabalit všechny předměty do co nejmenšího počtu kontejnerů [1] . V některých provedeních je povoleno překrývání (předmětů na sobě a/nebo na hranicích kontejneru), ale toto překrývání by mělo být minimalizováno.

Balení nekonečného prostoru

Mnohé z těchto problémů, pokud se velikost kontejneru zvětší ve všech směrech, se stanou ekvivalentními problémům s co nejhustším balením objektů v nekonečném euklidovském prostoru . Tento problém patří do řady vědních oborů a věnuje se mu značná pozornost. Keplerova domněnka předpokládala optimální řešení pro balení kuliček stovky let předtím, než to dokázal Thomas Hales . Pozornost si získaly i další tvary, včetně elipsoidů [2] , platónských a archimedovských těles [3] , včetně tetraedrů [4] [5] a dimerů různých koulí [6] .

Šestihranné balení kruhů

Tyto problémy se matematicky liší od myšlenek ve větě o balení kruhu . Související problém se zabalením kruhů se zabývá nabalením kruhů, případně různých velikostí, na povrchu, jako je rovina nebo koule.

Analogy kruhu v jiných dimenzích nelze sbalit s absolutní účinností v dimenzích větších než 1 (v jednorozměrném prostoru jsou analogy kruhu jen dva body). Při balení výhradně v kruzích tak bude vždy volné místo. Nejúčinnější způsob balení kruhů, šestiúhelníkové balení , je asi 91% účinný [7] .

Kulové těsnění ve vyšších rozměrech

Ve 3D prostoru poskytuje mřížka centrovaná na obličej optimální uspořádání koulí. Je dokázáno, že 8-rozměrná mřížka E8 a 24-rozměrná Leachova mřížka jsou v odpovídajících prostorech optimální.

Balení platónských těles ve třech rozměrech

Kostky lze snadno umístit do 3D prostoru tak, aby zcela vyplnily prostor. Nejpřirozenějším obalem jsou krychlové plástve . Žádný jiný pravidelný mnohostěn nemůže zcela vyplnit prostor, ale některé výsledky jsou známy. Čtyřstěn může poskytnout alespoň 85% balení. Jedna z nejlepších pravidelných dvanáctistěnových ucpávek je založena na výše zmíněné kubické mřížce centrované na plochu.

Tetraedry a oktaedry dohromady mohou zaplnit celý prostor v konfiguraci známé jako tetraedrický-oktaedrický obklad .

Tělo	Optimální hustota uložení mřížky
dvacetistěny	0,836357… [8]
dvanáctistěny	[osm]
osmistěny	18/19 = 0,947368… [9]

Modelování, které kombinuje metody lokálního zlepšování s náhodně generovanými výplněmi, naznačuje, že mřížkové výplně pro dvacetistěny, dvanáctistěny a osmistěny jsou také optimální v širší třídě všech výplní [3] .

Balení do 3D kontejnerů

Koule v euklidovské sféře

Problém najít nejmenší kouli, do které lze sbalit koule s otevřenými jednotkami bez překrývání, má jednoduchou a úplnou odpověď v -dimenzionálním euklidovském prostoru if , a v nekonečně dimenzionálním Hilbertově prostoru - bez omezení. Má smysl to zde popsat, aby se ukázal obecný problém. V tomto případě je možná konfigurace párově se dotýkajících jednotkových koulí. Středy umístíme do vrcholů pravidelného rozměrného simplexu s hranou 2. To je snadné, počínaje ortonormální bází. Snadné výpočty ukazují, že vzdálenost od libovolného vrcholu k těžišti je . Navíc jakýkoli jiný bod v prostoru má větší vzdálenost alespoň k jednomu z vrcholů. Pokud jde o zahrnutí kuliček, otevřené jednotkové koule se středem v bodech spadají do koule o poloměru , což je pro takovou konfiguraci minimální.

Abychom ukázali, že taková konfigurace je optimální, předpokládejme, že  jsou středy neprotínajících se koulí otevřených jednotek umístěných v kouli s poloměrem se středem v . Zvažte mapování z konečné množiny na mapování pro všechny . Protože pro všechny , je toto zobrazení 1-Lipschitz a podle Kirschbrownovy věty se rozšiřuje na globálně definované 1-Lipschitzovo zobrazení. Zejména existuje bod takový, že pro všechny máme , a tedy . To ukazuje, že v kouli o poloměru existují neprotínající se jednotky otevřené koule právě tehdy, když . Všimněte si, že v případě nekonečně-rozměrného Hilbertova prostoru to implikuje existenci nekonečného počtu neprotínajících se jednotkových otevřených koulí uvnitř koule o poloměru právě tehdy, když . Například jednotkové koule se středem v , kde  je ortonormální základna, se neprotínají a jsou obsaženy v kouli o poloměru se středem v počátku. Navíc pro maximální počet neprotínajících se kuliček otevřených jednotek uvnitř koule o poloměru r je rovna .

Koule v kvádru

Úloha určuje počet kulových objektů o daném průměru d , které lze sbalit do kvádru o velikosti a  ×  b  ×  c .

Identické koule ve válci

Úloha určuje minimální výšku h válce o daném poloměru R , do kterého je zabaleno n stejných kuliček o poloměru r (< R ) [10] .

Balení do 2D kontejnerů

Balící kruhy