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

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

на правах рукописи ЕАКУРОВД АННА ВЛАДИМИРОВНА

исследоваже! устой4бости и слсшзсти ьекоторых задач декретной многокритериальной спшизацж

05.13.16. - Применение вычислительной техники математического моделирования и математических методов в научных исследованиях.

АВТОРЕФЕРАТ

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

Запорожье - 1994

Работа выполнена в Запорожском государственном университете

Научный руководитель: доктор физико-математических наук,

профессор ПЕРЕПЕЛИЦА В.А. Официальные оппоненты: доктор физико - математических наук,

МЕТЕЛЬСКИИ H.H.

кандидат физико-математических наук, доцент ТУРЧИНА В.А.

Ведущая организация: Институт кибернетики им.В.М.Глушкова

АН Украины

Защита диссертации состоится " 199 У г. в

на заседании специализированного совета К 068.52.02 при

Запорожском государственном университете по адресу: 330600, г.Запорожье, ул. Жуковского, 66 ауд.

С диссертацией можно ознакомиться в библиотеке Запорожского государственного университета.

1994 г.

Автореферат разослан

Ученый секретарь специализированного совета

к.т.н., доцент _ СЫСОЕВ D.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Необходимость в исследовании устойчивости таких задач возникает потому, что многим, факторам, характеризующим реальные процессы, присуща неопределенность, а вычислениям - погрешность. При анализе устойчивости векторных задач выясняется величина диапазона изменения исходных данных, при которой оптимальное решение исследуемой задачи не изменяется. С другой стороны исследования устойчивости позволяют построить на базе определенной задачи путем вариации некоторых еэ числовых параметров класс задач, анализ которого позволяет получить более точное и адекватное описание модели. То есть совокупность всех представителей этого класса отражает реальную ситуацию, послужившую прототипом исследуемой задачи. Это также способствует повышению эффективности решения труднорешаэмых задач (таковыми являются большинство многокритериальных задач), т.к. по решению одной задачи можно получать решение континуума задач.

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

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

1. Исследовать условия е-устойчивости векторных комбинаторных задач с различным составом критериев векторной- целевой функции

(вц»).

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

3. Исследовать вычислительную сложность некоторых наиболеэ известных задач векторной оптимизации на графах в типичном случае.

4. Исследовать поведение саратовского множества и полного множества альтернатив при увеличении числа критериев ВЦф.

£>. Провести вароятностногстатистический анализ устойчивости векторных задач на графах.

Методика исследований. В диссертационной работэ использованы I понятия и методы комбинаторного анализа, дискретной оптимизации, теории графов, теории вероятностей, векторной оптимизации.

Научная новизна. В диссертации разрабатываются направления исследования устойчивости задач дискретной оптимизации, порождапциеся в условиях многокритериальное™: вычисление радиуса устойчивости для задач с варьируемым составом ВЦЭ, влияние изменения числа критериев на мощность множеств альтернзтив и на величину радиуса устойчивости. Полученные результаты обобщают часть иззестных результатов (В.К.Лзонтьэв, Э.Н.Гордеев) в области исследования устойчивости классических (о.днокритериальных) задач дискретной оптимизации. В работе показано как оценки вычислительной сложности позволяют использовать возможности статистического подхода к исследованию устойчивости.

Практическая ценность работы. Построенные методы позволяют более адекватно разрабатывать и анализировать многокритериальные математические модели в экономике и производстве, который используют векторные задачи дискретной оптимизации. Построение и исследование таких моделей проводится, например, в ВЦ Р4Н, ИК АН Украины, Белорусском государственном университете.

Достоверность полученных результатов подтверждается их соответствием выводам других авторов (Л.Н.Когерацкая, Т.Т.Лебедева, Т.И.Сергиенко, В.К.Леонтьев, Э.Н.Гордеев), работащих над проблемой устойчивости задач дискретной оптимизации.

Публикации и апробация работы. По теме диссертационной работы опубликовано 12 печатных работ. Основные результаты диссертации докладывались на научной школа-семинаре молодых ученых по

