Аналіз стійкості векторних задач цілочислової оптимізації

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М. ГЛУШКОВА

УДК 519.872

Автореферат

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

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

АНАЛІЗ СТІЙКОСТІ ВЕКТОРНИХ ЗАДАЧ ЦІЛОЧИСЛОВОЇ ОПТИМІЗАЦІЇ

01.05.02 - математичне моделювання та обчислювальні методи

СЕРГІЄНКО ТЕТЯНА ІВАНІВНА

Київ - 2008

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

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

Науковий керівник:

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

Офіційні опоненти:

Григорків Василь Степанович, доктор фізико-математичних наук, професор, Чернівецький національний університет імені Ю. Федьковича, завідувач кафедри економіко-математичного моделювання;

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

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

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий "" _____________ 2008 р.

Учений секретар спеціалізованої вченої ради Синявський В.Ф.

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

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

Ж. Адамар на початку ХХ сторіччя зв'язав поняття коректно поставленої математичної задачі з такими її властивостями: задача є розв'язуваною, має єдиний розв'язок, і цей розв'язок неперервно залежить від зміни вхідних даних задачі. Третю з наведених властивостей коректної задачі звичайно називають стійкістю. У другій половині минулого сторіччя А.М. Тихоновим, М.М. Лаврєнтьєвим, В.К. Івановим та їх послідовниками була розроблена математична теорія розв'язання некоректних задач. У рамках цієї теорії були запропоновані методи регуляризації, що дозволяють замінити некоректну задачу, якій властивий непередбачуваний вплив похибки вхідних даних на її розв'язок, деякою коректною задачею, стійкою до збурень вхідних даних.

Досвід показує, що жодна оптимізаційна задача, яка виникає на практиці, не може бути коректно поставлена і розв'язана без застосування результатів теорії стійкості. Найбільш детально розробленими й висвітленими у науковій літературі є підходи до проведення аналізу стійкості однокритеріальних задач оптимізації. Вони представлені у багатьох публікаціях, зокрема, Ю. Куммера, Ю. Гуддата, Б. Банка, Є.Г. Білоусова, в яких основні результати були одержані з використанням властивостей точково-множинних відображень. Однак майже всі складні практичні задачі прийняття рішень є багатокритеріальними задачами вибору з множини допустимих розв'язків деякої підмножини альтернатив, що задовольняють наперед заданому принципу оптимальності. Найчастіше як принцип оптимальності розглядається оптимальність за Парето, проте часто використовуються також оптимальність за Слейтером і оптимальність за Смейлом. Під дослідженням стійкості векторної оптимізаційної задачі звичайно розуміють вивчення поведінки множини оптимальних (за Парето, Слейтером чи Смейлом) розв'язків при збуреннях вхідних даних задачі. Широке використання за останні десятиріччя дискретних оптимізаційних моделей і значний розвиток методів дискретного програмування зумовили зацікавленість дослідників у вивченні проблеми стійкості дискретних багатокритеріальних задач. Серед них найбільш розповсюдженими є задачі цілочислової оптимізації, в яких вимога цілочисельності виконується для всіх або частини змінних. Труднощі, що виникають при вивченні проблеми стійкості таких задач, обумовлені, зокрема, істотною складністю дискретних моделей, які навіть при незначних змінах у вхідних даних часто поводяться непередбачувано.

Дослідження проблеми стійкості векторних задач дискретної оптимізації здійснюються у двох основних напрямах: теоретичному і конструктивному. Теоретичний напрям орієнтований на отримання результатів "якісного" характеру, а саме на визначення та дослідження умов, за яких множині оптимальних розв'язків оптимізаційної задачі притаманна та чи інша наперед задана властивість, що характеризує стійкість задачі до малих збурень вхідних даних. Дослідження у теоретичному напрямі стосовно проблеми стійкості цілочислових задач векторної оптимізації були розпочаті ще у 80-х роках минулого сторіччя в Україні в Інституті кібернетики імені В.М. Глушкова НАН України і здійснювались Л.М. Козерацькою, Т.Т. Лебєдєвою, Т.І. Сергієнко, Н.В. Семеновою під керівництвом академіка І.В. Сергієнка. Інший, конструктивний підхід до проблеми стійкості векторних задач дискретної оптимізації спрямований на одержання кількісних оцінок допустимих збурень вхідних даних. Він найбільш широко представлений у роботах В.О. Ємелічева, В.О. Перепелиці та їх учнів і пов'язаний з поняттям радіуса стійкості, введеного вперше В.К. Леонтьєвим для однокритеріальної траєкторної задачі. стійкість векторна цілочислова оптимізація

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась у рамках наукових тем та проектів Інституту кібернетики імені В.М. Глушкова НАН України:

- К.Ф.135.16 "Дослідження проблем стійкості, параметричного і пост-оптимального аналізу задач дискретної оптимізації" (1993-1994 рр.), проект ДФФД України № 1/346;

- К.Ф.135.22 "Дослідження проблем стійкості, параметричного і пост-оптимального аналізу векторних задач дискретної оптимізації" (1994-1996 рр.), проект ДФФД України № 12.3/139;

- М.Ф.135.08 "Дослідження проблеми даних задачі дискретної оптимізації: коректність, стійкість, регуляризація" (1997-1998 рр.), проект ДФФД України № 1.4/299;

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

- ВФК.135.13 "Розробка нових методів розв'язання складних дискретних та багатоекстремальних задач оптимізації та їх застосування" (2002-2006 рр.), номер держреєстрації 0102U003213;

- В.Ф.135.16 "Розробити, обґрунтувати методи та програмно-алгоритмічні засоби для створення нових інформаційних технологій та систем" (2003-2007 рр.), номер держреєстрації 0103U000712.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи одержані автором особисто. У роботах, написаних у співавторстві, автору дисертаційної роботи належать: [1-3] - доведення умов стійкості для векторної задачі цілочислової оптимізації з лінійними частковими критеріями; [5] - дослідження властивостей множин Парето, Слейтера і Смейла та умов стійкості за векторним критерієм для частково цілочислової задачі оптимізації з лінійними частковими критеріями; [6, 13] - доведення властивостей збурених конусів перспективних напрямків та збурених множин Парето і Слейтера, обґрунтування підходів до регуляризації векторної задачі цілочислової оптимізації; [7, 10, 14-17] - дослідження умов стійкості множин оптимальних і неоптимальних розв'язків та різних типів стійкості задачі цілочислової оптимізації з квадратичними частковими критеріями щодо збурень вхідних даних у векторному критерії; [9, 15-17] - дослідження умов стійкості оптимальних і неоптимальних розв'язків та різних типів стійкості задачі векторної цілочислової оптимізації щодо збурень вхідних даних в обмеженнях; [11, 12, 16, 17] - дослідження умов стійкості різних типів для задачі векторної цілочислової оптимізації стосовно збурень всіх її вхідних даних.

Апробація результатів дисертації. Результати досліджень, викладених у дисертації, доповідались і обговорювались на наукових семінарах в Інституті кібернетики імені В.М. Глушкова НАН України (Київ, 1988-2007 рр.), на симпозіумі "Питання оптимізації обчислень" (Київ, 1993 р.), а також на семінарах і конференціях, зокрема: ІІ міжнародній школі-семінарі "Теорія прийняття рішень" (Ужгород, 2004 р.), Міжнародних конференціях "Problems of decision making under uncertainties" (Бердянськ, 2005 р.; Чернівці, 2007 р.), Міжнародній конференції "Математическое программирование и приложения" (Єкатеринбург, 2007 р.).

Публікації. Основні результати дисертації опубліковано у 17 наукових працях. Із них 12 це статті в наукових фахових виданнях (3 статті опубліковано без співавторів), 5 праць надруковано у матеріалах наукових конференцій.

Структура та обсяг роботи. Дисертаційна робота, повний обсяг якої

становить 164 сторінки, складається із вступу, чотирьох розділів, висновків, 1 рисунка (одна сторінка) та списку використаних джерел, який містить 112 найменувань (8 сторінок).

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

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

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

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

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

Всі розглянуті типи стійкості по-різному описують ситуацію, за якої

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

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

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

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

У підрозділі 2.2 розроблено підхід до регуляризації за векторним критерієм вказаної повністю цілочислової задачі з лінійними частковими критеріями. Він ґрунтується на лемі 2.3, в якій стверджується, що задачі притаманна -стійкість за векторним критерієм, а саме: існує таке число, що для будь-якої збуреної матриці з множини збурених вхідних даних має місце включення. Підхід до регуляризації можливо нестійкої за векторним критерієм задачі полягає у переході від розв'язання початкової задачі до розв'язання -стійкої за векторним критерієм зміненої задачі, в якій порівняно з початковою, по-перше, певним чином змінено матрицю на матрицю, де параметр збурення, і, по-друге, відшукуються розв'язки з множини Слейтера. Доведено, що будь-який оптимальний за Слейтером розв'язок такої зміненої задачі з можливими збуреннями (помилками) у вхідних даних є одночасно Парето-оптимальним розв'язком початкової задачі.

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

Нехай - замикання будь-якої множини.

Теорема 2.10. Необхідною умовою -стійкості за векторним критерієм частково цілочислової задачі є виконання рівності. Якщо множина є обмеженою і замкненою, то вказана умова є і достатньою.

Теорема 2.11. Нехай множина замкнена. Необхідною умовою -стійкості за векторним критерієм задачі є рівність. Якщо, крім того, множина обмежена, то вказана рівність є і достатньою умовою.

Теорема 2.12. Якщо множина обмежена і замкнена, то виконання співвідношення є необхідною і достатньою умовою -стійкості за векторним критерієм задачі.

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

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

Встановлено зв'язки між поняттями стійкості за обмеженнями, з одного боку, і поняттями стійкого за обмеженнями ефективного розв'язку і ядра стійкості за обмеженнями, з іншого.

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

Введено також поняття стійкого за обмеженнями неефективного розв'язку.

Означення 3.8. Точку назвемо стійким за обмеженнями неефективним розв'язком задачі, якщо, таке, що тобто або, або.

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

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

Основні результати, одержані в розділі 3 відносно питань стійкості задачі, сформульовано в наступних твердженнях.

Позначимо - внутрішність множини .

Теорема 3.5. Співвідношення є необхідною і достатньою умовою як -, так і -стійкості за обмеженнями задачі.

Теорема 3.9. Нехай. Задача -стійка за обмеженнями тоді і тільки тоді, коли множина містить тільки стійкі за обмеженнями неефективні розв'язки.

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

Теорема 3.14. Задача -стійка за обмеженнями тоді і тільки тоді, коли має місце включення.

Теорема 3.16. Задача -стійка за обмеженнями тоді і тільки тоді, коли вона -стійка за обмеженнями.

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

Твердження 3.1. Існує число, таке, що для будь-яких значень параметра збурення з інтервалу справедлива рівність, більше того.

Наслідок 3.6. Існує число, таке, що для будь-якого значення параметра збурення задачі і є стійкими а обмеженнями.

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

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

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

Теорема 4.2. Множина стійка за векторним критерієм.

Теорема 4.3. Множина стійка за векторним критерієм.

Теорема 4.4. Всі точки множини нестійко за векторним критерієм належать цій множині, причому.

Теорема 4.5. Будь-яка точка x множини нестійко за векторним критерієм належить цій множині, причому.

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

Нехай - будь-яка множина з сукупності. Ядро стійкості за векторним критерієм множини означимо відповідно.

Отримано також висновки щодо стійкості задач. Зокрема, задачі завжди притаманна -стійкість (відповідно -стійкість) за векторним критерієм.

Підрозділ 4.2 присвячено з'ясуванню умов стійкості задачі відносно збурень всіх її вхідних даних: і тих, що відносяться до векторного критерію з квадратичними частковими критеріями, і тих, що пов'язані з описом допустимої області, яку складають всі цілочислові точки деякого опуклого многогранника. У пункті 4.2.1 доведені твердження стосовно необхідних та достатніх умов стійкості за векторним критерієм і обмеженнями (скорочено - стійкості) задачі.

Теорема 4.11. Необхідною і достатньою умовою -стійкості задачі є її -стійкість за обмеженнями. Введено поняття ядра стійкості задачі.

Наслідок 4.9. Задача є -стійкою тоді і тільки тоді, коли задача є -стійкою за обмеженнями.

Теорема 4.13. Задача є -стійкою тоді і тільки тоді, коли виконуються такі дві умови: задача є -стійкою за векторним критерієм, а задача є -стійкою за обмеженнями.

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

Теорема 4.15. Задача -стійка тоді і тільки тоді, коли вона -стійка за векторним критерієм і -стійка за обмеженнями.

Теорема 4.17. Задача -стійка тоді і тільки тоді, коли вона -стійка за векторним критерієм і -стійка за обмеженнями.

У пункті 4.2.2 вивчено деякі питання стійкості задач пошуку розв'язків, оптимальних за Слейтером і оптимальних за Смейлом. Стосовно задачі доведено, що її -стійкість (відповідно-стійкість) еквівалентна -стійкості за обмеженнями (відповідно-стійкості за обмеженнями).

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

1. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.И. Вопросы параметрического анализа и исследования устойчивости многокритериальных задач целочисленного линейного программирования // Кибернетика. - 1988. - № 3. - С. 41-44.

2. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.И. Необходимые и достаточные условия устойчивости многокритериальных задач целочисленного линейного программирования // Докл. АН УССР. Сер. А - 1988. - № 10. - С. 76-78.

3. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.И. Задачи целочисленного программирования с векторным критерием: Параметрический анализ и исследование устойчивости // Докл. АН СССР. - 1989. - 307, № 3. - С. 527-529.

4. Сергиенко Т.И. Об устойчивости по ограничениям многокритериальной задачи целочисленного программирования // Докл. АН УССР. Сер. А. - 1989. - № 3. - С. 79-81.

5. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.И. Задача частично целочисленной векторной оптимизации: вопросы устойчивости // Кибернетика. - 1991. - № 1. - С. 58-61.

6. Козерацкая Л.Н., Лебедева Т.Т., Сергиенко Т.И. О регуляризации задач целочисленной векторной оптимизации // Кибернетика и систем. анализ. - 1993. - № 3. - С. 172-176.

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

8. Сергиенко Т.И. Устойчивость по ограничениям задачи векторной оптимизации на целочисленных точках выпуклого многогранника // Докл. НАН Украины. - 2003. - № 11. - С. 61-64.

9. Лебедева Т.Т., Сергиенко Т.И. Сравнительный анализ различных типов устойчивости по ограничениям векторной задачи целочисленной оптимизации // Кибернетика и систем. анализ. - 2004. - № 1. - С. 63-70.

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

11. Лебедева Т.Т., Сергиенко Т.И. Устойчивость по векторному критерию и ограничениям векторной целочисленной задачи квадратичного программирования // Кибернетика и систем анализ. - 2006. - № 5. - С. 63-72.

12. Сергиенко Т.И. Устойчивость по векторному критерию и ограничениям целочисленных задач поиска решений, оптимальных по Слейтеру и Смейлу // Компьютерная математика. - Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины. - 2008. - № 1. - С. 145-151.

13. Козерацька Л.М., Лебєдєва Т.Т., Сергієнко Т.І. До питання про регуляризацію цілочислових задач векторної оптимізації // Тези симп. "Питання оптимізації обчислень", 22-24 листопада 1993. - Київ: Ін-т кібернетики ім. В.М. Глушкова НАН України, 1993. - С. 80-81.

14. Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Деякі умови оптимальності та стійкості в задачах векторної дискретної оптимізації з квадратичними функціями критеріїв // ІІ міжнародна школа-семінар "Теорія прийняття рішень". Ужгород, Ужгород. нац. ун-т, 2004. С. 55-56.

15. Lebedeva T.T., Semenova N.V., Sergienko T.I. Stability of optimal and non-optimal sets of solutions to vector discrete optimization problems // Abstracts of Intern. Conf. "Problems of decision making under uncertainties (PDMU-2005). September 12-17, 2005". - Berdyansk, 2005. - P. 34-36.

16. Лебедева Т.Т., Семенова Н.В., Сергиенко Т.И. Об устойчивости по векторному критерию и ограничениям векторной задачи дискретного квадратичного программирования // Ассоциация математического программирования. Информ. бюллетень № 11, конф. "Математическое программирование и приложения": Тез. докл. - Екатеринбург: Ин-т математики и механики, Урал. отд. РАН, 2007. - С. 194-195.

17. Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Про п'ять типів стійкості за векторним критерієм і обмеженнями векторної задачі дискретного квадратичного програмування // Abstracts of Intern. Conf. "Problems of decision making under uncertainties (PDMU-2007). May 2125, 2007". Chernivtsi, 2007. P. 164-165.

АНОТАЦІЇ

Сергієнко Т.І. Аналіз стійкості векторних задач цілочислової оптимізації. Рукопис.

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

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

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

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

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

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

Ключові слова: векторний критерій, цілочислова оптимізація, збурення вхідних даних, аналіз стійкості, типи стійкості, регуляризація.

Сергиенко Т.И. Анализ устойчивости векторных задач целочисленной оптимизации. Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2008.

В диссертации разработаны и усовершенствованы подходы к исследованию устойчивости векторных задач целочисленной оптимизации, состоящие в отыскании решений, оптимальных по Парето, Слейтеру или Смейлу.

Для полностью и частично целочисленной задач оптимизации с линейными частичными критериями получены необходимые и достаточные условия устойчивости разных типов относительно возмущений исходных данных в векторном критерии.

Для задачи векторной оптимизации на конечном множестве целочисленных точек выпуклого многогранника исследованы вопросы устойчивости оптимальных и неоптимальных по Парето решений к возмущениям исходных данных в ограничениях. Установлена связь между понятиями устойчивого по ограничениям оптимального и неоптимального решений и понятиями разных типов устойчивости задачи по ограничениям. Получены необходимые и достаточные условия устойчивости по ограничениям. Проведен анализ пяти типов устойчивости задачи по ограничениям. Сделан вывод о том, что выбор того или иного выпуклого многогранника для описания допустимой области задачи может влиять на ее устойчивость. Наиболее подходящим с точки зрения обеспечения устойчивости разных типов к изменениям исходных данных в ограничениях является многогранник, все целочисленные точки которого принадлежат его внутренности.

Для векторной задачи целочисленной оптимизации с квадратичными частичными критериями и конечным допустимым множеством проведен анализ устойчивости ряда подмножеств множества ее допустимых решений относительно возмущений исходных данных векторного критерия. Результаты такого анализа показали, что все оптимальные по Смейлу и неоптимальные по Слейтеру решения и только они задачи обладают уникальным свойством: при достаточно малых возмущениях векторного критерия эти решения устойчиво сохраняют принадлежность соответствующему подмножеству допустимого множества подмножеству всех решений, оптимальных по Смейлу, или подмножеству всех решений, неоптимальных по Слейтеру. Учитывая указанное свойство, разработан общий подход к исследованию устойчивости разных типов, получены необходимые и достаточные условия устойчивости разных типов относительно возмущений исходных данных векторного критерия.

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

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

Ключевые слова: векторный критерий, целочисленная оптимизация, возмущения входных данных, анализ устойчивости, типы устойчивости, регуляризация.

Sergienko T.I. Stability analysis of vector integer optimization problems. - Manuscript.

Thesis for Candidate Degree in Physics and Mathematics; specialty 01.05.02 - Mathematical Modelling and Computation Methods. - V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2008.

Approaches to investigating of stability of vector integer optimization problems are developed and improved. Necessary and sufficient conditions of several types of stability with respect to perturbations of initial data of vector integer optimization problems with different kinds of partial criterions and principles of optimality (Pareto, Slater or Smale) were obtained.

Analysis of stability with respect to vector criterion of the integer and mixed-integer programming problems with linear partial functions were carried out. Analysis of several types of stability with respect to quadratic vector criterion of integer optimization problem were worked out on the base of results of investigating the connection of such stability with stability of some optimal and nonoptimal solutions sets.

Analysis of stability with respect to constraints of multi-objective integer optimization problem are carried out for every considered type of stability. The relationship among stability of vector integer optimization problem with quadratic vector criterion and linear constraints with respect to perturbations of all initial data, stability with respect to initial data changes in linear constraints, and stability with respect to initial data changes in vector criterion is established.

Approaches to regularization of vector integer optimization problem were carried out. These approaches connect with the substitution of unstable ill-posed initial problem by the perturbed stable problem.

Key words: vector criterion, integer optimization problems, analysis of stability, perturbations of initial data, types of stability, regularization.

Размещено на Allbest.ru

...