Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ALGORITHM TO ENHANCE THE COHERENCE OF PAIRED COMPARISONS MATRIX WHEN CARRYING OUT EXPERT SURVEYS

Lomakin V.V. 1 Lifirenko M.V. 1
1 National Research Belgorod State University
The algorithm execution process to enhance the coherence matrix of pairwise comparisons in the implementation of the expert survey. Its use simplifies the decision-making procedure and expands its scope. Based on the matrix of pairwise comparisons matrix of cosines of the angles between the vectors of paired comparisons is built defining pairs and overall consistency of judgments. Introduced functional consistency, minimization of which corresponds to the production of more coherent matrix of pairwise comparisons. An experimental study of the dependence of the proposed functional and consistency, showing a relationship between them. The algorithm for automatic adjustment of the matrix of pairwise comparisons to enhance the coherence of judgments was built. Stepwise procedure is presented to enhance the coherence of the matrix of pairwise comparisons. The proposed approach is used in the software developed by the authors and allows you to correct logical errors in judgment expert.
decision-making
pairwise comparisons
coherence of paired comparisons matrix
processing expert data
1. Zhiljakov, E.G., Igrunova S.V., Devicyna S.N., Putivceva N.P., Medinceva S.V., Chashin Ju.G. Ob ispol’zovanii metoda parnyh sravnenij dlja prinjatija reshenij pri ocenivanii urovnja professional’nyh kompetencij obuchaemyh. – Nauchnye vedomosti BelGU, 2010, no.10, pp. 65–73.
2. Lifirenko M.V. Vserossijskij konkurs NIR studentov i aspirantov v oblasti informatiki i informacionnyh tehnologij «Programmnoe obespechenie podderzhki prinjatija reshenij na osnove ball’noj shkaly ocenki al’ternativ» Belgorod, 2012, no.2, pp. 526–536.
3. Lifirenko M.V., Lomakin V.V. Sistema podderzhki prinjatija upravlencheskih reshenij na osnove usovershenstvovannogo analitiko-ierarhicheskogo processa – Svidetel’stvo o gosudarstvennoj registracii programmy dlja JeVM № 2013616249.
4. Saati T. «Prinjatie reshenij. Metod analiza ierarhij». M.: Radio i svjaz’, 1993. 278 p.
5. Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, no.1, pp. 48–50.

При применении методов парных сравнений [1], в частности, метода анализа иерархий (МАИ) [4], одним из ключевых этапов процесса принятия решения является проверка на согласованность матрицы парных сравнений. В МАИ рекомендуется, чтобы отношение согласованности (ОС) матрицы не превышало 10 % [4]. В случае если положение не выдерживается, может оказаться, что полученные векторные оценки, характеризующие интенсивность свойств сравниваемых элементов, могут значительно отличаться от значений, полученных в результате идеального эксперимента.

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

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

Рассмотрим матрицу парных сравнений А:

lomak01.wmf (1)

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

Тогда строки матрицы А можно рассматривать как векторы lomak03.wmf, и в случае абсолютно согласованной матрицы они должны быть параллельны друг другу lomak04.wmf lomak05.wmf. Как видно, снижение зависимости элементов матрицы и соответственно увеличение угла между векторами из элементов строк матрицы говорит о том, что согласованность матрицы также снижается, и наоборот. Таким образом, рассчитывая косинус угла между векторами, определяется, насколько матрица парных сравнений согласованна.

Воспользуемся формулой расчета косинуса угла между векторами (2):

lomak06.wmf (2)

где lomak07.wmf – скалярное произведение векторов x и y.

Тогда выражение (2) для нахождения косинуса угла между векторами применительно для матрицы парных сравнений A (1) можно записать следующим образом:

lomak08.wmf (3)

Таким образом, на основании формулы (3) и расчета косинуса угла между векторами парных сравнений для каждого парного сравнения получаем матрицу:

lomak09.wmf (4)

