автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Дискретные экстремальные задачи в условиях неопределенности: вопросы стойкости

ЗАПОРІЗЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ЗІНЬКОВСЬКА ЮЛІЯ СЕРГІЇВНА

УДК 519.8

ДИСКРЕТНІ ЕКСТРЕМАЛЬНІ ЗАДАЧІ В УМОВАХ НЕВИЗНАЧЕНОСТІ: ПИТАННЯ СТІЙКОСТІ

-01.05.02- Математичне моделювання та обчислювальні методи в наукових дослідженнях

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

ЗАПОРІЖЖЯ -1997

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

Робота виконана в Запорізькому державному університеті Міністерства освіти України. Науковий керівник

доктор фізико-математичних наук, професор Перепелиця Віталій Опанасович

Запорізький державний університет, зав. кафедрою економічної кібернетики

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

доктор фізико-математичних наук, професор Яковлев Сергій Всеволодова1 Університет Внутрішніх Справ, начальник факультету управління та інформатики

кандидаг фізико-математичних наук, доцент Турчіна Валентина Андріївн: Дніпропетровський державний університет, доцент кафедри обчислювальні математики та математичної кібернетики

Провідна установа

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

Захист відбудеться "{%" 1997р. о Ув годині на засідай

спеціалізованої вченої ради К 08.04.02 при Запорізькому державному університеті : адресою: 330600, м.Запоріжжя, МСП-41, вул. Жуковського, 66.

З дисертацією можна ознайомитись у бібліотеці Запорізького державного університе за адресою: 330600, м.Запоріжжя, МСП-41, вул. Жуковського, 66.

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

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

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

Актуальність темп. Різноманітність та суперечність різних вимог до троектуємої системи або оптимізуємому об'єкту, неповнота інформації, істотність параметрів моделі, поведінка середи, що впливає на процес прийняття зішень та інше неминуче приводять до того, що реальні задачі оптимізації іоводиться розв'язувати в умовах невизначеності. При розв'язку будь-якої реальної задачі дослідник завжди має справу з деякою моделлю задачі, яка є іаближсною до вихідної. Взаємозв'язок реальної проблеми та варіанта її ібстракгного опису (математичної задачі) може ураховуватись на різних рівнях: 'ближче" до моделі або "ближче" до задачі. У другому випадку на базі задачі шникае деяка множина постановок для більш гнучкого відбиття особливостей моделі. Кожна з "проміжних" задач може бути достатньо строго сформульована і юзв'язана, а розв’язок усіх задач у сукупності дозволяє одержати більш точний та ідекватний опис моделі. Така сукупність будується шляхом варіації деяких шслових параметрів задачі. Тут виникає наступна проблема. При переході від іеальної сітуації до моделі найчастіше доводиться ігнорувати деякі суттєві іеталі. Питається, чи можна їх урахувати хоча б частково, нехай навіть за >ахунок деякого "ускладнення" задачі? Актуальність аналізу стійкості як раз юлягає в тому, що він є одним з методів урахування того факту, що в дійсності іавжди існує погрішність у вимірі та завданні числових параметрів. У зв'язку з щм виникає зацікавленість проаналізувати, як неточність вихідних даних іпливає на одержуваний розв'язок.

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

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

Конструктивніїіі підхід до проблеми дослідження стійкості траекторию задач дискретної ошимізації. основою якого є поняття радіусу стійкості укладено в роботах Леонт'сва В.К., Гордєєва Є.М., Сотскова Ю.Ю., Бакурово' Г.В., Ємелічева В.А., Кравцова МК.

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

Із зарубіжної літератури можна виділити роботи Blair С.Е., Jeroslow R.G. де одержано кількісні оцінки стійкості розв'язку для задачі часткові цілочисельної оптимізації; Wilson G.R., Jain Н.К., де досліджено стійкість дл; задачі псевдобулева програмування; Ruhe G., де проаналізовано складніст дослідження стійкості в потокових задачах.

Вище вказане дозволяє зробити висновок про актуальність обраної теми.

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

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

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

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

- радіусу стійкості для дискретних екстремальних задач.

Задачі, які необхідно вирішити для досягнення поставленої мети:

з

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок в розробку результатів у роботи, які написані е співавторстві:

- доведення теорем про специфіку вішіву топологічних критеріїв 112 стійкість задач з адитивними критеріями [1],[2];

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

- одержання умов стійкості для векторної задачі з нелінійними критеріям}

[7],[П];

- зведення задачі компоновки до векторної задачі розбиття графу : зваженими вершинами та ребрами [10],[12].

Апробація результатів дисертації. Основні результата дисертаційно роботи доповідалися і обговорювались на Всеукраїнській науковій конференці "Розробка та застосування математичних методів в науково-техлічни: дослідженнях" (Львів, 1995); на Українській конференції "Моделювання т; дослідження стійкості систем" (Київ, 1996); на науковому семінарі “Методі вирішення та математичне забезпеченім задач дискретної оптимізацїї” прі Вченій Раді НАН України з прблеми “Кібернетика”(Кшв, 1997), а також н; наукових семінарах кафедри економічної кібернетики Запорізького державногі університету.

Публікації. За результатами виконаних досліджень опубліковано 12 робіт в яких відображено основний зміст дисертаційної роботи: статей - 6 депонованих статей - 2, тези наукових конференцій - 4.

Структура та обсяг роботи. Дисертаційна робота викладена на 13: сторінках і складається зі вступу, п’яти розділів, висновків, додатку та списк; використаної літератури, в якому 120 найменувань.

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

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

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

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

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

Системою підмножин (СП) називаємо пару (Е,Т), де Е - скінчена шожина елементів, потужність \E\-q, а Т - деяка сукупність непустих і ід множин множини Е, які називають траєкторіями і Т = {/].

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

Для наведених нижче класів масових дискретних задач використано позначення 2^ де у = 0,4 - порядковий номер класу задач.

Для таких класів задач на множині Е задано векторну вагову функцію ВВФ)

іему(е)єІІ Уу=1,п ЧеєЕ.

На множині траєкторій Т задано векторну цільову функцію (ВЦФ)

шд критеріїв якої залежить від класу задачі.

Розглянуто наступні класи масових задач Zj, У = 0,4 з відповідним «бором критеріїв ВЦФ (2):

Це) = (м>, (е),...,^„(е),..., (е)),

О)

(2)

