Алгоритм повышения степени согласованности матрицы парных сравнений при проведении экспертных опросов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 891. 2, 004. 896
АЛГОРИТМ ПОВЫШЕНИЯ СТЕПЕНИ СОГЛАСОВАННОСТИ МАТРИЦЫ ПАРНЫХ СРАВНЕНИЙ ПРИ ПРОВЕДЕНИИ ЭКСПЕРТНЫХ ОПРОСОВ Ломакин В. В., Лифиренко М. В.
ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет»,
Белгород, e-mail: lomakin@bsu. edu. ru
Разработан алгоритм исполнения процесса повышения степени согласованности матриц парных сравнений при осуществлении экспертного опроса. Его применение упрощает проведение процедуры принятия решения и расширяет её область применения. На основании матрицы парных сравнений построена матрица косинусов углов между векторами парных сравнений, определяющая попарную и общую согласованность суждений. Введен функционал согласованности, минимизация которого соответствует получению более согласованной матрицы парных сравнений. Проведены экспериментальные исследования зависимости предложенного функционала и отношения согласованности, показавшие наличие взаимосвязи между ними. Построен алгоритм автоматической корректировки матрицы парных сравнений для повышения степени согласованности суждений. Представлена поэтапная процедура повышения степени согласованности матрицы парных сравнений. Предложенный подход используется в разработанном авторами программном обеспечении и позволяет корректировать логические ошибки в суждениях эксперта.
Ключевые слова: принятие решений, парные сравнения, согласованность матрицы парных сравнений, обработка экспертных данных
ALGORITHM TO ENHANCE THE COHERENCE OF PAIRED COMPARISONS MATRIX WHEN CARRYING OUT EXPERT SURVEYS Lomakin V.V., Lifirenko M.V.
National Research Belgorod State University, Belgorod, e-mail: lomakin@bsu. edu. ru
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.
Keywords: decision-making, pairwise comparisons, coherence of paired comparisons matrix, processing expert data
При применении методов парных сравнений [1], в частности, метода анализа иерархий (МАИ) [4], одним из ключевых этапов процесса принятия решения является проверка на согласованность матрицы парных сравнений. В МАИ рекомендуется, чтобы отношение согласованности (ОС) матрицы не превышало 10% [4]. В случае если положение не выдерживается, может оказаться, что полученные векторные оценки, характеризующие интенсивность свойств сравниваемых элементов, могут значительно отличаться от значений, полученных в результате идеального эксперимента.
При практическом использовании методов принятия решений вопросы повышения степени согласованности представляют для лиц, принимающих решение (ЛПР) и экспертов достаточную сложность, так как, несмотря на то, что метод ориентирован на формирование матрицы парных сравнений самим человеком, с другой стороны, существуют рекомендации о соответствии параметров согласованности.
В данной статье предлагается метод для выявления и автоматической корректировки суждений, влияющих на низкую согласованность парных сравнений, которые мы условно будем называть ошибочными. Разрабатываемый подход позволит ускорить процесс принятия решений и увеличить долю автоматизации в принятии решений.
Рассмотрим матрицу парных сравнений А: /
А =
і
ай
а
п!
а.
V
а
а
т
а,

а, —
(1)
V /
Для определения согласованности матрицы воспользуемся свойством абсолютно согласованной матрицы, говорящим, что в абсолютно согласованной матрице элементы жестко связаны, и между эле-
ментами матрицы выполняется свойство а.
— = const
для всех j.
Тогда строки матрицы, А можно рассматривать как векторы аі=(ап аі2 … аіпУ
и в случае абсолютно согласованной матрицы они должны быть параллельны друг
другу at || a., (cos (Z. ai = l). Как видно,
снижение зависимости элементов матрицы и соответственно увеличение угла между векторами из элементов строк матрицы говорит о том, что согласованность матрицы также снижается, и наоборот. Таким образом, рассчитывая косинус угла между векторами, определяется, насколько матрица парных сравнений согласованна.
Воспользуемся формулой расчета косинуса угла между векторами (2):
х, у
& gt-/(*'*)¦
У, У
(2)
где Х& gt-У/ - скалярное произведение векторов X и у.
Тогда выражение (2) для нахождения косинуса угла между векторами применительно для матрицы парных сравнений, А (1) можно записать следующим образом:
(3)
ҐУ — п 2, аік к=1 ¦ajk
У І к=1 к=1
Таким образом, на основании формулы (3) и расчета косинуса угла между векторами парных сравнений для каждого парного сравнения получаем матрицу:
а =
1
а
12
а
In
а
21
а
2 п
а
V
ЛІ
а
'л 2
1
(4)
/
Главная диагональ матрицы, а единичная, так как косинус угла в этих элементах определяется для двух одинаковых векторов, остальные элементы матрицы соответствуют неравенству: 0 & lt- а & lt- 1. По матрице, а можно оценить степень согласованности каждого парного сравнения по отношению к остальным. При этом наиболее низкие значения косинуса угла указывают на парное сравнение, которое наименее согласовано с остальными.
Кроме того, по матрице, а также можно определить общую степень согласованности матрицы A. Для этого необходимо найти среднее значение косинуса угла в матрице, а и затем его отклонение от абсолютно согласованной матрицы, где среднее значение косинуса угла принимает 1. Исходя из этого, вводится функционал и мера согласованности в виде:
П П
224
F (a) = l-^!-. (5)
п
Минимизация функционала (5) при ограничении, что оценки соответствуют применяемой шкале, приводит к получению более согласованной матрицы парных сравнений и более логически корректного управленческого решения.
Проведем исследование соответствия значений функционала F и значений ОС на примере матриц различных размерностей. На рис. 1 представлен график зависимости функционала (5) от ОС, а также его аппроксимации.
Эксперименты проводились для случайно заполненных 500 матриц парных сравнений для каждой размерности от 3 до 10, рассчитанные для матриц размера 6 на 6, где на вертикальной оси отложены значения функционала, а на горизонтальной оси ОС. Как видно, на графике прослеживается связь между этими величинами. Корреляция этих характеристик равна 0,7559, что также говорит об их высокой взаимосвязи.
Таким образом, можно сделать вывод, что возможно использовать матрицу, а для оценки степени согласованности. По полученному значению функционала (5) можно судить о согласованности матрицы, при этом возможно оценить влияние на согласованность отдельных элементов. Предложенная мера согласованности выгодно отличается от ОС тем, что при расчетах точно указывает на наиболее отклоняющиеся оценки в матрице парных сравнений.
При сравнении большого количества критериев или альтернатив достаточно сложно добиться согласованности матрицы сравнения. Предлагается алгоритм, который способен исправлять наиболее расходящиеся суждения эксперта от других, тем самым снижать функционал (5) и ОС.
Продемонстрируем возможность реализации предлагаемого алгоритма. Так как при абсолютно согласованных оценках должно соблюдаться свойство транзитивности, то должны соблюдаться следующие равенства:
а" а. л& quot-
-Е- = А- -± = В
акк
(6)
— = А-В.
аа
а
кк
Рис. 1. Исследование взаимосвязи введенного функционала и ОС на случайно заполненных
матрицах размера 6 на 6
Отсюда следует, что из сравнений одних элементов можно получить сравнения этих элементов с другими.
С нашей точки зрения рационально корректировать наиболее расходящиеся сравнения с остальными на основе более согласованных друг с другом оценок. Используя предложенный выше подход определения степени согласованности парных сравнений, возможно идентифицировать элементы с минимальными и максимальными значениями косинуса угла. Корректируя первоначальную матрицу, получаем приведенную матрицу, которая имеет лучшую согласованность элементов между друг другом. Таким образом, используя предлагаемый подход, эксперт получает возможность поиска и корректировки неточностей в произведенных оценках.
Построим алгоритм корректировки матрицы. Дана матрица парных сравнений Я (7):
(7)
Необходимо путем изменений исходной матрицы Я, имеющей высокий ОС более 10%, получить такую Я'-, которая бы имела ОС менее 10%.
Определим Парето-оптимальные сравнения по рассчитанному косинусу угла, а для построения новой матрицы Я'-. Для анализа неточностей эксперта в матрице парных сравнений на каждом шаге алгоритма определяется матрица косинусов углов а
аи • • & lt-hj • • а1п '-
R = ап • • ач • • ain
Л • • anj ¦. а ¦ «пп)
(5). Затем по матрице, а определяются Па-рето-оптимальные сравнения, которые
имеют наибольшие косинусы углов, и при этом они достаточны для нахождения других элементов матрицы парных сравнений. Далее по Парето-оптимальным сравнениям необходимо будет достроить матрицу.
Для определения Парето-оптимальных сравнений воспользуемся теорией графов. Построим граф О (8):
G = & lt-V, E& gt-,
(8)
где V = (У1, У2, …, Уп] - множество вершин, состоящих из элементов сравнения- Е = {е1, е2, ., ет} - множество ребер, характеризующих наличие сравнительной оценки для элементов, связанных вершин этим ребром- п — количество элементов сравнения- т — количество сравнений, равное
__И, если сравнение произведено для
2
всех парами элементов.
Также необходимо определить множество S, которое являются отображением превосходящих сравнительных оценок на множество ребер Е соответственно:
Я = К ^ ., ^т}. (9)
Также каждому ребру назначается вес
равный косинусу угла из матрицы а. Это описывается множеством Ж, которое является отображением множества косинуса углов на множество ребер:
Ж = {^ ^ …, Wm}. (10)
Необходимо условиться, что граф О (8) ориентированный и направление ребер указывает на превосходство одного элемента над другим.
Тогда для поиска Парето-оптимальных сравнений можно воспользоваться алгоритмом нахождения максимального остовного графа взвешенного связного неориентированного графа, используя алгоритм Кру-скала [5]. Поиск ведется на неориентированном графе, так как в данном случае учет превосходства одного элемента над другим не важен.
Дополнение остовного графа осуществляется путем перебора всех пар вершин остовного графа, которые не имеют прямой связи, и нахождения для этих пар соответствующего значений и определения новых
оценок ?'-={& lt-,}. Значение сравнительной оценки 5. получается перемещением по маршруту остовного графа, связывающего вершины рассматриваемой пары и перемножением сравнительных оценок. Если движение происходит против направления ребра, то берется обратная величина сравнительной оценки. Таким образом, поскольку при расчете сравнительных оценок используется свойство абсолютно согласованной матрицы, то полученному У будет соответствовать новое множество Ж'-(10), у которого все элементы единичны.
При получении множества сравнительных оценок У'- на этапе согласования оценок часто наступает ситуация, когда новые оценки не вписываются в диапазон используемой нами шкалы. Например, оценка 5, = 6 соответствует тому, что элемент 1 значительно превосходит элемент 2, а оценка ^ = 3 соответствует тому, что элемент 2 умеренно превосходит элемент 3. Тогда математически будет верно, что превосходство элемента 1 над элементом 3 будет 53 = 1 8. Как видно, при применении шкалы МАИ л3 выходит за рамки допустимых оценок (максимальная оценка 9). В связи с этим необходимо осуществить перевод оценок У'- в оценки У& quot-, соответствующие применяемой шкале. Для перевода можно предложить формулу соответствия шага по новой шкале к шагу по принятой шкале:
(5& gt-1
h=-
max
(11)
тах (Б)-1
где тах У'- - максимальная сравнительная оценка в множестве оценок У'-, которая
определяет верхнюю границу рассчитанных оценок, а max У'- - максимальная сравнительная оценка в множестве оценок S& quot- применяемой шкалы.
Таким образом, далее можно построить таблицу соответствия одной шкалы другой и затем получить с помощью неё S& quot- по S'-. Например, для стандарта из шкалы МАИ 3 будут соответствовать оценки, лежащие в диапазоне от 1 + h до 1 + 2h, а для единицы (равенство двух сравниваемых объектов) соответствует также единица из другой шкалы.
Получив S& quot- с оценками, соответствующими применяемой шкале, заполняется матрица R& quot-. Согласованность новой матрицы R& quot- проверяется вычислением ОС и функционала (6).
Таким образом, процесс повышения степени согласованности матрицы парных сравнений состоит из 4 этапов (рис. 2):
1. Построение по исходной матрице парных сравнений графа G (8).
2. Поиск максимального остовного подграфа в графе G (8).
3. Дополнение остовного графа до полного графа.
4. Приведение полученных оценок к оценкам по применяемой шкале.
Приведем пример расчета по полученному алгоритму для матрицы с оценками по шкале МАИ от 1 до 9. Процесс повышения согласованности для рассматриваемого случая представлен на рис. 3.
Дана матрица R (12):
R =
1 3 4 7 3& quot-
1/3 1 4 3 2
¼ 1/4 1 1/3 5
1/7 1/3 3 1 ¼
1/3 ½ 1/5 4 1
(12)
Приоритеты матрицы R (12):
P = (0,475 0,238 0,1 0,081 0,105).
(1З)
Г 1 0,920 0,476 0,714 0,878
0,920 1 0,545 0,906 0,673
ос= 0,476 0,545 1 0,287 0,315
0,714 0,906 0,287 1 0,380
0,878 0,673 0,315 0,380 1
Степень согласованности матри-
цы R (12) определяется коэффициентом ОС = 18,6%.
Матрица косинусов углов для Я:

1 этап
2 этап
4 этап
Поиск максимального остовного подграфа
Приведение оценок к применяемой шкале
v1
v4
/
v3
Рис. 2. Процесс повышения степени согласованности матрицы парных сравнений
На основе полученного, а в соответствии с алгоритмом строится граф О и находится максимальный остовной подграф.
Как видно, из полученного остовного графа на рис. 3 можно построить матрицу, где знаками вопроса обозначены сравнения, которые на данном этапе ещё неизвестны и их необходимо рассчитать по наиболее достоверным суждениям эксперта:
1 3? ? 3
1/3 1 4 3 ?
? ¼ 1? ?
? 1/3? 1 ?
1/3? ?? 1
R& quot-=
1 2 9 7 2 & gt-
½ 1 3 2 1
1/9 1/3 1 1 1/3
1/7 1/9 1 1 ½
½ 1 3 2 1
(14)
Пройдя все этапы алгоритма, получим итоговую матрицу парных сравнений Я& quot-:
Рассчитаем О С и новые приоритеты элементов сравнения по Я& quot-:
ОС = 1,3%, P = (0,469 0,193 0,064 0,080 0,193)).
Таким образом, ОС снизился с 18,6 до 1,3%, при этом наилучшая альтернатива не изменилась, а ранжирование элементов сравнений поменялось.
1 этап
4 этап
Поиск максимального остовного подграфа
Приведение оценок к применяемой шкале
Рис. 3. Процесс повышения согласованности матрицы парных сравнений на примере
Изложенный подход позволяет находить неточности в суждениях эксперта, а также с помощью алгоритма автоматически корректировать логические ошибки эксперта. Разработанный алгоритм может использоваться экспертом в качестве средства интеллектуальной поддержки процесса поиска и корректировки логически некорректных суждений. Представленный в статье подход был реализован в системе поддержки принятия решений «Решение» [2, 3].
Список литературы
1. Жиляков, Е.Г., Игрунова С. В., Девицына С. Н., Путив-цева Н.П., Мединцева С. В., Чашин Ю. Г Об использовании метода парных сравнений для принятия решений при оценивании уровня профессиональных компетенций обучаемых // Научные ведомости БелГУ. Серия «История. Политология. Экономика. Информатика». -2010. — № 10. — С. 65−73.
2. Лифиренко М. В. «Программное обеспечение поддержки принятия решений на основе балльной шкалы оценки альтернатив» — Всероссийский конкурс НИР студентов и аспирантов в области информатики и информационных технологий: сб. науч. работ: в 3 т. — Белгород: ИД «Белгород», 2012. — Т. 2. — 608 с.
3. Лифиренко М. В., Ломакин В. В. Система поддержки принятия управленческих решений на основе усовершенствованного аналитико-иерархического процесса // Свидетельство о государственной регистрации программы для ЭВМ № 2 013 616 249.
4. Саати Т. «Принятие решений. Метод анализа иерархий». — М.: Радио и связь, 1993.- 278 с.
5. Joseph B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. -1956. — Vol 7, No. 1. — C. 48−50.
References
1. Zhiljakov, E.G., Igrunova S.V., Devicyna S.N., Pu-tivceva N. P, Medinceva S.V., Chashin Ju.G. Ob ispol’zovanii metoda parnyh sravnenij dlja prinjatija reshenij pri ocenivanii urovnja professional’nyh kompetencij obuchaemyh. — Nauch-nye vedomosti BelGU, 2010, no. 10, pp. 65−73.
2. Lifirenko M. V Vserossijskij konkurs NIR studentov i aspiran-tov 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 usovershenstvovan-nogo analitiko-ierarhicheskogo processa — Svidetel’stvo o gosu-darstvennoj registracii programmy dlja JeVM № 2 013 616 249.
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.
Рецензенты:
Жиляков Е. Г., д.т.н., профессор, зав. кафедрой информационно-телекоммуникационных систем и технологий, НИУ БелГУ, г. Белгород-
Еременко В. Т., д.т.н., профессор, зав. кафедрой электроники, вычислительной техники и информационной безопасности, Госуниверситет — УНПК, г. Орел.
Работа поступила в редакцию 17. 01. 2014.

ПоказатьСвернуть
Заполнить форму текущей работой