Pakkaustehtävät

Pakkausongelmat ovat matematiikan  optimointiongelmia, jotka yrittävät pakata esineitä kontteihin. Pakkaamisen tavoitteena on joko pakata yksi kontti mahdollisimman tiiviisti tai pakata kaikki esineet mahdollisimman pienellä määrällä kontteja. Monet näistä tehtävistä voivat liittyä todellisiin pakkaus- , varastointi- ja kuljetusongelmiin. Jokaisella pakkausongelmalla on kaksoispeitto- ongelma , joka kysyy, kuinka monta tuotetta tarvitaan peittämään säiliön kaikki alueet kokonaan, kun taas tuotteet voivat mennä päällekkäin.

Pakkausongelma määrittelee:

• "säiliöt" (yleensä yksi 2D- tai 3D-kupera alue tai ääretön alue)
• joukko "esineitä", joista osa tai kaikki on pakattava yhteen tai useampaan säiliöön. Sarja voi sisältää useita tietyn kokoisia objekteja tai yhden kiinteän kokoisen objektin, jota voidaan käyttää useita kertoja.

Tyypillisesti pakkauksessa esineet eivät saa leikkiä eivätkä esineet ylittää kontin seiniä. Joissakin suoritusmuodoissa tavoitteena on löytää konfiguraatio, joka pakkaa yhden säiliön suurimmalla tiheydellä. Yleisemmällä tasolla tavoitteena on pakata kaikki esineet mahdollisimman harvoihin astioihin [1] . Joissakin suoritusmuodoissa päällekkäisyys (objektien päällekkäin ja/tai säiliön reunoilla) on sallittu, mutta tämä päällekkäisyys tulisi minimoida.

Infinite Space Packing

Monet näistä ongelmista, jos säiliön koko kasvaa kaikkiin suuntiin, vastaavat esineiden mahdollisimman tiheän pakkaamisen ongelmia äärettömässä euklidisessa avaruudessa . Tämä ongelma kuuluu useille tieteenaloille ja saa paljon huomiota. Keplerin olettamus oletti optimaalisen ratkaisun pallojen pakkaamiseen satoja vuosia ennen kuin Thomas Hales todisti sen . Muut muodot ovat saaneet huomiota, mukaan lukien ellipsoidit [2] , platoniset ja arkimedelaiset kiinteät aineet [3] , mukaan lukien tetraedrit [4] [5] ja eri pallojen dimeerit [6] .

Ympyröiden kuusikulmainen pakkaus

Nämä tehtävät ovat matemaattisesti erilaisia ​​kuin ympyrän pakkauslauseen ideat . Tähän liittyvä ympyräpakkausongelma koskee mahdollisesti erikokoisten ympyröiden pakkaamista pinnalle, kuten tasolle tai pallolle.

Ympyrän analogeja muissa ulottuvuuksissa ei voida pakata absoluuttisella tehokkuudella mitoissa , jotka ovat suurempia kuin 1 (yksiulotteisessa avaruudessa ympyrän analogi on vain kaksi pistettä). Siten vain ympyröissä pakatessa jää aina tyhjää tilaa. Tehokkain tapa pakata ympyröitä, kuusikulmainen pakkaus , on noin 91 % :n tehoinen [7] .

Pallopakkaus suuremmissa mitoissa

Kolmiulotteisessa avaruudessa kasvokeskeinen hila antaa optimaalisen pallopakkauksen. On osoitettu, että 8-ulotteinen hila E8 ja 24-ulotteinen Leach-hila ovat optimaaliset vastaavissa tiloissa.

Platonisten kiintoaineiden pakkaus kolmessa ulottuvuudessa

Kuutiot voidaan helposti sijoittaa 3D-avaruuteen niin, että ne täyttävät tilan kokonaan. Luonnollisin pakkaus on kuutiometriset kennot . Mikään muu säännöllinen monitahoinen ei voi täyttää tilaa kokonaan, mutta joitakin tuloksia tiedetään. Tetraedri voi antaa vähintään 85 % täytön. Yksi parhaista säännöllisistä dodekaedritiivisteistä perustuu edellä mainittuun kasvokeskeiseen kuutiohilaan.

