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

Содержание

Введение

1. Формализация нечетких понятий

2. Задача выбора лучшей альтернативы на основе нечетких отношений предпочтения

3. Мультипликативная модель группового выбора

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

5. Иллюстративный пример

Заключение

Список литературы

Приложение: листинг программы



Введение

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

В настоящее время существует значительный арсенал методов выбора лучшей альтернативы на основе экспертных методов оценивания. Как правило, все они в значительной степени ориентированы на форму представления экспертной информации. В данной работе рассматриваются методы обработки экспертной информации, заданной в виде отношений предпочтения, при этом экспертный опрос осуществляется на основе парного сравнения альтернатив. Данная процедура, с одной стороны, предполагает более «осторожное» использование человека в качестве измерительного инструмента, снижая субъективное влияние на результаты оценки, а с другой - является достаточно эффективной в том смысле, что при сравнении двух альтернатив эксперту проще увидеть преимущества одной и недостатки другой. Кроме того, оценивание альтернатив осуществляется по всей совокупности показателей или критериев выбора, нередко противоречащих друг другу. Такой подход позволяет решить проблему многокритериальности, которая сопутствует оцениванию сложных объектов. Таким образом, использование отношений предпочтения является эффективным способом представления экспертной информации в процедурах группового принятия решений, поэтому развитие различных подходов на этой основе является актуальной проблемой.

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

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

а) определения степеней доминирования-недоминирования с помощью порядковых взвешенных операторов агрегирования;

б) применения различных стратегий формирования выборочного множества;

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

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

Перечисленные модели группового выбора были положены в основе разработанного программного обеспечения.



Глава 1. Формализация нечетких понятий

1.1 Основные понятия теории нечетких множеств и отношений

программа алгоритм мультипликативный предпочтение

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

В основе понятия нечеткого множества лежит представление о том, что составляющие его элементы, обладающие общим свойством, могут обладать этим свойством в различной степени и, следовательно, принадлежать данному множеству с различной степенью. При таком подходе высказывания типа «элемент х принадлежит данному множеству» теряют смысл, поскольку необходимо указать «насколько сильно» или с какой степенью данный элемент принадлежит данному множеству. Один из простейших способов математического описания нечеткого множества - характеризация степени принадлежности элемента множеству числом, например, из интервала [0, 1].

Пусть Х - некоторое множество (в обычном смысле) элементов. Нечетким множеством С в Х называется совокупность пар вида , где , а функция принадлежности нечеткого множества С, значения которой определяют степень принадлежности этого элемента нечеткому множеству С. Множество M = [0,1] называется множеством принадлежности. Если M = {0,1}, то получим определение обычного подмножества B X, при этом функция принадлежности становится характеристической функцией. Обычные множества составляют подкласс класса нечетких множеств.

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

Нечеткое множество называется пустым, если его функция принадлежности равна нулю на всем множестве Х, т. е.

Универсальное множество Х также можно описать функцией принадлежности вида

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

Пусть А и В - нечеткие подмножества универсального множества U.

Дополнение нечеткого множества А задается функцией принадлежности вида

,

где n(x) - операция отрицания, которая определяется как отображение , удовлетворяющее свойствам:

1. n(0) = 1, n(1) = 0;

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

n называется обычным отрицанием, если ; слабым или интуитивным отрицанием, если ; сильным отрицанием, если .

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

.

Наиболее часто используется стандартное отрицание

.

Другим примером отрицания является отрицание Суджено

.

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

n( G(x,y) ) F( n(x), n(y)) или n( F(x,y) ) G( n(x), n(y)),



где n(x) - операция сильного отрицания.

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

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

Объединением нечетких множеств А и В в Х называется нечеткое множество АВ с функцией принадлежности вида

х Х ((х) = max{(х), (х)}, хХ).

Если {А} - конечное или бесконечное семейство нечетких множеств с функциями принадлежности (х, у), где уУ- параметр семейства, то объединением С = А множеств этого семейства является нечеткое множество с функцией принадлежности вида

х ((х) = , хХ).

Объединение нечетких множеств А и В в Х можно определить и через алгебраическую сумму их функций принадлежности:



