Бинарные отношения. 
Теория принятия решений

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

Определение.

Бинарным отношением () на множестве X называется подмножество декартова произведения <2 с Хх X.

Говорят, что элементы х, у е X находятся в отношении ?), если (х, у) е (), при этом пишут хОу.

Обратите внимание!

Отношения вводятся на некотором заранее заданном множестве X, которое называется множеством задания отношения.

Пример задания бинарного отношения. Пусть множество задания отношения представляет собой множество вещественных чисел, X = 9?. Зададим бинарное отношение Q следующим образом: числа х, у е ^ЧЛ находятся в отношении Q (xQy), если для них верно равенство х² + у² = 1. Тогда можно утверждать, что два произвольных числа х, у е находятся в отношении Q, если точка с координатами (х, у) лежит на окружности радиуса 1 с центром в начале координат.

Пример построения бинарного отношения (*): рассмотрим учебную группу студентов четвертого курса. На множестве Н величин, равных росту студентов, можно ввести, например, следующие отношения: Q_x = «больше», Q₂ = «равны», <2₃ = «не больше». Тогда для двух студентов Петрова, имеющего рост h_x = 180 см, и Семенова, имеющего рост h₂= 178 см, можно записать: h_xQ_xh₂ (Петров выше Семенова) и h., QJi_x (Семенов не выше Петрова). При этом элементы /г, и /г₂ не находятся в отношении Q₂.

На множестве В величии, равных среднему баллу студентов, тоже можно ввести отношения: Q, = «больше», Q₂ = «равны», <2₃ = «не больше». Тогда, если средние баллы Петрова и Семенова составляют 6, = 4,55 и Ь₂ = 4,55 соответственно, то можно записать: b_xQ₂b₂ и Ь^Ь₂.

Заметим, что утверждение «рост Петрова больше среднего балла Семенова» не имеет смысла. Кроме того, обозначив через G — множество студентов группы, можно ввести отношения 0 = «родственники» или ()₅ = «средний балл больше». Тогда студенты Петров и Семенов будут находиться в отношении 0, если являются родственниками. Если средний балл Петрова равен 4,55, а Иванова — 4,3, то Петров и Иванов находятся в отношении Петров 0₅ Иванов.

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

• 1. Полнота. Говорят, что отношение <2, заданное на множестве X, является полным, если для любой пары элементов х, у е X либо х (Уу, либо у Ох.
• 2. Симметричность. Говорят, что отношение (2, заданное на множестве X, является симметричным, если для пары элементов х, уеХ из х (Ху следует уОх (из того, что х находится в отношении <2 к г/ следует, что у находится в отношении 0 к х).
• 3. Антисимметричность. Говорят, что отношение <2, заданное на множестве Х_у является антисимметричным, если из того, что хОу и у Ох следует, что х = у у т. е. х и у — это один и тот же элемент множества X.
• 4. Рефлексивность. Говорят, что отношение 0, заданное на множестве X, является рефлексивным, если хОх для всякого х е X.
• 5. Иррефлексивность (антирефрексивность). Говорят, что отношение О, заданное на множестве X, является иррефлексивным, если для всякого х е X не выполнено хОх.
• 6. Транзитивность. Говорят, что отношение <2, заданное на множестве X, является транзитивным, если из того, что х (Уу и уОг_у следует хОг.
• 7. Ацикличность. Говорят, что отношение 0, заданное на множестве X,

является ацикличным, если для любых элементов х, у у г₂,…, г_п е X, где п —

произвольное натуральное число, для которых хОг₁₉ 2₁0г₂, …, г_п0У> верно, что х ^ у.

В примере (*) отношение (2₁ обладает свойствами транзитивности и ацикличности, отношение 0₂ обладает свойствами симметричности, рефлексивности и транзитивности, <2₃ — свойствами полноты, антисимметричности, рефлексивности и транзитивности.

Заметим, что отношения (2, и (2₂, заданные на множестве средних баллов студентов в примере (*), принципиально отличаются тем, что первое отношение позволяет упорядочить студентов по среднему баллу, а второе разбивает студентов на некоторые классы успеваемости. Таким образом, имеем два вида отношений: эквивалентности и порядка. Остановимся более подробно на каждом из них.

Определение Рефлексивное симметричное и транзитивное отношение 0 на множестве X называется отношением эквивалентности (безразличия). Для такого отношения вводят специальное обозначение х ~ у у х, у е X.

Примерами отношения эквивалентности являются отношения равенства или нестрогого неравенства, заданные на множестве вещественных чисел 5Я.

Отношение эквивалентности делит множество задания отношения на непересекающиеся классы, называемые классами {множествами) эквивалентности. Тогда классом эквивалентности для элемента х е X будет множество

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

Пример классов эквивалентности. Для группы студентов, описанной в примере (*), введем отношение = «одинаковый средний балл», которое является отношением эквивалентности. Тогда студент Семенов входит в множество эквивалентности студента Петрова и наоборот. При этом студенты Петров и Иванов не находятся в отношении 0₆. В данном случае студенты группы будут разбиты на классы эквивалентности, в каждом из которых будут студенты, имеющие одинаковый средний балл.

Определение Полное, рефлексивное антисимметричное и транзитивное отношение <2 на множестве X называется отношением (слабого) предпочтения, обозначается х > у, х_} у е X. При этом говорят, что х не хуже, чем (не менее предпочтителен, чем) у.

Примером отношения слабого предпочтения может быть отношение частичного порядка > (или <), заданное на множестве вещественных чисел.

Определение Иррефлексивное и транзитивное отношение () на множестве X называется отношением строгого предпочтения или отношением порядка, обозначается х> у_у х, у € X. При этом говорят, что х лучше (предпочтительнее) у.

Отношение строгого предпочтения можно задать с помощью отношения слабого предпочтения следующим образом

Обратите внимание!

Отношение строгого предпочтения не является и полным.

Примером отношения строгого предпочтения может быть отношение порядка > (или <), заданное на множестве вещественных чисел.

Пример отношений «меньше», «больше». В магазине продается три набора конфет: «Сладкие ночи» за 200 руб., «Золотые зубы» за 450 руб. и «Шоколадные грезы» за 600 руб. Пенсионерка Мария Петровна хочет выбрать для себя самые дешевые конфеты, а частный предприниматель Оксана Николаевна — самые дорогие. Тогда для Марии Петровны отношения предпочтения будут иметь следующий вид: 200 > 450, 450 > 600. Для Оксаны Николаевны отношение предпочтения будут следующими: 600 > 450, 450 > 200. Таким образом, для пенсионерки отношение предпочтения есть отношение порядка «меньше» ().

Отношение слабого предпочтения, заданное на множестве X, порождает отношение эквивалентности на X следующим образом:

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

Определение Предположим, что на некотором множестве X заданы отношение > или отношения > и ~. Предпочтительным множеством элемента х е X называется множество, состоящее из наборов элементов, которые более предпочтительны или безразличны заданному элементу х:

где знак V означает логическое ИЛИ.

Непредпочтительным множеством элементах € X называется множество, состоящее из наборов элементов, которые менее предпочтительны или безразличны заданному элементу х.

Пример графического представления отношения на множестве. Предположим, что множество задания отношения представляет собой квадрат со стороной, равной 1: Х= [0,1] х [0,1 ]. Отношения предпочтения и эквивалентности на X заданы следующим образом: для х = (х_{, х₂), у = (г/_р у₂) е X

верно х>у тогда и только тогда, когда х + х₂ > у] + у, и х~у тогда и только тогда, когда Тогда для элемента предпочтительным множеством Г* будет заштрихованная область, представленная на рис. 7.1, включая часть окружности с радиусом 1 /л/2, на которой и находится точка х, а непредпочтительным множеством Г_т будет оставшаяся незаштрихованная область, включая часть окружности с точкой х.

Использование бинарных отношений является удобным способом выявления предпочтений ЛПР в решаемой ЗПР, поскольку позволяет использовать такие понятия, как «хуже», «лучше», «не хуже», «одинаковые» и др. для сравнения имеющихся альтернатив. При этом выявление предпо;

Рис. 7.1. Предпочтительное и непредпочтительное множества чтений ЛПР с помощью бинарных отношений обладает следующими хара ктеристи кам и:

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

Недостатками метода бинарных отношений можно назвать его трудоемкость: для попарного сравнения п альтернатив требуется п (п — 1)/2 операций, а также невозможность анализа отдельно взятой альтернативы без сравнения ее с другими. Кроме того, не всякое отношение предпочтения может проявлять свойство ацикличности. Так, в детской игре «камень, ножницы, бумага» известно, что камень лучше ножниц, ножницы лучше бумаги, а бумага лучше камня, и выбрать наилучшую из трех альтернатив уже невозможно.

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