Emballeringsopgaver

Pakkeproblemer  er en klasse af optimeringsproblemer i matematik , der forsøger at pakke objekter ind i beholdere. Målet med pakningen er enten at pakke en enkelt beholder så tæt som muligt, eller at pakke alle genstande med så få beholdere som muligt. Mange af disse opgaver kan relatere til virkelige emballage- , lager- og transportproblemer. Hvert pakkeproblem har et dobbeltdækningsproblem , der spørger, hvor mange genstande der skal til for fuldstændigt at dække alle områder af beholderen, mens genstandene kan overlappe hinanden.

Pakningsproblemet specificerer:

• "beholdere" (normalt en enkelt 2D- eller 3D-konveks region eller uendelig region)
• et sæt "objekter", hvoraf nogle eller alle skal pakkes i en eller flere beholdere. Et sæt kan indeholde forskellige objekter med givne størrelser eller et enkelt objekt med faste størrelser, der kan bruges flere gange.

Typisk bør genstande i en pakke ikke krydse hinanden, og genstande bør ikke krydse containervægge. I nogle udførelsesformer er målet at finde en konfiguration, der pakker én beholder med maksimal tæthed. Mere generelt er målet at pakke alle genstande i så få beholdere som muligt [1] . I nogle udførelsesformer er overlapning (af genstande oven på hinanden og/eller på beholderens grænser) tilladt, men denne overlapning bør minimeres.

Infinite Space Packing

Mange af disse problemer, hvis størrelsen af ​​beholderen øges i alle retninger, bliver ækvivalente med problemerne med at pakke genstande så tæt som muligt i det uendelige euklidiske rum . Dette problem hører til en række videnskabelige discipliner og får stor opmærksomhed. Keplers formodning postulerede en optimal løsning til at pakke bolde hundreder af år før den blev bevist af Thomas Hales . Andre former har fået opmærksomhed, herunder ellipsoider [2] , platoniske og arkimedeiske faste stoffer [3] , herunder tetraedre [4] [5] og dimerer af forskellige sfærer [6] .

Sekskantet pakning af cirkler

Disse problemer er matematisk forskellige fra ideerne i cirkelpakningssætningen . Et relateret cirkelpakningsproblem omhandler pakningen af ​​cirkler, muligvis af forskellige størrelser, på en overflade, såsom et plan eller en kugle.

Analogerne af en cirkel i andre dimensioner kan ikke pakkes med absolut effektivitet i dimensioner større end 1 (i et-dimensionelt rum er analogen af ​​en cirkel kun to punkter). Der vil således altid være ledig plads, når man udelukkende pakker i cirkler. Den mest effektive måde at pakke cirkler på, sekskantet pakning , er omkring 91 % effektiv [7] .

Kuglepakning i højere dimensioner

I 3D-rum giver et ansigtscentreret gitter en optimal pakning af kugler. Det er bevist, at det 8-dimensionelle gitter E8 og det 24-dimensionelle Leach-gitter er optimale i de tilsvarende rum.

Pakning af platoniske faste stoffer i tre dimensioner

Kuber kan nemt placeres i 3D-rum, så de fylder hele rummet. Den mest naturlige pakning er kubiske honeycombs . Ingen anden regulær polyeder kan fylde rummet helt, men nogle resultater er kendte. Et tetraeder kan give mindst 85 % pakning. En af de bedste almindelige dodecahedron -pakninger er baseret på det førnævnte ansigtscentrerede kubiske gitter.

Tetraedre og oktaeder kan sammen fylde hele rummet i en konfiguration kendt som den tetraedriske-oktaedriske flisebelægning .

Legeme	Optimal gitterpakningstæthed
icosahedra	0,836357… [8]
dodekaeder	[otte]
oktaeder	18/19 = 0,947368… [9]

Modellering, der kombinerer lokale forbedringsmetoder med tilfældigt genererede pakninger, tyder på, at gitterpakninger til icosahedron, dodecahedron og octahedron også er optimale i en bredere klasse af alle pakninger [3] .

Pakning i 3D-beholdere

Kugler i en euklidisk sfære

Problemet med at finde den mindste kugle, som åbne enhedskugler kan pakkes ind i uden at overlappe , har et enkelt og fuldstændigt svar i -dimensionelt euklidisk rum hvis , og i uendeligt dimensionelt Hilbert-rum - uden begrænsninger. Det giver mening at beskrive det her for at vise det generelle problem. I dette tilfælde er konfigurationen af ​​parvis rørende enhedskugler mulig. Vi placerer centrene ved hjørnerne af en almindelig dimensionel simplex med kant 2. Dette er let at gøre, begyndende med en ortonormal basis. Lette beregninger viser, at afstanden fra ethvert toppunkt til tyngdepunktet er . Derudover har ethvert andet punkt i rummet en større afstand til mindst et af hjørnerne. Med hensyn til inklusion af bolde falder åbne enhedskugler centreret i punkterne ind i en bold med radius , hvilket er minimalt for en sådan konfiguration.

For at vise, at en sådan konfiguration er optimal, lad os antage,  at centrene for ikke-skærende åbne enhedskugler er placeret i en kugle med radius centreret ved . Overvej en kortlægning fra et endeligt sæt til at kortlægges til for alle . Da denne kortlægning for alle , , er 1-Lipschitz , og ifølge Kirschbrown-sætningen strækker den sig til en globalt defineret 1-Lipschitz-kortlægning. Især eksisterer der et punkt sådan, at for alt hvad vi har , og dermed . Dette viser, at der er ikke-skærende enhed åbne bolde i en kugle med radius , hvis og kun hvis . Bemærk, at i tilfælde af et uendeligt dimensionelt Hilbert-rum, indebærer dette eksistensen af ​​et uendeligt antal af ikke-skærende enheds åbne kugler inde i en kugle med radius , hvis og kun hvis . For eksempel skærer enhedskugler centreret ved , hvor  er en ortonormal basis, ikke og er indeholdt i en kugle med radius centreret ved origo. Desuden, for det maksimale antal ikke-skærende åbne enhedskugler inde i en kugle med radius r er lig med .

Kugler i en kasseform

Opgaven bestemmer antallet af sfæriske objekter med en given diameter d , der kan pakkes ind i en terning af størrelsen a  ×  b  ×  c .

Identiske kugler i en cylinder

Opgaven bestemmer minimumshøjden h af en cylinder med en given radius R , hvori n identiske kugler med radius r (< R ) er pakket [10] .

Pakning i 2D-beholdere

Pakningscirkler