(х)=

Пересечением нечетких множеств А и В в Х называется нечеткое множество АВ с функцией принадлежности вида

(х) = min{(х), (х)}, хХ.

Если {А} - конечное или бесконечное семейство нечетких множеств с функциями принадлежности (х, у), где уУ- параметр семейства, то объединением С = А множеств этого семейства является нечеткое множество с функцией принадлежности вида

(х) = , хХ.

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

(х) = (х)(х), хХ.

Дополнением нечеткого множества А в Х называется нечеткое множество А' с функцией принадлежности вида

(х) = 1 - (х), хХ.

Интересно, что при таком определении дополнения, вообще говоря, не выполняется закон комплементарности, то есть АА'Ш, AА'1 в отличии от обычных множеств.

Разность множеств А и В в Х определяется как нечеткое множество А\В с функцией принадлежности вида

(х) = .

Декартово произведение А…А нечетких множеств А в Х, i=1,…, n, определяется как нечеткое множество А в декартовом произведении Х = Х…Х с функцией принадлежности вида

x=(x_1, x_n) Xⁿ ((х) = min{(х), …, (х)}).

Выпуклой комбинацией нечетких множеств А, …, А в Х называется нечеткое множество А с функцией принадлежности вида

(х) = , где 0, i=1,2,…, n, = 1.

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

Таблица 1.1

Пересечение	Обозн.	Объединение	Обозн.
GAB(x,y) min(x,y)	AB	FAB(x,y) max(x,y)	AB
GAB(x,y) xy	AB	FAB(x,y) x+y-xy	AB
GAB (x,y) max(0, x+y-1)	AB	FAB(x,y)min(1,x+y)	AB

Как правило, называется пересечением нечетких множеств, - объединением, - алгебраическим произведением, - алгебраической суммой, - ограниченным произведением, - ограниченной суммой. Объединение и пересечение иначе называют классическими (именно эти операции впервые были предложены для формализации связок или и и основателем теории нечетких множеств Л. Заде).

Рассмотрим основные свойства операций над нечеткими множествами. Для этого в таблице 1.2 перечислены основные свойства бинарных операций, а и “+” или “-“ отмечено соответственно наличие или отсутствие свойства у нечеткой операции.

Таблица 1.2

	Свойство	,	,	,
1	Коммутативность	+	+	+
2	Ассоциативность	+	+	+
3	Дистрибутивность	+	-	-
4	Идемпотентность	+	-	-
5	Закон двойного отрицания	+	+	+
6	Законы де Моргана	+	+	+
7	Комплементарность	-	-	-
8	Законы, определяющие действия с	+	+	+
9	Законы, определяющие действия с U	+	+	+

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

A (B C) (A B) (A C),

A (B C) (A B) (A C),

A (B C) (A B) (A C),

A (B C) (A B) (A C).

Перечисленные в таблице 1.2 операции объединения и пересечения принадлежат классу треугольным норм и конорм.

Треугольной нормой (Т-нормой) называется операция T: [0,1][0,1][0,1], удовлетворяющая следующим условиям:

a) - коммутативность;

b) - ассоциативность;

c) - ограниченность;

d) - монотонность.

Пересечение, алгебраическое произведение и ограниченное произведение являются примерами Т-норм.

Треугольной конормой (S-конормой) называется операция S: [0,1][0,1][0,1], удовлетворяющая следующим условиям:

a) - коммутативность;

b) - ассоциативность;

c) - ограниченность;

d) - монотонность.

Объединение, алгебраическая и ограниченная суммы являются примерами S-конорм.

Легко заметить, что T-нормы и S-конормы связаны соотношением

.

Пусть и - две треугольные нормы. Будем говорить, что слабее или, что то же самое, сильнее , если

.

Аналогичное определение можно ввести для S-конорм.

Можно показать, что для любой Т-нормы имеет место неравенство



,

.

Для S-конорм выполняется аналогичное неравенство

,

.

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

Таблица 1.3

