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

Автор работы: Пользователь скрыл имя, 14 Февраля 2012 в 16:38, практическая работа

Описание работы

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

Файлы: 1 файл

ИДЗ 2.doc

— 225.00 Кб (Скачать файл)

Цель  работы:

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

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

  1. По исходному профилю предпочтения построить матрицу профиля.
  2. Найти оптимальную перестановку с помощью алгоритма ветвей и границ, записывая все промежуточные частичные и полные решения в таблицу.
  3. Найти приближенное решение задачи с помощью эвристического алгоритма, записываю последовательность действий в таблицу.
  4. Сравнить полученные в пунктах 2 и 3 результаты.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  1. ПО  ИСХОДНОМУ ПРОФИЛЮ  ПРЕДПОЧТЕНИЯ ПОСТРОИТЬ МАТРИЦУ ПРОФИЛЯ.
 

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

    1 > 2 > 3
    3 > 2 > 1
              1 > 2 > 3
 

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

      ,       где:  =

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

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

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

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

    Р12=0+2+0=2   

    Р13=0+2+0=2    

    Р21=2+0+2=4

    Р23=0+2+0=2

    Р31=2+0+2=4

    Р32=2+0+2=4 

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

    

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

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

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

    

.

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

      

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

    
Шаг k Множество S Дополнение

Т

Dlow >

=

<

Коментарии
1 0 0 - любое - Du = ∞
2 1 1 23 4+2=6 < ветвление
3 2 12 3 4+2=6 < полное решение

{123} Du = 6

4 2 13 2 2+2+4=8 > отсечение
5 1 2 13 4+2+2=8 > отсечение
6 2 21 3 4+2+2=8 > отсечение
7 2 23 1 2+4+4=10 > отсечение
8 1 3 12 4+4+2=10 > отсечение
9 2 31 2 4+4+2=10 > отсечение
10 1 32 1 4+4+4=12 > отсечение
 
 

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

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

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

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

    

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

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

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

Число строк

k

Построковые суммы

Si

Минимальная сумма

Smin

Строка с  минимальной суммой

imin

Элемент оптимальной  перестановки

ti min*

Исходная перестановка

T

3 S1 = 4

S2 = 6

S3 = 8

4 1 1 {23}
2 S2 = 2

S3 = 4

2 2 2 {3}
 

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

    

 

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

= 6. 

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

    

      

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

    совпадают. 

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

    Т* = {123}.

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

    ik а1 > a2 > a3
    i 1 2 3
 
  1. Необходимо  проверить условие 

    а) k =3−1 = 2.

    Сравниваем  , i2=1, i3=3.

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

    б) k = 3−2 = 1.

    Сравниваем  , i2=1, i1=2.

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

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

,

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

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

 

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

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

         S *:= {123}. 

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

Информация о работе Нахождение медиана Кемени