кибернетике, информатике и вычислительной технике (Киев, 19891990), на IV Всесоюзной школе-семинаре "Статистический и дискретный анализ данных и экспертное оценивание" (Одесса, 1991), на Всесоюзном семинаре "Дискретная оптимизация и исследование операций" (Новосибирск, 1992), на школе-семинаре "Комбинаторная оптимизация" (Полтава, Миргород, 1992), на семинарах Научного совета АН Украины по проблеме "Кибернетика" (1992-1993), на XX международной конференции САПР-93 (Гурзуф, 1993), на международной конференции "Теория приближений и задачи вычислительной математики " (Днепропетровск, 1993), на международной ' конференции по дискретной оптимизации (Минск-Магдебург, 1993), на международной конференции "Прикладное и имитационное моделированиэ-93" (Львов-Париж, 1993).

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

СОДЕРЖАНИЕ РА60ТЫ

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

Глава к посвящена исследованию е-устойчивости в траекторных задачах векторной оптимизации. В параграфах I и 2 приведены необходимые для всего дальнейшего изложения определения и понятия; описана формальная схема, в которую вписываются все, рассматриваемые в работе задачи.

Система подмножеств (СП) есть пара тг=(Е,Т), где Е - конечное множество элементов, Т - некоторая совокупность его непустых подмножеств г , называемых далее траекториями. Число | ^ - длина траектории На множестве Е задана векторная весовая функция

- б -

(ВВФ):

w(e) - (wt(e),w,(e).....wM(e))t

где wv(e)eR vue{I,2t...,N> veeE. На множестве траекторий T определена векторная целевая функция (ВЦф):

Fit) = (?t(t),...,Pv(t).....PN(t) ), (1)

состоящая из критериев двух видов:

MINSUM р (t) = S„(t,w) = w„(t) = Е wv(e) - »tn, (2)

v v v »ел v r

ЮМАХ P (t) = Ky(t,w) = box wv(t) - *tn (3)

•fit T

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

ВЦ© ?(t) определяет на Т паретовскоа множество (ПМ) T=(t«T: з t° е т, Pm^Ptt0). P(t)iP(t°)}.

Говоря об N-критериальной задаче, будем подразумевать задачу нахождения и представления в явном вида Ш Т, а обозначать такую задачу будем через Zn=(t,w,F)=(E,T,w,?). При атом под задачей ZH понимается массовая задача. Если ВЦ2> (I) состоит только из критериев тптдя (2) или только вида (3), то задачу ZN называем, соответственно, минисуымной или минимаксной.

Если занумеровать все элементы множества Е= (е1,е1,...,еа), то индивидуальную ВВФ w(e) удобно трактовать как матрицу W=nwvieи размерности NxQ, где 0=|Е|. Меняя матрицу W, будем получать различные индивидуальные задачи. Индивидуальную задачу массовой задачи ZN обозначаем через z(W) =zN(W)»(E,T,W,?), а Ш такой задачи - через T(W). Значение v-ro критерия Py(t) вида (2) и (3) в задаче z(W) будем обозначать через Sv(t,W) и il^t.W) соответственно.

Индивидуальную задачу назовем q-одвородной ( однородной ), если длина всех ее траекторий равна q (одинакова). Траакторная задача Z* однородна, если любая во индивидуальная задача однородна.

В пространстве к"® размерности NxQ задана норма. Под нормой матрицы В =» |bvl[| « R *** будем понимать число

|B|~maxt lbv3c):v=»1,2,...,н; 1с=1,2.....q>.

Через S Се) обозначим множество всех таких матриц В ю Rm, что норма |В|se, s>0.

Задачу z"(W+B), полученную из исходной задачи zH(ïï) при сложении матриц W а Ве8(е) будем называть возмущенной, а матрицу В - возмущащей. Величину е назовем порядком возмущения.

В 52 изложены необходимые а достаточные условия е-устойчивости в смысла определения 1, которое соответствует определении е-устойчивости одзокритериальных дискретных задач, введенному В.К.Леонтьевым.

• ОПРЕДЕЛЕНИЕ 1. Задачу zCfl) назовем е-устойчивой, если выполняется включения

т(!+в)=т(1) ув«8(8). (4)

Очевидно, что в случае, когда Т=Т(И), задача zM(W) является е-устойчивой при любом е>0. Задачу zM(W), для которой называем нетривиальной.

f+ rv M w