S-конормы	T-нормы
,	,
, >-1	, >0
,
S* (x,y min {1, x+y+xy}, -1	S(x,y max {, x+y-1-(1-x(1-y} -1

Рассмотрим операции над нечеткими множествами, не относящиеся к треугольным нормам.

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

Выпуклой комбинацией нечетких множеств называется нечеткое множество А с функцией принадлежности

,

где . Величины называются весовыми коэффициентами. Они позволяют учитывать “вклад” каждого нечеткого множества в результат.

Для нечетких множеств можно ввести операции, которые не имеют аналогов в классической теории множеств. Рассмотрим некоторые из них.

Пусть .

Операция нечеткое и определяется правилом

;

операция нечеткое или определяется правилом

.

В обоих случаях . Этот параметр определяет степень близости к логическим операциям и и или. Если , то операция нечеткое и превращается в классическую операцию и, а нечеткое или - в классическую операцию или. При имеем среднее арифметическое функций принадлежности нечетких множеств А и В.

Другим примером является -операция, определяемая правилом

.

Она является n-местной, а параметр определяет близость к той или иной логической связке. К такому же типу относится операция с функцией принадлежности

,

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

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

1.2 Нечеткие бинарные отношения, заданные на множестве

Пусть Х - некоторое множество. Нечеткое бинарное отношение определяется как нечеткое подмножество декартова произведения ХХ и задается функцией принадлежности вида : ХХ[0, 1], которая определяет степень выполнения отношения xRy.

Рассмотрим свойства нечетких отношений.

Пусть нечеткое отношение R задано функцией принадлежности вида (x,y) [0, 1]. Отношение R называется

- рефлексивным, если х Х ((x,x)=0);

- симметричным, если х, y Х ((x,y)= (y,x));

- транзитивным, если х, y (

Свойства антирефлексивности, антисимметричности определяются путем отрицания соответствующих кванторных предикатов. Кроме того, можно определить свойство совершенной антисимметричности, которое заключается в следующем х, y Х ((x,y)>0 (y,x)=0).

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

Пусть . Говорят, что нечеткое отношение является дополнением отношения R, если

.

Отношение является объединением отношений и , если

.

Отношение является пересечением отношений и , если

.



Отношение является алгебраической суммой отношений и , если

Отношение является алгебраическим произведением отношений и , если

.

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

К специальным операциям над нечеткими отношениями относятся различные композиции. Пусть ; X, Y, Z - компактные множества, - непрерывные функции.

Определим следующие композиции:

- (max-min) - композиция (максминная композиция) с функцией принадлежности

;

- (min-max) - композиция (минмаксная композиция) с функцией принадлежности

.



Пример. Пусть нечеткие отношения и заданы матрицами

	0.1	0.2	0	1	0.7			0.9	0	0.3	0.4
	0.3	0.5	0	0.2	0.1	,		0.2	1	0.8	0
	0.8	0	1	0.4	0.3			0.8	0	0.7	1
								0.4	0.2	0.3	0
								0	1	0	0.8

Максминная композиция есть нечеткое отношение , определяемое матрицей

	0.4	0.7	0.3	0.7
	0.3	1	0.5	0.8
	0.8	0.3	0.7	1

Пусть . Если

,

то есть , то R называется максминным транзитивным отношением.

Пример. Пусть задано нечеткое отношение.

R	a	b	c	d
a	0.2	1	0.4	0.4
b	0	0.6	0.3	0
c	0	1	0.3	0
d	0.1	1	1	0.1



Матрица отношения имеет вид

	a	b	c	d
a	0.2	0.6	0.4	0.2
b	0	0.6	0.3	0
c	0	0.6	0.3	0
d	0.1	0	0.3	0.1

Легко видеть, что

,

т.е., а значит, отношение R является транзитивным.

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

Нечеткое бинарное отношение, обладающее свойствами транзитивности и рефлексивности, называется нечетким отношением предпорядка.

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

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

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

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

Рефлексивное и симметричное отношение называется отношением сходства. Отношением подобия, или нечетким отношением эквивалентности, называется нечеткое бинарное отношение, обладающее свойствами рефлексивности, симметричности и транзитивности.

Свойства основных нечетких отношений представлены в следующей таблице.

Таблица 1.4.

Отношение	С в о й с т в а
	Р	АР	С	АС	Max-min T	min-max T	К
Предпорядок	+				+
Подобие	+		+		+
Различие		+	+			+
Сходство	+		+
Несходство		+	+
Нестрогий порядок	+			+	+		+
Строгий порядок		+		+	+		+
Порядковое отношение	+			+			+

Замечание. Символом “К” обозначено свойство наличия контуров в соответствующем графе без петель. Важно, что -срезам нечетких отношений соответствуют обычные отношения с аналогичным набором свойств.

1.3. Нечеткие отношения предпочтения

Пусть X-множество заданных альтернатив. Для оценки альтернатив из X привлекается эксперт, который для любой пары альтернатив может высказать одно и из следующих утверждений:

1. «x не хуже y» (обозначение xy).

2. «y не хуже x» (обозначение yx)

3. «x и y равноценны» (обозначение x y)

4. «x и y не сравнимы между собой» (обозначение x y)

Отношение R={(x, y)/x y} будем называть отношением предпочтения на X. Заметим, что R - рефлексивное отношение, поскольку считается, что альтернатива x не хуже себя.

Будем говорить, что альтернатива x строго лучше альтернативы y, если (x, y)R, но (y, x)R. Совокупность всех таких пар (x, y) образует отношение строгого предпочтения R^s на множестве X. Для более компактной записи определения воспользуемся определением отношения R^-1, обратного к R: (x, y)R^-1 (y, x)R, тогда отношение строгого предпочтения R^s можно записать в следующей форме:

.

Множество пар равноценных (эквивалентных) альтернатив образует отношение квазиэквивалентности

.

Заметим, что если задано отношение предпочтения R на X, то

.

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

Соответствующее R отношение безразличия R^I в X определяется следующим образом. Пара (x, y) R^I тогда и только тогда, когда либо не выполнено ни предпочтение x y, ни предпочтение y x, либо оба эти предпочтения выполнены одновременно. Отношение R^I можно записать в виде:

R^I = ((XX)\(RR^-1))(RR^-1).

Если (x, y) R^S, будем говорить, что альтернатива x доминирует над альтернативой y (x > y).

Альтернативу xX назовем недоминируемой в множестве X, если в множестве X нет ни одной альтернативы y, которая бы доминировала над x.

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

X^н.д. = xyX ( (y, x) R\R^-1 ).

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

Пусть X - заданное множество альтернатив. Нечетким отношением нестрого предпочтения на X будем называть любое заданное на этом множестве рефлексивное нечеткое отношение с функцией принадлежности R: XX [0, 1], при этом (R (x,x) = 1). Рефлексивность нечеткого отношения предпочтения отражает тот естественный факт, что любая альтернатива xX не хуже самой себя.

Если _R - функция принадлежности нечеткого отношения предпочтения на множестве альтернатив X, то для любой пары альтернатив (x, y) XX значение _R (x, y) понимается как степень выполнения предпочтения «x не хуже y».

По заданному на множестве X нечеткого отношения предпочтения R можно однозначно определить три соответствующих ему нечетких отношения: безразличия R^I(_R^I), квазиэквивалентности R^E(_R^E) и строгого предпочтения R^S(_R^S).

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

1. Нечеткое отношение безразличия:

_R^I(x, y) = max 1 - max {_R (x, y), _R (y, x)}, min {_R (x, y), _R (y, x)}} =

= max {min {1 - _R (x, y), 1 - _R (y, x)}, min {_R (x, y), _R ((y, x)}}

2. Нечеткое отношение квазиэквивалентности:

_R^e(x, y) = min {_R (x, y), _R (y, x)}

3. Нечеткое отношение строгого предпочтения:



Глава 2. Задача выбора лучшей альтернативы на основе отношений предпочтения

2.1 Постановка задачи

Пусть задано множество альтернатив X={x₁,…,x_n} и нужно выбрать лучшую, в некотором для их оценки, смысле. Для решения задачи привлекается группа экспертов E={E₁,…,E_m}. Каждый эксперт на основе парного сравнения альтернатив формирует матрицу парных сравнений A={a_ij}_nn, где a_ij оценка предпочтения в паре (x_i, x_j).

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

1) экспертный опрос: формирование нечеткого отношения предпочтения каждым экспертом

2) построение коллективного отношения предпочтения на основе индивидуальных отношений предпочтения

3) определение лучшей альтернативы на основе степеней доминирования - недоминирования

Далее рассмотрим более подробно некоторые элементы этой схемы.

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

· альтернатива x_i предпочтительнее альтернативы x_j (x_ix_j);

· альтернатива x_i равноценна альтернативе x_j (x_i x_j);

· альтернатива x_i не сравнима по предпочтению с альтернативой x_j (x_i x_j).

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

· в силу сложности оцениваемого объекта часто оказывается более целесообразным формировать оценку вариантов в целом, так как получить оценки отдельных составляющих затруднительно или даже невозможно;

· необходимость одновременного учета различных условий и критериев выбора, нередко противоречащих друг другу, предполагает более “осторожное” использование человека в качестве измерительного инструмента. Это означает, что поскольку для выбора альтернативы требуется сложная экспертная информация большого объема, то необходимо применение методов, которые снижают субъективное влияние на результаты выбора;

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

Полученная в результате парных сравнений информация используется для ранжирования альтернатив (в частном случае - для определения весовых коэффициентов критериев, показателей). Рассмотрим случай, когда парные сравнения проводятся единственным экспертом, тогда результат экспертизы можно представить в виде графа парных сравнений G или в виде матрицы парных сравнений A. Пусть сравниваются n альтернатив, тогда граф G содержит n вершин, причем если альтернатива x_i предпочтительнее x_j, то имеется дуга от вершины x_i к вершине x_j. G не содержит петель. Если среди альтернатив нет равноценных и несравнимых, то получим полный ориентированный граф, который иначе называется турниром. Этот термин возник от названия соревнований по круговой системе, когда каждая из n команд (игроков) играет со всеми другими, причем ничья не допускается. Число одержанных побед есть число очков данной команды. Если есть несравнимые альтернативы, то между вершинами отсутствует дуга; равноценным альтернативам соответствуют две противоположно направленные дуги. Граф парных сравнений в этом случае является ориентированным графом, но не турниром.

Матрица парных сравнений А= {a_ij}_nn задает отношение строгого предпочтения, которое соответствует структуре предпочтений ЛПР, при этом различают простую структуру, когда парное сравнение выявляет лишь факт превосходства одной альтернативы над другой, и взвешенную структуру, когда результат сравнения отражает не только факт, но и силу превосходства, которая оценивается некоторым весом. Симметричные элементы матрицы парных сравнений a_ij и a_ji должны выбираться равными, если соответствующие альтернативы равноценны или не сравнимы; если же x_ix_j, то a_ij > a_ji. Кроме этих очевидных условий, на элементы матрицы А накладываются дополнительные калибровочные ограничения, однозначно связывающие симметричные элементы a_ij и a_ji. Рассмотрим основные типы таких калибровок.

Простая калибровка (П):

(ij)

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

Турнирная калибровка (Т):



где a_ij - число очков, набранных игроком x_i во всех встречах с игроком x_j, а с - число таких встреч.

Степенная калибровка (С):

где а_ij означает, что альтернатива x_i превосходит альтернативу x_j в a_ij раз.

Кососимметрическая калибровка (К):

означает, что альтернатива x_i превосходит в парном сравнении x_j на a_ij.

Вероятностная калибровка (В):

где a_ij - вероятность превосходства x_i над x_j.

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

Рис. 2.1.

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

Таблица 2.1

Значение	Определение	Комментарий
1	Равноценность	Обе альтернативы одинаково предпочтительны.
3	Слабое превосходство	Эксперт отдает некоторое предпоч-тение первой альтернативе в паре.
5	Сильное превосходство	Эксперт определенно считает первую альтернативу редпочтительнее второй.
7	Явное превосходство	Первая альтернатива явно предпочтительнее второй, и опыт это подтверждает.
9	Абсолютное превосходство	Превосходство первой альтернативы не вызывает никаких сомнений.
2, 4, 6, 8	Значения, соответствующие промежуточным суждениям	Для случаев, когда выбор между соседними значениями основной шкалы затруднителен.

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

Современные системы поддержки принятия решений, как правило, ориентированы на активное использование экспертной информации. Простейшим способом ее получения является учет мнения одного специалиста. Однако при подготовке ответственных решений принято опираться на суждения не отдельного эксперта, а экспертной группы, в состав которой включаются специалисты различных направлений, что обеспечивает возможность разностороннего анализа альтернативных вариантов решений. Коллективное (или групповое) решение считается более обоснованным, чем индивидуальное. Важной практической задачей является формирование экспертной группы, членами которой могут быть только квалифицированные специалисты, хорошо знакомые с предметной областью, где проводится экспертиза, способные объективно оценивать ситуацию принятия решений. Кроме того, эксперты, включенные в группу, должны быть психологически совместимыми, в противном случае истинной причиной их разногласий может оказаться не сложность проблемы, а непонимание экспертами друг друга, связанное с различными способами восприятия и оценки ими информации. Качество эксперта оценивается с помощью коэффициента компетентности С_k, где k - номер эксперта, , m - число экспертов в группе. С_k представляет собой относительную характеристику, позволяющую сравнивать уровень компетентности данного эксперта с такими же показателями других членов экспертной группы. Будем считать, что для любого k С_k [0,1] и =1.

Рассмотрим некоторые подходы к определению коэффициентов компетентности экспертов. Существующие методы можно условно разделить на прямые и косвенные. Прямые методы основаны на непосредственном измерении этого свойства, косвенные базируются на анализе результатов экспертного опроса. Пусть Е = {E₁, …, E_m} - группа экспертов. Для получения исходной информации можно использовать одну из процедур:1) каждый эксперт оценивает компетентность всех членов группы и свою собственную, используя некоторую шкалу - числовую или лингвистическую, при этом понятие компетентности может быть конкретизировано целым набором показателей;2) поскольку компетентность - это качественный признак, то целесообразно использовать стандартный подход - парное сравнение, когда каждым экспертом формирует матрицу парных сравнений, устанавливая предпочтительность или равноценность в каждой паре других членов экспертной группы.

Заметим, что во втором случае вводить систему показателей, конкретизирующих понятие компетентности, не обязательно. Более того, каждый эксперт может истолковывать это понятие по-своему. От матрицы парных сравнений можно перейти к графу парных сравнений, который содержит столько вершин, сколько экспертов в группе (то есть m), причем от вершины E_i ведет дуга к вершине E_j, если данный эксперт считает, что эксперт E_i более компетентен в данной области, чем эксперт E_j. Если равноценных экспертов не существует в высказываниях данного эксперта, то граф парных сравнений представляет собой турнир - полный ориентированный граф.

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

Важнейшими проблемами при таком подходе являются:

1) формирование системы показателей, конкретизирующих понятие компетентности;

2) определение системы приоритетов на множестве этих показателей;

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

4) выбор оператора агрегирования для получения обобщенной оценки.

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

2.2 Формирование множества недоминируемых альтернатив

Обратимся теперь к задаче рационального выбора альтернатив из множества X, на котором задано нечеткое отношение предпочтения с функцией предпочтения _R: XX [0, 1].

Пусть X - обычное множество альтернатив и R - заданное на нем нечеткое отношение нестрогого предпочтения. Пусть, кроме того, R^s - соответствующее R нечеткое отношение строгого предпочтения. Поскольку исходное отношение предпочтения - нечеткое, то естественно ожидать, что соответствующее подмножество недоминируемых альтернатив окажется нечетким.

