Methodological basis of solving sphere packing problem: transformation of knapsack problem to open dimension problem

Abstract

Предметом статті є задача оптимальної упаковки куль різної розмірності в контейнер довільної геометричної форми. Мета полягає в тому, щоб побудувати математичну модель, в якій зв'язуються різні формулювання задачі. Задача упаковки куль (SPP) є задачею комбінаторної оптимізації, відомою як задача розкрою й упаковки. SPP полягає в розміщенні заданого набору куль із заданими радіусами в контейнері правильної або неправильної геометричної форми. Задача, яку необхідно вирішити, полягає в тому, щоб: дослідити математичні моделі двох постановок відповідно до класифікації задач розкрою й упаковки: задачі про рюкзак (KP) та задачі зі змінним розміром (ODP); побудувати математичну модель, яка дозволяє розв’язати задачу KP як задачу ODP. Використовувані методи: метод phi-функцій, збільшення розмірності задачі, гомотетичні перетворення. Задача KP формулюється як змішана задача дискретно-неперервного програмування. Пропонується новий підхід, в якому розв’язання задачі KP зводиться до розв’язання задачі ODP для упаковки нерівних і рівних куль у контейнерізі змінним коефіцієнтом гомотетії й який дозволяє використовувати jump-алгоритм для задачі KP. З цією метою задача KP для даного набору куль представляється у вигляді задачі нелінійного програмування, в якій коефіцієнт гомотетії розглядається в якості незалежної змінної, обмеженою знизу. Коефіцієнт гомотетії, який дорівнює одиниці, відповідає початковому розміру контейнера. Зображена графічна ілюстрація процесу оптимізації. Висновки. Запропонований підхід є методологічною основою для розв’язання задачі SPP. Універсальність підходу полягає в тому, що розв’язання задач іне залежить від її постановки (KP або ODP). Підхід застосовний для упаковки нерівних і рівних куль у контейнерах довільних просторових форм, для яких можуть бути побудовані phi-функції.