Баранов О. В. Математичні моделі та методи комбінаторної оптимізації на класах множин перестановок у геометричному проектуванні

Об'єкт - процес розміщення геометричних об'єктів у заданій області. Мета - розробка нових та вдосконалення існуючих математичних моделей та методів розв'язання комбінаторних оптимізаційних задач розміщення геометричних об'єктів на класах множин перестановок за рахунок скорочення надлишковості в описі областей допустимих розв'язків і врахування властивостей цільових функцій задач цього класу. Методи - методи багатовимірної геометрії та лінійної алгебри - для дослідження властивостей класів множин перестановок, відображених в евклідів простір; опуклий аналіз - для побудови оцінок мінімуму опуклих продовжень функцій, заданих на класах множин перестановок; методи оптимізації - для розв'язання оптимізаційних задач геометричного проектування; методи геометричного проектування для побудови математичних моделей задач розміщення геометричних об'єктів. Апаратура - персональний комп'ютер. Теоретичні та практичні результати - побудовані математичні моделі і розроблені методи та алгоритми можуть служити основою для побудови систем розв'язання комбінаторних оптимізаційних задач геометричного проектування в різних галузях, таких як проектування планів розкрою матеріалу в металообробній, текстильній галузях промисловості, при упаковці вантажів для перевезення, при складуванні контейнерів, компоновці обладнання тощо. Наукова новизна - вперше розроблено метод оптимізації лінійних функцій з лінійними обмеженнями на комбінаторних множинах, в основі якого лежать визначення фундаментальної системи розв'язків системи лінійних обмежень-нерівностей в комбінації зі схемою випадкового пошуку та розв'язки допоміжних екстремальних задач на комбінаторних множинах. Побудовано оцінки розв'язків, отриманих розробленим методом. Це дозволяє розв'язувати задачі комбінаторної оптимізації з лінійною цільовою функцією і лінійними обмеженнями на класах комбінаторних множин; побудовано математичну модель двокритеріальної задачі упаковки n-вимірних паралелепіпедів у n-вимірному паралелепіпеді. Запропоновано підхід до розв'язання задачі на основі схеми послідовної оптимізації критеріїв і методу гілок та меж. Це дає можливість враховувати розташування центру ваги системи при розв'язанні задач щільної упаковки n-вимірних паралелепіпедів у n-вимірному паралелепіпеді. Отримали подальший розвиток: метод дослідження екстремальних властивостей опуклих і сильно опуклих функцій, заданих на дискретних множинах. Запропоновані оцінки мінімуму опуклих і сильно опуклих функцій з урахуванням лінійних обмежень на класах комбінаторних множин перестановок. Побудовано оцінки та достатні умови мінімуму опуклих і сильно опуклих функцій на нових класах множин перестановок: множинах перестановок кортежів і композиції перестановок. Це дає можливість реалізації методів типу гілок та меж і оцінювання наближених розв'язків для задач оптимізації на зазначених класах множин; метод оптимізації оцінок мінімуму опуклих і сильно опуклих функцій на класах комбінаторних множин перестановок на основі використання методів недиференційованої оптимізації. Це дозволяє підвищити ефективність оцінок, що використовуються в методах типу гілок та меж; математична модель задачі розміщення n-вимірних паралелепіпедів у n-вимірному паралелепіпеді в частині врахування ортогональної орієнтації n-вимірних паралелепіпедів за допомогою перестановок їх лінійних розмірів. Це дозволяє одержувати більш ефективні розв'язки задач розміщення. Результати дисертаційної роботи впроваджені при розв'язанні задач раціонального розміщення заготівок, на листах металу в ЗАТ "Харківметал-2" (акт впровадження від 12.01.2010 р.). Розроблений комплекс математичних моделей і програмного забезпечення використано для автоматизації процесу розміщення прямокутних наліпок на листах матеріалу на етапі підготовки поліграфічної продукції до друку в ТОВ Видавництво "Ранок" м. Харкова (акт впровадження від 01.03.2010 р.). Результати роботи впроваджені в навчальний процес Харківського національного університету радіоелектроніки на кафедрі системотехніки (акт впровадження від 30.09.2010 р.). Розроблені математичні моделі, методи та програмне забезпечення можуть бути використані на підприємствах, діяльність яких пов'язана з складуванням та транспортуванням різного роду об'єктів, розкроєм матеріалу, у поліграфічному виробництві тощо.