Для всякого t°e T(f)' определим множество T(ff,t°)=t t«T(W): i^(to.t)s:0. v-1,2.....N>, где Ty(t°,t)-Pv(te,W) - ?y(t>).

В формулировка достаточных условий е-устойчивости в случав ыинисуымной задачи используем обозначение

n(te.t)=.|tel+ltl-2ner>t|. teeî(W)', t«T(W,t°).

ТЕОРША 1.1. Если в нетривиальной задаче z"(W) для всякой •

- а -

траектории существует такая траектория что

„ в я •»

выполняется неравенства Л) Л),

то она является в-устойчивой.

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

ТЕОРЕМА 1.2. Если нетривиальная задача е-устойчива, то

для всякой траектории 1°« т(НУ существует такая траектория •ит(*,1;0), что выполняются неравенства

Для однокритериальных задач получен критерий е-устойчивости: ТВОРЕНА 1.3. Не тривиальная минисуммная задача г1 (1)»(Е,Т,Ч,31) е-устойчива тогда и только тогда, когда для всякой траектории существует такая траектория что выполняется

неравенство > еа^,?).

Радиусом устойчивости индивидуальной задачи е(*) назовем число р(Я)»»ир{е: Т(И+В)£?(1) УВ«8(е)}.

ТЕОЕЕИА 1.4. Радиус устойчивости нетривиальной минисумыной задачи 2м(1) выражается формулой

р(Я)=» п1п пах «{а -т . (б)

Гвт«у,»в» ^.....н

Формула (5) представляет собой обобщение формулы В.К.Леонтьева для одаокритериальной линейной задачи ^ОТМЕ.Т.И.З^.

Результаты, представлящае собой достаточное условие, необходимое условие для минимаксных задач, а также критерий е-устойчивости задачи на узкие места сформулированы, соответственно, в теоремах 1.5.-1.7. для случая, когда для всякой

*ф ' м м

пары траекторий и значения целевой функции

- У -

достигаются не на общем ребре е* tent .

ТЕОРЕМА 1.Ь. Боля в нетривиальной минимаксной задаче zN(W) для всякой траектории t°«5(W)/ существует такая траектория teï(W,t°), что наполняются неравенства T*(t°,t) >2s, v<*1,2,...N, то она является е-устойчизой.

ТЕОРЕМА 1.6. Если нетривиальная минимаксная задача zM(ff) e-устойчива, то для всякой траектории t°e T(ff)/ существует такая

~ ~ о

траектория t«T(ff,t ), что выполняются неравенства

ТЕОРЕМА ' 1.7. Нетривиальная минимаксная задача z1(W)=(E,T,I,M1) e-устойчива тогда и только тогда, когда для всякой траектории tcT\T°(W) существует такая траектория teT° (ff), что выполняется неравенство (t,W)-Mt (t,W) > 2е.

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

P(W> «In «ai «tn T*(t°,t) / 2. (6)

а ~ ,-- о V-1.....M

t ÍT(»' t«T<V,t >

Формула (6) представляет собой обобщение формулы Э.Н.Гордеева для задач на узкие места на случай N критериев вида (3).

Условия е-устойчнвостн и формула радиуса устойчивости для минимаксных задач в более общей случае представлены в теоремах 1.9 - 1.11. В их формулировка использованы следулциэ обозначения, которые введены рехуррентно:

ev(t nt) - реоро е • t°nt, на котором Mv(t%W)=M1>(t,W);

M^(t\e^(t°nt),W) - первый квазимаксимум траектории t«î(ff,t°);

. Л» «V

ey(tnt) - ребро в « t°nt, на котором равны i-тые квазимаксимумы траекторий t°, t и выполняется- последовательность равенств, и неравенств : [^(t0,*) - ^(t.W)] >* ClÇ,{ t \ e„(tftnt). .

W) - 4c t° \ e^(tnte), I»...* t \ B^W*), W ) - V

\ Bottât0).,. W)J, ■ где K^(tnt°) » ie^fnt), e^(t°,t).....

e^it*,?) );

J(t°.t)=i v«C1,...,№: равенство Ky<t°,W)=Mv(t,W) достигается -на ребре etyt^nt) л такое ребро единственно);

