Среднее число недоминируемых вариантов,как основная вероятностная характеристикадля анализа задач многокритериальной оптимизации тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

Орлова, Елена Сергеевна АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Москва МЕСТО ЗАЩИТЫ
1995 ГОД ЗАЩИТЫ
   
01.01.11 КОД ВАК РФ
Автореферат по математике на тему «Среднее число недоминируемых вариантов,как основная вероятностная характеристикадля анализа задач многокритериальной оптимизации»
 
Автореферат диссертации на тему "Среднее число недоминируемых вариантов,как основная вероятностная характеристикадля анализа задач многокритериальной оптимизации"

г 1 V

2 9 М&Й ®

Российская академия на/к Институт проблем управлечил

нэ празах РУКОЛГ'СИ

Орлова Елена Сергеевна

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

oi.oi.il - Системный англиз и автоматическое управление.

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

МССКЕа 1995

Работ, выполнена г Институте проблем управления РАН

Научный руководитель: член-корр. РАН, д.т.н. Березовский Б.А.

■-- ошюне;-:ты: д.ф.-м.к., проф. Опойцев В.й.

д.т.к., проф. Полиноеский Б.Е.

Ведущее предприятие: Институт системного анализа РАН.

Защита состоятся " г. б ^ час.

на заседании диссертационного совета Ц оог.бй.оз Института прс"лем управления РАН. -

Адрес института: 117806, Москва, Профсоюзная ул.,65.

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

Автореферат разослан -</£* юз* г<

Ученый сехретФ^^^/'-Л

//""'"■'У '•>-.; ■ 1

Диссертационного '-А'УСли. ^^ Власов с.А.

к.т.н. Щ-г^^У

Актуальность темы... Задачи управления, возникавшие на :рактике, часто характеризуются существованием млсгих .ротивокачивкх целей и отсутстзием единого явно шислимого функционала качества. В этих случаях ;риходктся апеллировать к структуре предпочтений человека ;ли группы людей, оценивающих сравнительные достоинства •азличных управляющих воздействий с точки зрения своего снимания предмета. Этот человек илу группа людей обычно азывается лицом, принимасщкм решение (ЛПР).

Ооруализация понятия структура предпочтений ЛПР -есьма сложная задача, так как мощность множества ыбираемых вариантов отлична от единицы. Это йстоятельство служит основным препятствием алгоритмизации етрадиционных оптимизационных моделей. Поэтому изучение труктуры оптимума в неклэссических оптимизационных адачах есть изучение структуры подмножества. В таких адачах используются решающие правила, сводящиеся не к аксимизации подходящей функции, а к "максимизации" в мысле некоторого отношения предпочтения. Слово максимизация" взято здесь в кавычки, т.к. в отличие от аксимизации Функции ему невозможно придать однозначный мысл. Выражения "аеулучшае^ий вариант" и "вариант, лучший з остальных" - эквивалентны, если предпочтение писызается одной функцией. Выделяют различные множества ариантов, если отношение предпочтения является неполным.

з

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

В нашей ситуации неконтролируемым явглется исходнс множество вариантов, из которых выделяется оптимум, решающее правило наоборот обычно порождается системой aj методом принятия решений самым определенным образом. Нтз? на вход дегермилйровазного ренагщего правила псступге случайное множество. -Выход - оптимум - также буд; случайным множество*, а его мощность - случайнс малочисленной величиной. Натемгтич&ское озиданий зтс Беличааа определяется как среднее число недомшшруем! вариантов.

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

Ледь рабств Изучение Среднего числа недоминкруеш

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

Методы исследования. Системный анализ, теория вероятности, теория принятия решений, стохастическая геометрия, теория особенностей.

Научная новизна• В данной работе выведена основная асимптотическая Формула для ожидаемого числа пересечений максимумов выборки болькой размерности на оснсвь определенных геометрических структур. Доказаны теоремы, связывающие порядковые отношения и степень роста ожидаемого размера множества максимумов. Вычислены главные члены асимптотик среднего числа недоминируемых вариантов для А-Р." , меры v с независимыми непрерывными критериями, л-произзобьных порядковых отношений и Интересным

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

Исследованию математического ожидания числа недоминируемых вариантов посвящен ряд работ. Однако, в основном рассматривались слу"аи, когда оценки по критериям независимы, а бинарное отношение - паретовское, т.е. х Par у » xi s у^ для любого i и Xj < у^ для некоторого j.

Практическая и теоретическая ценность. Результаты

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

