Векторні задачі дискретної оптимізації: коректність та методи розв"язання - Автореферат

Національна академія наук України Інститут кібернетики імені В.М. Глушкова УДК 519.854 Векторні задачі дискретної оптимізації: коректність та методи розв’язання 01.05.01 - теоретичні основи інформатики та кібернетики Автореферат дисертації на здобуття наукового ступеня доктора фізико-математичних наук СЕМЕНОВА Наталія Володимирівна Київ 2010 Дисертацією є рукопис. Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України. Науковий консультант: доктор фізико-математичних наук, професор, академік НАН України Сергієнко Іван Васильович, Інститут кібернетики ім. В.М. Глушкова НАН України, директор Офіційні опоненти: доктор фізико-математичних наук, старший науковий співробітник Донець Георгій Панасович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу економічної кібернетики, доктор фізико-математичних наук, професор Грищенко Олександр Юхимович, Київський національний університет імені Тараса Шевченка, професор кафедри обчислювальної математики, доктор фізико-математичних наук, професор Остапенко Валентин Володимирович, Науково-навчальний комплекс “Інститут прикладного системного аналізу” МОН і НАН України при НТУУ “КПІ”, завідувач відділу чисельних методів оптимізації. З дисертацією можна ознайомитися в науково-технічному архіві Інститутут кібернетики імені В.М. Глушкова НАН України за адресою: 03680 МСП Київ- 187, проспект Академіка Глушкова, 40. Автореферат розісланий “ 08 “ травня 2010 р. Учений секретар спеціалізованої вченої ради Вагіс О.А. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ Актуальність теми. Останні, як правило, суперечливі в тому розумінні, що якість порівнюваних альтернатив неможливо адекватно виразити одним комплекс-ним критерієм, що представляє деяку згортку вхідних критеріїв. Дискретним багатокритеріальным задачам присвячено ряд досліджень. Але розв’язання таких задач є непростою справою, навіть для простих задач питання про належність точки множині Парето є NP-складним. Вагомий внесок у розвиток теорії та методів багатокритеріальної дискретної оптимізації в Україні внесли І.В. Сергієнко, В.С. Михалевич, Н.З. Шор, В.О. Трубін, В.Л. Волкович, А.І. Кукса, Ю.Ю. Червак, В.О. Перепелиця, Л.М. Козерацька, Т.Т. Лебєдєва та інші вчені. Робота виконана у відповідності з планами наукових досліджень відділу методів дискретної оптимізації, математичного моделювання та аналізу складних систем Інституту кібернетики імені В.М. Глушкова НАН України: 1) С.Г. 135.02 “Розробити і ввести в експлуатацію ППП для розв’язування на ЄС ЕОМ у діалоговому режимі задач дискретної та нелінійної оптимізації” (1986-1990 рр., № держреєстрації 01860045745); 2) І.П.135.12 “Розробити методи і програмні засоби розв’язання окремих класів задач прикладної математики для різних типів сучасних ЕОМ” (1990-1994 рр.); 3) В.Г.Е. 135.14 “Розробка і обґрунтування методів розв’язування та програмно-алгоритмічного забезпечення окремих класів задач дискретної оптимізації для ПЕОМ (1991-1994 рр., № держреєстрації 01910033078); 4) В.Ф.135.01 “Розробити та дослідити інтегровані наукомісткі програмно-алгоритмічні засоби розв’язування окремих класів задач прикладної математики на сучасних ЕОМ (1995-1998 рр., № держреєстрації 0109V027578); 5) грант К4С100 Уряду України та Міжнародного Наукового Фонду “Розробка та дослідження методів розв’язування окремих класів задач цілочислового програмування складної природи” (1995 р.); 6) 2/610-97 “Розроблення моделей, методів і програмно-алгоритмічного забезпечення для аналізу та оптимізації волоконно-оптичних мереж зв’язку” за Державною науково-технічною програмою (1997-2000 рр., № держреєстрації 0197U005622); 7) І.П.135.09 “Розробити математичну теорію методи та програмні засоби розв’язування окремих класів задач прикладної математики” (1998-2001 рр., № держреєстрації 0198V005043); 8) М.Ф.135.10 “Аналіз даних задач дискретної оптимізації: коректність, стійкість, регуляризація” за програмою міжнародного науково-технічного співробіт-ництва між Україною і Російською Федерацією (1998-2004 рр., № держреєстрації 0198U003465); 9) В.Ф.135.02 “Розробка та обґрунтування проблемно-орієнтованих методів та програмно-алгоритмічних засобів для розв’язування деяких класів задач прикладної математики на ПЕОМ” (1999-2002 рр., № держреєстрації 0199V001031); 10) ВФК.135.13 Розробка нових методів розв’язання складних дискретних та багатоекстремальних задач оптимізації та їх застосування” (2002-2006 рр., № держреєстрації 0102U003213); 11) В.Ф.135.16 “Розробити та обґрунтувати методи та програмно-алгоритмічні засоби для створення нових інформаційних технологій та систем” (2003-2007 рр., № держреєстрації 0103U000712); 12) ДП/152-2003 “Розробка математичних моделей, методів, інформаційних технологій та програмно-алгоритмічного забезпечення для аналізу та оптимізації процесів прийняття рішень в задачах класифікації та кластерного аналізу” (2003-2004 рр., № держреєстрації 0103U008791); 13) Ф7/275-2001 “Побудова і дослідження методів та інформаційних технологій розв’язання оптимізаційних дискретних задач велико