Problemă de ambalare a containerului

Problema containerizării este o problemă combinatorie NP -hard . Sarcina este de a împacheta obiecte cu o formă predefinită într-un număr finit de containere cu o formă predefinită, astfel încât numărul de containere utilizate să fie cel mai mic sau numărul sau volumul de obiecte (acel pachet) să fie cel mai mare.

Soiuri și metode de rezolvare a problemelor de ambalare

Există multe variante ale acestei probleme ( ambalare bidimensională , ambalare liniară , ambalare în funcție de greutate , ambalare în funcție de valoare etc.) care pot fi aplicate în diferite domenii, cum ar fi umplerea optimă a containerelor, încărcarea camioanelor cu o limită de greutate, crearea copii redundante pe suporturi amovibile etc. Deoarece problema este NP-hard , utilizarea unui algoritm de enumerare exactă este posibilă numai pentru dimensiuni mici. De obicei, pentru rezolvarea problemei se folosesc algoritmi polinomii aproximativi euristici .

Problema ambalării în containere unidimensionale identice

Enunțul problemei

Să fie un set de containere de dimensiune și un set de obiecte de dimensiune . Este necesar să găsiți un număr întreg de containere și o partiție a setului în subseturi astfel încât pentru toți . O soluție se numește optimă dacă este minimă. Minimul este notat în continuare cu OPT . $V$ $n$ $a_1,\dots,a_n$ $B$ $\{1,\puncte,n\}$ $B$ $S_1 \cup \dots \cup S_B$ $\sum_{i \in S_k} a_i \leq V$ $k=1,\puncte,B$ $B$ $B$

Ambalarea ca o problemă de programare cu numere întregi

Problema containerizării poate fi formulată ca o problemă de programare cu numere întregi după cum urmează:

Minimizați $B = \sum_{i=1}^n y_i$
sub restricții	$\sum_{j=1}^n a_j x_{ij} \leq V y_i,$	$\forall i \in \{1,\ldots,n\}$
	$\sum_{i=1}^n x_{ij} = 1,$	$\forall j \in \{1,\ldots,n\}$
	$y_i \in\{0,1\},$	$\forall i \in \{1,\ldots,n\}$
	$x_{ij} \in \{0,1\},$	$\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}$

unde , dacă containerul este utilizat și , dacă articolul este plasat în container . [unu] $y_i = 1$ $i$ $x_{ij} = 1$ $j$ $i$

Algoritmi polinomii aproximativi

Cei mai simpli algoritmi de împachetare polinomială sunt Best Fit Decreasing - BFD (Best Fit Descending) și First Fit Decreasing - FFD (First Fit Descending). Articolele sunt sortate în mărime necrescătoare și ambalate succesiv fie într-un container în care, după ambalare, rămâne cel mai mic volum liber - BFD, fie în primul container în care este plasat - FFD. S-a dovedit că acești algoritmi folosesc cel mult

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

containere [2] .

Cu toate acestea, există și algoritmi polinomi asimptotic ε-optimi pentru problema de împachetare.

Problema de a determina dacă OPT este doi sau trei este NP-hard. Prin urmare, pentru orice ε > 0, este dificil să împachetați articole în containere (3/2 − ε)OPT . (Dacă există un astfel de algoritm polinomial, atunci în timp polinomial este posibil să se determine dacă n numere nenegative se împart în două mulțimi cu aceeași sumă de elemente. Cu toate acestea, se știe că această problemă este NP-hard.) Prin urmare, dacă P nu coincide cu NP, atunci pentru problema de ambalare nu există un algoritm (PTAS)de Schemă de timp polinomială aproximativă . Pe de altă parte, pentru orice ε >0, se poate găsi o soluție cu cel mult (1 + ε)OPT + 1 containere în timp polinomial. Astfel de algoritmi aparțin PTAS-ului asimptotic. [3] Dar, deoarece ambele constante depind în mod arbitrar de ε în estimarea complexității acestei clase de algoritmi, astfel de algoritmi, spre deosebire de FFD și BFD, pot fi practic inutile. $an^b$

Abordare probabilistică

Pentru o anumită clasă de distribuții de probabilitate a dimensiunilor articolelor împachetate, inclusiv funcțiile de distribuție convexe în sus și în jos, există un algoritm practic de împachetare polinomială care este optim asimptotic aproape sigur pe măsură ce numărul de articole crește la nesfârșit. Pentru distribuțiile care nu sunt incluse în această clasă, pot fi construiți algoritmi optimi asimptotic polinomi individuali. [patru]

Note

↑ Silvano Martello și Paolo Toth. Probleme la rucsac (neopr.) . - Chichester, Marea Britanie: John Wiley and Sons , 1990. - P. 221. - ISBN 0471924202 .
↑ Yue, Minyi (1991), O dovadă simplă a inegalității FFD(L) ≤ (11/9)OPT(L) + 1, pentru toate L, pentru algoritmul de împachetare FFD , O dovadă simplă a inegalității FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica T. 7 (4): 321–331, ISSN 0168-9673 , DOI 10.1007/BF0300
↑ Fernandez de la Vega, W. & Lueker, GS (1981), Bin ambalarea poate fi rezolvată în termen de 1 + ε în timp liniar , Bin ambalarea poate fi rezolvată în 1 + ε în timp liniar, Combinatorica (Springer Berlin / Heidelberg) . — V. 1 (4): 349–355, ISSN 0209-9683 , DOI 10.1007/BF02579456
↑ A. V. Smirnov. Despre problema ambalării în containere. UMN, 1991, volumul 46, numărul 4(280), paginile 173–174. . Data accesului: 19 februarie 2016. Arhivat din original pe 7 martie 2016. (nedefinit)

Vezi și

Sarcini de ambalare
Cercuri de ambalare	Într-un cerc / într-un triunghi dreptunghic / într-un triunghi dreptunghic isoscel / într-un pătrat covorul Apollonius Teorema de ambalare a cercurilor Problema Tammes (pe sferă)
Ambalare cu baloane	Apolloniev într-o minge ambalaj dens numar de contact Limită de ambalare sferică (Hamming)
Alte pachete	La containere Tetraedre Seturi
Puzzle	Conway Slotobera - Graatsma

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă