Verpakkingsproblemen - Packing problems

Bollen of cirkels die losjes (boven) en dichter (onder) zijn verpakt

Onderdeel van een serie over
Puzzels
Types raden raadsel Situatie Logica dissectie Inductie Logisch raster Zelfreferentie Mechanisch Combinatie Bouw ontwarring Slot Go problemen Vouwen Stok Tegels Tour schuiven Schaken Doolhof  ( Logisch doolhof ) Woord en nummer Kruiswoordraadsel Sudoku Puzzelvideogames Doolhoven Metapuzzels
Onderwerpen Denkspelletje Dilemma Optische illusie Verpakkingsproblemen Paradox Probleemoplossing Puzzeljacht Syllogisme outside-the-box denken
Lijsten Onmogelijke puzzels Doolhof videogames Nikolai-puzzels Puzzelvideogames Puzzelonderwerpen
v t e

Verpakkingsproblemen zijn een klasse van optimalisatieproblemen in de wiskunde waarbij wordt geprobeerd objecten samen in containers te verpakken. Het doel is om ofwel een enkele container zo dicht mogelijk te verpakken of alle objecten in te pakken met zo min mogelijk containers. Veel van deze problemen kunnen te maken hebben met levensechte verpakkings- , opslag- en transportproblemen. Elke verpakking probleem een dubbele bedekking probleem , waarin wordt gevraagd hoeveel van dezelfde voorwerpen moeten alle van de houder, waarbij voorwerpen mogen overlappen volledig te bedekken.

Bij een probleem met het inpakken van een bak krijgt u:

• 'containers' (meestal een enkel twee- of driedimensionaal convex gebied of een oneindige ruimte)
• Een set 'objecten' waarvan sommige of alle in een of meer containers moeten worden verpakt. De set kan verschillende objecten bevatten waarvan de afmetingen zijn gespecificeerd, of een enkel object met een vaste afmeting dat herhaaldelijk kan worden gebruikt.

Gewoonlijk moet de verpakking zonder overlappingen tussen goederen en andere goederen of de containerwanden zijn. In sommige varianten is het de bedoeling om de configuratie te vinden die een enkele container met de maximale dichtheid verpakt. Meestal is het de bedoeling om alle objecten in zo min mogelijk containers te verpakken. In sommige varianten is overlapping (van objecten met elkaar en/of met de begrenzing van de container) toegestaan, maar moet deze worden geminimaliseerd.

Verpakken in oneindige ruimte

Veel van deze problemen worden, wanneer de containergrootte in alle richtingen wordt vergroot, gelijk aan het probleem om objecten zo dicht mogelijk in een oneindige Euclidische ruimte te verpakken . Dit probleem is relevant voor een aantal wetenschappelijke disciplines en heeft veel aandacht gekregen. Het vermoeden van Kepler vooronderstelde een optimale oplossing voor het verpakken van bollen honderden jaren voordat het door Thomas Callister Hales werd bewezen dat het juist was . Veel andere vormen hebben aandacht gekregen, waaronder ellipsoïden, Platonische en Archimedische lichamen, waaronder tetraëders , statieven (verenigingen van kubussen langs drie positieve as-parallelle stralen) en ongelijke bol dimeren.

Zeshoekige pakking van cirkels

De hexagonale pakking van cirkels op een 2-dimensionaal Euclidische vlak.

Deze problemen zijn wiskundig verschillend van de ideeën in de cirkelverpakkingsstelling . De bijbehorende cirkel verpakking probleem zich bezig met het verpakken van cirkels, eventueel van verschillende grootte, op een oppervlak, bijvoorbeeld het vliegtuig of een bol.

De tegenhangers van een cirkel in andere dimensies kunnen nooit met volledige efficiëntie worden verpakt in dimensies groter dan één (in een eendimensionaal universum is de cirkelanaloog slechts twee punten). Dat wil zeggen, er zal altijd ongebruikte ruimte zijn als u alleen cirkels inpakt. De meest efficiënte manier om cirkels te verpakken, zeshoekige pakking , levert een efficiëntie van ongeveer 91% op.

Bolpakkingen in hogere afmetingen

