Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 519.854

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

01.05.01 - теоретичні основи інформатики та кібернетики

Автореферат дисертації на здобуття наукового ступеня

доктора фізико-математичних наук

СЕМЕНОВА Наталія Володимирівна

Київ 2010

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий консультант: доктор фізико-математичних наук, професор, академік НАН України Сергієнко Іван Васильович, Інститут кібернетики ім. В.М. Глушкова НАН України, директор

Офіційні опоненти: доктор фізико-математичних наук, старший науковий співробітник Донець Георгій Панасович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу економічної кібернетики,

доктор фізико-математичних наук, професор Грищенко Олександр Юхимович, Київський національний університет імені Тараса Шевченка, професор кафедри обчислювальної математики,

доктор фізико-математичних наук, професор Остапенко Валентин Володимирович, Науково-навчальний комплекс “Інститут прикладного системного аналізу” МОН і НАН України при НТУУ “КПІ”, завідувач відділу чисельних методів оптимізації.

Захист відбудеться “ 11 “ червня 2010 р. об 11 годині на засіданні спеціалізованої вченої ради Д 26.194. 02 в Інституті кібернетики імені В.М. Глушкова НАН України за адресою: 03680 МСП Київ- 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві Інститутут кібернетики імені В.М. Глушкова НАН України за адресою: 03680 МСП Київ- 187, проспект Академіка Глушкова, 40.

Автореферат розісланий “ 08 “ травня 2010 р.

Учений секретар

спеціалізованої вченої ради Вагіс О.А.

Размещено на http://www.allbest.ru/

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Необхідність у подальшій розробці та удосконаленні методів дослідження коректності та розв'язання векторних задач дискретної оптимізації обґрунтовує актуальність дисертаційної роботи. Дискретним багатокритеріальным задачам присвячено ряд досліджень. Але розв'язання таких задач є непростою справою, навіть для простих задач питання про належність точки множині Парето є 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 “Побудова і дослідження методів та інформаційних технологій розв'язання оптимізаційних дискретних задач великої розмірності” (2001-2005 рр., № держреєстрації 0100U007549);

14) В.Ф.К.135.24. “Розробити та дослідити нову інформаційну технологію розв'язання різних класів дискретних оптимізаційних задач трансобчислювальної складності” (2007-2011 рр., № держреєстрації 0107U003610);

15) ВФ.135.26. “Розробити методи та програмно-алгоритмічні засоби розв'язання задач дискретної оптимізації для створення нових комп'ютерних технологій, у тому числі Grid-технологій” (2008-2012 рр., № держреєстрації 0108U001237);

16) ДЗ/470-2009. “Оптимізація процесу діагностики захворювань методами багатовимірного статистичного аналізу та дискретної оптимізації (2009-2010 рр., № держреєстрації” 0109U007130).

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

Досягнення мети роботи пов'язане із постановкою та розв'язанням таких проблем:

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

– знаходження необхідних і достатніх умов стійкості за векторним критерієм та за обмеженнями векторних задач дискретної оптимізації;

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

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

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

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

– побудова та обґрунтування ефективних методів та алгоритмів розв'язання різних класів задач дискретної оптимізації (у тому числі з векторним критерієм);

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

Об'єкт дослідження. Векторні задачі дискретної оптимізації, задачі дискретної оптимізації за умов невизначеності, неоднозначності та керованості даними. модель оптимізація векторний задача

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

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

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

Досліджено проблему розв'язуваності задач векторної оптимізації. Встановлено нові необхідні і достатні умови існування ефективних розв'язків за Парето, за Слейтером і за Смейлом, умови стійкої (нестійкої) розв'язуваності векторних задач за можливих збурень вхідних даних.

Досліджені різні типи стійкості векторних задач цілочислової оптимізації пошуку множин Парето, Слейтера та Смейла, які мають опуклі квадратичні та диз'юнктивні функції обмежень, до збурень вхідних даних обмежень. Сформульовані необхідні й достатні умови стійкості за обмеженнями. Отримані достатні умови стійкості за критерієм векторних задач дискретної оптимізації.

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

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

