2. Медиана Кемени

С введением мер близости (на отношениях), получена возможность определять расстояние между произвольной парой ранжирований.

Естественно предположить, что результирующее ранжирование F(P₁, ……P_m) должно быть расположено, как можно ближе к ранжированиям P₁,….P_m. Такое ранжирование М*(Р₁,…..Р_m) и называется медианой Кемени:

Е сли вместо ранжирования рассматриваются отношения частного порядка или эквивалентности, то медиану Кемени будем определять аналогично.

Медина Кемени определена на множестве ранжировании, либо частных порядков, либо эквивалентностей в зависимости от содержательной постановки задачи.

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

Любая пара альтернатив (a_i,a_j) может как принадлежать, так и не принадлежать медиане Кемени. Действительно, пусть мы отыскиваем медиану для единственного множества отношений, состоящего из отношений Р. но в качестве Р можно выбрать как отношение, содержащее пару (a_i,a_j), так и отношение, не содержащее её. Следовательно, медиана Кемени М*(Р₁,...,Р_m) удовлетворяет условию 4.

Выполнение условия 5 для медианы Кемени очевидно. Конкретный вид медианы М*(Р₁,…..Р_m) заранее неизвестен. Отыскание её, вообще говоря, является достаточно сложной оптимизационной задачей, алгоритмы решения которой будут изложены ниже.

Можно также показать, что для медианы Кемени выполняется также и условие 3.

Условие 1 оказывается, вообще говоря, для медианы Кемени невыполнимым.

Медиана Кемени – единственное результирующее, строгое ранжирование, являющееся нейтральным, согласованным и кондорсетовым.

Таким образом, медиана Кемени удовлетворяет принципу выбора Кондорсе, не приводя к парадоксу Кондорсе. С другой стороны, медиана Кемени удовлетворяет условиям 2 – 5 Эрроу, не удовлетворяя лишь условию 1, относительно целесообразности введения которого у исслед. нет единодушия, т.к. мед. Кемени – можно считать одним из наиболее корректных результирующих отношений.

Лекция № 15

Алгоритмы отыскания медианы Кемени (для ранжирований).

Задача отыскания медианы Кемени относится к числу универсальных задач дискретной оптимизации. (Но число оцениваемых экспертами альтернатив невелико № 20-30 и поэтому задача решается достаточно эффективно).

Возможны различные формы представления информации о ранжированиях Р₁,…..Р_m: .

Одна из наиболее распространенных матрицы отношений: .

При введении мер близости целесообразно рассматривать матрицы потерь: .

Расстояние от произвольного ранжирования Р, которому соответствует матрица: .

Для всех ранжировании Р₁,…,Р_m, указанных экспертами, которым соответствуют матрицы отношений определяется по формуле:

г де

Таким образом, суммарное расстояние от Р до Р₁,….Р_m указанных экспертами, можно представить с помощью d_ij (P, P_u). Заметим, что при P_ij = 1,

Определим элемент матрицы потерь r_ij как:

Чтобы получить r_ij, необходимо рассмотреть:

Элементы матрицы потерь определяются ранжированиями Р₁,…..Р_m и не зависят от ранжирования Р.

Тогда для произвольного ранжирования Р:

где I_p – множество пар индексов (i,j) таких, что в P

Пример: построения матрицы потерь

Пусть экспертами указаны ранжирования

Р₁ Р₂ Р₃ Р₄

которым соответствуют матрицы отношений

т огда , где P- произвольное ранжирование, в котором Р₁₄ =1, т.е. r₁₄ = 2+0+2+1=5

Значения ,

где Р – произвольное ранжирование, в котором Р₄₁=1, r₄₁ =0+2+0+1=3, остальные значения r_ij рассчитываются аналогично. Матрица потерь имеет следующий вид:

В матрице потерь нумерация строк и столбцов совпадает, причем строке и столбцу с определенным номером соответствует альтернатива, имеющая тот же номер.

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

Эвристический алгоритм.

Пусть - матрица потерь множества ранжирований.

1-ая интерпретация. Подсчитаем . Найдем

Альтернативу а_i1 ставим на первое место в искомом ранжировании. Полагаем S⁽¹⁾ = s_i1. Вычеркивая в строку и столбец с номером i₁ получаем матрицу множество индексов строк и столбцов

которой, соответственно:

К-ая интерпретация. В матрице потерь подсчитаем найдем ,

альтернативу a_ik ставим на К-ое место в искомом упорядочении. Полагаем .

Вычеркивая в строку и столбец с номером i_k получаем матрицу , множество индексов строк и столбцов которой . Алгоритм завершается после n-ой итерации , искомое упорядочение:Ц елесообразно использовать следующий простой алгоритм перехода от ранжирования Р_I к P_II, для которого выполнено необходимое условие оптимальности.

Последовательно проверяем справедливость соотношений . Как только для некоторого к оно нарушено альтернативы a_ik и a_ik+1 в ранжировании меняем местами, а отношение: , проверяем, начиная с альтернативы непосредственно предшествующей альтернативе подвергшейся перестановке.

После конечного числа шагов будет получено ранжирование P_II, для которого необходимое условие оптимальности выполнено.

Пример (для вышеприведенного случая)

Найдем ранжирование Р_I :

1-ая итерация. Подсчитаем:

м инимум достигается на

на первое место в ранжировании Р_I помещается альтернатива а₂ и из дальнейших рассмотрений исключается.

2-ая итерация. Подсчитаем:

м инимум достигается на , на второе место в ранжировании Р_I помещается альтернатива а₃ и из дальнейших рассмотрений исключается.

3-я итерация. Подсчитаем:

м инимум достигается на , на третье место в ранжировании Р_I помещается альтернатива а₄ и из дальнейших рассмотрений исключается.

Таким образом, ранжирование Р_I имеет вид:

Найдем теперь ранжирование P_II

Сравниваем r₄₁ и r₁₄, поскольку альтернативы a_n и a₁ стоят, соответственно, на предпоследнем и последнем местах в ранжировании Р_I

Так как r₄₁ < r₁₄, переходим к сравнению r₃₄ и r_43, т.к. r₃₄ < r₄₃, переходим к сравнению r₂₃ и r₃₂ r₂₃ > r₃₂, поэтому альтернативы а₂ и а₃ меняем местами поскольку r₂₄ < r₄₂, найденное ранжирование и является ранжированием P_II, для которого соотношения , выполнено.

Комбинаторный алгоритм отыскания медианы Кемени.

Существенная роль в алгоритмах отыскания медианы Кемени принадлежит оценкам величины суммарного расстояния от медианы Кемени Р* до ранжирований всех экспертов .

Нижней границей величины является величина .

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

Комбинаторный алгоритм основан на методе ветвей и границ с односторонней схемой ветвления.

При построении алгоритма следует максимально учесть специфику задачи. Для этой цели в матрице потерь ранжирований Р₁,….Р_m подсчитаем , , равное числу столбцов матрицы потерь (числу альтернатив), для которых r_ij > r_ji, и , , равна числу столбцов, для которых r_ij < r_ji. Если в матрице потерь нашлась строка с . Это означает, что х_i1 – альтернатива Кондорсе и в медиане Кемени она должна занимать первое место. Если после отбрасывания альтернативы Кондорсе х_i1, что соответствует отбрасыванию в матрице строки и столбца с номером i₁ обнаружится новая строка с , то и место альтернативы х_i2 в медиане Кемени определено: х_i2 расположена непосредственно за х_i1. Аналогично можно выделить и другие лучшие альтернативы, расположение которых в медиане становится известным.