Проблеми упаковки — це клас задач оптимізації в математиці, які включають спробу пакування об'єктів разом у контейнери. Мета полягає в тому, щоб або упакувати один контейнер якомога щільніше, або упакувати всі об'єкти, використовуючи якомога менше контейнерів.
У задачі пакування контейнера надається:
Контейнер, як правило, дво- або тривимірна опукла область, можливо нескінченного розміру. Залежно від проблеми може бути надано кілька контейнерів. Набір може містити різні об'єкти із зазначеними розмірами або один об'єкт фіксованого розміру, який можна використовувати багаторазово.
Пакування в нескінченному просторі Багато з проблем, коли розмір контейнера збільшується в усіх напрямках, стають еквівалентними проблемі упаковки об’єктів якомога щільніше в нескінченному евклідовому просторі . Ця проблема є актуальною для ряду наукових дисциплін. Гіпотеза Кеплера постулювала оптимальне рішення для упаковки сфер за сотні років до того, як її правильність довів Томас Каллістер Хейлз .
Шестикутна упаковка кіл
Найефективніший спосіб пакування кіл, шестикутне пакування, забезпечує приблизно 91% ефективності.
Сферичні упаковки більших розмірів
У трьох вимірах щільно упаковані структури пропонують найкращу гратчасту упаковку сфер і вважаються оптимальною з усіх упаковок. З «простими» сферичними упаковками в трьох вимірах («прості» ретельно визначені) є дев’ять можливих упаковок, які можна визначити.
Тетраедри та октаедри разом можуть заповнити весь простір у структурі, яка відома як тетраедричні-октаедричні соти . Твердий Оптимальна щільність укладання грат ікосаедр 0,836357. . . додекаедр (5 + )/8 = 0,904508. . . октаедр 18/19 = 0,947368. . . Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II 311–355 (1904). Моделювання, що поєднує локальні методи вдосконалення з випадковими упаковками, свідчить про те, що ґратчасті упаковки для ікосаедрів, додекаедрів і октаедрів є оптимальними в ширшому класі всіх упаковок.
Упаковка в 3-вимірні контейнери
Сфери в евклідову кулю
Проблема знаходження найменшої кулі такої, що непересічних відкритих одиничних кульок може бути упаковано всередині неї, має просту і повну відповідь у -вимірному евклідовому просторі, якщо , і в нескінченномірному гільбертовому просторі без обмежень. З точки зору включень куль, відкритих одиничних куль з центром входять до кулі радіуса , що є мінімальним для цієї конфігурації.
Однакові кулі в циліндрі
Визначте мінімальну висоту циліндра із заданим радіусом , який упакує однакових сфер радіуса . Для малого радіуса сфери утворюють упорядковані структури, які називаються стовпчастими структурами .
Багатогранники в сферах
Упакування в 2-вимірні контейнери
Досліджено багато варіантів двовимірних задач пакування.
Упакування кіл
Вам дається одиничних кіл, і ви повинні упакувати їх у найменший контейнер. Вивчено кілька типів контейнерів: Упакування кіл у колі — тісно пов'язана з розподілом точок в одиничному колі з метою знаходження найбільшого мінімального відриву між точками. Оптимальні рішення доведено для і . Упакування кіл у квадраті — тісно пов'язана з розподілом точок в одиничному квадраті з метою знаходження найбільшого мінімального відриву між точками. Для перетворення між цими двома формулюваннями задачі сторона квадрата для одиничних кіл буде . Оптимальні рішення доведено для . Упакування кіл у рівнобедреному прямокутному трикутнику — хороші оцінки відомі для . Упакування кіл у рівносторонньому трикутнику. Оптимальні рішення відомі для , а припущення доступні для .
Упакування квадратів Вам дається одиничних квадратів, і ви повинні упакувати їх у найменший можливий контейнер, де тип контейнера різний: Упакування квадратів у квадрат: доведено оптимальні рішення для від 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100 і будь-якого цілого квадрата Упакування квадратів у коло: позитивніі рішення відомі для .
Упакування прямокутників
Упакування ідентичних прямокутників у прямокутник : проблема упакування кількох екземплярів одного прямокутника розміром із можливістю повороту на 90° у більший прямокутник розміром має деякі застосування, наприклад завантаження коробок. укладання деревної маси . В прямокутник розміром (1600,1230) можна упакувати 147 прямокутників розміром (137,95).
Пов'язані поля Існують теореми щодо розміщення прямокутників (і паралелепіпедів) у прямокутниках (кубоїдах) без проміжків або накладень:
Прямокутник a × b можна запакувати смужками 1 × n тоді і тільки тоді, коли a ділиться на n або b ділиться на n. Теорема де Брейна: коробку можна запакувати гармонічною цеглинкою a × ab × abc, якщо коробка має розміри ap × abq × abcr для деяких натуральних чисел p, q, r (тобто коробка є кратною цеглинці.)
Упакування нестандартних предметів Упакування нестандартних об'єктів є проблемою, яка не підходить для рішень закритої форми; однак застосування до практичної науки про навколишнє середовище є досить важливою. Наприклад, частинки ґрунту неправильної форми упаковуються по-різному, оскільки розміри та форми змінюються, що призводить до важливих результатів для видів рослин щодо адаптації кореневих утворень і забезпечення руху води в ґрунті. C.Michael Hogan. 2010. Abiotic factor. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment. Washington DC
Див. також Упакування набору Проблема з упакування контейнера Головоломка Слотхаубера–Граатсми Головоломка Конвея Тетріс Проблема покриття Проблема ранця Тетраедрове упакування Еліпсоїдне упакування Проблема скорочення запасів Проблема з числом поцілунків Щільне упакування рівних сфер Випадкове закрите упакування Проблема з упакуванням стрічки
Примітки
Література
Посилання
Оптимізація тривимірного пакування контейнерів API для 3D пакування контейнерів Посилання на різні статті MathWorld про пакування | Пакування квадратів. Пакувальний центр Еріха www.packomania.com Сайт з таблицями, графіками, калькуляторами, довідниками тощо. «Box Packing» Еда Пегга молодшого, демонстраційний проект Wolfram, 2007. Найвідоміші упаковки рівних кіл у колі, до 1100 3D пакування коробок і циліндрів з телескопіюванням