Адрубаиия работы. Основные реьультст^ диссертации докладывались на:

-семинаре "Экспертные оценки и анализ данных' ИПУ РАК

'3933,1994); -семичарэ по зкспертны:: сценкам КГ/ (1 С.Рг.), -Нскгунарсдной конференции "Статистический и дчскретный анали^данш« к экспертные оценки" (Одесса,19?4).

Публикации ■ Па те*:е диссертации спубликовгнс з работы.

Стгуг.тура к ооьем рабсги. Диссертация состоит из введения, пята глав и заключения, сод е ряиг юс страниц, включая а рисунка, 1 таОлдцу и список литературы из наименовал'.». '

■ '• содержание работы.

• Во' ВУ5££УЖ обоспозшг.-.етоя актуальность рыбракной темы, формулируется ц?ль ръбот к кре<тно излагается ее содеркание.

К ' Л5УЕ5Й излагаются • оснор.нке понятия и

'определения. Дьется сбзср рзаультгтоь.- полученных ранег.

Функция выбора лзляс-т.-я формализацией понятия оптимальности и спредэляэтся как трс!;ка:

(л, J >А, С : Л -*2Д: X: С!Х) X), ГД6 Л -универсальное мнохество вариантов [решений); .1 - семейство допустимых предъявлений; значение теоретико-множественного оператора с на предъявлении >: с х интерпретируется как выбор из х.

Списивастся наиболее часто применяемые при Формализации структуры предпочтения ЛПР классы функций выбора, в частности, графодемкиантчая Функция.

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

Показывается, что позиция общей теории выбора, использующая как основной объект функции выбора, поззоляет рассматривать различные модели выбора с единых теоретико-мноиестгенных позиций, выяснять принадлежность 'тех или иных функций выбора известным классам Функций и т.д. Однако, этот подход с его высоким уровнем абстрактности не позволяет во многих случаях решать • конкретные проблемы выбора в задачах с многокритериальной структурой исходного мкйгества вариантов. Решение .этой проблемы основано на на пеплрком сравнении вариантов и выборе недоминируекнх.

Формальным выраяенлеы понятия попарного сравнения вариантов является бинарное отношение на множестве,

определяемое как подмкоаество в прямом произведении данного множества ьз себя: sc = а х л - бинарьое отношение на множестве а ^ Rn; запись хзеу означает., что (х, у) с

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

Описываются вероятностные характеристики бинзрных отношений в критериальном пространстве. Дается точное определение среднего числа недсмилируемых вариантов для бинарны:: отношений. Пусть л - выборочное пространство или, говоря другими, словами, исходное множество вариантов. Еудем считать что на а задана а-алгеора к вероятностная мера v Бинарное отношение н я а х а предполагается измеримым относительно соответствующей а-глге5ры. n -целочисленная случайная величина. Пусть х - повторная независимая выборка объема N. '¡исло недомилируемых в х вгриа.чтеь |>;txRxj' - случайно. Математическое отдание случайной величины | Мя.х^:: j назовем средним числом Кедоминируе^х паряантоэ еiri) в выборке объема N, т.е. eiN). = E|hax_xj, где е- - оператор катематического ожидания. ■ -

3 обзоре имеющихся результатов по исследовании! данной яеякчлаы замечено, что и основном уаооты, которые 'соевящеиы оценке величины среднего числа цгдом:-::шруешх

г

вариантов опираются на комбинаторную, технику Врандорфа-Нильсона и Собля. Указывается на преимущество подхода, в котором центральную роль играет функция распределения случайной величины - меры верхнего среза. Пусть и(а) - мера верхнего среза - случайная величина, определим ее функцию распределения F(m) = р (m (; <ш) = j{aeA: ш(а) < ш}. Тогда ПО теореме фубИКИ:

1

e(N) = N |(1 - ¡a)1,-1 dF(m) .

О

Пределы интегрирования £ 0, 1]'взяты, так как mfa) -зероятностная мера множества и, следовательно, Ososi.