Tetraedrit ja oktaedrit voivat yhdessä täyttää koko tilan konfiguraatiossa, joka tunnetaan nimellä tetraedri-oktaedrilaatoitus .

Runko	Optimaalinen hilan pakkaustiheys
ikosahedra	0,836357… [8]
dodekaedrit	[kahdeksan]
oktaedrit	18/19 = 0,947368… [9]

Paikallisia parannusmenetelmiä ja satunnaisesti generoituja pakkauksia yhdistävä mallinnus viittaa siihen, että ikosaedrin, dodekaedrin ja oktaedrin hilapakkaukset ovat optimaalisia myös laajemmassa kaikkien täytteiden luokassa [3] .

Pakkaaminen 3D-säiliöihin

Pallot euklidisessa pallossa

Ongelma löytää pienin pallo, johon avoimet yksikköpallot voidaan pakata ilman päällekkäisyyttä , on yksinkertainen ja täydellinen vastaus -ulotteisessa euklidisessa avaruudessa, jos , ja äärettömässä ulottuvuudessa Hilbert-avaruudessa - ilman rajoituksia. On järkevää kuvata se tässä yleisen ongelman osoittamiseksi. Tässä tapauksessa pareittain koskettavien yksikköpallojen konfigurointi on mahdollista. Keskipisteet sijoitetaan säännöllisen ulotteisen simpleksin, jonka reuna on 2, kärkipisteisiin. Tämä on helppo tehdä ortonormaalisesta perustasta alkaen. Helpot laskelmat osoittavat, että etäisyys mistä tahansa kärjestä painopisteeseen on . Lisäksi millä tahansa muulla avaruuden pisteellä on suurempi etäisyys ainakin yhteen kärkeen. Mitä tulee pallojen sisällyttämiseen, pisteisiin keskitetyt avoimet yksikköpallot putoavat palloon, jonka säde on minimaalinen tällaisessa kokoonpanossa.

Osoittaaksemme, että tällainen kokoonpano on optimaalinen, oletetaan, että  ne ovat ei-leikkautuvien avointen pallojen keskipisteet, jotka sijaitsevat pallossa, jonka säde on keskitetty . Harkitse kartoitusta äärellisestä joukosta , joka kartoittaa kaikille . Koska kaikille , tämä kuvaus on 1-Lipschitz ja Kirschbrownin lauseen mukaan se ulottuu globaalisti määriteltyyn 1-Lipschitz-kuvaukseen. Erityisesti on olemassa kohta sellainen, että kaikille meillä on , ja siten . Tämä osoittaa, että sädepallossa on ei-leikkausyksikön avoimia palloja, jos ja vain jos . Huomaa, että äärettömän ulottuvuuden Hilbert-avaruuden tapauksessa tämä tarkoittaa, että sädepallon sisällä on ääretön määrä ei-leikkausyksikön avoimia palloja, jos ja vain jos . Esimerkiksi yksikköpallot, joiden keskipiste on , jossa  on ortonormaali kanta, eivät leikkaa ja sisältyvät palloon, jonka säde on keskitetty origoon. Lisäksi ei-leikkautuvien avointen pallojen enimmäismäärälle pallon sisällä, jonka säde on r, on yhtä suuri kuin .

Pallot kuutiomuodossa

Tehtävä määrittää halkaisijaltaan d olevien pallomaisten kappaleiden lukumäärän, jotka voidaan pakata kuutioon , jonka koko on a  ×  b  ×  c .

Identtiset pallot sylinterissä

Tehtävä määrittää sylinterin minimikorkeuden h tietyllä säteellä R , johon on pakattu n identtistä kuulaa, joiden säde on r (< R ) [10] .

Pakkaus 2D-säiliöihin

Pakkaavat ympyrät