Задача пакування

 

Сфери або кола розташовані нещільно (вгорі) і щільніше (внизу)

Проблеми упаковки^[] — це клас задач оптимізації в математиці, які включають спробу пакування об'єктів разом у контейнери. Мета полягає в тому, щоб або упакувати один контейнер якомога щільніше, або упакувати всі об'єкти, використовуючи якомога менше контейнерів.

У задачі пакування контейнера надається:

• Контейнер, як правило, дво- або тривимірна опукла область, можливо нескінченного розміру. Залежно від проблеми може бути надано кілька контейнерів.
• Набір може містити різні об'єкти із зазначеними розмірами або один об'єкт фіксованого розміру, який можна використовувати багаторазово.

Пакування в нескінченному просторі

Багато з проблем, коли розмір контейнера збільшується в усіх напрямках, стають еквівалентними проблемі упаковки об’єктів якомога щільніше в нескінченному евклідовому просторі . Ця проблема є актуальною для ряду наукових дисциплін. Гіпотеза Кеплера постулювала оптимальне рішення для упаковки сфер за сотні років до того, як її правильність довів Томас Каллістер Хейлз .

Шестикутна упаковка кіл

Гексагональна упаковка кіл на 2-вимірній евклідовій площині.

Найефективніший спосіб пакування кіл, шестикутне пакування, забезпечує приблизно 91% ефективності.

Сферичні упаковки більших розмірів

Докладніше:

У трьох вимірах щільно упаковані структури пропонують найкращу гратчасту упаковку сфер і вважаються оптимальною з усіх упаковок. З «простими» сферичними упаковками в трьох вимірах («прості» ретельно визначені) є дев’ять можливих упаковок, які можна визначити.

Тетраедри та октаедри разом можуть заповнити весь простір у структурі, яка відома як тетраедричні-октаедричні соти .

Твердий	Оптимальна щільність укладання грат
ікосаедр	0,836357. . .
додекаедр	(5 + √5 )/8 = 0,904508. . .
октаедр	18/19 = 0,947368. . .

Моделювання, що поєднує локальні методи вдосконалення з випадковими упаковками, свідчить про те, що ґратчасті упаковки для ікосаедрів, додекаедрів і октаедрів є оптимальними в ширшому класі всіх упаковок.

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

Сфери в евклідову кулю

Докладніше:

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

Однакові кулі в циліндрі

Докладніше:

Визначте мінімальну висоту h циліндра із заданим радіусом R, який упакує n однакових сфер радіуса r (< R) . Для малого радіуса R сфери утворюють упорядковані структури, які називаються стовпчастими структурами .

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

Упакування в 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 .

Упакування квадратів

Вам дається n одиничних квадратів, і ви повинні упакувати їх у найменший можливий контейнер, де тип контейнера різний:

• Упакування квадратів у квадрат: доведено оптимальні рішення для n від 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 і будь-якого цілого квадрата
• Упакування квадратів у коло: позитивніі рішення відомі для n ≤ 35 .

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

Упакування прямокутників

Докладніше:

• Упакування ідентичних прямокутників у прямокутник : проблема упакування кількох екземплярів одного прямокутника розміром (l,w) із можливістю повороту на 90° у більший прямокутник розміром (L,W ) має деякі застосування, наприклад завантаження коробок. укладання деревної маси . В прямокутник розміром (1600,1230) можна упакувати 147 прямокутників розміром (137,95).

Пов'язані поля

Існують теореми щодо розміщення прямокутників (і паралелепіпедів) у прямокутниках (кубоїдах) без проміжків або накладень:

Прямокутник a × b можна запакувати смужками 1 × n тоді і тільки тоді, коли a ділиться на n або b ділиться на n.

Теорема де Брейна: коробку можна запакувати гармонічною цеглинкою a × ab × abc, якщо коробка має розміри ap × abq × abcr для деяких натуральних чисел p, q, r (тобто коробка є кратною цеглинці.)

Упакування нестандартних предметів

Упакування нестандартних об'єктів є проблемою, яка не підходить для рішень закритої форми; однак застосування до практичної науки про навколишнє середовище є досить важливою. Наприклад, частинки ґрунту неправильної форми упаковуються по-різному, оскільки розміри та форми змінюються, що призводить до важливих результатів для видів рослин щодо адаптації кореневих утворень і забезпечення руху води в ґрунті.

Див. також

• Упакування набору
• Проблема з упакування контейнера
• Головоломка Слотхаубера–Граатсми
• Головоломка Конвея
• Тетріс
• Проблема покриття
• Проблема ранця
• Тетраедрове упакування
• Еліпсоїдне упакування
• Проблема скорочення запасів
• Проблема з числом поцілунків
• Щільне упакування рівних сфер
• Випадкове закрите упакування
• Проблема з упакуванням стрічки

Примітки

1. Hudson, T. S.; Harrowell, P. (2011). Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures. Journal of Physics: Condensed Matter. 23 (19): 194103. Bibcode:2011JPCM...23s4103H. doi:10.1088/0953-8984/23/19/194103. PMID 21525553.
2. Circle Packing.
3. Smalley, I.J. (1963). Simple regular sphere packings in three dimensions. Mathematics Magazine. 36 (5): 295—299. doi:10.2307/2688954. JSTOR 2688954.
4. Betke, Ulrich; Henk, Martin (2000). Densest lattice packings of 3-polytopes. . 16 (3): 157—186. arXiv:math/9909172. doi:10.1016/S0925-7721(00)00007-9. MR 1765181.
5. Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904).
6. Torquato, S.; Jiao, Y. (Aug 2009). Dense packings of the Platonic and Archimedean solids. Nature. 460 (7257): 876—879. arXiv:0908.4107. Bibcode:2009Natur.460..876T. doi:10.1038/nature08239. ISSN 0028-0836. PMID 19675649.
7. Stoyan, Y. G.; Yaskov, G. N. (2010). Packing identical spheres into a cylinder. International Transactions in Operational Research. 17: 51—70. doi:10.1111/j.1475-3995.2009.00733.x.
8. Melissen, J. (1995). Packing 16, 17 or 18 circles in an equilateral triangle. Discrete Mathematics. 145 (1–3): 333—342. doi:10.1016/0012-365X(95)90139-C.
9. Honsberger, Ross (1976). Mathematical Gems II. . с. 67. ISBN .
10. ; Hautus, M.L.J (1971). Uniformly coloured stained glass windows. Proceedings of the London Mathematical Society. 3. 23 (4): 613—628. doi:10.1112/plms/s3-23.4.613.
11. C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC

Література

• Weisstein, Eric W. Klarner's Theorem(англ.) на сайті Wolfram MathWorld.
• Weisstein, Eric W. de Bruijn's Theorem(англ.) на сайті Wolfram MathWorld.

Посилання

• (англ.)
• API для 3D пакування контейнерів(англ.)
• Посилання на різні статті MathWorld про пакування | Пакування квадратів.(англ.)
• Пакувальний центр Еріха(англ.)
• www.packomania.com Сайт з таблицями, графіками, калькуляторами, довідниками тощо.(англ.)
• «Box Packing» Еда Пегга молодшого, демонстраційний проект Wolfram, 2007.(англ.)
• Найвідоміші упаковки рівних кіл у колі, до 1100(англ.)
• 3D пакування коробок і циліндрів з телескопіюванням^{[недоступне посилання з березень 2023]}