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

Размещено на http://www.allbest.ru/

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

Вычислительная техника и информационные технологии

Ю.В. Бугаев, И. Ю. Шурупова

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

Ключевые слова: альтернатива, профиль экспертных упорядочений, метод экстраполяции экспертных оценок, бесконечные оценки, коллективный выбор.

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

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

каждый из участников процедуры (избирателей) вырабатывает свое мнение об этих вариантах и отражает его в избирательном бюллетене в соответствии с инструкцией;

в соответствии с той или иной формальной процедурой по этой информации, поступившей от избирателей, определяется коллективное решение.

Поведение ЛПР существенно определяется ограниченным объемом кратковременной памяти, поэтому количество альтернатив, предъявляемых эксперту, а также число показателей качества, описывающих альтернативы, должны отвечать возможностям человека в данном аспекте [1]. Если число альтернативных решений достаточно велико (сотни и более), то задача поиска оптимального варианта не может быть решена прямым применением какого-либо известного механизма выбора, предполагающего привлечение экспертов, ввиду того что они ориентированы на осуществление экспертной оценки сразу всего имеющегося набора альтернативных решений, включаемого в предъявление X. Однако на практике при проектировании современных сложных производственных систем и планировании их деятельности такая ситуация возникает все чаще и чаще.

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

Пусть имеем обучающую выборку из альтернатив

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

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

(1)

где - структурная матрица -го экспертного упорядочения, число столбцов которой совпадает с числом альтернатив, а число строк зависит от вида ранжирования; , - число экспертов. При линейном упорядочении выборки матрица имеет вид

.

Система (1) соответствует наступлению определенного случайного события, вероятность которого определяется по формуле

(2)

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

, (3)

где - константа нормировки, которую при максимизации можно отбросить.

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

Следуя [2], случайные величины будем считать независимыми, нормально распределенными и, ввиду однородности выборки, имеющими одинаковую дисперсию . Тогда имеем вектор параметров распределения , где математические ожидания - истинные полезности альтернатив выборки, а совместная плотность распределения имеет вид

.

Поскольку полезности определяются с точностью до масштабного множителя, то можно положить = 1. Тем самым мы избавимся от неоднозначности оценок полезности.

Опыт нахождения ММП-оценок в МЭЭО [3] убеждает в том, что решение этой задачи не всегда конечно.

Пример 1. Пусть имеем следующие варианты экспертного упорядочения выборки их трёх альтернатив :

; ; ,

где символ означает «не хуже по предпочтению». Этому набору упорядочений соответствует ФП

(4)

максимум которой равен 0,148148 и достигается при следующих соотношениях полезностей альтернатив: ; =0,60914. Численная же оптимизация функции (4) в системе MathCad даёт следующие оценки полезностей: = 6,96689; = -3,18503; = -3,79417. При этих оптимальное значение совпадает с 0,148148. Условие = 0,60914, как видно, выполняется, а = 10,151916. В соответствии со значением функции нормального распределения полученное решение аппроксимирует бесконечно удалённую точку.

Однако очевидно, что такой аппроксимацией будет любое решение, удовлетворяющее условиям 8; = 0,60914, т.е. численное решение не единственно.

Проведённые исследования [3] показали, что помимо неоднозначности наличие бесконечных решений приводит к значительному смещению полученных оценок полезности. Поэтому вопрос о существовании или отсутствии бесконечных решений в МЭЭО весьма важен.

Пусть экспертов проранжировали элементы выборки из альтернатив на порядковой шкале по убыванию полезностей в соответствии со своими индивидуальными предпочтениями. Для каждой пары альтернатив () вычислим величины

, (5)

где - число случаев, когда эксперты указали , подобно тому, как это делается в процедуре Терстоуна-Мостеллера [2].

Далее на множестве альтернатив введём следующее бинарное отношение :

(6)

Очевидно, отношение (6) симметрично, так как , хотя , т.е. в общем случае . Геометрическим образом данного отношения будет неориентированный граф .

Согласно процедуре Терстоуна-Мостеллера, оценки полезности каждой альтернативы подбираются из условия примерного равенства

(7)

где - функция стандартного нормального распределения. Соотношение (7) справедливо и для МЭЭО-оценок. Следовательно, бесконечные оценки могут появиться только у альтернатив, входящих в пары, для которых = 1 (или 0). В этом случае в силу (7) (или ). Для таких пар отношение (6) не выполняется. Поэтому, в частности, альтернатива выборки, если она единственная имеет бесконечную оценку полезности, соответствует изолированной вершине графа .

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

Теорема 1. Пусть в графе вершины и достижимы одна из другой. Тогда , где оценки и являются координатами точки теоретического максимума ФП в МЭЭО.

Доказательство:

1. Докажем, что из следует . Тот факт, что означает, что в данном профиле альтернативы и по-разному упорядочены у различных экспертов.

Известна следующая теорема (теорема 2.6 [3]). Пусть в заданном профиле некоторые две альтернативы и по-разному упорядочены у различных экспертов. Тогда разность - в оптимальной точке ФП не может равняться бесконечности.

Утверждение теоремы 2.6 полностью совпадает с требуемым выводом.

2. Докажем основное утверждение теоремы. Пусть в графе вершины и взаимно достижимы. Возможны два случая:

В имеется ребро . Тогда и требуемое следствие получается согласно п. 1.

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

экстраполяция экспертная оценка голосование

Следовательно,

что и требовалось доказать.

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

1. На основании профиля предпочтений вычисляем по формуле (5) для всех пар альтернатив.

2. Строим отношение и на его основе граф .

3. Проверяем связность . Если он связный, то ММП-оценки всех альтернатив будут конечны.

Рассмотрим два иллюстрирующих примера. Сначала вернёмся к примеру 1. Согласно формуле (5), имеем:

; ; .

Следовательно, граф содержит только одно ребро и имеет две компоненты связности: и . Оценка бесконечна.

Пример 2. Пусть имеем следующие варианты упорядочения выборки их трёх альтернатив :

; ; .

Имеем: ; ; . Граф G содержит два ребра, (A1, А2) и (A1, А3), а значит, является связным. Бесконечных оценок нет. Численное решение даёт следующие значения оценок полезности: = 0; = 0,923; = - 0,923. Расчётные значения вероятностей превосходства, согласно (7), составляют: ; ; (все отличны от 0 и 1).

Теорема 1 определяет достаточные условия конечности решения. Выясним, каковы необходимые условия. Для этого нам понадобятся вычислительные формулы для вероятностей (2).

Сделаем замену переменных. В соответствии с правилами преобразования нормального распределения [4] данная замена преобразует плотность нормального распределения к виду

,

где (верхний индекс матрицы опущен). Тогда вероятность (2) определяется по формуле

.

Данное выражение можно преобразовать к виду

, (8)

где - вектор искомых параметров ФП. Как видим, формула вычисления вероятностей индивидуальна для каждого варианта упорядочения.

Теорема 2. Пусть граф несвязный и и принадлежат разным компонентам связности. Тогда в точке теоретического максимума функции правдоподобия .

Доказательство. Пусть и - компоненты связности, содержащие и , соответственно. Поскольку и принадлежат разным компонентам, то все эксперты считают их одинаково упорядоченными. Пусть, для определённости, . Возможны два случая:

1. Во всех структурных матрицах присутствует строка, соответствующая разности полезностей . Тогда среди нижних пределов интегрирования в каждом интеграле (8) имеется . Пусть найдена точка максимума ФП и в ней . Очевидно, что если положить , то от этого все интегралы увеличатся, ФП возрастёт, т.е. в оптимальном решении .

2. Строка, соответствующая разности , в явном виде присутствует не во всех структурных матрицах .

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

Вывод. Связность графа является необходимым и достаточным условием конечности точных ММП-оценок полезностей альтернатив в МЭЭО при экспертном ранжировании обучающей выборки на порядковой шкале. Для решения задачи проверки связности имеется несколько простых методов [5]: метод поиска связывающих маршрутов посредством поиска в глубину или в ширину, метод определения номеров компонент связности, являющийся составной частью алгоритма Краскала, и др.

Данный результат означает, что добавление новых данных на разностно-порядковой шкале не сделает решения конечными, просто внесёт некоторое отношение в величину бесконечно больших разностей.

Пример 3. Имеем 6 одинаковых упорядочений выборки их трёх альтернатив: . Численное решение, найденное при ограничении= 0, имеет вид (8,2160; 0,0012; -8,2172). Целевая функция в этой точке равна 1. Оценки и расположились почти симметрично относительно . Однако, например, точка (10,2160; 3,0012; -13,2172) даёт такое же значение и удовлетворяет ограничению. Таким образом, численное решение задачи не определено, а точное решение должно удовлетворять соотношению

; .

Добавим к исходным данным задачи результат ранжирования на разностно-порядковой шкале: пусть три эксперта считают, что , а три остальных - что . Получим следующий численный результат: (7,714; 1,755•10-7; -7,714). Следовательно , поскольку, согласно ранжированию, вероятность превосходства первой разности над второй равна 0,5. Изменение результатов ранжирования повлечёт иное соотношение между значениями данных разностей.

СПИСОК ЛИТЕРАТУРЫ

1. Ларичев, О. И. Объективные модели и субъективные решения / О. И. Ларичев. - М.: Наука, 1987. - 144 с.

2. Thurstone, L. L. A law of comparative judgment / L. L. Thurstone // Psychol. Rev. - 1927. - V. 34. - P. 273 286.

3. Миронова, М. С. Моделирование процедур коллективного выбора на основе экстраполяции экспертных оценок: дис. … канд. физ.-мат. наук / М.С. Миронова. - Воронеж: ВГУИТ, 2011. - 138 с.

4. Андерсон, Т. Введение в многомерный статистический анализ: [пер. с англ.] / Т. Андерсон. - М.: Физматгиз, 1963. - 500 с.

5. Липский, В. Комбинаторика для программистов: [пер. с пол.] / В. Липский. - М.: Мир, 1988. - 213 с.

Размещено на Allbest.ru