Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Дисертаційні роботи України
Фізико-математичні науки
Теоретичні основи інформатики та кібернетики

Диссертационная работа:

Шило Володимир Петрович. Методи розв'язання складних задач дискретної оптимізації: дисертація д-ра фіз.-мат. наук: 01.05.01 / НАН України; Інститут кібернетики ім. В.М.Глушкова. - К., 2003.

смотреть введение
Введение к работе:

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

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

У період становлення дискретної оптимізації, який нараховує трохи більше сорока років, з’явилося багато робіт, присвячених цій проблемі. Серед них монографії Корбута А.О. і Фінкельштейна Ю.Ю., Лесдона Л.С., Кофмана А. і Анрі-Лабордера А., Ху Т.; Ємелічева В.О., Ковальова М.М., Кравцова М.К; Пападімітріу Х. і Стайгліца К., Схрейвера А., роботи Журавльова Ю.І., Пардалоса П.М. та ін.

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

Вагомий внесок у розвиток дискретної оптимізації в Україні внесли Михалевич В.С., Сергієнко І.В., Шор Н.З., Трубін В.О., Червак Ю.Ю., Кукса А.І., Волкович В.Л., Перепелиця В.О. та інші вчені.

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

Побудова та дослідження методів розв’язання задач великої розмірності є одним із перспективних напрямків математичного (в тому числі дискретного) програмування. Розмірність та складність задачі математичного програмування визначається числом змінних, кількістю і характером обмежень, а також видом цільової функції. Дійсний же зміст терміну задача великої розмірності звичайно пов’язаний з можливостями обчислювальних алгоритмів, швидкістю, об’ємом оперативної пам’яті та іншими характеристиками ЕОМ, що використовуються. Методи розв’язання задач лінійного програмування великої розмірності досить добре розвинені, чого не можна сказати про цілочислові задачі. Цю прогалину стосовно задач цілочислового програмування та задач на графах автор значною мірою компенсував у своїй дисертаційній роботі.

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась у відповідності з планами наукових досліджень відділу №135 Інституту кібернетики імені В.М.Глушкова НАН України в рамках наукових тем та програм, в яких автор був виконавцем та відповідальним виконавцем (у більшості тем):

- С.Г. 135.02 «Розробити і ввести в експлуатацію ППП для розв’язування на ЄС ЕОМ у діалоговому режимі задач дискретної та нелінійної оптимізації» (1986 –1990 рр.), № держ. реєстрації 01860045745;

- В.Г.Е. 135.14 «Розробка і обгрунтування методів розв’язування та програмно-алгоритмічного забезпечення окремих класів задач дискретної оптимізації для ПЕОМ» (1991 – 1994 рр.), № держ. реєстрації 01910033078;

- В.Ф. 135.01 «Розробити та дослідити інтегровані наукомісткі програмно-алгоритмічні засоби розв’язування окремих класів задач прикладної математики на сучасних ЕОМ» (1994–1998 рр.), № держ. реєстрації 0195U024578;

- грант № К4С100 Уряду України та Міжнародного Наукового Фонду на 1995 рік «Розробка та дослідження методів розв’язування окремих класів задач цілочислового програмування складної природи»;

- І.П.135.09 «Розробити математичну теорію, методи та програмні засоби розв’язування окремих класів задач прикладної математики» (1998 – 2001рр.), № держ. реєстрації 0198U005043;

- проект 06.01/04104 “Розроблення моделей, методів і програмно-алгоритмічного забезпечення для аналізу та оптимізації волоконно-оптичних мереж зв’язку” Державної науково-технічної програми (1997 – 2000 рр.), № держ. реєстрації 0197U005622;

- програма міжнародного науково-технічного співробітництва між Україною і Російською Федерацією № 2М/98-98 " Аналіз даних завдань дискретної оптимізації: коректність, стійкість, регуляризація” (1998 – 2004 рр.), № держ. реєстрації 0198U003465;

- проект 01/07/97 “Побудова і дослідження методів та інформаційних технологій розв’язання оптимізаційних дискретних задач великої розмірності” Державного фонду фундаментальних досліджень (2001 – 2003 рр.), № держ. реєстрації 0101U007549;

- 1625 УНТЦ, проект “Математичне та програмне забезпечення оптимального проектування структур надійних мереж” (2001 – 2004 рр.).

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

Для досягнення мети в дисертації поставлені та розв’язані такі задачі:

- розробка підходу до автоматичного вибору алгоритму розв’язання оптимізаційної задачі;

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

- розробка нового методу локального пошуку для складних задач дискретної оптимізації;

- побудова нових алгоритмів локальної оптимізації для задач цілочислового програмування та задач на графах;

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

- розробка точних і наближених алгоритмів для задач на графах, що виникають при побудові кодів, які коригують помилки;

- оцінка знизу об’єму кодів для Z-каналу;

- визначення РЕСТАРТ розподілу та РЕСТАРТ критерію зупину алгоритму;

- розробка засобів для прискорення процесу розв’язання задач дискретної оптимізації;

- проведення серії обчислювальних експериментів по розв’язанню різних класів задач дискретного програмування запропонованими в дисертації та відомими методами;

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

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

