WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Построение агрегированного отношения предпочтения на основе нагруженного мажоритарного графа С. О. Смерчинская, Н. П. Яшина Аннотация Задачи выбора возникают на этапах ...»

Электронный журнал «Труды МАИ». Выпуск № 39 www.mai.ru/science/trudy/

УДК: 519.8

Построение агрегированного отношения предпочтения

на основе нагруженного мажоритарного графа

С. О. Смерчинская, Н. П. Яшина

Аннотация

Задачи выбора возникают на этапах проектирования и создания современных

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

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

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

Ключевые слова Принятие решений; групповой выбор; мажоритарный граф; отношение предпочтения;

ранжирование; агрегированное предпочтение; расстояние Хэмминга; коэффициенты участия экспертов .

Рассмотрим множество альтернатив A = {a1, a 2,..., a n }. На множестве A заданы бинарные отношения предпочтения 1, 2,..., m. Будем полагать, что эти отношения – строгие порядки, в частности, строгие ранжирования. Необходимо построить агрегированное отношение предпочтения, также являющееся строгим порядком, и согласованное c € предпочтениями 1, 2,..., m .

Обычно агрегированное отношение предпочтения используется при групповом 1, 2,..., m выборе. В этом случае – индивидуальные предпочтения экспертов .



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

Будем полагать, что упорядоченная пара альтернатив из A ai, a j t (или ai t a j ), где t = 1,..., m, если элемент ai менее предпочтителен, чем элемент a j *. Напомним, что строгим порядком называется транзитивное и асимметричное отношение .

Поставим каждому из отношений 1, 2,..., m в соответствие графы G1, G2,..., Gm, Gt = ( A, t ) причем – ориентированный граф с множеством вершин–альтернатив A = {a1, a2,..., an } и множеством дуг t. Множество дуг – это множество упорядоченных пар ai, a j (ai, a j A), входящих в отношение t .

Обозначим R t = rijt матрицу смежности графа Gt = ( A, t ), t = 1,..., m. Построим граф агрегированного предпочтения G = ( A, ) .

€ € Потребуем от агрегированного отношения, что

–  –  –

i (i=1,..., m) можно выбрать и по-другому: ai, a j элемент ai предпочтительней, * Отношения чем элемент a j, но стандартные процедуры выбора наилучших альтернатив (ядро, доминирующее подмножество и т. п.) удобнее реализовывать для отношения «менее предпочтителен»

–  –  –

При построении искомого агрегированного отношения будем использовать отношение предпочтения, соответствующее классическому мажоритарному графу [1] .

Напомним, что мажоритарный граф – это ориентированный граф, вершинами которого являются альтернативы, а ориентированная дуга из вершины ai в вершину a j проводится в том и только в том случае, если число экспертов, предпочитающих альтернативу ai альтернативе a j, превосходит половину общего числа экспертов. Для удобства применения

–  –  –

Напомним, что 1, 2,..., m – отношения строгого порядка и, следовательно, по утверждению 1 не содержат контуров, т. е. являются непротиворечивыми .



Алгоритм построения отношения без контуров по .

1. Проверяем граф G = ( A, ) на наличие контуров. Если контуров нет, то граф G = ( A, ) без весов на дугах и есть искомый граф G = ( A, ). Если контуры есть, переходим к п. 2 .

2. Из графа G = ( A, ) удаляем все дуги, которые принадлежат какому-либо контуру и имеют наименьший вес. Переходим к п. 1 .

Замечание. Данный алгоритм позволяет построить единственное отношение по, т. к. на каждой итерации из контуров удаляются все дуги одного (наименьшего) веса .

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

Будем рассматривать матрицы смежности как элементы булевой алгебры.

Введем на множестве матриц операцию конъюнкцию "&":

R k & R t = rijk & rijt (т. е. поэлементное умножение матриц) .

Опишем алгоритм нахождения K – матрицы смежности графа отношения k, в которой 1 соответствует дуге, входящей в какой-либо контур отношения .

