Проблеми упаковки[джерело?] — це клас задач оптимізації в математиці, які включають спробу пакування об'єктів разом у контейнери. Мета полягає в тому, щоб або упакувати один контейнер якомога щільніше, або упакувати всі об'єкти, використовуючи якомога менше контейнерів.
Пакування в нескінченному просторі[ред. | ред. код]
Багато з проблем, коли розмір контейнера збільшується в усіх напрямках, стають еквівалентними проблемі упаковки об’єктів якомога щільніше в нескінченному евклідовому просторі . Ця проблема є актуальною для ряду наукових дисциплін. Гіпотеза Кеплера постулювала оптимальне рішення для упаковки сфер за сотні років до того, як її правильність довів Томас Каллістер Хейлз .[1]
У трьох вимірах щільно упаковані структури пропонують найкращу гратчасту упаковку сфер і вважаються оптимальною з усіх упаковок. З «простими» сферичними упаковками в трьох вимірах («прості» ретельно визначені) є дев’ять можливих упаковок, які можна визначити. [3]
Тетраедри та октаедри разом можуть заповнити весь простір у структурі, яка відома як тетраедричні-октаедричні соти .
Моделювання, що поєднує локальні методи вдосконалення з випадковими упаковками, свідчить про те, що ґратчасті упаковки для ікосаедрів, додекаедрів і октаедрів є оптимальними в ширшому класі всіх упаковок. [6]
Проблема знаходження найменшої кулі такої, що kнепересічних відкритих одиничних кульок може бути упаковано всередині неї, має просту і повну відповідь у n -вимірному евклідовому просторі, якщо , і в нескінченномірному гільбертовому просторі без обмежень. З точки зору включень куль, k відкритих одиничних куль з центром входять до кулі радіуса , що є мінімальним для цієї конфігурації.
Визначте мінімальну висоту hциліндра із заданим радіусом R, який упакує n однакових сфер радіуса r (< R) . [7] Для малого радіуса R сфери утворюють упорядковані структури, які називаються стовпчастими структурами .
Вам дається nодиничних кіл, і ви повинні упакувати їх у найменший контейнер. Вивчено кілька типів контейнерів:
Упакування кіл у колі — тісно пов'язана з розподілом точок в одиничному колі з метою знаходження найбільшого мінімального відриву dn між точками. Оптимальні рішення доведено для n ≤ 13 і n = 19 .
Упакування кіл у квадраті — тісно пов'язана з розподілом точок в одиничному квадраті з метою знаходження найбільшого мінімального відриву dn між точками. Для перетворення між цими двома формулюваннями задачі сторона квадрата для одиничних кіл буде .Оптимальна упаковка 15 кружечків в квадраті Оптимальні рішення доведено для n ≤ 30 .
Упакування кіл у рівнобедреному прямокутному трикутнику — хороші оцінки відомі для n < 300 .
Упакування кіл у рівносторонньому трикутнику. Оптимальні рішення відомі для n < 13, а припущення доступні для n < 28 .[8]
Упакування ідентичних прямокутників у прямокутник : проблема упакування кількох екземплярів одного прямокутника розміром (l,w) із можливістю повороту на 90° у більший прямокутник розміром (L,W ) має деякі застосування, наприклад завантаження коробок. укладання деревної маси . В прямокутник розміром (1600,1230) можна упакувати 147 прямокутників розміром (137,95).
Існують теореми щодо розміщення прямокутників (і паралелепіпедів) у прямокутниках (кубоїдах) без проміжків або накладень:
Прямокутник a × b можна запакувати смужками 1 × n тоді і тільки тоді, коли a ділиться на n або b ділиться на n.[9][10]
Теорема де Брейна: коробку можна запакувати гармонічною цеглинкою a × ab × abc, якщо коробка має розміри ap × abq × abcr для деяких натуральних чиселp, q, r (тобто коробка є кратною цеглинці.)[9]
Упакування нестандартних об'єктів є проблемою, яка не підходить для рішень закритої форми; однак застосування до практичної науки про навколишнє середовище є досить важливою. Наприклад, частинки ґрунту неправильної форми упаковуються по-різному, оскільки розміри та форми змінюються, що призводить до важливих результатів для видів рослин щодо адаптації кореневих утворень і забезпечення руху води в ґрунті. [11]
↑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.
.svg)
