Просмотр кода страницы Задача об упаковке в контейнеры

'''Задача об [[Упаковка|упаковке]] в контейнеры''' — [[Класс NP|NP-трудная]] [[комбинаторика|комбинаторная]] задача. 
Задача заключается в упаковке объектов предопределённой формы в конечное число [[ISO-контейнер|контейнеров]] предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.

== Разновидности и методы решения задач упаковки ==
Существует множество разновидностей этой задачи ([[двумерная упаковка]], [[линейная упаковка]], [[упаковка по весу]], [[упаковка по стоимости]] и т. п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д.
Так как задача является [[NP-трудность|NP-трудной]], то использование точного переборного алгоритма возможно только при небольших размерностях. Обычно для решения задачи используют [[эвристика|эвристические]] приближённые полиномиальные алгоритмы.

== Задача упаковки в одномерные одинаковые контейнеры ==

=== Постановка задачи ===
Пусть дано множество контейнеров размера <math>V</math> и множество <math>n</math> предметов размеров <math>a_1,\dots,a_n</math>. Надо найти целое число контейнеров <math>B</math> и [[разбиение множества]] <math>\{1,\dots,n\}</math> на <math>B</math> подмножеств <math>S_1 \cup \dots \cup S_B</math> таких, что <math>\sum_{i \in S_k} a_i \leq V</math> для всех <math>k=1,\dots,B</math>. 
Решение называется оптимальным, если <math>B</math> минимально. 
Минимальное <math>B</math> далее обозначается '''OPT'''.

=== Упаковка как задача [[целочисленное программирование|целочисленного программирования]] ===
Задача упаковки в контейнеры может быть сформулирована как задача целочисленного программирования следующим образом:
{|
|-
|colspan="2"|Минимизировать <math> B = \sum_{i=1}^n y_i</math>
|
|-
|при ограничениях
|<math>\sum_{j=1}^n a_j x_{ij} \leq V y_i,</math>
|<math>\forall i \in \{1,\ldots,n\}</math>
|-
|
|<math>\sum_{i=1}^n x_{ij} = 1,</math>
|<math>\forall j \in \{1,\ldots,n\}</math>
|-
|
|<math> y_i \in \{0,1\},</math>
|<math>\forall i \in \{1,\ldots,n\}</math>
|-
|
|<math> x_{ij} \in \{0,1\},</math>
|<math>\forall i \in \{1,\ldots,n\} \, \forall j \in \{1,\ldots,n\}</math>
|}
где <math> y_i = 1</math>, если контейнер <math>i</math> используется и <math> x_{ij} = 1</math>, если предмет <math>j</math> помещён в контейнер <math>i</math>.<ref name=Martello1990>{{книга |заглавие=Knapsack problems |год=1990 |издательство=[[John Wiley & Sons|John Wiley and Sons]] |место=Chichester, UK |isbn=0471924202 |страницы=221 |ссылка=http://www.or.deis.unibo.it/kp/Chapter8.pdf |ref=Silvano Martello and Paolo Toth |язык=und |автор=Silvano Martello and Paolo Toth |archivedate=2013-09-21 |archiveurl=https://web.archive.org/web/20130921054814/http://www.or.deis.unibo.it/kp/Chapter8.pdf }}</ref>

=== Приближённые полиномиальные алгоритмы ===
Простейшими полиномиальными [[алгоритм]]ами упаковки являются алгоритмы ''Best Fit Decreasing — BFD '' (Наилучший подходящий по убыванию) и ''First Fit Decreasing — FFD'' (Первый подходящий по убыванию). Предметы упорядочивают по убыванию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём — BFD, либо в первый контейнер куда он помещается — FFD. Доказано, что эти алгоритмы используют не более
 
<math>\frac{11}{9}OPT + 1</math>

контейнеров<ref>{{citation
  | last = Yue
  | first = Minyi
  | contribution = A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm
  | journal = Acta Mathematicae Applicatae Sinica
  | volume = 7
  | month = October
  | year = 1991
  | pages = 321–331
  | doi = 10.1007/BF02009683
  | issn = 0168-9673
  | issue = 4
  | title = A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm }}</ref>.

Однако для задачи упаковки существуют и асимптотически ε -оптимальные полиномиальные алгоритмы.

Задача определения, равно ли '''OPT''' двум или трем является NP-трудной. Поэтому для любого ε > 0, трудно упаковать предметы в '''(3/2 − ε)OPT''' контейнеров. (Если такой полиномиальный алгоритм существует, то за полиномиальное время можно определить разделятся ли ''n'' неотрицательных чисел на два множества с одинаковой суммой элементов. Однако известно, что эта проблема NP-трудна.) Следовательно, если P не совпадает с NP, то для задачи упаковки в контейнеры нет алгоритма [[Приближенная схема полиномиального времени|приближенной схемы полиномиального времени]] (PTAS). С другой стороны, для всякого ε >0  можно найти решение с не более, чем '''(1 + ε)OPT + 1''' контейнерами за полиномиальное время. Такие алгоритмы относятся к асимптотической PTAS.<ref>{{citation
  | last1 = Fernandez de la Vega
  | first1 = W.
  | last2 = Lueker
  | first2 = G. S.
  | contribution = Bin packing can be solved within 1 + ε in linear time
  | journal = Combinatorica
  | publisher = Springer Berlin / Heidelberg
  | volume = 1
  | month = December
  | year = 1981
  | pages = 349–355
  | doi = 10.1007/BF02579456
  | issn = 0209-9683
  | issue = 4
  | title = Bin packing can be solved within 1 + ε in linear time }}</ref> Но поскольку в оценке сложности этого класса алгоритмов <math> a n^b</math> обе константы произвольно зависят от  ε, подобные алгоритмы в отличие от FFD и BFD могут быть практически бесполезными.

=== Вероятностный подход ===
Для некоторого класса [[Распределение вероятностей|вероятностных распределений]] размеров упаковываемых предметов, включающего функции распределения выпуклые вверх и вниз, существует практический полиномиальный алгоритм упаковки асимптотически оптимальный [[почти наверное]] при неограниченном росте числа предметов. Для распределений не входящих в этот класс могут строиться индивидуальные полиномиальные асимптотически оптимальные алгоритмы.<ref>{{Cite web |url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=4649&option_lang=rus |title=А. В. Смирнов. О задаче упаковки в контейнеры. УМН, 1991, том 46, выпуск 4(280), страницы 173–174. |access-date=2016-02-19 |archive-date=2016-03-07 |archive-url=https://web.archive.org/web/20160307123732/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=4649&option_lang=rus |deadlink=no }}</ref>

== Примечания ==
{{примечания}}

=== См. также ===
* [[Задачи упаковки]]
* [[Задача о ранце]]
* [[Задача о сумме подмножеств]]
* [[Оптимизация]]
* [[Упаковка шаров]]

{{Задачи упаковки}}
{{NP-полные задачи}}

[[Категория:NP-полные задачи]]
[[Категория:Задачи упаковки]]