Алгоритм декомпозиції для розв’язання оптимізаційних задач розміщення
DOI:
https://doi.org/10.32626/2308-5916.2019-19.126-131Анотація
У статті розглядається задача розміщення двовимірних опуклих об'єктів у прямокутній області мінімальної площі, яка відноситься до класу задач упаковки і розкрою. Об'єкти, що розміщуються, можуть неперервно транслюватися і обертатися. Будується математична модель задачі розміщення у вигляді задачі нелінійного програмування з використанням методу phi-функцій. Для пошуку локально-оптимальних розв’язків пропонується ефективний алгоритм декомпозиції, який зводить вихідну задачу до послідовності підзадач нелінійного програмування значно меншою розмірності з меншим числом нелінійних нерівностей. Перевага цього підходу підтверджується результатами численних експериментівЗавантаження
Посилання
Wascher G., Hauner H. and Schumann H. An improved typology of cutting and packing problems. European Journal of Operational Research. 2007. Vol. 183 (3), № 16. P. 1109–1130.
Bennell J., Oliveira J. The geometry of nesting problems. A tutorial. European J. Operational Research. 2008. Vol. 184. P. 397–415.
Chazelle B., Edelsbrunner H., Guibas L. The complexity of cutting complexes. Discrete & Computational Geometry. 1989. Vol. 4 (2). P. 139–181.
Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications. 2010. Vol. 43 (5). P. 535–553.
Stoyan Yu., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimzation. 2016. Vol. 65 (2). P. 283–307.
Wachter A., Biegler L. T. On the implementation of an interiorpoint filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. Vol. 106 (1). P. 25–57.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:
Автори зберігають авторські права та надають журналу право першої публікації роботи, одночасно ліцензованої за ліцензією Creative Commons Attribution License, яка дозволяє іншим поширювати роботу з посиланням на авторство роботи та її першу публікацію в цьому журналі.
Автори можуть укладати окремі додаткові договірні угоди щодо неексклюзивного розповсюдження опублікованої в журналі версії роботи (наприклад, розміщувати її в інституційному репозиторії або публікувати в книзі) з посиланням на її першу публікацію в цьому журналі.
Авторам дозволяється та заохочується публікувати свої роботи онлайн (наприклад, в інституційних репозиторіях або на своєму вебсайті) до та під час процесу подання, оскільки це може призвести до продуктивного обміну, а також до більш раннього та більшого цитування опублікованих робіт (див. The Effect of Open Access).
