Анотація до роботи:

Рудюк Л.В. Математична модель та чисельні методи розв’язання задачі оптимізації розміщення прямокутників. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. – Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків, 2006.

Дисертація присвячена дослідженню задач розміщення геометричних об’єктів прямокутної форми.

Для розв’язання задачі розроблені нові ефективні методи.

При побудові математичної моделі задачі використовується подання неопуклої множини припустимих розв’язків задачі у вигляді об’єднання опуклих підмножин. Доведена можливість заміни розв’язання вихідної задачі розв’язанням ряду побудованих підзадач.

Обґрунтована можливість використання методу Розена для розв’язання побудованих підзадач оптимізації. Доведено теорему про часову складність ітерації методу Розена. Надана статистична оцінка часової складності розв’язання обраної підзадачі оптимізації методом Розена.

Розроблено метод G-проекції розв’язання побудованих підзадач оптимізації. Доведено теорему про збіжність методу G-проекції. Доведено теорему про часову складність ітерації методу G-проекції. Надана статистична оцінка часової складності розв’язання обраної підзадачі оптимізації методом G-проекції.

Для розв’язання вихідної задачі оптимізації розроблено метод спрямованого перебору підзадач оптимізації. Надана статистична оцінка часової складності розв’язання задачі оптимізації методом спрямованого перебору.

Розроблено програмне забезпечення, яке реалізує побудовані методи.

В дисертаційній роботі отримані нові теоретично обґрунтовані результати, за допомогою яких розроблено математичний апарат розв’язання задач геометричного проектування для класу неперервно диференційованих критеріїв якості з використанням градієнтних методів.

Основні наукові результати дисертації.

1. Вдосконалено математичну модель задачі оптимізації розміщення прямокутників для неперервно диференційованих критеріїв якості.

2. Розроблено метод побудови опуклих підмножин множини припустимих розв’язків. Доведено можливість заміни розв’язання вихідної задачі оптимізації на множині складної структури розв’язанням ряду побудованих підзадач на опуклих підмножинах.

3. Розроблено спеціальний чисельний метод G-проекції для розв’язання обраної підзадачі оптимізації, що використовує специфічні риси поставленої задачі.

4. Доведено збіжність методу G-проекції.

5. Доведено теореми про часову складність ітерації методу G-проекції та методу Розена. Розраховані статистистичні оцінки часової складності розв’язання обраної підзадачі оптимізації методом G-проекції та методом Розена. Зроблено висновок, що розробленим методом G-проекції знаходиться розв’язок обраної підзадачі оптимізації за значно менший проміжок часу, ніж методом Розена, так як часова складність методу G-проекції є поліномом третього ступеня, а методу Розена – поліномом п’ятого ступеня.

6. Розроблено метод спрямованого перебору побудованих підзадач для розв’язання вихідної задачі оптимізації.

7. Розраховано статистистичну оцінку часової складності розв’язання вихідної задачі оптимізації методом спрямованого перебору. Зроблено висновок, що методом спрямованого перебору підзадач знаходиться розв’язок задачі оптимізації за значно менший проміжок часу, ніж за допомогою методу повного перебору, так як часова складність методу повного перебору є експоненціальною, а часова складність методу спрямованого перебору є поліномом третього ступеня.

8. Розроблено програмне забезпечення для розв’язання задачі оптимізації розміщення прямокутників у прямокутній області.

9. З використанням розробленого програмного забезпечення методами G-проекції та спрямованого перебору розв’язані задачі оптимізації розміщення прямокутних об’єктів в прямокутнику для різних критеріїв якості.

10. Результати дисертаційної роботи знайшли застосування в навчальному процесі Житомирського державного технологічного університету в дипломному проектуванні спеціалістів та атестаційних роботах магістрів, а також при викладанні навчальних курсів бакалаврам.