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

Шило В.П. Методи розв’язання складних задач дискретної оптимізації. – Рукопис.

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

Розроблено нові науково обгрунтовані методи розв’язання задач дискретної оптимізації складної природи, проведено їх дослідження та порівняльний аналіз з відомими методами. Запропоновано і досліджено метод глобального рівноважного пошуку, розроблено алгоритми цього методу для різних класів задач дискретного програмування. Побудовано нові змістовні та математичні моделі задач пошуку логічних структур надійних комунікаційних мереж і алгоритми їх розв’язання. Для задач на графах, що виникають при побудові кодів, які коригують помилки, розроблено і досліджено точні та наближені алгоритми. Отримано нові оцінки знизу для Z-каналу та умови стійкості розв’язків випадково генерованих задач цілочислового програмування з булевими змінними. На основі теоретичних та експериментальних досліджень проведено порівняльний аналіз розроблених автором і відомих методів.

Створено теоретичні основи для дослідження проблеми прискорення процесу розв’язання складних задач дискретної оптимізації, а саме: розроблено так звану РЕСТАРТ технологію, а на базі запропонованого автором методу імовірнісної декомпозиції створено новий підхід до проблеми автоматичного вибору алгоритму розв’язання оптимізаційної задачі.

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

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

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

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

3. Побудовано нові змістовні та математичні моделі задач пошуку логічних структур надійних комунікаційних мереж, запропоновано шляхи розв’язання таких задач.

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

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

6. З використанням теорії дискретного та стохастичного програмування і нових понять РЕСТАРТ розподілу та РЕСТАРТ критерію зупину алгоритму вперше розроблено РЕСТАРТ технологію, яка дозволяє досягти значного зменшення середнього часу розв’язання задач дискретної оптимізації.

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

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