In drie dimensies bieden dicht opeengepakte structuren de beste roosterverpakking van bollen en wordt aangenomen dat deze de optimale van alle pakkingen is. Bij 'eenvoudige' bolpakkingen in drie dimensies ('eenvoudig' wordt zorgvuldig gedefinieerd) zijn er negen mogelijke definieerbare pakkingen. Het 8-dimensionale E8-rooster en 24-dimensionale Leech-rooster zijn ook bewezen optimaal te zijn in hun respectieve echte dimensionale ruimte.

Verpakkingen van platonische lichamen in drie dimensies

Kubussen kunnen gemakkelijk worden gerangschikt om de driedimensionale ruimte volledig te vullen, de meest natuurlijke verpakking is de kubieke honingraat . Geen enkel ander platonisch lichaam kan op zichzelf de ruimte betegelen, maar er zijn enkele voorlopige resultaten bekend. Tetraëders kunnen een pakking van minimaal 85% bereiken. Een van de beste verpakkingen van reguliere dodecaëders is gebaseerd op het eerder genoemde face-centered cubic (FCC) rooster.

Tetraëders en octaëders kunnen samen alle ruimte vullen in een opstelling die bekend staat als de tetraëdrische-octaëdrische honingraat .

Simulaties die lokale verbeteringsmethoden combineren met willekeurige pakkingen suggereren dat de roosterpakkingen voor icosaëders, dodecaëders en octaëders optimaal zijn in de bredere klasse van alle pakkingen.

Verpakken in driedimensionale containers

Verschillende blokken in een balk

Bepaal het minimum aantal kubusvormige containers (bakken) dat nodig is om een ​​bepaalde set artikelblokken te verpakken (3 dimensionale rechthoeken). De te verpakken rechthoekige blokken kunnen op elke as 90 graden worden gedraaid.

Bollen in een Euclidische bal

