Нахождение медиана Кемени

Цель  работы:

Для заданного  профиля предпочтения найти медиану  Кемени.

Программа работы:

1. По исходному профилю предпочтения построить матрицу профиля.
2. Найти оптимальную перестановку с помощью алгоритма ветвей и границ, записывая все промежуточные частичные и полные решения в таблицу.
3. Найти приближенное решение задачи с помощью эвристического алгоритма, записываю последовательность действий в таблицу.
4. Сравнить полученные в пунктах 2 и 3 результаты.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. ПО  ИСХОДНОМУ ПРОФИЛЮ  ПРЕДПОЧТЕНИЯ ПОСТРОИТЬ МАТРИЦУ ПРОФИЛЯ.

 

     Заданный  профиль предпочтения:

 

     Матрица профиля предпочтения позволяет  представить в компактном виде все  отношения ранжирования профиля  предпочтения.

      ,       где:  =

     i, j – элементы ранжирований,

     k – номер ранжирования,

     m – число всех ранжирований.

    Рассчитаем  для каждой пары альтернатив значение матрицы профиля Р: 

    Р₁₂=0+2+0=2   

    Р₁₃=0+2+0=2    

    Р₂₁=2+0+2=4

    Р₂₃=0+2+0=2

    Р₃₁=2+0+2=4

    Р₃₂=2+0+2=4 

Матрица профиля предпочтения имеет вид:

    

Сумма элементов относительно главной диагонали =2*m=6 

2. НАХОЖДЕНИЕ  ОПТИМАЛЬНОЙ ПЕРЕСТАНОВКИ С ПОМОЩЬЮ АЛГОРИТМА  ВЕТВЕЙ И ГРАНИЦ.

 

    Идея  метода заключается в том, что  проверяются неполные или частичные решения, используется операция ветвления и нахождения границ, тем самым стремимся к минимальному расстоянию до ранжирования. То есть вычисляется оценка расстояния D для некоторого частичного решения.

    

.

Найдем  построковые суммы в матрице профиля предпочтения:

      

    Таблица 1Промежуточные вычисления нахождения оптимальной перестановки с помощью  алгоритма ветвей и границ 

      
 

    Оптимальная перестановка Т = {123} при этом расстояние наилучшего полного решения  D_U=6.

3. НАХОЖДЕНИЕ ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧИ С ПОМОЩЬЮ ЭВРИСТИЧЕСКОГО АЛГОРИТМА.

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

1. Вычисляются суммы элементов для каждой строки матрицы профиля Р.
2. Номер строки с минимальной суммой записывается в оптимальную перестановку.
3. Из матрицы профиля удаляется строка и столбец с выбранным номером.
4. Вычисляются новые строковые суммы, до тех пор, пока не будет найдено полное решение.

 

    

Необходимо  найти оптимальную перестановку Т*. 

Расчеты приведены в таблице 2.

     Таблица 2 – Промежуточные вычисления для  нахождения медианы Кемени с помощью  эвристического алгоритма 

 

    Таким образом, оптимальная перестановка Т* = {123}. 
 

    

 

    Вычисляем стоимость решения (сумма верхней треугольной матрицы): D_U =

= 6. 

    Вычисляем наименьшее возможное расстояние:

    

      

    Решения, полученные с помощью двух разных алгоритмов, полностью 

    совпадают. 

    Для полной достоверности правильности расчетов проведем процедуру улучшения эвристик.

    Т* = {123}.

    Пронумеруем перестановку:

 

1. Необходимо  проверить условие 

а) k =3−1 = 2.

Сравниваем  , i₂=1, i₃=3.

P₂₃ (=2)  < P₃₂ (=4) , условие выполняется.

б) k = 3−2 = 1.

Сравниваем  , i₂=1, i₁=2.

P₁₂ (=2)  < P₂₁ (=4) , условие выполняется. 

     Все условия выполняются, следовательно,  перестановка Т* = {123} является решением задачи. Причем, расстояние от перестановки до профиля предпочтения D_U = 6.  

,

где     D_u^прибл – приближенное решение алгоритма (эвристический алгоритм),

     D_u^точн – точное решение алгоритма (алгоритм ветвей и границ).

 

4. Сравнение  полученных в пунктах 2, 3 результатов.

При нахождении медианы Кемени с помощью  алгоритма ветвей и границ и эвристического алгоритма, мы получили оптимальное решение Duвг=Duэвр=Dleast=6. Окончательные ранжирования в двух алгоритмах совпадают и имеют следующий вид:

     S *:= {123}. 

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