Главная диагональ матрицы α единичная, так как косинус угла в этих элементах определяется для двух одинаковых векторов, остальные элементы матрицы соответствуют неравенству: 0 ≤ αij ≤ 1. По матрице α можно оценить степень согласованности каждого парного сравнения по отношению к остальным. При этом наиболее низкие значения косинуса угла указывают на парное сравнение, которое наименее согласовано с остальными.

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

lomak10.wmf (5)

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

Проведем исследование соответствия значений функционала F и значений ОС на примере матриц различных размерностей. На рис. 1 представлен график зависимости функционала (5) от ОС, а также его аппроксимации.

Эксперименты проводились для случайно заполненных 500 матриц парных сравнений для каждой размерности от 3 до 10, рассчитанные для матриц размера 6 на 6, где на вертикальной оси отложены значения функционала, а на горизонтальной оси ОС. Как видно, на графике прослеживается связь между этими величинами. Корреляция этих характеристик равна 0,7559, что также говорит об их высокой взаимосвязи.

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

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

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

lomak12.wmf (6)

pic_10.tif

Рис. 1. Исследование взаимосвязи введенного функционала и ОС на случайно заполненных матрицах размера 6 на 6

Отсюда следует, что из сравнений одних элементов можно получить сравнения этих элементов с другими.

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

Построим алгоритм корректировки матрицы. Дана матрица парных сравнений R (7):

lomak13.wmf (7)

Необходимо путем изменений исходной матрицы R, имеющей высокий ОС более 10 %, получить такую R′, которая бы имела OС менее 10 %.

Определим Парето-оптимальные сравнения по рассчитанному косинусу угла α для построения новой матрицы R′. Для анализа неточностей эксперта в матрице парных сравнений на каждом шаге алгоритма определяется матрица косинусов углов α (5). Затем по матрице α определяются Парето-оптимальные сравнения, которые имеют наибольшие косинусы углов, и при этом они достаточны для нахождения других элементов матрицы парных сравнений. Далее по Парето-оптимальным сравнениям необходимо будет достроить матрицу.

Для определения Парето-оптимальных сравнений воспользуемся теорией графов. Построим граф G (8):

G = <V, E>, (8)

где V = {v1, v2, …, vn} – множество вершин, состоящих из элементов сравнения; E = {e1, e2, …, em} – множество ребер, характеризующих наличие сравнительной оценки для элементов, связанных вершин этим ребром; n – количество элементов сравнения; m – количество сравнений, равное lomak14.wmf, если сравнение произведено для всех парами элементов.

Также необходимо определить множество S, которое являются отображением превосходящих сравнительных оценок на множество ребер E соответственно:

S = {s1, s2, …, sm}. (9)

Также каждому ребру назначается вес равный косинусу угла из матрицы α. Это описывается множеством W, которое является отображением множества косинуса углов на множество ребер:

W = {w1, w2, …, wm}. (10)

Необходимо условиться, что граф G (8) ориентированный и направление ребер указывает на превосходство одного элемента над другим.

Тогда для поиска Парето-оптимальных сравнений можно воспользоваться алгоритмом нахождения максимального остовного графа взвешенного связного неориентированного графа, используя алгоритм Крускала [5]. Поиск ведется на неориентированном графе, так как в данном случае учет превосходства одного элемента над другим не важен.

Дополнение остовного графа осуществляется путем перебора всех пар вершин остовного графа, которые не имеют прямой связи, и нахождения для этих пар соответствующего значений и определения новых оценок lomak15.wmf. Значение сравнительной оценки lomak16.wmf получается перемещением по маршруту остовного графа, связывающего вершины рассматриваемой пары и перемножением сравнительных оценок. Если движение происходит против направления ребра, то берется обратная величина сравнительной оценки. Таким образом, поскольку при расчете сравнительных оценок используется свойство абсолютно согласованной матрицы, то полученному S′ будет соответствовать новое множество W′(10), у которого все элементы единичны.

