Введение

Проблемы, которые пытаются найти наиболее эффективный способ упаковки объектов в контейнеры, – это геометрические задачи упаковки. Задачи упаковки – это класс оптимизационных задач в математике, включающий попытку упаковать объекты вместе в контейнеры. Цель состоит в том, чтобы максимально плотно упаковать один контейнер или упаковать все объекты, используя минимальное количество контейнеров. Многие из этих задач связаны с реальными проблемами, возникающими при упаковке, хранении и транспортировке. Каждая задача упаковки имеет двойственную задачу покрытия, которая определяет, сколько одинаковых объектов требуется для полного покрытия всех областей контейнера, при этом допускается перекрытие объектов. В задаче об упаковке в контейнеры (или задаче о размещении предметов в контейнерах) дано: контейнер, обычно двумерная или трехмерная выпуклая область, возможно, бесконечного размера. В зависимости от задачи может быть задано несколько контейнеров. Набор объектов, часть или все из которых необходимо упаковать в один или несколько контейнеров. Набор может содержать различные объекты с указанными размерами или один объект фиксированного размера, который можно использовать многократно. Обычно упаковка должна осуществляться без перекрытия объектов друг с другом или со стенками контейнера. В некоторых вариантах целью является поиск конфигурации, обеспечивающей максимальную плотность упаковки в одном контейнере. Чаще целью является упаковка всех объектов в минимальное количество контейнеров. В некоторых вариантах допускается перекрытие (объектов друг с другом и/или с границей контейнера), но его следует минимизировать.

В бесконечном пространстве

Многие из этих проблем, при увеличении размера контейнера во всех направлениях, становятся эквивалентны задаче максимально плотной упаковки объектов в бесконечном евклидовом пространстве. Эта задача имеет значение для ряда научных дисциплин и привлекала значительное внимание. Гипотеза Кеплера постулировала оптимальное решение для упаковки сфер за столетия до того, как оно было доказано Томасом Каллистером Хейлсом. Внимание было уделено и другим формам, включая эллипсоиды, платоновы и архимедовы тела, триподы (объединения кубов вдоль трех лучей, параллельных положительным осям координат), и димеры из сфер разного размера.

Шестиугольная упаковка из кругов

Эти проблемы математически отличаются от идей, лежащих в основе теоремы об упаковке кругов. Связанная с ней задача об упаковке кругов рассматривает упаковку кругов, возможно, разных размеров, на поверхности, например, на плоскости или сфере. Соответствующие кругу объекты в других измерениях никогда не могут быть упакованы с полной эффективностью в измерениях, больших единицы (в одномерной вселенной аналогом круга являются всего две точки). Иными словами, при упаковке только кругов всегда будет оставаться незаполненное пространство. Наиболее эффективный способ упаковки кругов, гексагональная (или шестиугольная) упаковка, обеспечивает эффективность примерно 91%.

Сфера упаковки в более высоких размерах

В трех измерениях плотные упаковки обеспечивают наилучшее решетчатое размещение сфер и считаются оптимальными среди всех возможных упаковок. Для «простых» трехмерных упаковок сфер («простые» определены строго) существует девять различных определяемых упаковок. Также доказано, что 8-мерная решетка E8 и 24-мерная решетка Лича являются оптимальными в соответствующих реальных пространствах.

Упаковки платонических твердых веществ в трех измерениях

Кубы можно легко расположить так, чтобы полностью заполнить трехмерное пространство, при этом наиболее естественной упаковкой является кубическая сотовая структура. Ни одно другое платоново тело не может самостоятельно заполнять пространство плиткой, но существуют некоторые предварительные результаты. Тетраэдры могут достигать плотности упаковки не менее 85%. Одна из лучших упаковок правильных додекаэдров основана на вышеупомянутой гранецентрированной кубической решетке (ГЦК). Тетраэдры и октаэдры вместе могут заполнить все пространство в структуре, известной как тетраэдрическая октаэдрическая сотовая структура. Максимальная плотность решетчатой упаковки икосаэдра составляет 0,836357, а додекаэдра – (5 + √5)/8 = 0,904508.

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

