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

Задачи, в которых делается попытка найти наиболее эффективный способ упаковки объектов в контейнеры.

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

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

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

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

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

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

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

Гексагональная упаковка кругов

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

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

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

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

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

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

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

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

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

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

Упаковка девяти L-трикубов в куб

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

Определите минимальное количество кубоидных контейнеров (ящиков), необходимых для упаковки заданного набора кубоидов предметов. Прямоугольные кубоиды, которые нужно упаковать, можно поворачивать на 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 ( a ^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). Elsevier: 241–252. doi :10.1016/s0377-2217(02)00123-6.
2. Донев, А.; Стиллингер, Ф.; Чайкин, П.; Торквато, С. (2004). "Необычно плотные кристаллические упаковки эллипсоидов". Physical Review Letters . 92 (25): 255506. arXiv : cond-mat/0403286 . Bibcode : 2004PhRvL..92y5506D. doi : 10.1103/PhysRevLett.92.255506. PMID  15245027. S2CID  7982407.
3. Torquato, S.; Jiao, Y. (август 2009 г.). «Плотные упаковки платоновых и архимедовых тел». Nature . 460 (7257): 876–879. arXiv : 0908.4107 . Bibcode :2009Natur.460..876T. doi :10.1038/nature08239. ISSN  0028-0836. PMID  19675649. S2CID  52819935.
4. Хаджи-Акбари, А.; Энгель, М.; Киз, АС; Чжэн, Х.; Петчек, РГ; Палффи-Мухорай, П.; Глотцер, С.К. (2009). «Неупорядоченные, квазикристаллические и кристаллические фазы плотно упакованных тетраэдров». Nature . 462 (7274): 773–777. arXiv : 1012.5138 . Bibcode :2009Natur.462..773H. doi :10.1038/nature08641. PMID  20010683. S2CID  4412674.
5. Chen, ER; Engel, M.; Glotzer, SC (2010). «Плотные кристаллические димерные упаковки правильных тетраэдров». Дискретная и вычислительная геометрия . 44 (2): 253–280. arXiv : 1001.0586 . Bibcode :2010arXiv1001.0586C. doi : 10.1007/s00454-010-9273-0 . S2CID  18523116.
6. Stein, Sherman K. (март 1995), «Упаковка штативов», Математические развлечения, The Mathematical Intelligencer , 17 (2): 37–39, doi :10.1007/bf03024896, S2CID  124703268. Перепечатано в Gale, David (1998), Gale, David (ред.), 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. Bibcode : 2011JPCM...23s4103H. doi : 10.1088/0953-8984/23/19/194103. PMID  21525553. S2CID  25505460.
8. «Упаковка кругов».
9. Smalley, IJ (1963). «Простые регулярные упаковки сфер в трех измерениях». Mathematics Magazine . 36 (5): 295–299. doi :10.2307/2688954. JSTOR  2688954.
10. Betke, Ulrich; Henk, Martin (2000). "Плотнейшие решетчатые упаковки 3-многогранников". Computational Geometry . 16 (3): 157–186. arXiv : math/9909172 . doi : 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. doi :10.1111/j.1475-3995.2009.00733.x.
13. Teich, EG; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, SC (2016). «Кластеры многогранников в сферическом ограничении». Proc. Natl. Acad. Sci. USA . 113 (6): E669–E678. Bibcode :2016PNAS..113E.669T. doi : 10.1073/pnas.1524875113 . PMC 4760782 . PMID  26811458. 
14. Мелиссен, Дж. (1995). «Упаковка 16, 17 или 18 кругов в равносторонний треугольник». Дискретная математика . 145 (1–3): 333–342. doi : 10.1016/0012-365X(95)90139-C .
15. Honsberger, Ross (1976). Mathematical Gems II . Математическая ассоциация Америки . стр. 67. ISBN 0-88385-302-7.
16. Кларнер, DA ; Хаутус, MLJ (1971). «Однородно окрашенные витражи». Труды Лондонского математического общества . 3. 23 (4): 613–628. doi :10.1112/plms/s3-23.4.613.
17. C.Michael Hogan. 2010. Абиотический фактор. Энциклопедия Земли. Ред. Эмили Моноссон и К. Кливленд. Национальный совет по науке и окружающей среде. Вашингтон, округ Колумбия
18. Абрахамсен, Миккель; Мильцов, Тиллманн; Надя, Сейферт (2020), Структура для полноты двумерных задач упаковки , arXiv : 2004.07558 ${\displaystyle \exists \mathbb {R} }$.

Ссылки

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

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

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

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

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

• Задача на упаковку кругов на Python