При получении множества сравнительных оценок S′ на этапе согласования оценок часто наступает ситуация, когда новые оценки не вписываются в диапазон используемой нами шкалы. Например, оценка lomak17.wmf соответствует тому, что элемент 1 значительно превосходит элемент 2, а оценка lomak18.wmf соответствует тому, что элемент 2 умеренно превосходит элемент 3. Тогда математически будет верно, что превосходство элемента 1 над элементом 3 будет lomak19.wmf. Как видно, при применении шкалы МАИ lomak20.wmf выходит за рамки допустимых оценок (максимальная оценка 9). В связи с этим необходимо осуществить перевод оценок S′ в оценки S″, соответствующие применяемой шкале. Для перевода можно предложить формулу соответствия шага по новой шкале к шагу по принятой шкале:

lomak21.wmf (11)

где max S′ – максимальная сравнительная оценка в множестве оценок S′, которая определяет верхнюю границу рассчитанных оценок, а max S″ – максимальная сравнительная оценка в множестве оценок S″ применяемой шкалы.

Таким образом, далее можно построить таблицу соответствия одной шкалы другой и затем получить c помощью неё S″ по S′. Например, для стандарта из шкалы МАИ 3 будут соответствовать оценки, лежащие в диапазоне от 1 + h до 1 + 2h, а для единицы (равенство двух сравниваемых объектов) соответствует также единица из другой шкалы.

Получив S″ c оценками, соответствующими применяемой шкале, заполняется матрица R″. Согласованность новой матрицы R″ проверяется вычислением ОС и функционала (6).

Таким образом, процесс повышения степени согласованности матрицы парных сравнений состоит из 4 этапов (рис. 2):

1. Построение по исходной матрице парных сравнений графа G (8).

2. Поиск максимального остовного подграфа в графе G (8).

3. Дополнение остовного графа до полного графа.

4. Приведение полученных оценок к оценкам по применяемой шкале.

Приведем пример расчета по полученному алгоритму для матрицы с оценками по шкале МАИ от 1 до 9. Процесс повышения согласованности для рассматриваемого случая представлен на рис. 3.

Дана матрица R (12):

lomak23.wmf (12)

Приоритеты матрицы R (12):

P = (0,475 0,238 0,1 0,081 0,105). (13)

Степень согласованности матрицы R (12) определяется коэффициентом ОС = 18,6 %.

Матрица косинусов углов для R:

lomak24.wmf

pic_11.wmf

Рис. 2. Процесс повышения степени согласованности матрицы парных сравнений

На основе полученного α в соответствии с алгоритмом строится граф G и находится максимальный остовной подграф.

Как видно, из полученного остовного графа на рис. 3 можно построить матрицу, где знаками вопроса обозначены сравнения, которые на данном этапе ещё неизвестны и их необходимо рассчитать по наиболее достоверным суждениям эксперта:

lomak25.wmf

Пройдя все этапы алгоритма, получим итоговую матрицу парных сравнений R″:

lomak26.wmf (14)

Рассчитаем ОС и новые приоритеты элементов сравнения по R″:

ОС = 1,3 %,

P = (0,469 0,193 0,064 0,080 0,193)).

Таким образом, ОС снизился с 18,6 до 1,3 %, при этом наилучшая альтернатива не изменилась, а ранжирование элементов сравнений поменялось.

pic_12.wmf

Рис. 3. Процесс повышения согласованности матрицы парных сравнений на примере

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

Рецензенты:

Жиляков Е.Г., д.т.н., профессор, зав. кафедрой информационно-телекоммуникационных систем и технологий, НИУ БелГУ, г. Белгород;

Еременко В.Т., д.т.н., профессор, зав. кафедрой электроники, вычислительной техники и информационной безопасности, Госуниверситет – УНПК, г. Орел.

Работа поступила в редакцию 17.01.2014.