Приводятся Формулы дисперсия недоминируемых вариантов зля повторной независимой выборки объема N, где х -юстоянная или пуассоковски распределенная случайная зеличина. Из этих формул можно видеть, что если среднее шсло недоминируемых вариантов определяется функцией >аспределения меры верхнего среза случайной точки, для вхождения дисперсии необходимо знать еще распределение (еры объединения верхних срезов двух случайных точек.

Рассматриваются сравнения и типы распределения,' на :оторые накладываются лишь ¿«.которые регулирующие условия, •арантирущие отсутствие теоретико-множественных затруднений. Приводятся теоремы о распределении числа ;едоминируемых вариантов. В частности, теорема о том, что

-'э

центрирозанное и нормированное число недоминируемых вариантов имеет асимптотически нормальное распределение.

Приводятся- оценки дисперсии • и четвертого центрированного момента для пуассоновски распределенного м при > -» х>.

1с второй главе рассматривается вероятностные и

мощкостнне характеристики двух множеств: множества

к

недохиЕируемых вариантов мьхЕ;х> и множества наилучших вариантов тах^(х). Множество всевозможных вариантов, которые могут бить предъявлены к сравнению, будем .обозначать через и. На нем задано бинарное отношение предпочтения и х у, т.е. для некоторых пар вариантов х, у < V. утверждается. что х л/чае, чем у, что и обозначается как т) е я. Рассмотрим два семейства решавдкх правил. ассоциированных с х-, выделяющих »шояьстьа: !;-недоминйруемых вариантов - это такие .варианты, что для каждого из них число более предпочтительных вариантов, чем последний в анализируемом множестве, ве превосходит к; к-наилучших варианты - ото вауиан'/н,- которые предпочтительнее всех остальных, за ксьличеикеи, быть моает. а вариантов.

Мощности множества недочшшруемых вариантов мк () и иноаестве. наилучших вариантов, а такае их средние и

.»*'(К) соответственно - ' основные «сследуечие объекты данвей главы.

Даится асимптотические формулы, описывающие связи между м!с и mk, для зтого рассматривается верхний срез бинарного отношения R в точке л с и. "о есть множество r^ = {у £ 11: (у,.-:) £ R} И НИЖНИЙ срез - MrfOSeCTBO Я = {ус и: (х, у) £ R}. Мера верхнего (нижнего) сргза, обозначаемая через (соответственно т(^) - это

измеримая функция на %.

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

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

Приводится следующая теорема. Пусть f - монотонная полунепрерывная функция слева in р. в R, такая, что FCt) = о при х s о, f(t) = 1 при t » 1. Пусть и есть единичный отрезок. Зададим на и бинарные отношения ч„ и RF гак:

г ■

(х, у) е Rp • Fix) £ у (х, у) е Rf « .4 < Ft у) .

Пусть р - равномерное распределение на у. Мера верхнигс (нигнего) среза в случайной точке для отношения имеет функции распределения р. .

В третьей главе исследуются различные специальные случаи слузадных. лодмяосеств и бинарных отномекий, пс которым осуществляется выбор: прямое произведение бингрш> отношений, равномерное распределение для связок. Ш вероятностная структура представляет интерес, как - с теоретической, так и с практической точки зрения. ИзучаетС51 постановка задачи с бесконечны« объемом выборки.

Лс двум множествам, снабженными о-алгеорами, вероятксстнымя*мерами, и измеримыми бинарными .отношениями, можно "построить ах прямое произведение и снабдить его -ты же структурами: с-?лгебра есть тогда произведение с-алгебр, мера - произведение мер. а бинарное- отношении определяется следующим образом: и - х бяьарных хэтаошеша на прямом произведении а = х а2 если у * = , х^Ь / =,Лу, I у2).

./■ " *1в|7х» ТлЧ'г: . " -

• Ткшгчньш примером пряного- произведения является широко .исследовавшиеся отношение Парето в и с независимыми жхотериямЕ. .

• арпБОДТзтся теорема о /том," что среднее число ведогаквдуемых вариантов в сэмнехктелкх определяют, среднее

11

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

Точнэя Формулировка 'теоремы следующая: Пусть е'{п), е" (п) есть средние числа чедомюшруемых вариантов и сомножителях в выборка объема п. Тогда:

е{ п) =

■ Е

05 1+,3*11-1

п - 1

1 J

^~ * — I

Исследование ?той формулы показывает, чхо в ассимлтотяяэ среднего возникает логарифм. объегла выборки, когда средние в сомножителях расгут одинаково.

Б этой Ее гл?ве рассмотрена задгча равнойерноЗ плотности на п-связкых точек к похйзазо, что с-иа сводится к случаю многомерного нормального гаспрецелгния.

. ро втором .параграфе рэслгатркзется слздугчгя модель. позволяющая работать с беггконе'пшм . множеством исходных вариантов:* Пусть и - счзтаое мнохесгвс с. бинарным отношением на нем. Вкборяа х с и обладает .гзойством, что события {ахе х> пезарлсимн а имеет, вероятность г1-

