С введением мер близости (на отношениях), получена возможность определять расстояние между произвольной парой ранжирований.
Естественно предположить, что результирующее ранжирование F(P1, ……Pm) должно быть расположено, как можно ближе к ранжированиям P1,….Pm. Такое ранжирование М*(Р1,…..Рm) и называется медианой Кемени:
Если вместо ранжирования рассматриваются отношения частного порядка или эквивалентности, то медиану Кемени будем определять аналогично.
Медина Кемени определена на множестве ранжировании, либо частных порядков, либоэквивалентностей в зависимости от содержательной постановки задачи.
Во всех трех случаях множества отношений, которым принадлежит указываемый экспертами набор отношений, являются универсальными. Так как и ранжирования и отношения частного порядка и эквивалентности транзитивны, а медиану Кемени мы отыскиваем в том же классе отношений, - медиана Кемени обладает свойством транзитивности.
Любая пара альтернатив (ai,aj) может как принадлежать, так и не принадлежать медиане Кемени. Действительно, пусть мы отыскиваем медиану для единственного множества отношений, состоящего из отношений Р. но в качестве Р можно выбрать как отношение, содержащее пару (ai,aj), так и отношение, не содержащее её. Следовательно, медиана Кемени М*(Р1,...,Рm)удовлетворяет условию 4.
Выполнение условия 5 для медианы Кемени очевидно. Конкретный вид медианы М*(Р1,…..Рm) заранее неизвестен. Отыскание её, вообще говоря, является достаточно сложной оптимизационной задачей, алгоритмы решения которой будут изложены ниже.
Можно также показать, что для медианы Кемени выполняется также и условие 3.
Условие 1 оказывается, вообще говоря, для медианы Кемени невыполнимым.
Таким образом, медиана Кемени удовлетворяет принципу выбора Кондорсе, не приводя к парадоксу Кондорсе. С другой стороны, медиана Кемени удовлетворяет условиям 2 – 5 Эрроу, не удовлетворяя лишь условию 1, относительно целесообразности введения которого у исслед. нет единодушия, т.к. мед. Кемени – можно считать одним из наиболее корректных результирующих отношений.
Задача отыскания медианы Кемени относится к числу универсальных задач дискретной оптимизации. (Но число оцениваемых экспертами альтернатив невелико № 20-30 и поэтому задача решается достаточно эффективно).
Возможны различные формы представления информации о ранжированиях Р1,…..Рm: .
Одна из наиболее распространенных матрицы отношений:.
При введении мер близости целесообразно рассматривать матрицы потерь:.
Расстояние от произвольного ранжирования Р, которому соответствует матрица:.
Для всех ранжировании Р1,…,Рm, указанных экспертами, которым соответствуют матрицы отношений определяется по формуле:
где
Таким образом, суммарное расстояние от Р до Р1,….Рm указанных экспертами, можно представить с помощью dij (P, Pu). Заметим, что при Pij = 1,
Определим элемент матрицы потерь rij как:
Чтобы получить rij, необходимо рассмотреть:
Элементы матрицы потерь определяются ранжированиями Р1,…..Рm и не зависят от ранжирования Р.
Тогда для произвольного ранжирования Р:
где Ip – множество пар индексов (i,j) таких, что в P
Пример: построения матрицы потерь
Пусть экспертами указаны ранжирования
Р1Р2Р3Р4
которым соответствуют матрицы отношений
тогда , где P- произвольное ранжирование, в котором Р14 =1, т.е. r14 = 2+0+2+1=5
Значения ,
где Р – произвольное ранжирование, в котором Р41=1, r41 =0+2+0+1=3, остальные значения rij рассчитываются аналогично. Матрица потерь имеет следующий вид:
В матрице потерь нумерация строк и столбцов совпадает, причем строке и столбцу с определенным номером соответствует альтернатива, имеющая тот же номер.
Задача отыскания медианы Кемени для ранжирований может быть сформулирована как задача отыскания такого упорядочивания альтернатив, а, следовательно, строк и столбцов матрицы потерь, чтобы сумма её элементов, расположенных над диагональю была минимальна, таким образом, вся информация о ранжированиях экспертов, необходимая для отыскания медианы Кемени, содержится в матрице потерь.