Задача об упаковке в контейнеры

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

Разновидности и методы решения задач упаковки

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

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

Постановка задачи

Пусть дано множество контейнеров размера V {displaystyle V} и множество n {displaystyle n} предметов размеров a 1 , … , a n {displaystyle a_{1},dots ,a_{n}} . Надо найти целое число контейнеров B {displaystyle B} и разбиение множества { 1 , … , n } {displaystyle {1,dots ,n}} на B {displaystyle B} подмножеств S 1 ∪ ⋯ ∪ S B {displaystyle S_{1}cup dots cup S_{B}} таких, что ∑ i ∈ S k a i ≤ V {displaystyle sum _{iin S_{k}}a_{i}leq V} для всех k = 1 , … , B {displaystyle k=1,dots ,B} . Решение называется оптимальным, если B {displaystyle B} минимально. Минимальное B {displaystyle B} далее обозначается OPT.

Упаковка как задача целочисленного программирования

Задача упаковки в контейнеры может быть сформулирована как задача целочисленного программирования следующим образом:

где y i = 1 {displaystyle y_{i}=1} , если контейнер i {displaystyle i} используется и x i j = 1 {displaystyle x_{ij}=1} , если предмет j {displaystyle j} помещён в контейнер i {displaystyle i} .

Приближённые полиномиальные алгоритмы

Простейшими полиномиальными алгоритмами упаковки являются алгоритмы Best Fit Decreasing — BFD (Наилучший подходящий по убыванию) и First Fit Decreasing — FFD (Первый подходящий по убыванию). Предметы упорядочивают по невозрастанию размеров и последовательно пакуют либо в контейнер, в котором после упаковки останется наименьший свободный объём — BFD, либо в первый контейнер куда он помещается — FFD. Доказано, что эти алгоритмы используют не более

11 9 O P T + 1 {displaystyle {frac {11}{9}}OPT+1}

контейнеров.

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

Задача определения, равно ли OPT двум или трем является NP-трудной. Поэтому для любого ε > 0, трудно упаковать предметы в (3/2 − ε)OPT контейнеров. (Если такой полиномиальный алгоритм существует, то за полиномиальное время можно определить разделятся ли n неотрицательных чисел на два множества с одинаковой суммой элементов. Однако известно, что эта проблема NP-трудна.) Следовательно, если P не совпадает с NP, то для задачи упаковки в контейнеры нет алгоритма приближенной схемы полиномиального времени (PTAS). С другой стороны, для всякого ε >0 можно найти решение с не более, чем (1 + ε)OPT + 1 контейнерами за полиномиальное время. Такие алгоритмы относятся к асимптотической PTAS. Но поскольку в оценке сложности этого класса алгоритмов a n b {displaystyle an^{b}} обе константы произвольно зависят от ε, подобные алгоритмы в отличие от FFD и BFD могут быть практически бесполезными.

Вероятностный подход

Для некоторого класса вероятностных распределений размеров упаковываемых предметов, включающего функции распределения выпуклые вверх и вниз, существует практический полиномиальный алгоритм упаковки асимптотически оптимальный почти наверное при неограниченном росте числа предметов. Для распределений не входящих в этот класс могут строиться индивидуальные полиномиальные асимптотически оптимальные алгоритмы.