JMf.t) « { V « J(t°,t): равенство Mj,(t°\ev(t°nt).W) « и ïyftNeiytt'Vit).*) достигается на ребре e^(t°,t) и такое ребро единственно>.

Jl(t°,t)={ V « J1"1 (t°,t): равенство. Hj,(t°\ ^(tnt°),W) = - \ ^,(tr>t°), ff) достигается на ребре e^,(t°nt) и такое ребро единственно},

ТЕОРЕМА 1.9. Если в нетривиальной минимаксной задаче zM(ff) для всякой траектории t0«?^)' существует такая траектория WT(W,t ), что выполняется система неравенств

Bj,(tf»t ),W) s 2e, * v(t°.t) > 2e, yv « {1,2,...N)\J(t°,t), то она является е-устойчивой.

TEOEEUA 1.10. Если нетривиальная минимаксная задача 2м (W) е-устойчива, то для всякой траектории t°« T(W)y существует такая траектория t«T (W,t°), что выполняется система неравенств (^(t0.»)-^1 (t \ Kh(tnt°), W) г 2e. .

UC^Cf.WJ-H^-^tt-V K^(tnte).W) a 2e. * ;Cf..?> i2a, w« (1,2,...N)\J(t°,t), Если для всякой пары траекторий t°« T(W)/ и t«d(W,t°) множество J(t ,t)=0, то из теорем 1.9 и 1.10 получаются, соответственно, формулировки теорем 1.5 и 1.6.

Для минимаксных задач в таком случае формула вычисления

}

радиуса устойчивости имеет вид

»»л пая ( _ С. 1/201.(1°\

»••Г,«/ IV« а«».«

т»п Л) / 2 | . (7)

Формула (7) на имеет аналога в однокритердадьном случае, такое обобщение- возникает только в условиях многокритериапьности.

Для формулировка условий е-устойчивости задач с произвольной комбинацией минисуымных и минимаксных (в частном случае, когда

Г* Г* р г*

ТС*)7, )) критериев используем обозначение

2. если ?v(t) - H„Ct,w), T*(t°,t)/ n(te,t), если ?v(t) - Sv(t,w).

В теоремах 1.12. и 1.13 сформулированы, соответственно, достаточное я необходимое условия е-устойчивости задач zH (W) с ВЦ® (I)—(3). Получена формула радиуса устойчивости нетривиальной задачи zN(ff) с ВЦЗ> (1)-(3)

»V о

p(W)^ min жах »la Т -, (t ,t).

О— . -i -, о l'ai.....н

t t «f< W,t »

Индивидуальную задачу z(W) называем локально неустойчивой,

если p(W)«0. Для всякого t®« T(W)' вводам множество траекторий,

строго дршширущкх траекторию t°: « . « » « tu „ »

T(W,t Г - С «CI): f it) <0, v=I,2,...,N }.. (8) В следугией теореме сформулирован критерий локальной неустойчивости рассматриваемых задач ( минимаксные критерии

-12 "

рассматриваются в частном случае).

ТЕОРШ Ый. Всякая нетривиальная задача а(?) с ВЦ® (1)-(3) локально неустойчива, тогда и только тогда, когда существует такая траектория 1®« Т(и)', что Чф.Х") -

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

м м м ^ » м .

обозначение 1°) = { : «Ч^.гм уч0«

ъачк.г0)}.

ТЕОРИИ 1.16. Всякая нетривиальная минимаксная задача 2(1) локально неустойчива, тогда и только тогда, .когда существует такая траектория 1;"« 5(70'', что Т(Ч,г°)\Т(ЯД°) - 0.

По формулам (7), (8) и критериям локальной неустойчивости построен алгоритм направленного перебора для вычисления радиуса устойчивости нетривиальной задачи ъ(Я) с ВНР (1)-(3).

Теоремы об условиях е-устойчивостп q-oдзopoдш^x задач для увеличивающих (уменьпшщих возмущений) представлены в параграфе 3.

В 5 4- рассматриваются следующие 2 варианта определения е-устойчавости, аналоги которых для -многокритериальных целочисленных задач встречаются в работах Козерацкой Л.Н., Лебедевой Т.Т. и Сергианко Т.И. .

ОПРЕДЕЛЕНИЕ 2. Задачу 2(1) назовем е-устойчивой, если выполняются включения т(*+в)ат(я) ув«в(е).