Наукова новизна одержаних результатів, що виносяться до захисту:

- створено новий підхід до вирішення проблеми автоматичного вибору алгоритму розв’язання оптимізаційної задачі, що базується на використанні розробленого автором методу імовірнісної декомпозиції;

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

- для задач дискретної оптимізації складної природи запропоновано новий метод глобального рівноважного пошуку;

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

- запропоновано нові змістовні та математичні моделі задач пошуку логічних структур надійних комунікаційних мереж і алгоритми розв’язання таких задач;

- для задач на графах, що виникають при побудові кодів, які коригують помилки, розроблено і досліджено точні та наближені алгоритми;

- одержано нові оцінки знизу максимального об’єму кодів для Z-каналу;

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

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

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

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

Одержані в дисертації результати можуть слугувати теоретичною основою для подальшого дослідження різних аспектів розробки методів дискретної оптимізації. Вони можуть бути використані в учбовому процесі при читанні спеціальних курсів з дискретної оптимізації.

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи одержані автором особисто. У роботах, що написані у співавторстві, автору дисертації належить: [2] – розробка математичних моделей задач розміщення комутаційного обладнання та алгоритмів для розв’язання таких задач; [3–5] – алгоритми розв’язання задач оптимізації маршрутних стратегій; [6] – розробка методу імовірнісної декомпозиції для задач цілочислового лінійного програмування з булевими змінними великої розмірності та створення на його основі підходу до проблеми автоматичного вибору алгоритму розв’язання оптимізаційної задачі; [7] – отримання умов стійкості розв’язків випадково генерованих задач цілочислового лінійного програмування з булевими змінними; [10] – розробка процедур зведення задачі класифікації об’єктів до задачі розрізу графа та розв’язання цієї задачі; [12,13] – алгоритми розв’язання задач на графах та їх обгрунтування; [14] – створення РЕСТАРТ технології для прискорення процесу розв’язання задач дискретної оптимізації; [17,18] – розробка математичних моделей задач знаходження надійної логічної структури комунікаційної мережі при відмові її компонент та підходів до розв’язання таких задач; [19] – розробка та дослідження алгоритму пошуку покриття; [23] – математична постановка задачі про проведення взаємозаліків та алгоритми її розв’язання; [24] – алгоритми розв’язання задач про фарбування вершин графа; [26] – алгоритми розв’язання задач оптимального розміщення комутаційного обладнання в мережі передачі даних; [27] – розробка точних та наближених алгоритмів для ряду задач на графах; [28] – алгоритми розв’язання задач дискретної оптимізації, що виникають при побудові перешкодозахищених кодів, та їх обгрунтування; [29] – застосування РЕСТАРТ технології при розв’язанні цілочислових розподільних задач методом неявного перебору.

Апробація результатів дисертації. Результати досліджень, представлені в дисертації, доповідались і обговорювались на семінарах Наукової ради НАН України з проблеми “Кібернетика” (Київ, 1989–2002), Республіканському семінарі з дискретної оптимізації (Ужгород, 1989), 15-й Всесоюзній школі-семінарі з обчислювальних мереж (Москва, 1990), Міжнародній конференції “Теледоступ в наукових дослідженнях, медицині та бізнесі” (Київ, 2001), Conference “MaxClique 01” (University of Klagenfurt, Austria, 2001), 7-й та 8-й щорічних наукових конференціях НАУКМА (Київ, 2001, 2002), Міжнародній конференції “Актуальні проблеми інформатики” (Київ, 2002), 17th ACM Symposium on Applied Computing (Madrid, 2002), Міжнародній школі-семінарі “Теорія прийняття рішень”(Ужгород, 2002).

Публікації. Основні результати дисертації опубліковано в 29 наукових роботах. З них 23 – у наукових фахових виданнях (журналах та збірниках наукових праць), 6 робіт – у матеріалах наукових конференцій.

Подобные работы
Волох Людмила Василівна
Метод нелінійного оцінювання в задачах стохастичної оптимізації та ідентифікації
Роскладка Андрій Анатолійович
Параметричні задачі та стійкість при моделюванні евклідовими комбінаторними задачами оптимізації
Роскладка Олена Володимирівна
Задачі оптимізації на полікомбінаторних множинах: властивості та розв'язування
Рудянова Тетяна Миколаївна
Граничний аналіз задач векторної оптимізації
Ємець Олег Олексійович
Теорія і методи комбінаторної оптимізації на евклідових множинах в геометричному проектуванні
Онищенко Борис Олегович
Мінорантні методи глобальної стохастичної оптимізації
Савчук Михаил Николаевич
Асимптотические методы в задачах вероятностной комбинаторики
Норкин Владимир Иванович
Стохастические методы решения задач невыпуклого стохастического программирования и их приложения
Норкiн Володимир Iванович
Стохастичнi методи розв'язання задач неопуклого стохастичного програмування та єх застосування
Березовский Олег Анатольевич
Исследование алгоритмов решения экстремальных параметрических матричных задач с использованием методов негладкой оптимизации

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net