Konténer csomagolási probléma

A konténerezési probléma NP - kemény kombinatorikus probléma. A feladat az előre meghatározott alakú objektumok véges számú előre meghatározott alakú konténerbe történő becsomagolása oly módon, hogy a felhasznált konténerek száma a legkisebb legyen, vagy az objektumok száma vagy térfogata (az a csomag) a legnagyobb legyen.

Fajták és módszerek a csomagolási problémák megoldására

Ennek a problémának számos változata létezik ( kétdimenziós csomagolás , lineáris csomagolás , tömeg szerinti csomagolás , érték szerinti csomagolás stb.), amelyek különböző területeken alkalmazhatók, mint például konténerek optimális feltöltése, teherautók súlykorlátozással történő rakodása, létrehozása redundáns másolatok cserélhető adathordozón stb. Mivel a probléma NP-nehéz , a pontos felsorolási algoritmus csak kis méretek esetén lehetséges. Általában heurisztikus közelítő polinomiális algoritmusokat használnak a probléma megoldására.

Az egydimenziós, azonos konténerekbe való csomagolás problémája

A probléma leírása

Legyen egy méretű tárolókészlet és egy méretű objektumkészlet . Meg kell találni egy egész számú tárolót és a halmaz részhalmazokra való felosztását úgy, hogy minden . Egy megoldást akkor nevezünk optimálisnak, ha minimális. A minimumot tovább jelöli az OPT . $V$ $n$ $a_1,\pontok,a_n$ $B$ $\{1,\pontok,n\}$ $B$ $S_1 \csésze \pontok \csésze S_B$ $\sum_{i \in S_k} a_i \leq V$ $k=1,\pontok,B$ $B$ $B$

Csomagolás egészszámú programozási problémaként

A konténerezési probléma egészszámú programozási problémaként a következőképpen fogalmazható meg:

Minimalizálás $B = \sum_{i=1}^n y_i$
korlátozások alatt	$\sum_{j=1}^n a_j x_{ij} \leq V y_i,$	$\mindig \in \{1,\ldots,n\}$
	$\sum_{i=1}^n x_{ij} = 1,$	$\forall j \in \{1,\ldots,n\}$
	$y_i \in\{0,1\},$	$\mindig \in \{1,\ldots,n\}$
	$x_{ij} \in \{0,1\},$	$\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}$

hol , ha a tárolóedényt használják , és ha a tételt a konténerbe helyezték . [egy] $y_i = 1$ $én$ $x_{ij} = 1$ $j$ $én$

Hozzávetőleges polinomiális algoritmusok

A legegyszerűbb polinomiális csomagolási algoritmusok a Best Fit Decreasing - BFD (Best Fit Descending) és a First Fit Decreasing - FFD (First Fit Descending). A tételeket nem növekvő méretben válogatják, és egymás után csomagolják vagy egy tartályba, amelyben a csomagolás után a legkisebb szabad térfogat marad - BFD, vagy az első konténerbe, ahová elhelyezik - FFD. Ezek az algoritmusok legfeljebb bizonyítottan használhatók

$\frac{11}{9}OPT + 1$

konténerek [2] .

Vannak azonban aszimptotikusan ε -optimális polinomiális algoritmusok is a csomagolási problémára.

Annak meghatározása, hogy az OPT kettő vagy három, NP-nehéz. Ezért minden ε > 0 esetén nehéz a tételeket (3/2 − ε)OPT tartályokba csomagolni. (Ha létezik ilyen polinomiális algoritmus, akkor polinom időben meg lehet határozni, hogy n nemnegatív szám osztódik-e két halmazra azonos elemösszeggel. Ez a probléma azonban köztudottan NP-nehéz.) Ezért, ha P nem esik egybe NP-vel, akkor a csomagolási problémára nincs Approximate Polynomial Time SchemePTAS ( . Másrészt bármely ε >0 esetén lehet olyan megoldást találni, amelyben polinomiális időben legfeljebb (1 + ε)OPT + 1 konténer található. Az ilyen algoritmusok az aszimptotikus PTAS-hoz tartoznak. [3] Mivel azonban mindkét konstans tetszőlegesen függ ε-tól az algoritmusok ezen osztályának komplexitásának becslésében, az ilyen algoritmusok, ellentétben az FFD-vel és a BFD-vel, gyakorlatilag használhatatlanok lehetnek. $an^b$

Valószínűségi megközelítés

A csomagolt tételek méretének valószínűségi eloszlásának egy bizonyos osztályához , beleértve a felfelé és lefelé konvex eloszlásfüggvényeket, létezik egy gyakorlatias polinomiális csomagolási algoritmus, amely szinte biztosan aszimptotikusan optimális , mivel az elemek száma korlátlanul növekszik. Az ebbe az osztályba nem tartozó eloszlások számára egyedi polinomiális aszimptotikusan optimális algoritmusok szerkeszthetők. [négy]

Jegyzetek

↑ Silvano Martello és Paolo Toth. Hátizsákproblémák (neopr.) . - Chichester, Egyesült Királyság: John Wiley and Sons , 1990. - P. 221. - ISBN 0471924202 .
↑ Yue, Minyi (1991), Az FFD(L) ≤ (11/9)OPT(L) + 1 egyenlőtlenség egyszerű bizonyítéka, minden L-re, az FFD bin-packing algoritmusra , Az FFD egyenlőtlenség egyszerű bizonyítéka (L) ≤ 11/9 OPT (L) + 1, ∀L az FFD tárolóedény-csomagoló algoritmushoz, Acta Mathematicae Applicatae Sinica T. 7 (4): 321-331, ISSN 0168-9673 , DOI 10.10207/96F
↑ Fernandez de la Vega, W. & Lueker, GS (1981), A tárolóedények csomagolása lineáris időben 1 + ε-n belül megoldható, a ládacsomagolás lineáris időben 1 + ε-n belül megoldható, Combinatorica (Springer Berlin / Heidelberg) . — V. 1 (4): 349–355, ISSN 0209-9683 , DOI 10.1007/BF02579456
↑ A. V. Szmirnov. A konténerekbe való csomagolás problémájáról. UMN, 1991, 46. kötet, 4. szám (280), 173–174. oldal. . Hozzáférés dátuma: 2016. február 19. Az eredetiből archiválva : 2016. március 7. (határozatlan)

Lásd még

Csomagolási feladatok
Csomagolási körök	Körben / derékszögű háromszögben / egyenlő szárú derékszögű háromszögben / négyzetben Apollonius szőnyeg Körcsomagolási tétel Tammes probléma (a szférában)
Léggömb csomagolás	Apolloniev egy bálban sűrű csomagolás elérhetőség Gömb alakú csomagolási határ (Hamming)
Egyéb csomagok	A konténerekhez Tetraéder Készletek
Kirakós játék	Conway Slotobera - Graatsma

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma