Рябенко Антон Євгенович. Математичні моделі та методи для векторних задач оптимізації організаційних структур та землекористування: дисертація канд. фіз.-мат. наук: 01.05.02 / Дніпропетровський національний ун-т. - Д., 2003.
Анотація до роботи:
Рябенко А.Є. Математичні моделі та методи для векторних задач оптимізації організаційних структур та землекористування. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02- математичне моделювання та обчислювальні методи. Дніпропетровський національний університет. Дніпропетровськ, 2003.
У роботі автором побудована та досліджена математична модель для процесів формування організаційних структур та землекористування орними угіддями.
Основні результати полягають у наступному.
Запропонована узагальнена математична модель, що сформульована у вигляді векторної задачі покриття графа типовими підграфами.
Здійснено обґрунтування оцінок обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, у тому числі знайдено новий NP-важкий клас в оптимізаційній постановці, встановлено важкорозв’язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у ВЦФ двох критеріїв вигляду MAXSUM.
В класах NP-важких та важкорозв’язуваних задач покриття графа зірками та ланцюгами виділено нові поліноміально розв’язувані підкласи одно- та двокритеріальних задач. Розроблено відповідні алгоритми їх розв’язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності.
Здійснено подальший розвиток теорії алгоритмів з оцінками стосовно одно- та багатокритеріальних задач покриття графа ланцюгами. Для багатокритеріальної задачі покриття графа ланцюгами двох типів побудовано малотрудомісткий алгоритм та доведені теореми, що встановлюють достатні умови, при яких цей алгоритм майже завжди гарантує знаходження розв’язку, точного за критеріями вагового вигляду та асимптотично точного за критерієм кількості ланцюгів у покритті, в 1-критеріальному випадку цей алгоритм є статистично ефективним. Для оптимізаційної задачі покриття графа скінченою множиною ланцюгів побудовано малотрудомісткий алгоритм градієнтного типу та доведено теореми про достатні умови його асимптотичної точності.
Досліджена інтервальна задача покриття графа зірками, тобто при умові, коли ребра графа зважені інтервальними значеннями. Здійснено зведення інтервальної задачі покриття до двокритеріальної із векторною вагою ребер, доведено її важкорозв’язуваність, а також факт її нерозв’язуваності за допомогою алгоритмів лінійної згортки критеріїв.
У дисертації наведено нове вирішення наукової задачі, що полягає у побудові нових математичних моделей та розробці методів і алгоритмів розв’язання задач формування організаційних структур та землекористування орними угіддями.
Автором запропонована узагальнена математична модель, що сформульована у вигляді векторної задачі покриття графа типовими підграфами, та на відміну від існуючих більш адекватно відображає суть реальних задач, тому що враховує необхідність використання фіксованих структур у шуканих розв’язках, а також різні види невизначеності, наприклад, інтервальне задання даних та умову багатокритеріальності.
Досліджено векторні задачі покриття графів зірками та ланцюгами, що найчастіше зустрічаються в процесі моделювання різноманітних варіантів задачі формування цільових груп та задачі землекористування.
Здійснено обґрунтування оцінок обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, в тому числі : знайдено NP-важкий клас в оптимізаційній постановці, встановлено важкорозв’язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у ВЦФ двох критеріїв вигляду MINSUM. Виділено нові поліноміально розв’язувані підкласи одно- та двокритеріальних задач у класах NP-важких та важкорозв’язуваних задач покриття графа зірками та ланцюгами. Розроблено відповідні алгоритми їх розв’язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності.
Здійснено подальший розвиток теорії алгоритмів з оцінками стосовно одно- та багатокритеріальних задач покриття графа ланцюгами. Для багатокритеріальної задачі покриття графа ланцюгами двох типів побудовано малотрудомісткий алгоритм та доведені теореми, що встановлюють достатні умови, при яких цей алгоритм майже завжди гарантує знаходження розв’язку, точного за критеріями вагового вигляду та асимптотично точного за критерієм кількості ланцюгів у покритті. В 1-критеріальному випадку цей алгоритм є статистично ефективним. Для оптимізаційної задачі покриття графа скінченою множиною ланцюгів побудовано малотрудомісткий алгоритм градієнтного типу та доведено теореми про достатні умови його асимптотичної точності.
Досліджена інтервальна задача покриття графа зірками, тобто при умові, що ребра графа заважені інтервальними значеннями. Здійснено зведення інтервальної задачі покриття до двокритеріальної із векторною вагою ребер, доведено її важкорозв’язуваність, а також факт її нерозв’язуваності за допомогою алгоритмів лінійної згортки критеріїв.
Усі отримані результати сформульовано у вигляді теорем та лем, доведення яких базується на застосуванні математичного апарату теорії дискретної оптимізації, теорії складності дискретних задач, методів оцінювання обчислювальної складності дискретних багатокритеріальних задач, методів інтервального числення, теорії алгоритмів з оцінками та теорії ймовірності.
Теоретичні результати, отримані в дисертації, можна рекомендувати для використання при розробці програмного забезпечення, що призначено для комп’ютерних систем підтримки прийняття рішень у галузі сільськогосподарського виробництва, а також у галузі індустріальної соціології при організації соціально-економічних відносин в колективах з метою формування цільових груп.
Публікації автора:
Перепелиця В.О., Рябенко А.Є. Оцінки надійності в задачах формування цільових груп// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. - 2000. - №1. - С. 90-93.
Перепелиця В.О., Рябенко А.Є. Дослідження обчислювальної складності теоретико-графової задачі формування цільових груп// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. - 2000. - №2. - С. 100-104.
Перепелиця В.О., Рябенко А.Є. Ефективні алгоритми для задач покриття графів зірками і ланцюгами// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. - 2002. - №2. - С. 74-80.
Заховалко Т.В., Рябенко А.Е. Исследование разрешимости интервальной задачи покрытия графа звездами с помощью алгоритмов линейной свертки критериев//Питання прикладної математики та математичного моделювання.- Дніпропетровськ: РВВ ДНУ, 2003.–С.55-65.
Перепелиця В.О., Рябенко А.Є. Теоретико-графова модель задач формування цільових груп//Економічна кібернетика: проблеми методології та підготовки фахівців. Матер. V Всеукр. наук.-метод.конф. – К.: КНЕУ, 2000. – С.138 – 139.
Перепелица В.А., Рябенко А.Е. О принятии решений в задачах с интервальными данными//"Problems of Decision Making and Control (PDMU-2002)". Abstract. – Киев, 2002. – С.85.
Рябенко А.Є. Оптимізація рішень для інтервальних задач на графах//Праці Міжнар.шк.-семінара “Теорія прийняття рішень”. – Ужгород, 2002. – С.60.