Для формулировки достаточных и необходимых условий е-устойчивости в смысле определения 2 минисуммных задач используем обозначения: а1 (гв,г)-и"|+|?|-|гвп г°«Т(1)/, г « ?(ю и

ТКОРКМА 1.20. Если в нетривиальной ыинисумыной задаче г"(Я) для всякой тройки траекторий 1;°*Т(1)', Т(*ДЭ) и

- 13 -

^«5(1)45 (И, 1:°) выполняются уодовяя

I) и".^) > еп^г0.^). з\«а.....ю. ; 1=1.2.

2) г ц* ^ ,г_>1 > нал«., 11 у«£1.....ю,

1 4 » ™ „ „ V V

то задача е-устойчива в смысла определения 2.

ТЕОРЕМА 1.21. Если нетривиальная минисуммная задача 2м(Я) е-устойчива в. смысле определения 2, то для всякой тройки траекторий и Т(ЯД°) одновременно

выполняются условия

I) и*,?^ 2: еО^Г.^), .....Ю, 1=1,2,

2)

Г а vlelI.....Н>. ^^

В следующих теоремах представлены достаточное и необходимое условия е-устойчнвости минимаксных задач для определения 2 (далее для простоты изложения рассмотрен только частный случай минимаксных задач).

ТЕОРЕМА 1.22. Если в нетривиальной минимаксной задача г,н( 1) для всякой тройки траекторий г°еТ(1)/', Т(1,0 и

мм м

1Ж«Т(*)\Т(ЯЛ°) одновременно выполняются условия

1) > 2в. .....н>., 1=1,2,

2) { ^ / V V,, 1 > 2е V,««.....Ю,

то задача е-устойчивя в смысле определения 2.

ТЕОРЕУА 1.23. Если нетривиальная минимаксная задача 2М(1)

е-устоЯчта в смысла определения 2, то для всякой тройка траекторий ТАМГ) л Т(*)\ Т(*Л°) одновременно

выполняется усдовая

1) (Г.^у* 28. у^а.....н>.-1=1.2,

' г ЛЛ )| а 2а у «С1,...,Н}(

2) ] Л 4 " * V/ V,. I 11$ (?ж,?4)|' г 2е у<«СХ..:-..Н>,

ОПРЕДЕЛЕНИЕ 3. Задачу 2(1) назовем е-устойчивой, если выполняется равенства

Т('*+В)«Т(1) УВ«В(е). Соотватствущиэ определению 3 достаточное и необходимое условия е-устойчивоста для минисушшх (минимаксных) задач получены при объединении условий теорем 1.1 и 1.20 (1.5 и 1.22) и, соответственно, теорем 1.2 и 1.21 (1.8 и 1.23). В виду аналогичности их формулировок, а такжэ громоздкости, в диссертации сформулировано только достаточное условие мивисуммвой. задачи.

ТЕОРШ. 1.24. Если в нетривиальной минисуммной задаче гм(1) для всякой тройки траекторий Т(*,1°) и

N М М

одновременно выполняются условгя I) К*.^) > еп^г",?). ?(«С1,....Н>, 1-1,2,

» V* V ,

„ » " * 1

о " J

3) для всякой траектории существует такая траектория

ит(*.г°). что выполняются неравенства «с $(г°.г)>епивЛ), у»1,2,...н,

V -1,2,..я, то задача е-устойчива в смысле определения 3.

В работе показано как результат, сформулированный в виде теорем 1.16, 1.20 -1.23, согласуется с соответствупцими критериями устойчивости, полученными Л.Н.КозерацкоЙ, Т. Т .Лебедевой и Т.И.Сергиенко для многокритериальных задач* целочисленного линейного программирования (ЦШ).

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

В постановка задач яа графах используем дополнительные обозначения, которые введены в §5.

Зп - множество всех п-вершинных графов С = (7,В); I =« { к^., 1=1,...,г, я1 < ** <...< ?гг}

3(п,Н,г) - множество всех графов в в у которых на множестве ребар К задана целочисленная ВВФ вида

*(е)=(*4(е).....тгу(е),...,*м(е)), где ^(е) в I, .....Н;

Т=Ш - множество всех допустимых решений (ЫДР), иля траекторий, длина которых равна <!• При определенном виде траектории Ъ имеем следующие задачи:

7,"- задача коммивояжера; г - гамильтонов цикл; q=n; х"- задача об остовных деревьях; г - остовное дерево; q=n-I; 7."- задача о совершенных паросочэтаниях; I - совершенно) паросочетание; q=n/2, п - четное;

В главах 2 я 3 под искомым решением задачи наряду с ПМ ' подразумевается полное множество альтернатив (ПМА) Т. ПМ определяется как подмножество ПМ минимальной мощности такое, чт

?<т*) =« с ?(г): г « 1*> т.

Всякий.граф С«з(п,Н,г) однозначно определяет собой некотору индивидуальную задачу . Поэтому далее наряду с. термине

- lb -

"задача z(W)" условимся использовать термин "задача z на графа G".

В { 6 введено понятие идеальной задачи, которое состоит в следующая. Индивидуальная задача z(W) обладает свойством X, если найдется хотя бы одно решение t=»(V,Et) такое, что каздоа ребро е « взвешено N-мерным вектором вида (w1,...,w1)

Цри атом указанное решение t также обладает свойством X. Множество таких траекторий обозначим через Т^; множество

индивидуальных задач, обладаниях свойством X. Такие задачи называем идеальными. .

Пусть определена функция ф=ср(п)=о(У5)-<» при п-«».

ТЕОРЕМА 2.1. Если выполняется неравенство (r^+l )5п/(1пп+1«:панр), то для почти всех графов G<?(n,N,r) векторные задачи о коммивояжера , о совершенных паросочтаниях, о минимальном остовном дереве с ВД5 (I)—(3) являются идеальными.

В 5 7 на основа свойства идеальности получены оценки сложности исследуемых задач в "типичном" случае..

В работах-В.А.Вюличева, В.А.Перепелица для исследуемых задач было устновлэно, что максимальная мощность ПЫ и ГШ растет' экспоненциально с ростом размерности задачи, если ВЩ (I) содержит хотя бы два критерия весового вида (2) и значение г=г(п) растет достаточно быстро с ростом п. Однако оставался открытым вопрос о том, для какой доли графов G«s(n,N,r) модность Ш я ГШ. ограничена снизу экспоненциальной функцией от п. Ответ на этот вопрос дают сдэдущие теоремы.

ТЕОРЕМА 2.2. Если r^s УЙ/ср, то для векторной задачи коммивояжера с ВЦ» (1)-(3) на почти всех графах G«3(n,N,r) мощность ША |Т 1=1 и мощность ПЫ Т ограничена снизу функцией

ф(п)=о((ф1УЯ)п), экспоненциально растущей от а.

ТЕОРЕМА 2.3. Если ЛУй/ср, то для задета об остовных деревьях о ВЦ» (Т)-(З) на почти всех графах G«s(n,N,r) мощность Ш1 |i|=l и мощность Ш 5 ограничена снизу функцией <}>(n)»o((<pj-yii),v,'t), экспоненциально растущей от п.

ТЕОРЕМА 2.4. Если г^УгТ/ф, то для задачи о совершенных паросочетаниях с ВЦЗ (1)-(3) на почти всех графах G«#(n,N,r) мощность DMA IT 1=1 л мощность DM Т ограничена снизу функцией

п

ф(п)=о((Уйр) экспоненциально растущей от п.-

Поскольку вычислительная сложность оценивается относительно длины входа количеством элементарных операций, затрачиваемых .на нахождение и представление в явном вида решения, то нижней оценкой сложности проблемы нахождения Ш (ПМА) может слуаить мощность

Л А

множества т (Т). Согласно теоремам 2.2-2.4 проблема нахождения ЕМ рассматриваемых задач (имещих ИМ экспоненциальной мощности ) является труднорвшаемой. Однако, проблема нахождения ПМА почти для всех графов сводится к нахождения одного ПО.

В глава 3 рассмотрены следующие ' вопросы: I) поведение DM и ПМА при увеличении числа критериев ВЦФ; 2) вероятностный анализ устойчивости решения задач Z*. а =» 1,2,3; 3) вероятностный анализ мощности ядра устойчивости для одного класса локально • неустойчивых задач.

В параграфа 8 показано, что существовавшее до настоящего времени мнение о расширении ЛМ при увеличении числа критериев вообще говоря, является неточным. Обозначим через At начальную систему критериев ВГф, т.е. At=f?t (t),...,?н (t)J. Новая задача

будет получаться из исходной путем замены системы критериев At на систему ),.... PN (t)>. Действительно, в'

«w

определенна! случаях имеет место совпадение множеств Т (А4) и

м • -- • • . —... „__

Т(АЖ). Например, да? так называемых полных задач, когда выполняется равенство : I » i » I. Ясно, что в атом случае на существует элементов t « Т, за счет которых может расшириться Ш или ГОД.

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

ТЕОРЕМА ЗЛ. Если г^ á n/(iniiMnínn/q>), то почти все индивидуальные задачи aH(W)«Z , а=1.2,3 на графах Ges(n,H,r) не являются строго 'аффективными .

В случае, когда ЗУТ справедлива теорема о "немонотонности" пяратовского множества .

ТЕОРЕМА 3.2. Существуют индивидуальные задачи z** в=»1,2,3," у которых при замене системы критериев на систему критериев где Atc А^ , выполняется включение

=> 5 а,).

