Problém s balením kontejneru

Problém kontejnerizace je NP - těžký kombinatorický problém. Úkolem je zabalit předměty předdefinovaného tvaru do konečného počtu kontejnerů předem definovaného tvaru tak, aby počet použitých kontejnerů byl nejmenší nebo počet nebo objem předmětů (toho balíčku) byl největší.

Odrůdy a metody řešení problémů s balením

Existuje mnoho variant tohoto problému ( dvourozměrné balení , lineární balení , balení podle hmotnosti , balení podle hodnoty atd.), které lze použít v různých oblastech, jako je optimální plnění kontejnerů, nakládání kamionů s omezením hmotnosti, vytváření redundantní kopie na vyměnitelná média atd. Protože problém je NP-hard , je použití přesného výčtového algoritmu možné pouze pro malé rozměry. Obvykle se k řešení problému používají heuristické přibližné polynomiální algoritmy.

Problém balení do jednorozměrných identických obalů

Prohlášení o problému

Nechť existuje množina nádob o velikosti a množina objektů o velikosti . Je potřeba najít celočíselný počet kontejnerů a rozdělení množiny do podmnožin tak, aby pro všechny . Řešení se nazývá optimální, pokud je minimální. Minimum je dále označeno OPT . $PROTI$ $n$ $a_1,\tečky,a_n$ $B$ $\{1,\tečky,n\}$ $B$ $S_1 \cup \tečky \cup S_B$ $\sum_{i \in S_k} a_i \leq V$ $k=1,\tečky,B$ $B$ $B$

Balení jako problém celočíselného programování

Problém kontejnerizace lze formulovat jako problém celočíselného programování takto:

Minimalizovat $B = \sum_{i=1}^n y_i$
pod omezeními	$\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\}$

kde , pokud je kontejner použit a pokud je položka umístěna v kontejneru . [jeden] $y_i = 1$ $i$ $x_{ij} = 1$ $j$ $i$

Přibližné polynomiální algoritmy

Nejjednoduššími polynomiálními algoritmy balení jsou Best Fit Decreasing - BFD (Best Fit Descending) a First Fit Decreasing - FFD (First Fit Descending). Položky jsou roztříděny v nezvětšujících se rozměrech a následně baleny buď do kontejneru, ve kterém po zabalení zbývá nejmenší volný objem - BFD, nebo do prvního kontejneru, kde je umístěn - FFD. Tyto algoritmy se osvědčily nanejvýš

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

kontejnery [2] .

Existují však také asymptoticky ε -optimální polynomiální algoritmy pro problém balení.

Problém určení, zda je OPT dva nebo tři, je NP-těžký. Proto je pro jakékoli ε > 0 obtížné zabalit položky do (3/2 − ε)OPT kontejnerů. (Pokud takový polynomiální algoritmus existuje, pak v polynomiálním čase je možné určit, zda se n nezáporných čísel dělí na dvě množiny se stejným součtem prvků. Je však známo, že tento problém je NP-těžký.) P se neshoduje s NP, pak pro problém s balením neexistuje žádný algoritmus (PTAS)přibližného polynomického časového schématu . Na druhou stranu, pro jakékoli ε >0 lze najít řešení s nejvýše (1 + ε)OPT + 1 kontejnery v polynomiálním čase. Takové algoritmy patří mezi asymptotické PTAS. [3] Protože však obě konstanty libovolně závisí na ε při odhadu složitosti této třídy algoritmů, mohou být takové algoritmy na rozdíl od FFD a BFD prakticky nepoužitelné. $an^b$

Pravděpodobnostní přístup

Pro určitou třídu rozdělení pravděpodobnosti velikostí zabalených položek, včetně distribučních funkcí konvexních nahoru a dolů, existuje praktický polynomiální balicí algoritmus, který je téměř jistě asymptoticky optimální , když se počet položek neomezeně zvyšuje. Pro distribuce, která nejsou zahrnuta v této třídě, lze konstruovat jednotlivé polynomické asymptoticky optimální algoritmy. [čtyři]

Poznámky

↑ Silvano Martello a Paolo Toth. Problémy s batohem (neopr.) . - Chichester, UK: John Wiley and Sons , 1990. - S. 221. - ISBN 0471924202 .
↑ Yue, Minyi (1991), Jednoduchý důkaz nerovnosti FFD(L) ≤ (11/9)OPT(L) + 1, pro všechna L, pro algoritmus FFD bin-packing , Jednoduchý důkaz nerovnosti FFD (L) ≤ 11/9 OPT (L) + 1, ∀L pro algoritmus FFD bin-packing, Acta Mathematicae Applicatae Sinica T. 7 (4): 321–331, ISSN 0168-9673 , DOI 10.103607/BF
↑ Fernandez de la Vega, W. & Lueker, GS (1981), Bin packing lze vyřešit v rámci 1 + ε v lineárním čase , Bin packing může být vyřešen v rámci 1 + ε v lineárním čase, Combinatorica (Springer Berlin / Heidelberg) . — V. 1 (4): 349–355, ISSN 0209-9683 , DOI 10.1007/BF02579456
↑ A. V. Smirnov. K problému balení do kontejnerů. UMN, 1991, ročník 46, číslo 4(280), strany 173–174. . Datum přístupu: 19. února 2016. Archivováno z originálu 7. března 2016. (neurčitý)

Viz také

Balicí úkoly
Balící kruhy	V kruhu / v pravoúhlém trojúhelníku / v rovnoramenném pravoúhlém trojúhelníku / ve čtverci Koberec Apollonius Věta o balení kruhu Tammesův problém (na sféře)
Balení balónků	Apolloniev v kouli husté balení kontaktní číslo Sférická hranice balení (Hamming)
Další balíčky	Do kontejnerů Tetraedry Sady
Hádanka	Conway Slotobera - Graatsma

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém