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

Дата добавления: 2013-12-23; просмотров: 2397; Нарушение авторских прав

Задача отыскания медианы Кемени относится к числу универсальных задач дискретной оптимизации. (Но число оцениваемых экспертами альтернатив невелико № 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 рассчитываются аналогично. Матрица потерь имеет следующий вид:

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

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

<== предыдущая лекция	\|	следующая лекция ==>
Медиана Кемени	\|	Эвристический алгоритм