УПАКОВКА ГОМОТЕТИЧНИХ СФЕРОЇДІВ У БІЛЬШОМУ СФЕРОЇДІ ЗА ДОПОМОГОЮ АЛГОРИТМУ СТРИБКА (JUMP ALGORITHM)
Ключові слова:
упаковка, куля, сфероїд, оптимізація, алгоритм стрибкаАнотація
У статті розглядається математична модель задачі оптимальної упаковки гомотетичних сфероїдів (сфер у конкретному випадку) більший сфероїд (сфера у конкретному випадку). Радіуси сфер мають бути змінними. Запропоновано новій алгоритм знаходження стартових точок, що належать області допустимих значень. З використанням алгоритмн стрибка, вирішення задачі зводиться до розв’язання послідовності задач математичного програмування, що дає об'єктивні покращення. Запропонована стратегія розв’язання складеться с чотирьох етапів. Перший етап включає формування стартових точок та обчислення локального мінімуму. Під час другого етапу виконуються безперервній перехід від одного локального мінімуму до іншого. На третьому етапі відбувається зменшення розмірності простору рішення. На четвертому етапі пари сфер перебудовуються, щоб отримати задані. Ми приводимо результати чисельних експериментів для сфер та сфероїдів.
Завантаження
Посилання
Wang, J. Packing of unequal spheres and automated radiosurgical treatment planning / J. Wang // Journal of Combinatorial Optimization. – 1999. – Vol.3. – P. 453–463.
Chen, D.Z. Algorithms for congruent sphere packing and applications / D.Z. Chen , X. Hu, Y. Huang,, Y. Li, J. Xu // Proc. of Sym. on Comp. Geometry'2001. – 2001. – P. 212–221.
Sutou, A. Global optimization approach to unequal sphere packing problems in 3D / A. Sutou, Y. Day // Journal of Op t. Theory and Appl. – 2002. – Vol. 114(3). – P. 671–694.
Uhler, C. Packing Spheroids with Overlap / C. Uhler, S.J. Wright // SIAM Rev. – 2013. – Vol. 55(4). – P. 671–706.
Stoyan, Yu. Packing of Various Solid Spheres into a Parallelepiped / Yu. Stoyan, G.Yaskov, G. Scheithauer // Central European Journal of Operational Research. – 2003. – Vol. 11(4). – P. 389–407.
Zeng, Z.Z. An algorithm to packing unequal spheres in a larger sphere / Z.Z. Zeng, W.Q. Huang, R.C. Xu // Advanced Mat. Research. – 2012. – Vol. 546-547. – P. 1464-1469.
Stoyan, Yu. Packing unequal circles into a strip of minimal length with a jump algorithm / Yu. Stoyan, G. Yaskov // Optimization letters. – 2014. –Vol. 8. – P. 949–970.
Stoyan, Yu.G. Packing identical spheres into a cylinder / Yu.G. Stoyan, G.N. Yaskov // Int. Transactions in Operational Research. – 2010. – Vol. 17(1). – P. 51–70.
Stoyan, Yu.G. A mathematical model and a solution method for the problem of placing various-sized circles into a strip / Yu.G. Stoyan, G.N. Yaskov // European Journal of Op erational Research. – 2004. – Vol. 156. – P. 590–600.
Wächter, A. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming / A. Wächter, L.T. Biegler // Mathematical Programming. – 2006. – Vol. 106(1). – P. 25–57.
Zoutendijk, G. Methods of feasible directions. A study in linear and non-linear programming / G. Zoutendijk. Amsterdam-London-New York-Princeton: Elsevier Publishing Company. – 1960. – 126 p.