Het probleem van het vinden van de kleinste bal zodat onsamenhangende open eenheidsballen erin kunnen worden verpakt, heeft een eenvoudig en volledig antwoord in -dimensionale Euclidische ruimte als , en in een oneindig dimensionale Hilbertruimte zonder beperkingen. Het is de moeite waard om hier een gedetailleerde beschrijving te geven, om een ​​idee te geven van het algemene probleem. In dit geval is een configuratie van paarsgewijze raakeenheidkogels beschikbaar. Plaats de middelpunten op de hoekpunten van een regelmatige dimensionale simplex met rand 2; dit is eenvoudig te realiseren vanuit een orthonormale basis. Een kleine berekening laat zien dat de afstand van elk hoekpunt tot het zwaartepunt . Bovendien heeft elk ander punt van de ruimte noodzakelijkerwijs een grotere afstand tot ten minste één van de hoekpunten. In termen van insluitingen van ballen, zijn de ballen van de open eenheid gecentreerd in een bal met een straal , die minimaal is voor deze configuratie. ${\displaystyle k}$${\displaystyle n}$${\displaystyle k\leq n+1}$${\displaystyle k}$${\displaystyle a_{1},\dots ,a_{k}}$${\displaystyle (k-1)}$${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle a_{1},\dots ,a_{k}}$${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$

Laten we , om aan te tonen dat deze configuratie optimaal is, de middelpunten van onsamenhangende open eenheidskogels bevatten in een kogel met een straal gecentreerd op een punt . Beschouw de kaart van de eindige verzameling tot het nemen van de corresponderende voor elk . Daar alle , deze kaart is 1-Lipschitz en de Kirszbraun stelling zij zich uitstrekt tot een 1-Lipschitz map die wereldwijd wordt gedefinieerd; in het bijzonder bestaat er een punt zodanig dat voor alles men heeft , zodat ook . Dit toont aan dat er disjuncte eenheids open ballen zijn in een bal met een straal als en slechts als . Merk op dat in een oneindig dimensionale Hilbertruimte dit impliceert dat er oneindig veel onsamenhangende open eenheidsballen zijn binnen een bal met straal als en slechts als . Bijvoorbeeld, de eenheidsballen gecentreerd op , waar een orthonormale basis is, zijn disjunct en opgenomen in een bal met een straal gecentreerd op de oorsprong. Bovendien, voor , het maximale aantal onsamenhangende open eenheidsballen binnen een bal met straal r is . ${\displaystyle x_{1},\stippen ,x_{k}}$${\displaystyle k}$${\displaystyle r}$${\displaystyle x_{0}}$${\displaystyle \{x_{1},\dots ,x_{k}\}}$${\displaystyle \{a_{1},\dots ,a_{k}\}}$${\displaystyle x_{j}}$${\displaystyle a_{j}}$${\displaystyle 1\leq j\leq k}$${\displaystyle 1\leq i<j\leq k}$${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$${\displaystyle a_{0}}$${\displaystyle 1\leq j\leq k}$${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$${\displaystyle k}$${\displaystyle r}$${\displaystyle r\geq r_{k}}$${\displaystyle r}$${\displaystyle r\geq 1+{\sqrt {2}}}$${\displaystyle {\sqrt {2}}e_{j}}$${\displaystyle \{e_{j}\}_{j}}$${\displaystyle 1+{\sqrt {2}}}$${\displaystyle r<1+{\sqrt {2}}}$${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$

Bollen in een balk

Bepaal het aantal bolvormige objecten met een gegeven diameter d dat kan worden verpakt in een balk met de grootte a × b × c .

Identieke bollen in een cilinder

Bepaal de minimale hoogte h van een cilinder met gegeven straal R die n identieke bollen met straal r (< R ) zal pakken . Voor een kleine straal R schikken de bollen in geordende structuren, zuilvormige structuren genoemd .

Veelvlakken in bollen

Bepaal de minimale straal R die verpakken n identiek eenheidsvolume veelvlakken van een bepaalde vorm.

Verpakken in 2-dimensionale containers

De optimale verpakking van 10 cirkels in een cirkel

Er zijn veel varianten van 2-dimensionale verpakkingsproblemen bestudeerd. Zie de gelinkte pagina's voor meer informatie.

Inpakken van cirkels

Je krijgt n eenheidscirkels en moet ze in de kleinst mogelijke container verpakken. Er zijn verschillende soorten containers onderzocht:

• Cirkels in een cirkel inpakken - nauw verwant aan het spreiden van punten in een eenheidscirkel met als doel de grootste minimale scheiding, d _n , tussen punten te vinden. Optimale oplossingen zijn bewezen voor n  ≤ 13 en  n  = 19.
• Het inpakken van cirkels in een vierkant - nauw verwant aan het spreiden van punten in een eenheidsvierkant met als doel de grootste minimale scheiding, d _n , tussen punten te vinden. Om tussen deze twee formuleringen van het probleem om te rekenen, is de vierkante zijde voor eenheidscirkels L  = 2 + 2/ d _n .
  

  De optimale verpakking van 15 cirkels in een vierkant
  Optimale oplossingen zijn bewezen voor n  ≤ 30.
• Verpakkingscirkels in een gelijkbenige rechthoekige driehoek - goede schattingen zijn bekend voor n <300.
• Verpakkingscirkels in een gelijkzijdige driehoek - Optimale oplossingen zijn bekend voor n <13, en vermoedens zijn beschikbaar voor n  <28.

Verpakken van vierkanten

U krijgt n eenheidsvierkanten en moet deze in de kleinst mogelijke container verpakken, waarbij het containertype varieert:

• Kwadraten in een vierkant verpakken : Optimale oplossingen zijn bewezen voor n  = 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 en elk vierkant geheel getal. De verspilde ruimte is asymptotisch O ( a ^7/11 ).
• Vierkantjes in een cirkel verpakken : Er zijn goede oplossingen bekend voor n tot en met 35.
  

  De optimale verpakking van 10 vierkanten in een vierkant

Verpakking van rechthoeken

• Identieke rechthoeken in een rechthoek verpakken: Het probleem van het verpakken van meerdere exemplaren van een enkele rechthoek van formaat ( l , w ), waardoor 90 ° rotatie mogelijk is, in een grotere rechthoek van formaat ( L , W ) heeft enkele toepassingen, zoals het laden van dozen op pallets en in het bijzonder de opslag van houtpulp . Het is bijvoorbeeld mogelijk om 147 rechthoeken van formaat (137,95) in een rechthoek van formaat (1600,1230) te verpakken.
• Verschillende rechthoeken in een rechthoek verpakken: Het probleem van het inpakken van meerdere rechthoeken van verschillende breedtes en hoogtes in een omsluitende rechthoek met een minimale oppervlakte (maar zonder grenzen aan de breedte of hoogte van de omsluitende rechthoek) heeft een belangrijke toepassing bij het combineren van afbeeldingen tot een enkele grotere afbeelding . Een webpagina die een enkele grotere afbeelding laadt, wordt vaak sneller weergegeven in de browser dan dezelfde pagina die meerdere kleine afbeeldingen laadt, vanwege de overhead die gepaard gaat met het opvragen van elke afbeelding van de webserver. Het probleem is over het algemeen NP-compleet, maar er zijn snelle algoritmen voor het oplossen van kleine gevallen.

Gerelateerde velden

Bij tegel- of mozaïekproblemen mogen er geen gaten of overlappingen zijn. Veel van de puzzels van dit type omvatten het inpakken van rechthoeken of polyomino's in een grotere rechthoek of een andere vierkantachtige vorm.

Er zijn belangrijke stellingen over het betegelen van rechthoeken (en balkjes) in rechthoeken (kubussen) zonder openingen of overlappingen:

Een a × b- rechthoek kan worden verpakt met 1 × n stroken als n deelt a of n deelt b .

Stelling van de Bruijn : Een doos kan worden verpakt met een harmonische steen a × ab × abc als de doos de afmetingen ap × abq × abcr heeft voor sommige natuurlijke getallen p , q , r (dwz de doos is een veelvoud van de steen.)

De studie van polyomino- tegels betreft grotendeels twee klassen van problemen: een rechthoek betegelen met congruente tegels, en een van elke n -omino in een rechthoek verpakken.

Een klassieke puzzel van de tweede soort is om alle twaalf pentomino's te rangschikken in rechthoeken van 3×20, 4×15, 5×12 of 6×10.

Inpakken van onregelmatige voorwerpen

Het verpakken van onregelmatige voorwerpen is een probleem dat zich niet goed leent voor oplossingen in gesloten vorm; de toepasbaarheid op praktische milieuwetenschap is echter vrij belangrijk. Onregelmatig gevormde bodemdeeltjes pakken bijvoorbeeld anders in naarmate de grootte en vorm variëren, wat leidt tot belangrijke resultaten voor plantensoorten om wortelformaties aan te passen en waterbeweging in de bodem mogelijk te maken.

Het probleem om te beslissen of een bepaalde reeks polygonen in een bepaalde vierkante container kan passen, is volledig gebleken voor de existentiële theorie van de reële getallen .

Zie ook

• Inpakken instellen
• Bakverpakkingsprobleem
• Slothouber–Graatsma puzzel
• Conway puzzel
• Tetris
• Dekkingsprobleem
• Knapzak probleem
• Tetraëder verpakking
• Ellipsoïde verpakking
• Probleem met snijvoorraad
• Kussen nummer probleem
• Nauwe verpakking van gelijke bollen
• Willekeurig sluiten pakket
• Stripverpakkingsprobleem

Opmerkingen:

Referenties

• Weisstein, Eric W. "De stelling van Klarner" . MathWereld .
• Weisstein, Eric W. "De stelling van Bruijn" . MathWereld .

Externe links

• Optimalisatie van driedimensionale bakverpakking
• API voor 3D-bakverpakking
• 3D dozen en cilinders verpakken met telescopische

Veel puzzelboeken en wiskundige tijdschriften bevatten artikelen over verpakkingsproblemen.

• Links naar verschillende MathWorld-artikelen over inpakken
• MathWorld-aantekeningen over het inpakken van vierkanten.
• Erich's inpakcentrum
• www.packomania.com Een site met tabellen, grafieken, rekenmachines, referenties, enz.
• "Box Packing" door Ed Pegg, Jr. , het Wolfram Demonstration Project , 2007.
• Meest bekende pakkingen van gelijke cirkels in een cirkel, tot 1100

• Probleem met cirkelverpakkingsuitdaging in Python