1. Ищем контуры с помощью матрицы связности ненагруженного графа G = ( A, ) .

Матрицу односторонней связности S находим по матрице смежности R [3] .

2. Находим матрицу сильной связности S по формуле S &ST = S .

3. Находим матрицу смежности контуров K:

S & R = K, единицы этой матрицы соответствуют дугам, входящим в какой-либо контур графа G = ( A, ) .

При программной реализации алгоритма число альтернатив и экспертов практически ничем не ограничивается .

Зададим правило подсчета для величины d из формулы (2) .

–  –  –

рассчитывается для мажоритарного графа .

Сравним значения величин, полученных по формуле (3) для различных агрегированных отношений .

В работах [1], [2] приводятся следующие варианты построения агрегированного отношения .

1. Построение мажоритарного графа [1], т. е. построение отношения. В этом случае в графе G = ( A, ) могут быть контуры, и тогда выбор наилучших альтернатив затруднен (выше мы уже писали об этом) .

2. Построение агрегированного отношения ra = Tr r' [2], где отношение r ' = \ k, где k – отношение, состоящее из дуг, входящих в какой-либо контур. Таким образом, контуры из удаляются полностью. В этом случае мы можем удалить слишком много элементов, вплоть до того, что r ' = .

–  –  –

где D A – рассчитывается для графа с применением нашего алгоритма; D K – рассчитывается для графа со всеми удаленными контурами. Но в мажоритарном графе могут содержаться контуры, т. е. условие 1 о непротиворечивости не выполняется .

–  –  –

в контуре не все дуги с наименьшим весом, а столько, сколько необходимо для разрушения контуров. Но в этом случае агрегированное отношение предпочтения будет строиться неоднозначно, т. е. можно получить несколько отношений без контуров с одним и тем же € значением D( ). Таким образом, не выполнится одно из основных условий – однозначный выбор наилучших альтернатив .





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

Пример 2 .

A = {a1, a 2, a3, a 4 }. Задан профиль предпочтений Пусть множество альтернатив

–  –  –

Внешне устойчивые подмножества: {a1, a2 },{a2, a3},{a2, a4 } .

Ядра нет .

Доминирующие подмножества (внешне устойчивые): 3 варианта .

Если убрать все контуры, то ядро: {a1},{a2 },{a3 },{a4 } .

Модифицируем алгоритм для решения задач, в которых компетентность экспертов различна, и заданы весовые коэффициенты участия каждого эксперта в построении агрегированного отношения: k1,..., k m. (Например, если эксперты – члены какого-нибудь жюри, то председатель обычно имеет два голоса.) В этом случае каждому отношению предпочтения t ( t = 1,..., m ) фактически ставится в соответствие нагруженный граф с весом каждой дуги kt. Но для удобства работы алгоритма лучше не вводить соответствующие ~ матрицы весов, а вместо матрицы смежности R t использовать матрицу R t = kt R t .

Если в результате работы алгоритма и последующего выбора наилучших альтернатив получен неудовлетворительный результат, например, слишком большое число наилучших альтернатив, предлагается, либо пересмотреть экспертные оценки и затем использовать алгоритм повторно; либо оценить компетентность экспертов на основе полученных от каждого из них отношений предпочтения. Для оценки компетентности t ( t = 1,..., m ) экспертов выясним насколько каждое индивидуальное предпочтение согласованно с остальными предпочтениями экспертов. Для этого необходимо по формуле (2) найти величины D( t ). В соответствии с ними можно либо вообще удалить из рассмотрения отношения предпочтения, заданные наименее компетентными экспертами, либо ввести коэффициенты участия каждого эксперта, а затем применить алгоритм повторно .

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

Пример 3 .

Множество A = {a1, a 2, a3, a 4 }. Задан профиль предпочтений экспертов при m = 3 :

определения коэффициентов участия каждого эксперта вычислим по формуле (2) величины D( i ) (i=1, 2, 3), отражающие компетентность экспертов. Для этого предварительно найдем

