Оптимальне розміщення геометричних об’єктів. Декомпозиція множини припустимих розв’язків на опуклі підмножини. Модифікація методу можливих напрямків, генетичного алгоритму в комбінації з методом спрямованого переходу. Метод спрямованого переходу.
Аннотация к работе
Задачі оптимізації розміщення полягають у пошуку оптимального розміщення геометричних обєктів в заданій області при наявності заданих технологічних обмежень і критерію оптимальності. Ці задачі виникають у промисловості (оптимального розкрою матеріалів, раціонального використання відходів), при побудові генеральних планів підприємств (розміщення будівель з метою мінімізації сумарної вартості проекту, яка пропорційна площі ділянки, що займає підприємство, та довжині комунікацій), при проектуванні різноманітних пристроїв, якість яких залежить від параметрів розміщення елементів (розміщення модулів апаратури з метою мінімізації довжини зєднувальної мережі), на будівництві, при розрахунку максимально можливих навантажень на елементи конструкції (знаходження небезпечного для конструкції розміщення тимчасових навантажень, при якому виникають максимальні внутрішні зусилля), при розміщенні вантажів та проектуванні транспортних засобів (розміщення елементів з метою мінімізації відхилення центру мас системи від заданої точки або множини точок), у авіамоторобудуванні (розміщення лопаток турбіни з метою мінімізації дисбалансу), при складанні розкладів виконання заданого обєму робіт та ін. Для таких задач розроблено багато різних підходів та методів розвязання, кожен з яких має свої особливості, переваги та недоліки. Відповідно, більшість розроблених методів використовують цю особливість, тобто потребують лінійності функції цілі та, часто, лінійності функцій, які входять у систему обмежень задачі. Існує ряд практичних задач оптимізації, в математичних постановках яких критерій якості розміщення описується нелінійною функцією.У вступі обґрунтовано актуальність теми дослідження, визначено обєкт, предмет, мету, задачі та методи дослідження, сформульовано наукове та практичне значення даної роботи. Розвязок цих задач знаходиться на межі множини припустимих розвязків. Серед практичних задач оптимізації розміщення, відокремлені та надалі розглядаються задачі, в яких: · обєкти, що розміщуються, можна розбити на орієнтовані прямокутники (паралелепіпеди); В другому розділі наведено змістовні постановки практичних задач оптимізації розміщення; зроблено математичну постановку задачі оптимізації розміщення прямокутників на опуклій області та задачі оптимізації розміщення на області із зонами заборони обєктів, кожен з яких можна розбити на прямокутники (паралелепіпеди). , , де - параметр розміщення; - множина припустимих розвязків задачі, що визначається обмеженнями неперетину обєктів та невиходу їх за межі заданої опуклої області; - неперервно диференційована функція або функція максимуму неперервно диференційованих функцій.Побудовано математичну постановку та методи розвязання задачі оптимізації розміщення обєктів, кожен з яких можна розбити на прямокутники (паралелепіпеди), на опуклій області із зонами заборони. Запропоновано математичну постановку та побудовано методи розвязання задачі пошуку невигідного розміщення навантажень. Запропоновано математичну постановку задачі оптимізації розміщення прямокутників, як задачі частково-дискретного програмування, що дозволило описати множину припустимих розвязків задачі системою лінійних нерівностей з булевими змінними.
План
ОСНОВНИЙ ЗМІСТ РОБОТИ
Вывод
1. Побудовано математичну постановку та методи розвязання задачі оптимізації розміщення обєктів, кожен з яких можна розбити на прямокутники (паралелепіпеди), на опуклій області із зонами заборони.
2. Запропоновано математичну постановку та побудовано методи розвязання задачі пошуку невигідного розміщення навантажень.
3. Запропоновано математичну постановку задачі оптимізації розміщення прямокутників, як задачі частково-дискретного програмування, що дозволило описати множину припустимих розвязків задачі системою лінійних нерівностей з булевими змінними.
4. При розвязанні поставлених задач: - Набула подальшого розвитку ідея декомпозиції множини припустимих розвязків на опуклі підмножини.
- Розроблено метод спрямованого переходу між підмножинами, модифікацію генетичного алгоритму та модифікований метод гілок та меж для організації вибору підмножин.
- Розроблено модифікацію методу можливих напрямків для розвязання мінімаксних підзадач.
5. Створено програмний продукт для розвязання задач оптимізації розміщення геометричних обєктів з використанням запропонованих підходів.
6. Проведено ряд обчислювальних експериментів для порівняння результатів розвязання задачі з аналогами.
7. Результати дисертаційної роботи використовуються на дочірньому підприємстві “Житомир Ворд Білдінг Сістемс Україна”, на ПП “Здобуток ІІ” (м.Житомир) та в навчальному процесі у Житомирському державному технологічному університеті.
Список литературы
1. Яремчук С.І., Шаповалов Ю.О. Застосування генетичного алгоритму до задач розміщення // Вісник ЖІТІ / Технічні науки. - 2002. - №(2)21 - С.130-133.
2. Яремчук С.І., Шаповалов Ю.О. Оптимізація розміщення прямокутних обєктів на опуклій області методом гілок та меж // Вісник ЖІТІ, 2004. - №4(31) Том 2 / Технічні науки - С.161-167.
3. Яремчук С.І., Шаповалов Ю.О. Модифікація методу можливих напрямків для задачі оптимізації розміщення // Вісник Хмельницького національного університету, 2005. - №5(69) Ч.1,Т.2 / Технічні науки - С.146-151.
4. Яремчук С.І., Шаповалов Ю.О. Оптимізація розміщення обєктів, які можна розкласти на прямокутники //Радиоэлектроника и информатика, 2006. - №1. - С.87-90.
5. С.І. Яремчук, Ю.О. Шаповалов, І.М. Музика. Оптимізація розміщення обєктів спеціального виду на області з зонами заборони // Вісник ЖДТУ, 2006. - №4(39) / Технічні науки. - С.258-263.
6. Шаповалов Ю.А. Размещение источников поля с использованием методов дискретного программирования // Проблемы теоретической и прикладной математики: Труды 34-й Региональной молодежной конференции. Екатеринбург: УРО РАН. - 2003. - С.161-167.
7. Яремчук С.И., Шаповалов Ю.А. Оптимизация размещения элементов прямоугольной формы методом возможных направлений // Труды пятой международной научно-практической конференции “Современные информационные и электронные технологии”. Одесса. - 2005. - С.214.
8. Яремчук С.І., Шаповалов Ю.О. Імовірнісні методи в задачах оптимізації розміщення // Тези ХХХ наукової конференції, присвяченої 45-ій річниці Житомирського державного технологічного університету. Житомир. - 2005. - С.40.
9. Яремчук С.І., Шаповалов Ю.О. Розвязання мінімаксної задачі оптимізації розміщення прямокутників модифікованим методом можливих напрямків // Збірник матеріалів ІІІ українсько-польської наукової конференції молодих вчених “Механіка ті інформатика”. Хмельницький. - 2005. - С.211-214.
10. Яремчук С.І., Шаповалов Ю.О. Метод можливих напрямків для задачі оптимізації розміщення фігур, що складаються з прямокутників. // 10-й ювілейний міжнародний молодіжний форум "Радіоелектроніка і молодь в ХХІ ст.": Зб. матеріалів форуму. - Харків: ХНУРЕ, 2006. - C.473.
11. С.И. Яремчук, Ю.А. Шаповалов. Модификация метода возможных направлений для задачи оптимизации размещения объектов специального вида. // Электронное моделирование, 2007. - №2. - С. 29-38.
12. С.И. Яремчук, Ю.А. Шаповалов. Минимаксная задача оптимизации размещения объектов специального видана многосвязной области. // Кибернетика и системный анализ, 2007. - №3. - С. 128-137.