Пели рчд £ рх расходится; то сС%еи выборка с еданичнеа вероятности) бесконечен. Однако моцчссть множества аедшшшруемых V яыборг.б варкаагев можзт сыть ограничена г. а еэ вероятностные . харашехистаьа могут быть Еырагени черэз , Для некоторых глаесов бинарных откояениа среднее тесло яелочитфуемьх езряйнтоз при р^р вычислено кап.

функция р.

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

Показано, что среднее число недолинируемых вариантов е(я) асимптотически эквивалентно умноженному па к преобразования Лапласа Функции распеределения меры верхнего среза F(y), что дает широкие возможности для нахождения асимптотик е(к). Точная формулировка основной теоремы этой главы такова:

Теорема. Пусть Ftp) - правильно-меняющаяся Функция, то есть для всех о < t < 1 существует предел:

lim F(Mt)/F(n) = c(t).

который по экстремальной лемме равен t", « - называется показателем F. Тогда:

L(N) = | e~HN df(n) * Г (а) И"« F^ J - , О

при n -» се, где Г (а) - гамма-функция, f - функция распределения меры верхнего среза. )'

Приведены примеры нахождения асимптотик для случая, когда и - отношение Парето, для сравнения по Подинозскому.

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

Отношение п с нв х й15 есть относительное сравнение определяемое кснусом к = кш (т.?. vйu и у, V - -л е я), который является компактно телесным локально-конусгкым многообразием. •,'".*'' -- '

Мера ч задается ллотносты; • -г = рау, где р -удовлетворяет свойствам: вир р - V, т.е. носитель р есть компактное локально-конусное стратифицированное

подмногообразие V г. я™, я Р = ьь?, гдз ь - непрерывная функция, отличная от нуля на V, Ь(V) - расстояние от ч.. до п^хг, а > -1. . \

Теогема. Пусть а^я"; к; V - описанные визе, пэра1 (у,к) удэалетворяет условие трансверсальности, :: размерность страта V (сильного сстпмукз) махсккальноД размерЕостя ), Тогда!

1«;