Согласно определению отношения _R^s, для любых альтернатив x, y X величина _R^s(x, y) есть степень, с которой альтернатива x доминирует над альтернативой y. Следовательно, при фиксированном y X функцию _R^s(y, x) можно рассматривать как функцию принадлежности нечеткого множества альтернатив x над которыми строго доминирует альтернатива y. Множество «всех» альтернатив x, которые не доминируются альтернативой y, представляют собой дополнение в X введенного множества _R^s(y, x). Согласно определению дополнения получаем, что это новое нечеткое множество описывается функцией принадлежности вида

(1- _R^s (y, x)) (2.1)



Для выделения в X подмножества «всех» альтернатив, каждая из которых не доминируется ни одной альтернативой из X, нужно взять пересечение нечетких множеств вида (2.1) по всем y X. Это пересечение мы и назовем нечетким подмножеством недоминируемых альтернатив и обозначим его _R^н.д.(x). Согласно классическому определению пересечения нечетких множеств, получаем следующее выражение для функции принадлежности этого множества

Применяя закон де Моргана данное определение можно заменить иначе

(2.2)

Значение _R^н.д.(x) представляет собой степень, с которой альтернатива x не доминируется ни одной из других альтернатив множества X. Важно, что если _R^н.д.(x⁰) = для некоторой альтернативы x⁰, x⁰ может доминироваться другими альтернативами, но со степенью не выше 1-.

Пользуясь определением нечеткого отношения _R^s, нетрудно показать, что

,

тогда множество недоминируемых альтернатив описывается функцией принадлежности вида



Это выражение можно рассматривать как способ обработки нечеткой информации, заданной в форме полно R для выделения в X подмножества недоминируемых альтернатив.

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

Определение 1. Множество альтернатив с максимальной степенью недоминирования образует множество недоминируемых альтернатив.

X ^н.д. = {xx X, _R^н.д. (x) = sup _R^н.д. (z)}

zX

а его элементы называются максимальными недоминируемыми альтернативами множества.

Пример. Пусть в конечном множестве X = {x₁, x₂, x₃, x₄} задано вида

R	x1	x2	x3	x4
x1	1	0.2	0.3	0.1
x2	0.5	1	0.2	0.6
x3	0.1	0.6	1	0.3
x4	0.6	0.1	0.5	1

Пользуясь введенными выше определениями, получаем

Rs	x1	x2	x3	x4
x1	0	0	0.2	0
x2	0.3	0	0	0.5
x3	0	0.4	0	0
x4	0.5	0	0.2	0
x1	x2	x3	x4
0.5	0.6	0.8	0.5

Отсюда видно, что наибольшую степень недоминируемости, равную 0.8, имеет альтернатива x₃, поэтому выбор ее в качестве решения следует считать рациональным в рамках рассматриваемого подхода.

