Теоретико-числові методи розв"язання задач комбінаторної оптимізації - Автореферат

Національна академія наук УкраїниАвтореферат дисертації на здобуття наукового ступеня доктора технічних наук Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та Міністерства освіти та науки України. Науковий консультант: доктор фізико-математичних наук, професор, академік НАН України СЕРГІЄНКО Іван Васильович, Інститут кібернетики імені В.М. Офіційні опоненти: доктор технічних наук, член-кореспондент НАН України ГУБАРЕВ Вячеслав Федорович, Інститут космічних досліджень НАН України та НКА України, заступник директора, доктор технічних наук, старший науковий співробітник ТЕСЛЕР Геннадій Семенович, Інститут проблем математичних машин і систем НАН України, головний науковий співробітник, доктор технічних наук, професор ВОРОНІН Альберт Миколайович, Національний авіаційний університет МОН України, професор.Необхідність розвязання саме цих задач стимулювало розвиток теорії комбінаторної оптимізації; 2) задачі з комбінаторики і комбінаторної оптимізації мають місце в теорії звязку; 3) в розпізнаванні мовних сигналів, розпізнаванні образів також є задачі комбінаторної оптимізації. Тому однією з важливих проблем цієї області є виявлення властивостей цільової функції задач комбінаторної оптимізації, використання яких дозволяло б установити закономірність зміни її значень від упорядкування аргументу і від специфіки структури вхідних даних, формування математичних постановок цих задач, які б відображали їхню комбінаторну природу, виявлення властивостей комбінаторних конфігурацій як аргумента цільової функції. Створення методології комплексного підходу до аналізу цільової функції в задачах комбінаторної оптимізації, який охоплює широкий спектр досліджень: комбінаторних матриць, комбінаторних функцій, комбінаторних конфігурацій як аргументу цільової функції, підкласів розвязних задач із класів комбінаторної оптимізації, результати якого дають можливість розробити методи знаходження оптимального розвязку, що ґрунтуються на розпізнаванні структури вхідних даних - актуальні проблеми комбінаторної оптимізації. Метою роботи є створення нового підходу до виявлення властивостей цільової функції в задачах комбінаторної оптимізації, розроблення методу моделювання структури вхідних даних і нових загальних постановок задач комбінаторної оптимізації, які б відображали їхню комбінаторну природу, введення нових підкласів розвязних задач із різних класів, розроблення нового локального методу знаходження оптимального розвязку, що ґрунтується на певному способі упорядкування комбінаторних конфігурацій та моделюванні і розпізнаванні структури вхідних даних, виявлення спільних властивостей утворення та упорядкування комбінаторних конфігурацій (аргументу цільової функції), узагальнення методів їхнього генерування. Предмет дослідження - комбінаторні конфігурації як аргумент цільової функції, комбінаторні матриці і комбінаторні функції, якими задаються вхідні дані, структурне перетворення вхідних даних, залежність цільової функції від упорядкування комбінаторних конфігурацій та від транспозиції елементів перестановки, підкласи розвязних задач із класів задач комбінаторної оптимізації.З використанням цих властивостей розроблено метод моделювання структури вхідних даних і сформульовано нові постановки задач комбінаторної оптимізації, вхідні дані в яких задаються функціями натурального аргументу.