«Управление и Оптимизация Производственного Предприятия»

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

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

Бинарные отношения и дискретная оптимизация. Как известно, бинарное отношение А на конечном множестве Q = {q₁ , q₂ ,..., q_k } - это подмножество т.н. декартова квадрата Q² = { (q_m , q_n ), m, n = 1,2,…,k }. При этом пара (q_m , q_n ) входит в А тогда и только тогда, когда между q_m и q_n имеется рассматриваемое отношение.

Каждую кластеризованную ранжировку, как и любое бинарное отношение, можно задать матрицей || 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].

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

Arg min ∑ D (A_i ,A) ,

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

∑ D (A_i ,A) = D (A₁ ,A) + D (A₂ ,A) + D (A₃ ,A) +…+ D (A_р ,A) .

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

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

Arg min ∑ D (A_i ,A) → Arg min М D (A₁ , A) .

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

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

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