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

При таком условии альтернативы можно сравнить между собой лишь попарно. Такие попарные сравнения называются бинарными отношениями. Обозначается бинарное отношение (на примере критерия Байеса из нашей таблицы) А1RА2 – альтернатива А1 лучше альтернативы А2.

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

Бинарным отношением на множестве Ω называется произвольное подмножество R множества Ω Х Ω , где Ω Х Ω – это множество всех упорядоченных пар (ai ;aj) , где ai , aj Î Ω . #

Бинарные отношения очень удобно изображать наглядно. Представим четыре стратегии из нашего примера в виде точек на плоскости. Если имеем, что какая-то альтернатива лучше другой, то проведем стрелку от лучшей альтернативы к худшей. На примере критерия Байеса из нашей таблицы имеем А1RА2 , поэтому на плоскости проведем стрелку от точки А1 к точке А2. Аналогичным образом поступим со всеми начальными данными из таблицы. Заметим, что бинарные отношения не исключают отношения элемента с самим собой. На рисунке такое бинарное отношение будет задаваться петлёй со стрелкой. В результате получим следующую картину:

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

Дадим математически точное определение графа.

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

Две вершины, соединенные дугой, называются смежными вершинами. Дуга, соединяющая две вершины, называется инцидентной этим вершинам. Две вершины, соединенные дугой, называются инцидентными этой дуге.

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

1)Максимальным элементом множества Ω по бинарному отношению R называется такой элемент х Î Ω , что "у Î Ω выполняется отношение хRy .

Иначе говоря, максимальный элемент множества должен быть "лучше" каждого элемента этого множества. Не исключается и то, что он может быть "лучше" самого себя, кроме этого максимальный элемент может быть одновременно и "хуже" какого-либо элемента этого множества. Слова "лучше" и "хуже" не совсем верно передают смысл бинарных отношений.

Для графов понятие максимальный элемент – это вершина, из которой исходят стрелки во все остальные вершины графа. Например, на рис. 1 максимальным элементом будет вершина А1 – из неё выходят стрелки во все остальные вершины графа.

2)Оптимальным по Парето элементом множества Ω по бинарному отношению R называется такой элемент х Î Ω , что ù$у Î Ω для которого выполнялось бы отношение уRх .

Иначе говоря, оптимальный по Парето элемент множества – это такой элемент, "лучше" которого в рассматриваемом множестве нет.

Для графов понятие оптимальный по Парето элемент – это вершина, в которую не входит ни одна стрелка. Например, на рис. 1 оптимальным по Парето элементом будет вершина А1 – в неё не входит ни одна стрелка.

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

Рассмотрим несколько примеров.

У графа на рис. 2 максимальным элементом будет вершина А1 – из неё выходят стрелки во все остальные вершины графа. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 3 максимальным элементом будет также вершина А1 – из неё выходят стрелки во все остальные вершины графа. Заметим: то, что в неё входит стрелка из вершины А4 , по определению совершенно не важно. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 4 максимальными элементами будут вершины А1 и А4 – из них выходят стрелки во все остальные вершины графа. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 5 максимального элемента нет. Оптимальными по Парето элементами будут вершины А1 и А4 – в них не входит ни одна стрелка.

Отметим очевидные особенности.

У графа либо нет максимальных элементов, либо есть.

Оптимальными по Парето элементами могут быть несколько вершин графа, либо таковых может не быть.

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

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

Матрица смежности вершин графа – это квадратная матрица размера m x m (m – это количество вершин) с элементами:

сij =

По матрицам смежности искать максимальные элементы и элементы, оптимальные по Парето – одно удовольствие! Максимальные элементы – это те, чьи строки состоят из всех единиц (кроме себя самих – там может быть как нуль, так и единица). А оптимальные по Парето элементы – это те, чьи столбцы состоят из всех нулей.

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

Элементы матрицы инцидентности будут такими:

сij =

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

Налицо также очевидна закономерность: максимальные элементы – это те, чьи строки содержат единиц на одну меньше, чем количество строк (вершин), а оптимальные по Парето элементы – это те, чьи строки не содержат минус единиц.

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