Розроблено та обґрунтовано поліедральний підхід до розв'язання векторних задач дискретної оптимізації на різних комбінаторних множинах: перестановок, розміщень, поліперестановок, полірозміщень та ін. з різними функціями критеріїв.

Досліджено складні задачі дискретної оптимізації з неточно заданими коефіцієнтами цільової функції і опуклими функціями обмежень.

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

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

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

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

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

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

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи отримані автором особисто. З робіт, виконаних із співавторами, на захист виносяться лише результати, одержані особисто здобувачем. У роботах, виконаних у співавторстві, автору дисертації належать: у монографії [1] - розділи 1, 2, 5, 6, 7, параграф 4.4 розділу 4, параграфи 9.5 і 9.6 розділу 9; в [8, 9, 10, 11] - постановка задачі, необхідні і достатні умови оптимальності розв'язків, підхід до розв'язання задачі, алгоритми; в [12-14] - поліедральний підхід до розв'язання задачі, умови оптимальності, алгоритм; в [15] - загальна схема дослідження, теореми 4-11, алгоритм розв'язання задачі, аналіз результатів обчислювального експерименту; в [16] - теореми 2-7, в [17-19] - постановка задачі, загальна схема дослідження; в [20-21, 28] - постановка задачі, загальна схема дослідження, достатні умови стійкості, результати розділів 6, 7 в [21]; в [22] - дослідження властивостей допустимої області задачі, критерії допустимості та оптимальності, алгоритми розв'язання задачі; в [23] - постановка задачі, розділ 1; в [24] - постановка задачі, теореми 1-3, алгоритм; в [25-27] - введення шести класів задач з керованими та невизначеними даними, встановлення властивостей та співвідношень між класами, розробка та обгрунтування декомпозиційного підходу та алгоритмів; в [30-31] - результати розділів, присвячених умовам оптимальності, топологічним і структурним властивостям множин вхідних даних, при яких зберігається ефективність розв'язків, розробка поліедрального підходу; в [32] - постановка задачі, основні поняття та означення, підхід до розв'язання задачі.

Решта 6 статей написано без співавторів.

