Проблемы с упаковкой

Проблемы, связанные с поиском наиболее эффективного способа упаковки объектов в контейнеры.

Сферы или круги упакованы свободно (вверху) и более плотно (внизу).

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

В задаче об упаковке мусора людям дается:

• Контейнер , обычно двух- или трехмерная выпуклая область , возможно , бесконечного размера. В зависимости от проблемы может быть предоставлено несколько контейнеров.
• Набор объектов , некоторые или все из которых должны быть упакованы в один или несколько контейнеров. Набор может содержать разные объекты с указанными размерами или один объект фиксированного размера, который можно использовать повторно.

Обычно упаковка не должна перекрывать товар и другие товары или стенки контейнера. В некоторых вариантах цель состоит в том, чтобы найти конфигурацию, которая упаковывает один контейнер с максимальной плотностью упаковки . Чаще всего цель состоит в том, чтобы упаковать все объекты в как можно меньшее количество контейнеров. ^[1] В некоторых вариантах перекрытие (объектов друг с другом и/или с границей контейнера) допускается, но должно быть сведено к минимуму.

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

Многие из этих задач при увеличении размера контейнера во всех направлениях становятся эквивалентными задаче максимально плотной упаковки объектов в бесконечном евклидовом пространстве . Эта проблема актуальна для ряда научных дисциплин и ей уделяется значительное внимание. Гипотеза Кеплера постулировала оптимальное решение для упаковки сфер за сотни лет до того, как ее правильность доказал Томас Каллистер Хейлз . Внимание привлекли многие другие формы, в том числе эллипсоиды, ^[2] Платоновы и архимедовы тела ^[3], включая тетраэдры , ^{[4] [5]} триподы (объединения кубов вдоль трех положительных осно-параллельных лучей), ^[6] и неравные сферы. димеры. ^[7]

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

Шестиугольная упаковка кругов на двумерной евклидовой плоскости.

Эти проблемы математически отличаются от идей теоремы об упаковке кругов . Связанная с этим проблема упаковки кругов касается упаковки кругов , возможно, разных размеров, на поверхности, например, плоскости или сферы .

Аналоги круга в других измерениях никогда не могут быть упакованы с полной эффективностью в измерениях больше единицы (в одномерной вселенной аналог круга состоит всего из двух точек). То есть всегда будет неиспользованное пространство, если люди будут только набивать круги. Самый эффективный способ упаковки кругов — шестиугольная упаковка — обеспечивает эффективность примерно 91%. ^[8]

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

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

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

Кубы можно легко расположить таким образом, чтобы они полностью заполнили трехмерное пространство, причем наиболее естественной упаковкой являются кубические соты . Ни одно другое платоновское тело само по себе не может замостить пространство, но некоторые предварительные результаты известны. Тетраэдры могут достигать упаковки не менее 85%. Одна из лучших упаковок правильных додекаэдров основана на вышеупомянутой гранецентрированной кубической (ГЦК) решетке.

Тетраэдры и октаэдры вместе могут заполнить все пространство, образуя структуру, известную как тетраэдрически-октаэдрические соты .

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

Упаковка в 3-х мерные контейнеры

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

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

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