Различные кубоиды в кубоид

Определите минимальное количество контейнеров в форме кубоидов, необходимых для упаковки заданного набора кубоидов. Прямоугольные кубоиды, которые необходимо упаковать, могут быть повернуты на 90 градусов вокруг каждой оси.

Сферы в евклидово шаре

Проблема нахождения наименьшего шара, в котором можно упаковать k непересекающихся открытых единичных шаров, имеет простое и полное решение в n-мерном евклидовом пространстве при , и в бесконечномерном гильбертовом пространстве без ограничений. Стоит подробно описать это здесь, чтобы дать представление об общей задаче. В этом случае доступна конфигурация из k попарно касающихся единичных шаров. Обычно центры помещают в вершины правильного n-мерного симплекса с ребром длиной 2; это легко реализовать, начиная с ортонормального базиса. Несложные вычисления показывают, что расстояние каждой вершины от барицентра равно . Более того, любая другая точка пространства обязательно имеет большее расстояние хотя бы до одной из k вершин. В терминах включений шаров, k открытых единичных шаров с центрами в содержатся в шаре радиуса , который является минимальным для данной конфигурации. Чтобы доказать оптимальность этой конфигурации, пусть – центры k непересекающихся открытых единичных шаров, содержащихся в шаре радиуса r с центром в точке . Рассмотрим отображение из конечного множества в , которое сопоставляет каждому соответствующий . Поскольку для всех , это отображение 1-липшицево, и по теореме Киршбрауна оно может быть продолжено до 1-липшицева отображения, определенного глобально; в частности, существует точка такая, что для всех выполняется , а следовательно, и . Это показывает, что k непересекающихся открытых единичных шаров в шаре радиуса r существуют тогда и только тогда, когда . Заметьте, что в бесконечномерном гильбертовом пространстве это означает, что внутри шара радиуса r существует бесконечно много непересекающихся открытых единичных шаров тогда и только тогда, когда . Например, единичные шары с центрами в , где – ортонормальный базис, не пересекаются и содержатся в шаре радиуса с центром в начале координат. Более того, для , максимальное количество непересекающихся открытых единичных шаров внутри шара радиуса r равно .

Сферы в кубоиде

Люди определяют количество сферических объектов заданного диаметра d, которые можно упаковать в параллелепипед заданного размера.

Одинаковые сферы в цилиндре

Люди определяют минимальную высоту h цилиндра с заданным радиусом R, достаточную для упаковки n идентичных сфер радиусом r (< R). При небольшом радиусе R сферы выстраиваются в упорядоченные структуры, называемые столбчатыми структурами.

Полиэдры в сферах

Люди определяют минимальный радиус R, достаточный для упаковки n идентичных многогранников единичного объема заданной формы.

Упаковка в двумерные контейнеры

Было изучено множество вариантов двумерных задач об упаковке.

Упаковка прямоугольников

Упаковка идентичных прямоугольников в прямоугольник: Задача упаковки нескольких экземпляров одного прямоугольника размером (l,w) с возможностью поворота на 90° в больший прямоугольник размером (L,W) имеет ряд применений, таких как загрузка ящиков на поддоны и, в частности, штабелирование древесной массы. Например, можно упаковать 147 прямоугольников размером (137,95) в прямоугольник размером (1600,1230). Упаковка различных прямоугольников в прямоугольник: Задача упаковки нескольких прямоугольников различной ширины и высоты во внешний прямоугольник минимальной площади (без ограничений на ширину или высоту внешнего прямоугольника) имеет важное применение при объединении изображений в одно большое изображение. Веб-страница, загружающая одно большое изображение, часто отображается в браузере быстрее, чем та же страница, загружающая несколько маленьких изображений, из-за накладных расходов, связанных с запросом каждого изображения с веб-сервера. В общем случае задача является NP-полной, но существуют быстрые алгоритмы для решения небольших экземпляров.