2.3 Алгоритм выбора лучшей альтернативы на основе степеней доминирования-недоминирования

Рассмотрим следующую задачу. Пусть задано множество альтернатив X и каждая альтернатива характеризуется несколькими признаками с номерами j = 1,…,m. Информация о попарном сравнении альтернатив по каждому из признаков j представлена в форме отношения предпочтения Rj. Таким образом, имеется m отношений предпочтения Rj на множестве X, причем заданы коэффициенты j относительной важности этих отношений, , j [0,1]. Задача заключается в том, чтобы выбрать лучшую альтернативу из множества X.

Для решения данной задачи используется следующий алгоритм:

1. Построить нечеткое отношение Q1, как пересечение исходных отношений

(_Q1(x, y) = min {₁(x, y),… _m(x, y)})

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



3. Построить нечеткое отношение Q2 как выпуклую комбинацию исходных нечетных отношений предпочтения

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

5. Найти пересечение нечетких множеств Q₁^н.д и Q₂^н.д, считая функцию принадлежности по формуле.

^н.д.(x) = min { _Q1^н.д.(x), _Q2^н.д. (x)}.

6. Определить множество X ^н.д.

X ^н.д = {xx X, ^н.д (x) = sup ^н.д (x)}.

7. Рекомендуется рациональным считать выбор альтернатив из множества X ^н.д..

Следует отметить, что в зависимости от типа задачи рациональным могут считаться выборы не только альтернатив из множества X^н.д, но и в том или ином смысле слабо доминируемых альтернатив (или не очень сильно недоминируемых), т.е. альтернатив, которые принадлежат множеству X^н.д со степенью не ниже некоторой заданной.

Пример. Пусть X = {x₁, x₂, x₃} и на X заданы три одинаково важных отношения предпочтения:

R1	x1	x2	x3
x1	1	1	0
x2	1	1	0
x3	0	0	1