Апробація результатів дисертації. Основні результати досліджень, викладені у дисертації, доповідались на наукових семінарах в Інституті кібернетики імені В.М. Глушкова НАН України (Київ, 1987-2010), Київському національному університеті імені Тараса Шевченка та на таких наукових конференціях, симпозіумах та семінарах: 3-ій українській конференції з автоматичного керування “Автоматика-96” (Севастополь, 1996); науково-технічній конференції ”Методы математического программирования и их программное обеспечение” (Свердловск, 1989); Intern. Summer Seminar “Stochastic Dinamical Systems” (Судак, 2003); міжнародній конференціії “Обчислювальна та прикладна математика”, присвяченій 80-річчю академіка НАНУ І.І. Ляшка (Київ, 2002); Міжнародних конференціях: “Математическое программирование и приложения“ (Єкатеринбург, 2003 і 2007); “Dynamical systems modelling and stability investigation“ (Київ, 1999 і 2003); ”Моделювання та оптимізація складних систем” (Київ, 2001); ”Problems of Decision Making under Uncertainties” (Тернопіль, 2004; Бердянськ, 2005; Алушта, 2006; Чернівці, 2007; Рівне, 2008; Східниця, 2009); IV Всеросійському симпозіумі “Математическое моделирование и компъютерные технологии”, (Кисловодськ, 2000); Всеросійській конференції ”Дискретный анализ и исследование операций” (Новосибірськ, 2000); Intern. Conference on applied mathematics dedicates to the 65-th anniversary of B.N. Pshenichniy (Київ, 2002); міжнародному симпозіумі “Питання оптимізації обчислень” (Київ, 1993, Кацивелі, 2001, 2005, 2007, 2009); Intern. Ukrainian - Polish Workshop “Problems of stochastic and discrete optimization” (Канів, 2005); Міжнар. конференціях, присвячених: 70-річчю акад. І.В. Сергієнка, “Applied Optimization and Metaheuristic Innovations” (Київ, 2006); 50-річчю Інституту кібернетики імені В.М. Глушкова НАНУ, “Discrete and Global Optimization” (Ялта, 2008); міжнародних школах-семінарах “Теорія прийняття рішень” (Ужгород, 2004); “Problems of Decision Making under Uncertainties“ (Новий Світ, 2007, 2008; Кам'янець-Подільський, 2009). International conference “Knowledge, Dialogue, Solution” (Varna, 2006, 2007, 2008; Київ, 2009); міжнародній школі-семінарі “Методы оптимизации и их приложения” (Іркутськ, 1990); Республіканському семінарі з дискретної оптимізації (Ужгород, 1989); міжнародних науково-практичних конференціях “Трансформаційні процеси в економіці держави та регіонів” (Запоріжжя, 2006) та “Математичне та програмне забезпечення інтелектуальних систем” (Дніпропетровськ, 2007).

Публікації. Основні результати та висновки дисертації опубліковані у 76 наукових працях, з них 1 монографія, 27 статей у наукових фахових виданнях, затверджених у переліку ВАК України, 4 - в зарубіжних журналах, 44 - у матеріалах та тезах доповідей на міжнародних наукових конференціях.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, семи розділів, висновків, списку використаних джерел (285 найменувань). Загальний обсяг роботи становить 297 сторінок, основний текст роботи викладено на 267 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

У підрозділі 3.3 досліджені питання існування строго та слабо ефективних (напівефективних) розв'язків задачі (С,Х) та рівності всіх видів ефективних множин.

У підрозділі 3.4 досліджена розв'язуваність задач векторної оптимізації з необмеженою многогранною допустимою областю.

Сформульовані і доведені необхідні і достатні умови існування розв'язків. Досліджена розв'язуваність задач векторної оптимізації за умов необмеженої допустимої області та можливих збурень вхідних даних.

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

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

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

У підрозділі 4.4 досліджені деякі структурні і топологічні властивості простору початкових даних.

В підрозділі 4.5 сформульовані достатні умови стійкості і нестійкості задачі пошуку Парето-оптимальних розв'язків.

У підрозділі 4.6 представлені результати вивчення стійкості за обмеженнями векторних задач цілочислової оптимізації з опуклими квадратичними функціями обмежень. Визначення умов стійкості в змісті введених означень ґрунтується на встановленні ряду фактів, що стосуються наступних питань: існування околу O (u) точки u такого, що задача Q_P (F,X) розв'язувана uO (u), обмеженість множини , для деякого ₀.

У підрозділі 4.7 представлені необхідні й достатні умови для всіх типів стійкості за обмеженнями задачі Z_P (F,X).

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

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

У пункті 5.3. для ілюстрації запропонованого методу наведений приклад розвязаня задачі вигляду (5) за точним алгоритмом.

Розроблений декомпозиційний метод для розв'язання задач вигляду (5) був реалізований на ПЕОМ в обчислювальному середовищі Turbo Pascal. Для розв'язання підзадач лінійного програмування використовувався симплекс-метод з відновленням точності та упакованим зберіганням вхідної матриці, а для розв'язання підзадач частково цілочислового лінійного програмування використовувався метод гілок та меж Ленда-Пауелла. Був проведений обчислювальний експеримент по розв'язанню тестових задач, умови яких генерувались за допомогою датчика псевдовипадкових чисел, результати якого наведені в таблиці 5.1. Аналіз результатів проведеного обчислювального експерименту показав, що розроблений декомпозиційний метод є досить ефективним для розв'язання досліджених задач цілочислової оптимізації з неоднозначно заданими даними.

У підрозділі 5.4 ідеї декомпозиційного підходу поширені на задачі цілочислової оптимізації, які одночасно містять неоднозначно задані дані двох типів (керовані та неточно задані) у векторі c та матриці A.

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

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

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

У підрозділі 6.2 представлено декомпозиційний підхід до знаходження гарантуючих і оптимістичних розв'язків задач (10) і (11).

Основна ідея запропонованих точного і наближеного методів полягає в наступному. Якщо розв'язок задачі МР є недопустимим у задачі (11), то він виключається з наступного розгляду додаванням нового лінійного обмеження до обмежень вигляду (16) задачі МР. Таким чином, обмеження (16) має таку властивість, що відтинає недопустимий розв'язок, а також частину недопустимої області задачі (11) із усіх наступних розглядів. Усі додані обмеження є правильними відсікаючими площинами, тобто такими, що не відтинають ніяку частину допустимої області нелінійної задачі (11).

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

У підрозділі 6.4 описані деякі способи задання множин невизначеності: як дискретних і многогранних множин, як множин, що містять збурення, обмежені за нормою, та отримані критерії перевірки розв'язків на допустимість у задачах (10) і (11) при деяких множинах невизначеності.

У підрозділі 6.6 розроблений підхід застосовано до розв'язання задачі цілочислової лінійної оптимізації з даними, що задаються множинами їх можливих значень.

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

У підрозділі 7.1 дана загальна характеристика та формальна постановка задачі векторної оптимізації на комбінаторній множині перестановок.

Теорми 7.1-7.4 встановлюють взаємозв'язок між задачею і , визначеній на неперервній допустимій множині. Це дає можливість застосовувати класичні методи неперервної оптимізації до розв'язання векторних комбінаторних задач на перестановках і на цій основі розвивати нові ефективні методи, використовуючи властивості комбінаторних множин і їх опуклих оболонок.

У підрозділі 7.4 побудований алгоритм розв'язання векторної задачі на комбінаторній множині перестановок.

У підрозділах 7.5-7.8 досліджені також векторні задачі оптимізації на інших комбінаторних множинах. Розроблено та обґрунтовано поліедральний підхід до розв'язання векторних задач на комбінаторних множинах: перестановок, розміщень, поліперестановок, полірозміщень та ін. з лінійними та дробово-лінійними функці-ями критеріїв. Наведені результати обчислювального експерименту.

ВИСНОВКИ

У дисертації розроблені теоретичні основи математичного апарату дослідження коректності та розв'язання різних класів задач дискретної оптимізації за умов багатокритеріальності, можливих збурень, керованості і невизначеності вхідних даних. Дисертація є новим комплексним дослідженням, що розв'язує важливі актуальні наукові проблеми як теоретичного напряму, пов'язані з якісним аналізом векторних задач дискретної оптимізації: визначенням та дослідженням умов коректності, так і конструктивного: побудови та обгрунтування точних та наближених методів розв'язання різних класів задач цілочислової та комбінаторної оптимізації за умов множинно заданих та керованих даних.

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

1. Створено теоретичні основи математичного апарату дослідження коректності та розв'язання різних класів задач дискретної оптимізації за умов можливих збурень та невизначеності вхідних даних.

2. Досліджено проблему розв'язуваності задач векторної оптимізації. Встановлено необхідні і достатні умови існування розв'язків за Парето, за Слейтером і за Смейлом, достатні умови стійкої (нестійкої) розв'язуваності таких задач при можливих збуреннях вхідних даних.

3. Досліджені різні типи стійкості векторних задач цілочислової оптимізації пошуку множини Парето, які мають опуклі квадратичні та диз'юнктивні функції обмежень до збурень вхідних даних обмежень.

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

5. Досліджені задачі цілочислової оптимізації з неточно заданими даними, які відповідають різним ситуаціям, що моделюються; розроблено та обґрунтовано декомпозиційний підхід до розв'язання різних класів таких задач.

6. Розроблено та обґрунтовано поліедральний підхід до розв'язання векторних задач дискретної оптимізації на різних комбінаторних множинах: перестановок, розміщень, поліперестановок, полірозміщень та ін. з лінійними, дробово-лінійними та опуклиими функціями критеріїв.

7. Досліджено складні задачі дискретної оптимізації з неточно заданими коефіцієнтами цільової функції і опуклими функціями обмежень.

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

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

10. Розроблено декомпозиційний метод розв'язання векторних задач з допустимою областю частково дискретної структури.

11. Запропоновані методи розв'язання задач дискретної оптимізації, що поєднують пошук оптимального розв'язку із знаходженням невизначених та керованих даних моделі.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

1. Семенова Н. В. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи дослідження та розв'язання / Н.В. Семенова, Л.М. Колєчкіна. Київ: Наук. думка, 2009. 266 с.

2. Семенова Н. В. Методы поиска гарантирующих и оптимистических решений задач целочисленной оптимизации в условиях неопределенности данных / Н. В. Семенова // Кибернетика и систем. анализ. 2007. № 1. С.103-114.

3. Семенова Н. В. Устойчивость по ограничениям векторных задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений / Н. В. Семенова // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2007. №6. С. 132-139.

4. Семенова Н. В. Гарантирующие и оптимистические решения задач целочисленной оптимизации с выпуклыми квадратичными функциями ограничений / Н. В. Семенова // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2006. №5. С. 39-47.

5. Семенова Н.В. О решении задач целочисленной оптимизации на выпуклых множествах в условиях неопределенности данных / Н.В. Семенова // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2005. №4. С. 107-112.

6. Семенова Н.В. Условия оптимальности в векторных задачах комбинаторной оптимизации / Н.В. Семенова // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2008. №7. С. 152-160.

7. Семенова Н.В. О решении векторных задач частично дискретной оптимизации / Н.В. Семенова // Комп'ютерна математика. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2008. №2. С. 156-164.

8. Семенова Н.В. Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и систем. анализ. 2008. № 3. С. 158-172.

9. Семенова Н.В. Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. 2008. № 6. С. 26-41.

10. Семенова Н.В. Розв'язання багатокритеріальних задач комбінаторної оптимізації на множині поліперестановок / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Доповіді НАН України. 2009. № 2. С. 41-48.

11. Семенова Н.В. Оптимізація на комбінаторній множині перестановок в умовах неточно заданих даних / Н.В. Семенова, О.С. Мащенко // Вісник Київського університету. Серія фіз.-мат. науки. 2009, вип. 3. С. 184-189.

12. Семенова Н.В. Поліедральний підхід до розв'язання одного класу векторних задач комбінаторної оптимізації / Н.В. Семенова, Л.М. Колєчкіна // Доповіді НАН України. 2009. № 6. С. 46-53.

13. Семенова Н.В. Многокритериальные задачи на комбинаторном множестве полиразмещений: полиэдральный подход к их решению / Н.В. Семенова, Л.Н. Колечкина // Кибернетика и систем. анализ. 2009. №3. С. 118-126.

14. Семенова Н.В. Розв'язування задач векторної оптимізації з дробово-лінійними функціями критеріїв на комбінаторній множині розміщень / Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна // Наук. вісті Нац. техн. ун-ту України «Київський політехнічний інститут». 2009. № 2. С. 53-60.

15. Семенова Н.В. Об одном подходе к решению векторных задач с дробно-линейными функциями критериев на комбинаторном множестве размещений / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. 2010. №1. С. 131-144.

16. Сергиенко И.В. О существовании решений в задачах векторной оптимизации / И.В. Сергиенко, Т.Т. Лебедева, Н.В. Семенова // Кибернетика и систем. анализ. 2000. №6. С. 39-46.

17. Лебєдєва Т.Т. Деякі умови оптимальності та розв'язуваності в задачах векторної оптимізації з опуклою допустимою множиною / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2002. № 1. С. 142 -148.

18. Лебєдєва Т.Т. До питання про розв'язуваність задач векторної оптимізації з необмеженою допустимою областю / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Комп'ютерна математика. Оптимізація обчислень. 2. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України. 2001. С. 221-227.

19. Лебєдєва Т.Т. Умови оптимальності та розв'язуваності в задачах лінійної векторної оптимізації з опуклою допустимою множиною / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Доповіді НАН України. 2003. №10. С. 80-85.

20. Лебедева Т.Т. Об устойчивости по критерию векторных задач целочисленного квадратичного программирования / Т.Т. Лебедева, Н.В. Семенова, Т.И. Сергиенко // Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України, 2003. № 2. С.140-146.

21. Лебедева Т.Т. Устойчивость векторных задач целочисленной оптимизации: взаимосвязь с устойчивостью множеств оптимальных и неоптимальных решений / Т.Т. Лебедева, Н.В. Семенова, Т.И. Сергиенко // Кибернетика и систем. анализ. 2005. № 4. С. 90-100.

22. Сергиенко И.В. Задачи целочисленного программирования с неоднозначно заданными данными: точные и приближенные решения / И.В. Сергиенко, Н.В. Семенова // Кибернетика и систем. анализ.1995. № 6. С. 75-91.

23. Семенов В.В. О векторной задаче оптимального управления в гильбертовом пространстве / В.В. Семенов, Н.В. Семенова // Кибернетика и систем. Анализ. 2005. № 2. С. 117-130.

24. Сергиенко И.В. Некоторые задачи целочисленного программирования с неоднозначно заданными данными / И.В. Сергиенко, В.А. Рощин, Н.В. Семенова // Проблемы управления и информатики. 1998. № 6. С. 116-123.

25. Сергиенко И.В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными / И.В. Сергиенко, В.А. Рощин, Н.В. Семенова // Журнал вычислительной математики и математической физики. 1990. 29, №5. С. 786-791.

26. Рощин В.А. Вопросы решения и исследования одного класса задач неточного целочисленного программирования / В.А. Рощин, И.В. Сергиенко, Н.В. Семенова // Кибернетика. 1989. № 2. С. 42-47, 64.

27. Сергиенко И.В. Решение задач неточного целочисленного программирования / И.В. Сергиенко, В.А. Рощин, Н.В. Семенова // Доклады АН УССР. 1988. № 12. С. 61-64.

28. Lebedeva T.T. Stability of vector integer optimization problems with quadratic criterion functions / T.T. Lebedeva, N.V. Semenova, T.I. Sergienko // Theory of stochastic processes. Kyiv, Institute of Mathematics of NASU. 2004. 10 (26), № 3-4. P. 95-101.

29. Семенова Н. Векторные задачи на комбинаторном множестве полиразмещений: условия оптимальности и подход к решению / Наталия Семенова // Inform. Theories and Knowledge.”-Sofia, Bulgaria. 2008. 2. P. 187-195. (Intern. Book Series “Information science and computing”, N7).

30. Natalia Semenova. Vector Combinatorial Problems in a Space of Combinations with Linear Fractional Functions of Criteria / N. Semenova, L. Kolechkina, A. Nagirna // Information theories & applications. 2008. 15, № 3. С. 240-245.

31. Natalia Semenova. Multicriterion problems on the combinatorial set of polyarrangements / N. Semenova, L. Kolechkina // Information Theories and Knowledge. 2009. 2. P. 115-127. (Intern. Book Series “Information science and computing”, N7).

32. Семенова Н.В. Многокритериальные задачи лексикографической оптимизации c линейными функциями критериев на нечетком множестве альтернатив / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Information Theories and Knowledge. 2009. 3. P. 139-149. (Intern. Book Series “Information science and computing”, N7).

33. Семенова Н.В. Устойчивость по ограничениям векторных задач целочисленной оптимизации с дизъюнктивными линейными функциями ограничений / Н.В. Семенова // XII-th International conference “Knowledge-dialogue-solution”. Proceedings. 2006. FOI-commerce. Sofia. P. 162-165.

34. Рощин В.А. О решении задач целочисленного программирования с неточными даными / В.А. Рощин, Н.В. Семенова, И.В. Сергиенко // Методы матема-тического программирования и их программное обеспечение. Тезисы докл. научно-технич. конф., Свердловск, 1989.- С. 104-105.

35. Рощин В. А. Исследование одного класса задач целочисленного программиро-вания с неточными данными / В.А. Рощин, Н.В. Семенова, И.В. Сергиенко // Методы оптимизации и их приложения. Тезисы докл. Международная школа-семинар (10-22 сентября 1989г., Иркутск). Иркутск, 1989. С. 163.

36. Рощин В.А. Метод решения некоторых задач целочисленного программирования с неточными данными / В.А. Рощин, Н.В. Семенова, И.В. Сергиенко // Республиканский семинар по дискретной оптимизации. Тезисы докл. (Ужгород, 20-22 ноября 1989г.). Киев. 1990. С. 64-65.

37. Семенова Н.В. Декомпозиційний метод розв'язування одного класу задач цілочислового програмування з неточними даними / Н.В. Семенова // Симпозіум “Питання оптимізації обчислень“ (22-24 листопада 1993 р.). Kиїв. 1993. С. 153-154.

38. Сергієнко І.В. Наближене розв'язування задач цілочислового програмування в умовах неоднозначно заданих даних / І.В. Сергієнко, В.О. Рощин, Н.В. Семенова // 3-я українська конференція з автоматичного керування “Автоматика-96“. Праці. 1 (Севастополь, 9-14 вересня 1996 р.).

39. Сергієнко І.В. Метод декомпозиції для розв'язування задач цілочислового програмування з неоднозначно заданими даними / І.В. Сергієнко, В.О. Рощин, Н.В. Семенова // Intern. cоnf. “Dynamical systems modeling and stability investigation“. Thesis of cоnf. reports (May 25-26, 1999). Київ, 1999.

40. Сергиенко И.В. О проблеме разрешимости задач векторной оптимизации / И.В. Сергиенко, Т.Т. Лебедева, Н.В. Семенова // Сборник науч. трудов IV Всероссийского симп. “Математическое моделирование и компъютерные технологии”, 2. Кисловодск, 2000. С. 36-37.

41. Сергиенко И.В. О cуществовании решений в задачах векторной целочисленной оптимизации / И.В. Сергиенко, Т.Т. Лебедева, Н.В. Семенова // Всероссийская конференция ”Дискретный анализ и исследование операций”. Материалы конференции. Новосибирск: Изд-во ИМ СО РАН. 2000. С. 142.

42. Лебєдєва Т.Т. До питання про розв'язуваність задач векторної оптимізації з необмеженою допустимою областю / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Комп'ютерна математика. Оптимізація обчислень. Зб. наук. праць. 2.- Київ: Ін-т кібернетики імені В.М. Глушкова НАН України.- 2001. С. 221 - 227.

43. Сергієнко І.В. Існування розв'язків в задачах векторної оптимізації / І.В. Сергієнко, Т.Т. Лебєдєва, Н.В. Семенова // ”Моделювання та оптимізація складних систем”. Міжнародна конференція. Праці конференції. 1. Київ, Вид.-полігр. центр “Київський університет”. 2001. С. 40-42.

44. Lebedeva T.T. Conditions of optimality and solvability in vector optimization problems with a convex feasible domain / T.T. Lebedeva, N.V. Semenova, T.I. Sergienko // Intern. Conf. on applied mathematics dedicates to the 65-th anniversary of B.N. Pshenichniy. Abstracts. Kyiv. 2002. P. 48.

...