Второй способ

Решения , формирующие , предпочтительнее любого решения .

Данная формулировка формализована в виде выражения:

. (2)

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

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

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

А	x1 x3 x2 Рисунок 2 – Виды графовых моделей для определения наилучших (предпочтительных) решений.   а) x1 x3 x4 x7 x5 x6 x8 x2 б)

На Рис. 2а) решения , так как при , и , а также и . На Рис. 2б) решения и являются наилучшими, так как они непосредственно либо транзитивно доминируют все остальные решения.

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

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

А	x1 x3 x2 Рисунок 3 – Виды графовых моделей отношений, для которых не выполняются условия для наилучший решений   а) x1 x3 x4 x7 x5 x2 б) x6

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

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

1) : ( предпочтительнее для всех ), тогда если элемент доминируем, то он не включается в ;

2) решения и эквивалентны ( ~ );

3) решения и не сравнимы.

Реализация третьего условия предполагает, что:

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

б) для пары элементов (где - отношение предпочтения ) выполняется условие и условие , тогда между ними имеются две разнонаправленные стрелки.

Тогда является максимальным элементом в модели если:

.

Первому условию соответствуют решения , на Рис. 3б), второму условию – решения на Рис. 3а).

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

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

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

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

Особенности построения алгоритма формирования множества далее прокомментированы на примерах.

Пример 4. Вид графа и матрицы отношения (Рис. 4).

x4 x3 x5 x1 x2

Рисунок 4 – Вид графовой модели и матрицы отношений, для которых формируется множество

Матрица отображает непосредственное (не транзитивное) предпочтение решения над решением .

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

Для рассматриваемого примера синтаксис определения состава множества (в рассмотрение введен массив ) имеет следующий вид:

Цикл i=1 до 5

MaxR[i]=1;

Цикл j=1 до 5

Цикл i=1 до 5

Если a[i,j]=1 то

MaxR[j]=0;

Пример 5. Вид графа и матрицы парных сравнений для отношения (Рисунок 5).

x4

x3

x5

x1

x2

Рисунок 5 – Вид графовой модели и матрицы отношений, для которых формируется множество

Предлагаемый код программы для формирования множества (вектора ) следующий:

Рисунок 6 – Вид графовой модели бинарных отношений, для которых формируется множество

Цикл i=1 до 5

MaxR[i]=1;

Цикл i=1 до 5

Цикл j=1 до 5

Если a[i,j]=1 то

Если a[j,i]=0 то

MaxR[j]=0;

Если (a[j,i]=1)&(MaxR[i]=0) то

MaxR[j]=0;

Подобный синтаксис определения элементов множества (массива ) может быть применен и для вида графа в Примере 6 (Рисунок 6).

Пример 6. Вид графа бинарных отношений для множества решений Х.

x4

x3

x5

x1

x2

Рисунок 6 – Вид графовой модели отношений, для которой формируется множество

Понятно, что в результате должно быть получено множество в виде: . Таким образом условиями включения/не включения элемента в множество являются:

1)

2) если

3) если и и .

Задание. Выполнить проверку применимости приведенного программного кода для графов отношений следующего вида (Рис.7).

x4

x3

x5

x1

x2

x4

x3

x5

x1

x2

а) б)

Рисунок 7– Виды графовых моделей отношений, для которых формируются множества