, rn+s е (n ; n

где s - показатель в представлении плотности Р = bhb, т.е. скорость убывания плотности при подходе к страту.

Во втором параграфе найдены главные члены асимптотик среднегочисла e(.v) недоминируемых вариантов для а = r", меры V с независимыми непрерывными критериями, R произвольных порядковых отношений и n s3. Приведены таблицы всех возможных случаев неинвариантнкх относительно поворота к сдвига для п = 2, п = 3, с такими характеристиками для каждого случая как мера верхнего среза га(.\) и главные члены асимптотик функции распределения верхнего среза F(t) и среднего числа недоминируемых вариантов е(Я). Асимптотики среднего числа недоминируемых вариантов вычисляется по Формуле:

е(Л) * ЛГ(в> Fj_ 5 J •

Этой формулой ножно воспользоваться в силу того, что из вычислений F(t) видно, что функция распределения верхнего среза F(t) для порядковых бинарных отношений правильно-меняющаяся и имеет вид te(ln t)ß.

Пяхзз слава посвящена рассмотрению произвольных порядков. Рассмотрим произвольное упорядочивание (линейный порядок) множества а = {1,...,г ;, определенное с помощью произвольной перестановки, выбранной однородно из

16

сннм-зтрическсй группы на л. Дано й таких произвольных .независимых перестановок, определим произвольный частичный порядок на п как пересечение всех <з - упорядочиваний, определенных с помсщьз этих перестановок.

В гляве используются геометрические Формула, которые' Золез отракаих сущность проблемы, ортаьтсм в ¿-мерном . Пвхлидоеом пространстве обозначим замыкание сьязанчой компоненты пространства с удаленными координатными плоскостями, то есть ортанх задается системой нерзвекств;

б1х.>0, 1= 1.....а, где ^ - есть Порядковый конус К

определен как объединение набора ортантов, и порядковые бинарные отношения определена следующим образом:

(х,>К^ в А-у е К.

В этой главе получена 'асимптотикиоамдгеуого числа . элементов максимумов для бсльиой повторной независимей выборки х с независимыми непрерывными координатами ДЛл п -» п - размер выборки с фиксированным а, я с о0> Хотя эти асимптотики, очевидно зависимы от 5, теорема говорит, что их поведение является вполне умеренным. ' .

Теорема, функция ев(А;= Ет5<х), где п ■ - размер' х, . .чскет быть разлсаена в асимптотические ряды: *''

- . е,.(п) = I S'»г,inГini<",•

где г пробегает дискретное подмножество рациональных чг.сел

а {фактически, объединение конечного числа арифметических прогрессий■), г. 1 - натуральнее ч;:сло не лреБьим:и,ее <2-1.

Доказывается теорема о нахождения среднего числа недоминируемых вариантов с помочь» многогранника Ньютона ассоциированного с произвольным;; порядками.

Пусть £ с гйп - подмножество интегрируемой решетки в к13 со всэми неотрицательными координатами. Определим обычным способом - многогранник Еьотона £ как выпуклую оболочку суммы (Минковского) £ ж положительный замкнутый ортант Р.^. Луч. (1.,... ,ОгО пересекает П^ в единственной точке. Любуй из (равных) координат этой точки назовем удаленность!) £ и коразмерность грани содержащей выше упомянутой течку в п , уменьшенную на 1-, назовем краткостью £ . Очевидно, что удаленность равна кула тогда и только тогда, когда V есть качало координат, и кратность V не большое чем <3-1.

Пусть б есть подмножество о. определяющее порядковое отношение Для любой взриины <э0 предполагаем

единственно определенное афикное отображение р.^ самого в себя,которое переводит вершину в начало координат и куб <а в единичный куб.

Множество £, таким образом, отображение в подмногестьо г^п р.^ и можно определить кратность и удаленность вершины ч0 как образ б ог этого отображения. Пусть максимальная удаленность вериины ц0 ёсть г, и среди

верпин, где удаленность достигает своею максимума-, максимальная кратность равна к. Назовгм отк числа крптностьэ и удаленностью Я соответственно.

Теорема. Ожидаемое число максимальных элементов в повторно?! независимой выборке с независимыми координатами размерности а, евчзгнней с порядковыми отношениями Кз, при п ™ растет как (п1~5>'гп.-Л:.

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

Порядковое отношение гг,. в будем называть

ч-мерными, если существует некоторое г.одмкожество координат имеЕ'доэ размер к, так что многество определяющее отношение к зависит только от подмножества.

з

Геометрически это означает; что конус . к^. который представляет объединение ортяитэ?,' есть фактически пересечение (<з-к) - мерного координатного подпространства и некоторого к-мерного конуса.

Теорема. ОЕИдаемсе число ея максимальных элементов в •большой выборке,.связанной с порядковыми отношениями Яз не • стрим»:тся к о при п-*м тогда и только тогда.,. когда "эти отношения содержатся в некотором (одномерном) линейной-порядке. ' ' ; .1

Вывод. Среднее число недсминигуемых вариантов . стремится к о при а->« тогда и только тогда, когда основная

19

часть отношений п, - циклична.

Отсюда следует, что транзитивное замыкание порядкового отношения либо полно, либо представляет собой линейны порядок, либо отношение Парэто в некоторой размерности причем эта размерность зависит ог

поведения е5<

Теорема. Следующие утверждения эквивалентны:

1. Транзитивное замыкание порядкового отношения определено как конус, который является пересечением к-иерного ортанта (конуса Парето) и (а-к) - мерного линейного пространства, кг2.

2. ожидаемое число максимальных элементов растет как

.глк-1(п)+0(.1лк"2(п)).

Основные результаты работы.

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

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

3. Рассмотрен вопрос о нахождении асимптотик среднего

20

и дигтерапт вариантов, недоминируемых по порядкспым Шикарным отношениям.

4. Исследовано пгхотдение среднего числа недомипируемых вариантов дли прямых арслзьеденпй бинарных отношений.

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

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

7. Введено понятие многогранника Ньетош,

#

ассоциированного с порядковым:! отношениями. Доказана возможность нахождения главных членов асимптотического разложения ожидаемого числа максимальных элементов для произвольных порядков через характеристики многогранника.

8. Показано, что среднее число недоминируемых вариактов для порядковых бинарных отношений не пропадает при п « тогда и только тогда когда данное отношение с одерзится в лииейно координатном упорядочивания.'" Доказано, что вероятность цикла з конечной выборке нулевая.

21

Публикации по теме диссертации.

1. Орлова Е.С., "Асимптотики среднего числа недоминчруемых вариантов для бинарных отношений", // Автоматика и телемеханика, и, Москва, 1991.

2. Барышников Ю.М., Орлова Е.С., "Мнсдоство максимумов для произвольных порядков",// Автоматика и телемеханика, В печати.

3. ВагуshniV.ov Ум. , Orlova Е., "Random Orders and Their Maxima", Order,1994.