Исследование поведения Ш при изменении числа критериев ВЦФ в

некотором смысла аналогично исследованию устойчивости решения при

возмущении параметров ВЦ5 на некоторый порядок е > О.

Обозначим Зерез z(W,A.) исходную индивидуальную задачу с ВШ Д. ^ • 1 А

У (t) , а через ) - задачу с ВЦ» ? (t). Возмущающее

множество л (е, Ht) определим как множество матриц B=nbVki, где

f О,'если v • CI.....

Ч* " |aes е, если v « (Ht+I,...,Ha)'.

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

з

УТВЕРЖДЕНИЕ I. Задача й(*,Д4) являатоя локально неустойчивой

для возмущений В « з(е,

УТВЕРЖДЕНИЕ 2. Задача ) является к-устойчивой в смысле

определения 2 для V к > 0.

В параграфа 9 исследуем а-устойчивость в типичном случае,

когда рассматривается массовая задача.

Будем считать, что индивидуальная задача ¡зн(1) на графе

0*<5(п,Н,г) обладает свойством ( ), если она является

е-устойчивой в смысла определений I ( соответственно, определений Ч

2 и 3 ). у (п,>/,г), 1=1,2,3 - множество графов, определяющих МДР

е-устойчивых в смысле определения I (2,3) задач г"(Я).

ОПРЕДЕЛЕНИЕ 4. Задача 7," является е-устойчивой в смысла

определения I ( соответственно, определений 2 и 3 ) на почти всех

графах 0 « ?(п,И,г) , если выполняется равенство

13 1(П,Н,Г)|Ш 1»(п.к.г)|--Т)-