R2	x1	x2	x3
x1	1	1	1
x2	0	1	1
x3	0	0	1

R3	x1	x2	x3
x1	1	1	0
x2	1	1	0
x3	1	0	1

Строим отношение Q1 = R1R2R3:

Q1	x1	x2	x3
x1	1	1	0
x2	0	1	0
x3	0	0	1

и находим подмножество недоминируемых альтернатив:

x1	x2	x3
1	0	1

Строим отношение Q₂ = 1/3 (₁(xi, xj) + ₂ (xi, xj) + ₃(xi, xj)):

Q2	x1	x2	x3
x1	1	1	1/3
x2	2/3	1	2/3
x3	1/3	0	1



и находим подмножество недоминируемых альтернатив в множестве:

x1	x2	x3
1	2/3	1/3

Результирующее множество недоминируемых альтернатив есть пересечение множеств Q1 ^н.д. и Q2 ^н.д.:

x1	x2	x3
1	0	1/3

Отсюда заключаем, что в данном примере рациональным следует считать выбор альтернативы x₁, имеющей максимальную степень недоминируемости.



Глава 3. Мультипликативная модель группового выбора

3.1 Мультипликативное отношение предпочтения

Определение 1. Нечеткое отношение предпочтения , называется мультипликативным отношением предпочтения, если его элементы удовлетворяют условию . Заметим, что мультипликативное отношение предпочтения можно получить, используя шкалу Саати. В этом случае .

Определение 2. Нечеткое отношение предпочтения называется аддитивным отношением предпочтения, если его элементы удовлетворяю условию .

Пусть в результате экспертного опроса каждым экспертом E_k представлено мультипликативное отношение предпочтения на множестве альтернатив X(|x|=n). Если в опросе участвуют m экспертов, то получим n мультипликативных отношений предпочтения .

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

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

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

Функцию f можно представить с помощью некоторой функции h, , причем

Заметим, что при x=1 мы имеем , откуда . При , получаем ,

Известно, что общее решение функционального уравнения вида

задается в функцией:

Таким образом, используя данный результат, получаем, что

.

Так как и , то .

Подведя итоги, сформулируем следующее:

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



3.2 Агрегирование отношений предпочтения

3.2.1 Арифметические порядковые операторы агрегирования

Под агрегированием понимается переход от вектора агрегированных значений к скалярной величине путем использования специальных операторов агрегирования. В основе каждого оператора агрегирования лежит совокупность свойств процедуры агрегирования, среди которых важное место отводится стратегии агрегирования. Различают дизъюнктивную, конъюнктивную и компромиссную стратегии. При формировании коллективного отношения предпочтения дизъюнктивной стратегии отвечают операторы объединения нечетких отношений (например, классическое объединение в виде max, алгебраическая сумма и др.). Конъюнктивная стратегия реализуется операциями пересечения (например, min, алгебраическое произведение, и др.). Компромиссным стратегиям соответствуют операторы осреднения (квазиарифметические, геометрические, гармонические средние). Выбор оператора агрегирования - сложная проблема. Однако в настоящее время существует множество подходов к ее решению. Пусть a=(a₁,…,a_n) - набор агрегируемых величин (агрегатов); u=(u₁,…,u_n) - набор весовых коэффициентов, позволяющих учитывать значимость агрегатов.

Определение 3. Арифметический порядковый оператор взвешенного агрегирования (OWA - оператор), ассоциированный с вектором w (w_i [0,1], и ), есть отображение

F: [0, 1]ⁿ⁺¹ [0, 1],

F(W, A) = ,



где В = (b₁,..., b_n) - вектор, полученный из А = (a₁,...,a_n) упорядочением элементов по невозрастанию.

Пример. Пусть W = (0.3, 0.5, 0.1, 0.0) и А = (0.4, 0.9, 0.7, 1.0), тогда

В = (1, 0.9, 0.7, 0.4) и F(W,A) = 0.3 1 + 0.50.9 + 0.10.7 + 00.4 = 0.82.

К основным свойствам OWA-оператора относятся коммутативность, монотонность, идемпотентность.

Различные OWA-операторы отличаются друг от друга наборами весов...