–  –  –

альтернатива – a3 .

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

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

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

— отсутствие контуров;

— транзитивность .

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

Утверждение 3. Если граф не имеет контуров, то он содержит хотя бы одну вершину ai такую, что ai = (нет исходящих дуг) и хотя бы одну вершину a j такую, что 1a j = (нет входящих дуг) .

Доказательство следует из того, что граф без контуров можно разложить на уровни [3]. А по определению уровней графа существуют вершины ai и a j : ai = и 1a j = .

–  –  –

На рис. 11 предложен построенный по формуле (4) график зависимости вероятности того, что мажоритарный граф не содержит контуров, от числа альтернатив. Из графика видно, что вероятность существования мажоритарного графа без контуров ничтожно мала, начиная уже с 7 альтернатив. Конкретно, при n = 7 p 0,02, а при n = 8 уже 0,007. Этот факт усиливает преимущества предложенного в работе алгоритма по сравнению с алгоритмом построения мажоритарного графа .

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

Библиографический список

1. Миркин Г. Н. Проблема группового выбора. М.: Наука, 1974 .

2. Осипова В. А., Подиновский В. В., Яшина Н. П. О непротиворечивом расширении отношений предпочтения в задачах принятия решений. //Журнал выч. мат. и мат. физики, 1984, №6. с. 831-839 .

3. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975 .

Сведения об авторах

Смерчинская Светлана Олеговна, ст.

преподаватель, Московский авиационный институт (государственный технический университет) Тел.: (499)158-48-11, mail:

dep805@mai.ru .

Яшина Нина Павловна, доцент, Московский авиационный институт (государственный




Похожие работы:

«Практические работы 1-2 КОМПЛЕКТ ГИДРАВЛИЧЕСКОГО АВАРИЙНОСПАСАТЕЛЬНОГО ИНСТРУМЕНТА "Спрут" для использования аварийно-спасательными подразделениями Назначение: с целью быстрого разрушения элементов конструкций при спасении людей и имущества.Состав комплекта: кусачки КГС-80...»

«Министерство образования Республики Беларусь Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники"МАТЕРИАЛЫ МЕЖДУНАРОДНОГО НАУЧНО-ТЕХНИЧЕСКОГО СЕМИНАРА (Минск, январь – декабрь 2012 г.) Минск БГУИР 2012...»

«Министерство жилищно-коммун? иного хозяйства РСФСР Ордена Трудового Краевого Знамени Академия коммунального хозяйства нм. К. JLПамфилова Ут в ь р и е и о приказом Министерства жилищнокофинального хозяйства РСФСР ОТ 21 ноября 1986 г. й 495 ИНСТРУКЦИЯ Н П Т ВО О ЗИ Н А.J ОБРАБО А РО И К...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ ЗАВАЛИШИНСКИ...»

«"Ученые заметки ТОГУ" Том 5, № 4, 2014 ISSN 2079-8490 Электронное научное издание "Ученые заметки ТОГУ" 2014, Том 5, № 4, С. 1216 – 1220 Свидетельство Эл № ФС 77-39676 от 05.05.2010 http://pnu.edu.ru/ru/ejournal/about/ ejo...»

«Мищенко Илья Никитич Развитие многоуровневых моделей магнитной динамики однодоменных частиц для описания кривых намагничивания и мёссбауэровских спектров магнитных наноматериалов Специальность 05.27.01 – Твердотельная электроник...»

«ИНФОРМАЦИОННЫЕ ВОЙНЫ №1 (21) 2012 I. ИНФОРМАЦИОННОЕ ПРОТИВОБОРСТВО. АКТУАЛЬНЫЕ ПРОБЛЕМЫ. ТЕОРИЯ УДК 658.314.7:330.115 © Цыганов В.В., Бочкарева Ю.Г. Tsyganov V., Bochkareva Y. ПРОГРЕССИВНЫЕ МЕХАНИЗМЫ ИНФОРМА...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.