і%,(0 = шіп м>у(е) -» тіл, ее/ Т у=1,и, (3)

./%,(/) = тах ™„(е) —> шіп, еєґ Т У=1,И, (4)

7^(0 - шіп ^у(е) -» тах, ЄЄ! Т У=1,Л, (5)

/\,(/) = шах (е) -> тах, еєґ г у = 1,и; (6)

К(() = X >^(е)-^ор/, є є/ Т (7)

^(0 = Х еє/ Г і^= 1,и — 1,

^(0 = <0 -> орі, т у = и; (В)

^(0=£ н-„(е)->о/>г, СЄГ Г и= 1,и -1,

^„(0 = ^(0-»орг, т у= /і; (9)

/Ч'(0=Х ^(е)-^/, у=1,п-2,

т у=п-1,

т V-п.

топологічними критеріями розуміємо критерії, що пов’язані з

структурою графу. При їх визначенні завжди визнаємо, що Е уявляє собою множину ребер даного графу Є, при цьому підмножина / с Е утворює зв'язний підграф / графу Є: $(і) = тах сіецу - ступень ?, сІ(Л) - діаметр / .

Задачі з ііггервальними вихідними даними було розглянуто в роботах М.ІлЬига, Рощін В.А., Семенової Н.В. та Левіна В.І. На відміну від результатів, що одержано для задач цілочисельного програмування, в поданій дисертаційній роботі розглянуто клас задач на СП (Е,Г), де на множині Е визначена інтервальна вагова функція (ІВФ)

Ч«) = [и'1(е),»2(е)]. (10)

іе м'і(е) (м>2(е)) - нижня (верхня) межі заданого інтервалу.

На множині траєкторій Т визначена інтервальна цільова функція (ІЦФ), цо містить наступні критерії:

^і(0 = X ^і(е)-» шах, (11)

еє/ 7

ВЦФ /*'(/) вигляду (3)-(9) та ІЦФ (11)-(13) визначають на множині опустимих розв’язків (МДР) паретовську множниу (ТІМ) Т, що містить усі аретовські оптимуми (ПО): ? є Т, якщо не існує такої траєкторії і° еТ, для

Багатокритеріальною задачею будемо називати задачу знаходження та эбраження ПМ Т в явному вигляді.

Якщо занумерувати усі елементи множини Е = [el,e2,...,eqJ, то

ідивідуальпу ВВФ w(e) з класів Zy, j = 0,4 зручно трактувати як матрицю

У ~ У просторі Rnq, v= 1,и, q-\E\. Змінюючи матрищо W, будемо

держу вати різні індивідуальні задачі.

Для кожного класу масових задач Zj,j— 0,4 введені позначення

ідивідуальної задачі, тобто: z°(fV) - індивідуальна задача з класу Z0; z* ()V) - з іасу Z,; - з класу Zj,j - 2,4; задачу з ЩФ (11)-(13) позначаємо через

'(W) і називаємо інтервальною. ПМ таких задач позначаємо відповідно ’\W),T (ІУ), T‘'(IV). Взагалі (без уточнення класу) символами T(IV) та (IV) позначаємо МДР та ПМ задачі. Значення v-ro критерія Fy(t) вигляду )-(б) в задачі z°(FF) будемо позначати через Mv(t,W).

^2(0= £ w2(e)->max,

п r-l Т

(12)

F} (t) = max( w, (є) - w, (e)) -» min.

(13)

кої викопуються нерівності: F(t°)< F(t ), F(t0)^ F(t ) - для критеріїв, що іінімізовані та F(t°)> F(t ), F(t° ) ^ F(t) - для критеріїв, що максимізовані.

В роботі Козіної Г.Л. та Перепелиці В.О. було зроблено обгрунтування того факту, що інтервальну задачу z‘ (W) можна звести до задачі багатокритеріальної оптимізації з тим же МДР T(W) та ВЦФ F(t) = (Fl(t),F2(t),F3(t)) вигляду (11)-(13). Таким чином, при дослідженні ПМ

інтервальної задачі z'(JV) можна використовувати твердження, що одержують відносно 3-критеріальної задачі з двома ваговими та одним мінімаксним критеріями.

В подальшому, для визначеності, при дослідженні Є -стійкості задач з ВЦФ (3)-(6) усі леми та теореми розглядаються для критерія (4), який називають критерієм вигляду MINMAX, а в критеріях (7)-(9) під символом opt розуміємо min.

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

Для задач з ВВФ (ІВФ) у просторі Rnq (R3g) задамо норму. Під нормою матриці В = \ будемо розуміти число ІВІ = max|!6VK|:v= 1,и, к = l,gj

Через ЕГ(і') позначаємо множину всіх таких матриць В з R"4, що норм:

Щ<£, £>0.

Задачу z(W + В), що одержана з вихідної задачі z(W) при складенн матриць W та В є g’(f), будемо називати збуреною, а матрицю В збурюючою. Величину є назвемо порядком збурення.

Визначення 2.1. Задача z(W) с Є -стійкою, якщо виконуються включення

T(W + B)cT(W) УВєЄ(є). (14

Якщо T(fV)= T(W), то задача z(fV) є Є -стійкою при будь-якому £>0 Тому цей випадок будемо виключати, а задачу z(W), для якої різниц: T(W) = T(fV) \ Т(IV) ?£ 0, будемо називати нетривіальною.

В індивідуальних задачах г°(ІУ), г*(1¥), гг(Цг), г‘(Щ з відповідних

класів масових задач Zj,j = 0,4 для будь-якої траєкторії /° є Т(1¥) визначена

множина парето-оптимальних траєкторій, що домінують траєкторію /°. Для цього введені позначення множин індексів V є//, / = 1,7, якими занумеровані критерії (3)-(9), що уявляють собою підмножини //Є {1>2,...,л}, які не перетинаються. Тоді ця множина визначається наступним чином:

- для класу

Г°(Г,/°)={7 єГ°(^):г;0°,7)>0,^є/()/ = м}, (15)

де г;о°,7)= МУ(1°,Ю- К(7.Ю,

С(7>°)= МХ,(7,Ш)-МУ,Ш), V € /3,/4;

-для класу —1,4

ГгаГ,Г°)= {7 єТг(И^):ту(ї°,7)>0, V є/6,/7|,

гЧ^,г°) = {7 єГ’(^):г"(/°,7)> 0, V є/5|,

де гЛ/0,7)=^(Г0,^)-^(7,Ж), V єІ/,1 = 5/7;

- для інтервальної задачі г' (IV)

7| 2(Ж,/°) = {7 є2(Ж):г;(7,/°) > 0, V = 1.2І

~ г ~ 1 (1?)

Г3(^,*'3) = {7 є Т3(IV):г;(7,г°) > 0,1/ = з), де г;(7,і°)=гл7,ю-ру(і°,ю, у=їз.

Для інтервальної задачі х (ГГ) введено два типи збурення вхідних даних, що не виводять вихідну задачу з класу інтервальних:

\)Єх(є)=[в = 'ІЬук\Ьук<є,є>Ь,Ь1+'мі <1>2 +н-2| (18)

де \\>(е) = [к>[ (е),н>2 (е)] - вихідна вага, Ь(е) = ^ (е),Ь1(е)^ - збурююча вага;

2)г2(^) = |г = |бис|Ьиг <^,0<£<шт у|, (19)

де <1к = Щк — - ширина інтервалу, к = 1,д.

Як відомо, траєкторію Ґ єТ задачі г(їУ) назвемо слабо ефективною (оптимальною за Слейтором), якщо З Г° єТ:Г„(Ґ)> Ру(і°) V V є\,п.

Множину усіх слабо ефективних траєкторій для задач г°(ЇУ), г (IV), гг(Иг), г'(Ж) позначаємо відповідно через Р°(И/),Р (IV), Рг(И:),Р'(РУ), а для задачі з критеріями (11),(12) - через Р^(Ю. Очевидно, що Т(ІУ)с Р(}У).

Радіусом стійкості будь-якої індивідуальної задачі г(1¥) назвемо число р№) = &щ>\є-.Т(ІУ + В)^Т(Ш)УВ єВ(е)}.

Третій розділ присвячено методам дослідження £-стійкості задач, що поставлені у другому розділі.

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

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

формуліровці використано визначення і -го квазіоптимуму, що вводиться рекурентно:

е„(/° Гі ґ) - ребро, на якому досягається рівність значень і'-го кригерія паретовської та непаретовської траєкторій, тобто А/Дґ°,£Г) = М„(?, IV); множину номерів критеріїв, для яких виконується ця рівпість позначено через

А*0,0;

Мій,IV)- перший квазіоптимум траєкторії і єГ°((У,1°); гл /) - ребро, на якому однакові / -ті квазіоптимуми траєкторій /°, І та викопується послідовність рівностей та нерівностей:

[а/дЛя-> му{7,їУ)]>\м{у(г\щ= мі(7,яо]>...>[м;(Л0О= міи,ю]

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

Наступна теорема є критерієм стійкості у загальному випадку для задачі

;еред яких хоча б одне строге.

З крнтерія стійкості (20) отримано формулу для обчислення радіусу ггійкоеті задач класу Z0:

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

Сформульовано критерій А'-стійкості задачі з топологічними критеріями, інайдено формулу обчислення радіусу стійкості задачі гг(1¥) з класу

І/є (Л 7)-

г°(Ил) з класу И0

Теорема 3.3. Для того, щоб нетривіальна задача г°(ЇУ) була £-стійкою, необхідно та достатньо, щоб для будь-якої траєкторії є Т(\¥) існувала така траєкторія І є7’°(^,/0), для якої б виконувалася система нерівностей:

(20)

р(ІУ)= тіп шах тіп-1°ІГ(И')ТєГ°(ІУ,і0) ■

(21)

тіп

У€(і_п}и((0,?)

p(W)- min шах minimin v\'~\ ^ f (22)

(°еГ(Н') ГєГг(»'/')

1ІІСІА. illiil Л llilil л ) ».fcjz /<j\

P(^,0) 1^5 ф°,Г)

де с(*0,Г) = |/0| + |Г|-2|г°Г)7| - кількість різних ребер у парі траєкторій t°J eT(W).

Внаслідок досліджень впливу топологічних критеріїв на стійкість розв'язку вихідної задачі доведені наступні теореми:

Теорема 3.5. Якщо при включенні до ВЦФ нестійкої задачі z (W) топологічних критеріїв (8) або (та) (9) усі елемента множини P2(W)\T (IV) стають елементами множини Тг(ІУ) та додержуються нерівності Tv(t°,t)> £ c(t°,t), то одержувана нетривіальна задача гг(ї¥) &Zj,j = 2,4 £-стійка. В противному разі, задача ze(W) - нестійка.

Теорема 3.6. Якщо при включенні до ВЦФ є -стійкої задачі z (fV) eZt топологічних критеріїв (8) або (та) (9) відбувається звуження ПМ одержуваної задачі ze(W) (тобто T2(W)czT‘(W)), то нетривіальна задача ze(W) -нестійка.

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

За допомогою лінійного перетворення, що залишає незмінними межі області значень інгервалу w(e) = ^wx(e),w2(e)^,e єЕ критерій (13) перетворено до максимізованого:

F3(t) = min(D(W)-dk)-^> max, (23)

ее£ Т

де dk = w2il - w{k ,k = ],q - ширина інтервалу,

D(W) = min d(e) + maxd(e); d(e') = min d(e), d(e") = maxd(e).

ce£ еє£ ге£ еє£

З урахуванням критерія (23) введено ще дві збурюючі множини, що < підмножинами збурення S’i(s) вигляду (18):

1) збурення, що не впливають на величини D(W) та dk:

3d(£) = {B = Кк' < є, є > 0, (b2k +W2k)~ (Ьік + wu) = dk}; (24)

2) збурення, при яких D(IV) = const, a dk* const:

ZD(£) = {B = AK>bl7C<£, є>0,0<Аk<d(e")-dk], (25)

= b2k —Ь1к,- ширина інтервалу збурення.

Для кожного із збурень ‘Sx(e), “В2(є), ’Pj(e), 'S D(s) досліджено умови ■стійкості та визначено формули радіусу стійкості. Для виводу обгрунтування ірмул радіусу стійкості введені такі позначення:

£Tl2(fV,t°), 7" eT3(fF,t°); f12(IV,t°)uT3(W,t°)=fn(IV,t0);

V3(t ”,И/) або Mj({0JV)- і -ті квазіоптимуми у траєкторіях t ",t°;

(t°,t ) = c(t°,7)-</>(t°,t ) - кількість різних ребер у парі траєкторій ,t eT(fV); 0(t°,t)-число ребер е' та е" в траєкторіях t,t°; w(t ,t°), у-1,2; T’w(t ,t°) - позначення величин відповідно

’(t ,t°), v= 1,2; v3(t,t°), що задовольняють нерівностям

д*

,(7,t°)>~-c'(t,t°),v = l, 2 та r3(7,t°)>A\ де

= min А* , А* = d(e") - dk.

Відповідно до збурень ), &о(є)отримано наступні

рмули радіусу стійкості:

(IV) = rmn_ max mini ,W)-M3(t",W)),

/,еГ(Н')ГєГ (w,P) I c(t ,t') 2 1

*‘(7",W)~m,(7'\w))}, h№(7",t0)] 1

(26)

Pz(W) = mini/} (IV); mm^ j (27)

pd(W) = min max (28)

1°еГ(Ю ГеГ1>2(Г,(0) ^1.2 c(t ,t)

f r'w(7' t^ і

pD(W) = min_ max min ^ 0 ’ , -[тіп{(М‘(/°,Г)-M3(7",W)),

l°EТ(ІУ)7еТ (И\г°) L с (t ,t ) 2.

(M3(7",W))}, r3*w(7'',f0)]

. (29)

Четвертий розділ присвячено розгляду та вивченню векторної задачі розбиття графу, яка виникає на одному з етапів проектування радіоелектронної апаратури - етапі компоновки.

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

у

F, = F{(x) - Е min А, -> min, (ЗО)

1<;<л

^2 = = таХ (X Iй Х > т1П> (31)

р і=1 ‘ ІР

= ьи хір ХІР -» тах> (32)

р=і ,•* і 7=і

>■ п я

р*=^«(*)=£ ЕЕ ст!/тах- (33>

Р=і ■=' >=>

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

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

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

ІІДМНОЖИН.

В п’ятому розділі проведено практичне дослідження теоретичних іезультатів. Для кожного класу задач наведено розрахункові приклади. Числові >езультати с підтвердженням теоретичних досліджень.

ВИСНОВКИ

У висновках сформульовано основні результати, які отримано в дассртаційній роботі:

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

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

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

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

5.Одержано умови стійкості та формули обчислеіпія радіусу стійкості іадачі розбиття графу з подвійним зваженням.

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Bakurova A.V., Perepelitsa V.A., Zin'kovskaya J.S. Research of Stability of Vector Ptoblem on Spanning Tree with Topological Criteria. IKM’97 digital proceedings. Bauhaus-Universitat/Weimar/Germany, 1997,- P. 159-165 (article).

2. Бакурова A.B., Зиньковская Ю.С., Перепелица B.A. Исследование устойчивости векторных задач на системах подмножеств при дополнении ВЦФ топологическими критериями // Доповіді НАН України (прийнято до друку 30.05.97 за №270).

3. Бакурова Г.В., Зіньковська Ю.С. Дослідження стійкості 3-критеріальної задачі формування інвестиційиого портфелю // Міжвідомчий зб. наук. пр. Машинна обробка інформації. - КНЕУ, 1997. -60. - С.183-188.

4. Зиньковская Ю.С. Вычисление радиуса устойчивости многокритериальных задач с нелинейными критериями II 36. наук. пр. -Придніпровський науковий вісник, 1997. - №15(26). - С.43-48.

5. Зиньковская Ю.С. Исследование векторной задачи компоновки: некоторые вычислительные алгоритмы и их оценки // 36. наук. пр. -Придніпровський науковий вісник, 1997. - №43(54). - С.8-14.

6. Зиньковская Ю.С. Об устойчивости одной векторной задачи на графах со взвешенными вершинами и ребрами // 36. наук. пр. ЗДУ, 1995.-5.-Ч.1.-С.31-34.

7. Бакурова А.В., Зиньковская Ю.С., Перепелица В.А. Исследование траєкторних задач с нелинейными критериями в условиях неопределенности h РЖ “Математика”, 1996, 8Г88. - 24с. Деп. в ГНТБ 25.01.96r., №378-Ук96.

8. Зиньковская Ю.С. Вычислительная схема алгоритма для задачи компоновки на гиперграфе // РЖ “Математика”, 1997, ЗГ20. - 20с. - Деп. в ГИТЕ 12.08.96г., №1679-Ук96.

9. Бакурова А.В., Зиньковская Ю.С., Перепелица В.А. Исследование устойчивости задач векторной дискретной оптимизации // Материалы конф Второй Сиб.конгрссс ИНПРИМ-96. - Новосибирск. - 1996. - С.132-133.

10. Бакурова А.В., Зиньковская Ю.С., Перепелица В.А. Исследование устойчивости одной задачи автоматизации проектирования электронно» аппаратуры П Материалы конф. Ассоциация мат. програм. - Екатеринбург ИМиМ УрОРАН. - 1995. - 5. - С.32-35.

11. Бакурова Г.В., Зіньковська Ю.С. Багатокритеріальні моделі задач н; графах: аналіз стійкості // Тези допов. Всеукр. наук. конф. “Розробка -к застосування математичних методів в науково-технічних дослідженнях”. - Львів

- 1995.-С. 14.

12. Бакурова Г.В., Зіньковська Ю.С., Перепелиця В.О. Математичн; модель задачі компоновки конструктивних вузлів електронної апаратури // Та» же-Львів.-1995.- С. 13.

Зіньковська Ю.С. Дискретні екстремальні задачі в умовах невизначеності: питання стійкості. - Рукопис.

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

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

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

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

Зиньковская Ю.С. Дискретные экстремальные задачи в условиях неопределенности: вопросы устойчивости. - Рукопись.

Диссертация на соискание ученой степени кандидата физикоматематических наук по специальности 01.05.02 - математическое

моделирование и вычислительные методы в научных исследованиях. -Запорожский государственный университет, Запорожье, 1997.

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

Ключевые слова: устойчивость, радиус устойчивости, возмущение, возмущающее множество, система подмножеств, алгоритм, разбиение графа.

Zin’kovskaya J.S. Discrete extreme problems in conditions of the indefiniteness: the stability questions. - Manuscript.

Thesis for a candidate of physical - mathematical sciences degree by speciality 01.05.02 - mathematical modeling and computational methods in scientific research, Zaporozhye state university, Zaporozhye, 1997.

Stability of the discrete extreme problems is under discussion. Dissertation covers classes of the trajectory problems on the systems of the subsets with vector and interval weighting functions. Stability conditions for different types of the given data perturbations have been proved. Formulae of calculation of the stability ramus which are considered to be the quantitative characteristics of the stability have been obtained. Stability of the vector problem of the graph partition with weighted apices and edges has been investigated. The system of algorithms and the estimations of their computational complexity for the above mentioned nontrajectory problem have been proposed.

Key words: stability, stability radius, perturbation, perturbating set, system of subsets, algorithm, partition of graph.