ТЕОРЕМА 3.3. Если г" * п/(1пп+1п1пп/ф), то задача г", а=1,2,3 не является а-устойчивой в смысле определений 2 и 3 на почти всех графах &&(п,1{,г) для *е>0.

В теореме 3.4 обоснованы нижние оценки радиуса устойчивости для задач г", а=»1,2,3 с ВЦФ (1)-(3).

ТЕОРЕ54А 3.4. Если г14 з п/(:пп+1а1пп/ф), где ср=ф(п)-®, п-®, то для задач 8=1,2,3 на почти всех графах (^(п.Н.г) радиус устойчивости либо равен нулю, либо удовлетворяют неравенству

Г (я1-*1), если У-Лгни«, .....N.

Р(»)ь ] , , V -V

I в противном случае.

ТЕОРЕМА 3.5. Если 5 П/(1пП+1п.1пП/ф), где ф=ф(П)-к», П~о», то для минимаксных задач 7.", а=1,2,3 на почти всех графах &ез(п,11,г)

радиус устойчивости вычисляется по формуле

р(*> = «in «in *y(t°,t> / 2, где t«T(l).

t°«?«v>' v"1.....*

& заключении сформулированы основные результаты работы, которые состоят в следующем:

1. Предложен количественный подход в исследовании устойчивости векторных комбинаторных задач. Обоснованы необходимые и достаточные условия векторных комбинаторных задач с критериями вида HUSUM, КОДАХ в любой комбинации для трех вариантов определения е-устойчивости. Для однокритериальных траектории* задач с функционалами линейным и узкого места получены критерии е-устойчивости.

2. Получен ряд формул для вычисления радиуса устойчивости исследуемых задач для определенного состава ВЦФ и конкретного вида возмущений (увеличивающего, уменьшающего, смешанного). Не основании обобщенной формулы и полученного критерия локально! неустойчивости построен алгоритм вычисления радиуса устойчивости.

3. Обоснованы оценки вычислительной сложности в типично* случае для векторных задач о коммивояжере, об остовных деревьях, < совершенных ларосочетания с критериями вида ЫШЛШ, МИМАХ в любо! комбинации.

4. Сформулировано новое направление исследования устойчивосп при изменении числа критериев ВЦФ, скорректировано существовавши

мнение о неубывании паретовского множества при добавлении новы:

критериев.

5. Предложен вероятностно-статистический подход исследованию устойчивости и сформулированы соответствующие теорем

о достаточных условиях.

Основные положение диссертации опубликованы а следупди работах :

1. Бакурова A.B. К исследованию устойчивости экстремальны задач на графах.// Методы и программные средства оптимизации моделирования и создания вычислительных систем : Сб.науч.трудов. Киев: Ин-т кибернетики им.В.М.Глушкова АН УССР, 1990. - С.16-19.

2. Бакурова A.B., Варанвик Г.Л., Максишко Н.К. Об одно

алгоритме решения задачи землепользования. -Запорожье, 1989.-14с.- Деп. в УкрНИИНТИ 27.09.89. Л 2106-Ук89.

3. Бакурова A.B., Емеличев В.А., Перепелица В.А. К проблеме устойчивости векторных задач на графах // Информационный бюллетень.. Ассоциации мят.прогр. - Вып.4. - Екатеринбург. - Институт математики и механики УрО РАН - 1993 - с.19.

4. Бакурова A.B., Кувяйцевя С.А. Векторная задача о лесах: оценки вычислительной сложности, разрешимость с помощью MC, устойчивость // Тези допов1дей наук.конф. викл.та студ. университету (Вип.П).- Загор1жжя - ЗДУ - 1992 - c.J2-I3.

5. Бакурова A.B., Максшко Н.К., Перепелица В.А., Оценки сложности и устойчивос.ти дискретных многокритериальных задач // Материалы IV Всесоюзной школы-семинара "Статистический и дискретный анализ данных и экспертное оценивание".- Одесса.-J991.- С.276-278.

6. Бакурова A.B., Перепелица В.А. Вероятностный анализ устойчивости экстремальных задач на графах // Математическое программирование и приложения : Тезисы докладов,- Свердловск : УрО АН СССР, 1991.- С.12-13.

7. Бакурова A.B., Перепелица В.А. Исследование устой -чивости и сложности векторных задач на графах. Деп. в УкрНИЭНТИ 14.10.1992, N 1Б77-УК92. - 30с.

8. Бакурова A.B., Перепелица В.А. Исследование устойчивости векторных задач на графах // САПР-93: Новые информ анионные технологии в науке, образовании и бизнесе. Тезисы докладов XX международной конференции. - 4-13.05.93.- Гурзуф. -с.86-88.

9. Бакурова A.B., Перепелица В.А. О методах вычисления радиуса устойчивости векторных задач на графах. Тезисы международной конференции "Теория приближений и задачи вычислительной математики ", Днепропетровск, 1993г. - С.15.

10. Bakurova A.V., Rnellcbev 7.A., Perepelltsa Y.А. Stability's conditions o.f combinatorial problema oí vector optimization // Workshop on Discrete Optimization. Abatracts. - ■ May, 1993. - Minsk-Magdeburg. - P.3.

11. Bakurova A., Perepelltsa V. About Power of Sets Alternatives by Increasing Number Criteria Vector Objective Function // Applied Modelling & Simulation. - International 93

Lviv Cmíorenoa. - Sept.3Q-Oot.2, 1993 - Paria - P.9-10.

12. Бакурова Г.Б., Переголвдя B.O. Имов1рностний анал1з складност! 1 ctííkoctí вакторво! аадач1 ком!вояхара // ДАН УкраЗня. - 1993. - ЛИ. - С.