Методы средних баллов. Целочисленное программирование успешно применяется и для усреднения ответов экспертов. В теории принятия решений большое место занимают экспертные опросы. Сначала рассмотрим балльные оценки. Часто опрашиваемых просят выставить баллы объектам, изделиям, технологическим процессам, предприятиям, проектам, заявкам на выполнение научно-исследовательских работ, идеям, проблемам, программам,  политикам и т.п., а затем рассчитывают средние баллы и рассматривают их как интегральные  оценки, выставленные коллективом опрошенных.  Какими формулами пользоваться для вычисления средних величин? Ведь видов средних величин очень много. По традиции обычно применяют среднее арифметическое. Мы уже более 25 лет знаем, что такой способ некорректен, поскольку баллы обычно измерены в т.н. порядковой шкале. Как доказано в монографии [6], обоснованным является использование медиан  в качестве средних баллов. Однако полностью игнорировать средние арифметические нерационально из-за их привычности и распространенности. Поэтому целесообразно использовать одновременно оба метода - и метод средних арифметических рангов (баллов), и методов медианных рангов. Такая рекомендация находится в согласии с концепцией устойчивости, рекомендующей использовать различные методы для обработки одних и тех же данных с целью выделить выводы, получаемые одновременно при всех методах [6]. Такие выводы, видимо, соответствуют реальной действительности, в то время как заключения, меняющиеся от метода к методу, зависят от субъективизма исследователя, выбирающего метод обработки исходных экспертных оценок.

Пример сравнения восьми проектов. Рассмотрим конкретный пример применения только что сформулированного подхода. По заданию руководства фирмы анализировались восемь проектов, предлагаемых для включения в план стратегического развития фирмы. Они были обозначены следующим образом: Д, Л, М-К, Б, Г-Б, Сол, Стеф, К (по фамилиям менеджеров, предложивших их для рассмотрения). Все проекты были направлены 12 экспертам, назначенным Правлением фирмы. В приведенной ниже табл.6 приведены ранги восьми проектов, присвоенные им каждым из 12 экспертов в соответствии с их представлением о целесообразности включения проекта в стратегический план фирмы (ранг 1 - самый лучший проект, который обязательно надо реализовать, ранг 2 - второй по привлекательности проект, ... , ранг 8 - наиболее сомнительный проект).

Анализируя результаты работы экспертов (т.е. упомянутую табл.8), члены Правления фирмы были вынуждены констатировать, что полного согласия между экспертами нет, а потому данные табл.6 следует подвергнуть более тщательному математическому анализу.

Метод средних арифметических рангов. Сначала был применен метод средних арифметических рангов. Для этого прежде всего была подсчитана сумма рангов, присвоенных проектам (см. таблицу). Затем эта сумма была разделена на число экспертов, в результате рассчитан средний арифметический ранг (именно эта операция дала название методу). По средним рангам строится итоговая ранжировка (в другой терминологии - упорядочение), исходя из принципа - чем меньше средний ранг, чем лучше проект. Наименьший средний ранг, равный 2,625, у проекта Б, - следовательно, в итоговой ранжировке он получает ранг 1. Следующая по величине сумма, равная 3,125, у проекта М-К, - и он получает итоговый ранг 2. Проекты Л и Сол имеют одинаковые суммы (равные 3,25), значит, с точки зрения экспертов они равноценны (при рассматриваемом способе сведения вместе мнений экспертов), а потому они должны бы стоять на 3 и 4 местах и получают средний балл (3+4)/2 = 3,5. Дальнейшие результаты приведены в табл.7 ниже.

Табл.6. Ранги 8 проектов по степени  привлекательности для включения в план стратегического развития фирмы

№ эксперта	Д	Л	М-К	Б	Г-Б	Сол	Стеф	К
1	5	3	1	2	8	4	6	7
2	5	4	3	1	8	2	6	7
3	1	7	5	4	8	2	3	6
4	6	4	2,5	2,5	8	1	7	5
5	8	2	4	6	3	5	1	7
6	5	6	4	3	2	1	7	8
7	6	1	2	3	5	4	8	7
8	5	1	3	2	7	4	6	8
9	6	1	3	2	5	4	7	8
10	5	3	2	1	8	4	6	7
11	7	1	3	2	6	4	5	8
12	1	6	5	3	8	4	2	7

Примечание. Эксперт № 4 считает, что проекты М-К и Б равноценны, но уступают лишь одному проекту - проекту Сол. Поэтому проекты М-К и Б должны были бы стоять на втором и третьем местах и получить баллы 2 и 3. Поскольку они равноценны, то получают средний балл (2+3)/ 2 = 5/ 2 = 2,5.

Итак, ранжировка по суммам рангов (или, что то же, по средним арифметическим рангам) имеет вид:

Б < М-К < {Л, Сол} < Д < Стеф < Г-Б < К .       (1)

Здесь запись типа "А<Б" означает, что проект А предшествует проекту Б (т.е. проект А лучше проекта Б). Поскольку модели Л и Сол получили одинаковую сумму баллов, то по рассматриваемому методу они эквивалентны, а потому объединены в группу (в фигурных скобках). В терминологии математической статистики ранжировка (1) имеет одну связь.

Метод медиан рангов. Значит, наука сказала свое слово, итог расчетов - ранжировка (1), и на ее основе предстоит принимать решение? Но тут наиболее знакомый с современной эконометрикой член Правления вспомнил, что ответы экспертов измерены в порядковой шкале, а потому для них неправомерно проводить усреднение методом средних арифметических. Надо использовать метод медиан.

Что это значит? Надо взять ответы экспертов, соответствующие одному из проектов, например, проекту Д. Это ранги 5, 5, 1, 6, 8, 5, 6, 5, 6, 5, 7, 1. Затем их надо расположить в порядке неубывания (проще было бы сказать - "в порядке возрастания", но поскольку некоторые ответы совпадают, то приходится использовать непривычный термин "неубывание"). Получим последовательность: 1, 1, 5, 5, 5, 5, 5, 6, 6, 6, 7, 8. На центральных местах - шестом и седьмом - стоят 5 и 5. Следовательно, медиана равна 5.

Табл. 7. Результаты расчетов по методу средних арифметических и методу медиан для данных, приведенных в табл.6.

	Д	Л	М-К	Б	Г-Б	Сол	Стеф	К
Сумма рангов	60	39	37,5	31.5	76	39	64	85
Среднее арифметическое рангов	5	3,25	3,125	2,625	6,333	3,25	5,333	7,083
Итоговый ранг по среднему арифметическому	5	3,5	2	1	7	3,5	6	8
Медианы рангов	5	3	3	2,25	7,5	4	6	7
Итоговый ранг по медианам	5	2,5	2,5	1	8	4	6	7

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

Б < {М-К, Л} < Сол < Д < Стеф < К <Г-Б  .       (2)

Поскольку проекты Л и М-К имеют одинаковые медианы баллов, то по рассматриваемому методу ранжирования они эквивалентны, а потому объединены в группу (кластер), т.е. с точки зрения математической статистики ранжировка (2) имеет одну связь.

Сравнение ранжировок по методу средних арифметических и методу медиан. Сравнение ранжировок (1) и (2) показывает их близость (похожесть). Можно принять, что проекты М-К, Л, Сол упорядочены как М-К < Л < Сол, но из-за погрешностей экспертных оценок в одном методе признаны равноценными проекты Л и Сол (ранжировка (1)), а в другом - проекты М-К и Л (ранжировка (2)). Существенным является только расхождение, касающееся упорядочения  проектов К и Г-Б: в ранжировке (1) Г-Б < К, а в ранжировке (2), наоборот, К < Г-Б. Однако эти проекты - наименее привлекательные из восьми рассматриваемых, и при выборе наиболее привлекательных проектов для дальнейшего обсуждения и использования на  это расхождение можно не обращать внимания.

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

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

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

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

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

Введем необходимые понятия, затем сформулируем алгоритм согласования кластеризованных ранжировок в общем виде и рассмотрим его свойства. Пусть имеется конечное число объектов, которые мы для простоты изложения будем изображать натуральными числами 1,2,3,...,k и называть «носителем». Под кластеризованной ранжировкой, определенной на заданном носителе, понимаем следующую математическую конструкцию. Пусть объекты разбиты на группы, которые будем называть кластерами. В кластере может быть и один элемент. Входящие в один кластер объекты будем заключать в фигурные скобки. Например, объекты 1,2,3,...,10 могут быть разбиты на 7 кластеров: {1}, {2,3}, {4}, {5,6,7}, {8}, {9}, {10}. В этом разбиении один кластер {5,6,7} содержит три элемента, другой - {2,3} - два, остальные пять - по одному элементу. Кластеры не имеют общих элементов, а объединение их (как множеств) есть все рассматриваемое множество объектов.

Вторая составляющая кластеризованной ранжировки - это строгий линейный порядок между кластерами. Задано, какой из них первый, какой второй, и т.д. Будем изображать упорядоченность с помощью знака <. При этом кластеры, состоящие из одного элемента, будем для простоты изображать без фигурных скобок. Тогда кластеризованную ранжировку на основе введенных выше кластеров можно изобразить так:

А = [ 1 < {2,3} < 4 < {5,6,7} < 8 < 9 < 10 ] .

Конкретные кластеризованные ранжировки будем заключать в квадратные скобки. Если для простоты речи термин "кластер" применять только к кластеру не менее чем из 2-х элементов, то можно сказать, что в кластеризованную ранжировку А входят два кластера {2,3} и {5,6,7} и 5 отдельных элементов.

Введенная описанным образом кластеризованная ранжировка является бинарным отношением на множестве {1,2,3,...,10}. Его структура такова. Задано отношение эквивалентности с 7-ю классами эквивалентности, а именно, {2,3}, {5,6,7}, а остальные состоят из оставшихся 5 отдельных элементов. Затем введен строгий линейный порядок между классами эквивалентности.

         Следующее важное понятие - противоречивость. Оно определяется для четверки - две кластеризованные ранжировки на одном и том же носителе и два различных объекта - элементы того же носителя.  При этом два элемента из одного кластера будем связывать символом равенства = , как эквивалентные .  Пусть А и В - две кластеризованные ранжировки. Пару объектов (a, b) назовем  «противоречивой» относительно А и В, если эти два элемента по-разному упорядочены в А и В, т.е. a < b в А и a > b в В (первый вариант противоречивости) либо a > b в А и  a < b в В (второй вариант противоречивости).  Подчеркнем, что в соответствии с этим определением пара объектов (a, b), эквивалентная хотя бы в одной кластеризованной ранжировке, не может быть противоречивой:  равенство a = b не образует "противоречия" ни с a < b, ни с a > b.

В качестве примера рассмотрим две кластеризованные ранжировки

В = [{1,2} < { 3,4, 5} < 6 < 7 < 9 < {8, 10}],

C = [3 < {1, 4} < 2 < 6 < {5, 7, 8} < {9, 10}].

Совокупность  противоречивых пар объектов для двух кластеризованных ранжировок А и В назовем «ядром противоречий» и обозначим S(A,B). Для рассмотренных выше в качестве примеров трех кластеризованных ранжировок А, В и С, определенных на одном и том же носителе {1, 2, 3,..., 10},  имеем

S(A,B) = [ (8, 9)], S(A,C) = [ (1, 3), (2,4) ] ,

S(B,C) = [ (1, 3), (2, 3), (2, 4), (5, 6), (8,9) ] . 

Как при ручном, так и при программном нахождении ядра можно в поисках  противоречивых пар просматривать пары (1,2), (1,3), (1.,4), ...., (1, k), затем (2,3), (2,4), ..., (2, k), потом (3,4), ..., (3, k), и т.д., вплоть до (k-1, k).

Пользуясь понятиями дискретной математики, «ядро противоречий» можно изобразить графом с вершинами в точках носителя. При этом противоречивые пары задают ребра этого графа. Граф для S(A,B) имеет только одно ребро (одна связная компонента более чем из одной точки), для S(A,C) - 2 ребра (две связные компоненты более чем из одной точки), для S(B,C) - 5 ребер (три связные компоненты более чем из одной точки, а именно, {1, 2 , 3, 4}, {5, 6} и {8, 9}).

          Предлагаемый алгоритм согласования некоторого числа кластеризованных ранжировок состоят из трех этапов. На первом выделяются противоречивые пары объектов во всех парах кластеризованных ранжировок.  На втором формируются кластеры итоговой кластеризованной ранжировки (т.е. классы эквивалентности - связные компоненты графов, соответствующих объединению попарных ядер противоречий). На третьем этапе эти кластеры (классы эквивалентности) упорядочиваются. Для установления порядка между кластерами произвольно выбирается один объект из первого кластера и второй - из второго, порядок между кластерами устанавливается такой же, какой имеет быть между выбранными объектами в любой из рассматриваемых кластеризованных ранжировок. Корректность подобного упорядочивания, т.е. его независимость от выбора той или иной пары объектов,  вытекает из соответствующих теорем, доказанных в статье [9]. Два объекта из разных кластеров согласующей кластеризованной ранжировки могут оказаться эквивалентными в одной из исходных кластеризованных ранжировок (т.е. находиться в одном кластере). В таком случае надо рассмотреть упорядоченность этих объектов в какой-либо другой из исходных кластеризованных ранжировок. Если же во всех исходных кластеризованных ранжировках два рассматриваемых объекта находились в одном кластере, то естественно считать (и это является уточнением к этапу 3 алгоритма), что они находятся в одном кластере и в согласующей кластеризованной ранжировке.

Результат согласования кластеризованных ранжировок А, В, С,... обозначим f(А, В, С,...). Тогда

f(А, В) = [1<2<3<4<5<6<7<{8, 9}<10],

f(А, С) = [{1,3}<{2, 4}<5<6<7<8<9<10],

f(В, С) = [{1,2,3,4}<{5,6}<7<{8,9}<10],

f(А, В, С) = f(В, С) = [{1,2,3,4} <{5,6}<7<{8, 9}<10].

В случае f(А, В) дополнительного изучения с целью упорядочения требуют только объекты 8 и 9. В случае f(В, С) объекты 1,2,3,4 объединились в один кластер, т.е. кластеризованные ранжировки оказались настолько противоречивыми, что процедура согласования не позволила провести достаточно полную декомпозицию задачи нахождения итогового мнения экспертов.

Рассмотрим некоторые свойства алгоритмов согласования.

1. Пусть D = f(А, В, C,...). Если a<b в согласующей  кластеризованной ранжировке D, то a<b или a=b в каждой из исходных ранжировок А, В, C, ...

2. Построение согласующих кластеризованных ранжировок может осуществляться поэтапно. В частности, f(A, B, C) = f(f(A, B), f(A, C), f(B, C)) . Ясно, что ядро противоречий для набора кластеризованных ранжировок является объединением таких ядер для всех пар рассматриваемых ранжировок.

3. Построение согласующих кластеризованных ранжировок нацелено на выделение общего упорядочения в исходных кластеризованных ранжировках. Однако при этом некоторые общие свойства исходных кластеризованных ранжировок могут теряться. Так, при согласовании ранжировок В и С, рассмотренных выше, противоречия в упорядочении элементов 1 и 2 не было - в ранжировке В эти объекты входили в один кластер, т.е. 1 = 2, в то время как 1<2 в кластеризованной ранжировке С. Значит, при их отдельном рассмотрении можно принять упорядочение 1 < 2. Однако в  f(В,C) они попали в один кластер, т.е. возможность их упорядочения исчезла. Это связано с поведением объекта 3, который "перескочил" в С на первое место и "увлек с собой в противоречие" пару (1, 2), образовав противоречивые пары и с 1, и с 2. Другими словами, связная компонента графа, соответствующего ядру противоречий, сама по себе не всегда является полным графом. Недостающие ребра при этом соответствуют парам типа (1, 2), которые сами по себе не являются противоречивыми, но "увлекаются в противоречие" другими парами.

Бинарные отношения и дискретная оптимизация. Как  известно, бинарное отношение А на конечном множестве 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].

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