А.И. Орлов       
Основы теории принятия решениий       
Учебное пособие. Москва, 2002.

7. Экспертные оценки, бинарные отношения и дискретная оптимизация
    

Бинарные отношения и дискретная оптимизация. Как известно, бинарное отношение А на конечном множестве Q = {q1 , q2 ,..., qk } - это подмножество т.н. декартова квадрата Q2 = { (qm , qn ), m, n = 1,2,…,k }. При этом пара (qm , qn ) входит в А тогда и только тогда, когда между qm и qn имеется рассматриваемое отношение.

Каждую кластеризованную ранжировку, как и любое бинарное отношение, можно задать матрицей || x(a, b) || из 0 и 1 порядка k x k. При этом x(a, b) = 1 тогда и только тогда, когда a < b либо a = b. В первом случае x(b, a) = 0, а во втором x(b, a) = 1. При этом хотя бы одно из чисел x(a, b) и x(b, a) равно 1. Из определения противоречивости пары (a, b) (см. выше) вытекает, что для нахождения всех таких пар достаточно поэлементно перемножить две матрицы || x(a, b) || и || y(a, b) ||, соответствующие двум кластеризованным ранжировкам, и отобрать те и только те пары, для которых x(a, b) y(a, b)=x(b, a) y(b, a)=0.

В экспертных методах принятия решений в производственном менеджменте используют, в частности, такие бинарные отношения, как ранжировки (упорядочения, или разбиения на группы, между которыми имеется строгий порядок), отношения эквивалентности, толерантности (отношения сходства). Как известно, каждое бинарное отношение А можно описать матрицей || a(i, j) || из 0 и 1, причем a(i, j) = 1 тогда и только тогда, когда qi и qj находятся в отношении А, и a(i, j) = 0 в противном случае.

Определение. Расстоянием Кемени между бинарными отношениями А и В, описываемыми матрицами || a(i, j) || и || b(i, j) || соответственно, называется число

D (A, B) = ∑ │a(i, j) - b(i, j) │,

где суммирование производится по всем i, j от 1 до k.

Легко видеть, что расстояние Кемени - это число несовпадающих элементов в матрицах || a(i, j) || и || b(i, j) || .

Расстояние Кемени основано на некоторой системе аксиом. Эта система аксиом и вывод из нее формулы для расстояния Кемени между упорядочениями содержится в книге [4], которая сыграла большую роль в развитии в нашей стране такого научного направления, как анализ нечисловой информации [5]. В дальнейшем под влиянием Кемени были предложены различные системы аксиом для получения расстояний в тех или иных нужных для социально-экономических исследований пространствах, например, в пространствах множеств [6].

С помощью расстояния Кемени находят итоговое мнение комиссии экспертов. Пусть А1 , А2 , А3 ,…, Ар - ответы р экспертов, представленные в виде бинарных отношений. Для их усреднения используют т.н. медиану Кемени

Arg min ∑ D (Ai ,A) ,

где Arg min - то или те значения А, при которых достигает минимума указанная сумма расстояний Кемени от ответов экспертов до текущей переменной А, по которой и проводится минимизация. Таким образом,

∑ D (Ai ,A) = D (A1 ,A) + D (A2 ,A) + D (A3 ,A) +…+ D (Aр ,A) .

Кроме медианы Кемени, используют среднее по Кемени, в котором вместо D (Ai ,A) используют D2 (Ai ,A) .

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

Arg min ∑ D (Ai ,A) → Arg min М D (A1 , A) .

Здесь М - символ математического ожидания. Предполагается, что ответы р экспертов А1 , А2 , А3 ,…, Ар есть основания рассматривать как независимые одинаково распределенные случайные элементы (т.е. как случайную выборку) в соответствующем пространстве произвольной природы, например, в пространстве упорядочений или отношений эквивалентности. Систематически эмпирические и теоретические средние и соответствующие законы больших чисел изучены в работе [7].

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

Предыдущая страница | Оглавление | Следующая страница



Защита от автоматического заполнения   Введите символы с картинки*