Задача о нахождении наименьшего шара, в который можно упаковать k непересекающихся открытых единичных шаров , имеет простой и полный ответ в n -мерном евклидовом пространстве, если , и в бесконечномерном гильбертовом пространстве без ограничений. Здесь стоит описать подробно, чтобы дать представление об общей проблеме. В этом случае доступна конфигурация из k попарно касательных единичных шаров. Люди размещают центры в вершинах правильного размерного симплекса с ребром 2; это легко реализовать, исходя из ортонормированного базиса . Небольшое вычисление показывает, что расстояние каждой вершины от барицентра равно . При этом любая другая точка пространства обязательно находится на большем расстоянии хотя бы от одной из k вершин. С точки зрения включений шаров k открытых единичных шаров с центром в входят в шар радиуса , минимального для этой конфигурации. ${\displaystyle k\leq n+1}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\displaystyle (k-1)}$ ${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$

Чтобы показать, что эта конфигурация оптимальна, пусть – центры k непересекающихся открытых единичных шаров, содержащихся в шаре радиуса r с центром в точке . Рассмотрим отображение из конечного множества с учетом соответствующего для каждого . Так как для всех это отображение 1- липшицево и по теореме Киршбрауна продолжается до 1-липшицева отображения, определенного глобально; в частности, существует такая точка, что для всех имеется , так что также . Это показывает, что в шаре радиуса r имеется k непересекающихся единичных открытых шаров тогда и только тогда, когда . Обратите внимание, что в бесконечномерном гильбертовом пространстве это означает, что существует бесконечно много непересекающихся открытых единичных шаров внутри шара радиуса r тогда и только тогда, когда . Например, единичные шары с центром в , где – ортонормированный базис, не пересекаются и включены в шар радиуса с центром в начале координат. Более того , при максимальное число непересекающихся открытых единичных шаров внутри шара радиуса r равно . ${\displaystyle x_{1},\dots ,x_{k}}$ ${\displaystyle x_{0}}$ ${\displaystyle \{x_{1},\dots ,x_{k}\}}$ ${\displaystyle \{a_{1},\dots ,a_{k}\}}$ ${\displaystyle x_{j}}$ ${\displaystyle a_{j}}$ ${\displaystyle 1\leq j\leq k}$ ${\displaystyle 1\leq i<j\leq k}$ ${\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$ ${\displaystyle a_{0}}$ ${\displaystyle 1\leq j\leq k}$ ${\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$ ${\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$ ${\displaystyle r\geq r_{k}}$ ${\displaystyle r\geq 1+{\sqrt {2}}}$ ${\displaystyle {\sqrt {2}}e_{j}}$ ${\displaystyle \{e_{j}\}_{j}}$ ${\displaystyle 1+{\sqrt {2}}}$ ${\displaystyle r<1+{\sqrt {2}}}$ ${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$

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

Люди определяют количество сферических объектов заданного диаметра d , которые можно упаковать в кубоид размером . ${\displaystyle a\times b\times c}$

Идентичные сферы в цилиндре

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

Многогранники в сферах

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

Упаковка в 2-х мерные контейнеры

Оптимальная упаковка 10 кружков в круг.

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

Упаковка кружков

Людям даны n единичных кругов , и они должны упаковать их в наименьший возможный контейнер. Были изучены несколько видов контейнеров:

• Упаковка кругов в круг - тесно связана с распределением точек в единичном круге с целью найти наибольшее минимальное расстояние d _n между точками. Оптимальные решения доказаны для n ≤ 13 и n = 19 .
• Упаковка кругов в квадрат - тесно связана с распределением точек в единичном квадрате с целью найти наибольшее минимальное расстояние d _n между точками. Для преобразования между этими двумя формулировками задачи квадратная сторона единичного круга будет равна . ${\displaystyle L=2+2/d_{n}}$

  

  Оптимальная упаковка 15 кругов в квадрате.

  Оптимальные решения доказаны при n ≤ 30 .
• Упаковка кругов в прямоугольник
• Упаковка кругов в равнобедренный прямоугольный треугольник — хорошие оценки известны для n < 300 .
• Упаковочные круги в равносторонний треугольник . Оптимальные решения известны для n < 13 , а гипотезы доступны для n < 28 . ^[14]

Упаковка квадратов

Людям дают n единичных квадратов , и они должны упаковать их в минимально возможный контейнер, тип контейнера может быть разным:

• Упаковка квадратов в квадрат : оптимальные решения были доказаны для n от 1 до 10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100 и любого целого квадрата . Потерянное пространство асимптотически ^равно O ( 3/5 ) .
• Упаковка квадратов в круг : Хорошие решения известны для n ≤ 35 .

  

  Оптимальная упаковка 10 квадратов в квадрате

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

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

Связанные поля

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

Существуют важные теоремы о разбиении прямоугольников (и кубоидов) на прямоугольники (кубоиды) без промежутков и перекрытий:

Прямоугольник a × b можно упаковать полосками 1 × n тогда и только тогда, когда n делит a или n делит b . ^{[15] [16]}

Теорема де Брейна : Коробку можно упаковать гармоническим кирпичом a × ab × abc, если коробка имеет размеры ap × abq × abcr для некоторых натуральных чисел p , q , r (т. е. коробка кратна кирпичу). ^[15]

Изучение мозаики полимино в основном касается двух классов задач: замостить прямоугольник совпадающими плитками и упаковать по одному из каждого n -мино в прямоугольник.

Классическая головоломка второго рода — расположить все двенадцать пентамино в прямоугольники размером 3×20, 4×15, 5×12 или 6×10.

Упаковка нестандартных предметов

Упаковка объектов неправильной формы представляет собой проблему, которая не поддается решению в закрытой форме; однако применимость к практической науке об окружающей среде весьма важна. Например, частицы почвы неправильной формы упаковываются по-разному в зависимости от размера и формы, что приводит к важным результатам для видов растений по адаптации корневых образований и обеспечению движения воды в почве. ^[17]

Было показано, что проблема решения вопроса о том, может ли данный набор многоугольников поместиться в данный квадратный контейнер, является полной для экзистенциальной теории реальности . ^[18]

Смотрите также

• Проблема с упаковкой контейнера
• Плотная упаковка равных сфер
• Пазл Конвея
• Проблема с покрытием
• Проблема с обрезкой материала
• Эллипсоидная упаковка
• Проблема с числом поцелуев
• Задача о рюкзаке
• Случайная закрытая упаковка
• Упаковка комплекта
• Загадка Слотубера – Граатсмы
• Проблема с упаковкой ленты
• Упаковка тетраэдра
• Тетрис

Примечания

1. Лоди, А.; Мартелло, С.; Моначи, М. (2002). «Задачи двумерной упаковки: обзор». Европейский журнал операционных исследований . 141 (2). Эльзевир: 241–252. дои : 10.1016/s0377-2217(02)00123-6.
2. Донев, А.; Стиллинджер, Ф.; Чайкин П.; Торквато, С. (2004). «Необычайно плотные кристаллические упаковки эллипсоидов». Письма о физических отзывах . 92 (25): 255506. arXiv : cond-mat/0403286 . Бибкод : 2004PhRvL..92y5506D. doi : 10.1103/PhysRevLett.92.255506. PMID  15245027. S2CID  7982407.
3. Торквато, С.; Цзяо, Ю. (август 2009 г.). «Плотные упаковки платоновых и архимедовых тел». Природа . 460 (7257): 876–879. arXiv : 0908.4107 . Бибкод : 2009Natur.460..876T. дои : 10.1038/nature08239. ISSN  0028-0836. PMID  19675649. S2CID  52819935.
4. Хаджи-Акбари, А.; Энгель, М.; Ключи, АС; Чжэн, X.; Петчек, Р.Г.; Палффи-Мухорай, П.; Глотцер, Южная Каролина (2009). «Неупорядоченные, квазикристаллические и кристаллические фазы плотноупакованных тетраэдров». Природа . 462 (7274): 773–777. arXiv : 1012.5138 . Бибкод : 2009Natur.462..773H. дои : 10.1038/nature08641. PMID  20010683. S2CID  4412674.
5. Чен, скорая помощь; Энгель, М.; Глотцер, Южная Каролина (2010). «Плотные кристаллические димерные упаковки правильных тетраэдров». Дискретная и вычислительная геометрия . 44 (2): 253–280. arXiv : 1001.0586 . Бибкод : 2010arXiv1001.0586C. дои : 10.1007/s00454-010-9273-0 . S2CID  18523116.
6. Штейн, Шерман К. (март 1995 г.), «Упаковка штативов», Математические развлечения, The Mathematical Intelligencer , 17 (2): 37–39, doi : 10.1007/bf03024896, S2CID  124703268. Перепечатано в журналах Гейл, Дэвид (1998), Гейл, Дэвид (ред.), Tracking the Automatic ANT , Springer-Verlag, стр. 131–136, doi : 10.1007/978-1-4612-2192-0, ISBN. 0-387-98272-8, МР  1661863
7. Хадсон, ТС; Харроуэлл, П. (2011). «Структурные поиски с использованием изоточечных наборов в качестве генераторов: плотнейшие упаковки для бинарных смесей твердых сфер». Физический журнал: конденсированное вещество . 23 (19): 194103. Бибкод : 2011JPCM...23s4103H. дои : 10.1088/0953-8984/23/19/194103. PMID  21525553. S2CID  25505460.
8. «Упаковка круга».
9. Смолли, IJ (1963). «Простые упаковки правильных сфер в трех измерениях». Журнал «Математика» . 36 (5): 295–299. дои : 10.2307/2688954. JSTOR  2688954.
10. Бетке, Ульрих; Хенк, Мартин (2000). «Плотнейшие решетчатые упаковки 3-многогранников». Вычислительная геометрия . 16 (3): 157–186. arXiv : math/9909172 . дои : 10.1016/S0925-7721(00)00007-9 . MR  1765181. S2CID  12118403.
11. Минковский, Х. Dichteste gitterförmige Lagerung congruenter Körper. Нахр. Акад. Висс. Геттингенская математика. Физ. КИ. II 311–355 (1904).
12. Стоян, Ю.Г.; Яськов, Г.Н. (2010). «Упаковка одинаковых сфер в цилиндр». Международные сделки в области операционных исследований . 17 :51–70. дои : 10.1111/j.1475-3995.2009.00733.x.
13. Тейх, Э.Г.; ван Андерс, Г.; Клоца, Д.; Джемучадзе Дж.; Глотцер, Южная Каролина (2016). «Кластеры многогранников в сферическом ограничении». Учеб. Натл. акад. наук. США . 113 (6): E669–E678. Бибкод : 2016PNAS..113E.669T. дои : 10.1073/pnas.1524875113 . ПМЦ 4760782 . ПМИД  26811458. 
14. Мелиссен, Дж. (1995). «Упаковка 16, 17 или 18 кругов в равносторонний треугольник». Дискретная математика . 145 (1–3): 333–342. дои : 10.1016/0012-365X(95)90139-C .
15. Хонсбергер, Росс (1976). Математические жемчужины II . Математическая ассоциация Америки . п. 67. ИСБН 0-88385-302-7.
16. Кларнер, Д.А .; Хаутус, MLJ (1971). «Одноцветные витражи». Труды Лондонского математического общества . 3. 23 (4): 613–628. дои : 10.1112/plms/s3-23.4.613.
17. К.Майкл Хоган. 2010. Абиотический фактор. Энциклопедия Земли. редакторы Эмили Моноссон и К. Кливленд. Национальный совет по науке и окружающей среде. Вашингтон
18. Абрахамсен, Миккель; Мильцов, Тильманн; Надя, Зайферт (2020), Структура полноты задач двумерной упаковки , arXiv : 2004.07558 ${\displaystyle \exists \mathbb {R} }$.

Рекомендации

• Вайсштейн, Эрик В. «Теорема Кларнера». Математический мир .
• Вайсштейн, Эрик В. «Теорема де Брейна». Математический мир .

Внешние ссылки

• Оптимизация трехмерной упаковки в контейнеры

Многие книги по головоломкам, а также математические журналы содержат статьи по проблемам упаковки.

• Ссылки на различные статьи MathWorld об упаковке
• Заметки MathWorld об упаковке квадратов.
• Упаковочный центр Эриха
• www.packomania.com Сайт с таблицами, графиками, калькуляторами, справочниками и т. д.
• «Упаковка коробок», Эд Пегг-младший , Демонстрационный проект Вольфрама , 2007 г.
• Наиболее известные упаковки равных кругов в круге, до 1100.

• Проблема с упаковкой кругов в Python