Автор работы: Пользователь скрыл имя, 14 Февраля 2012 в 16:38, практическая работа
Цель работы:
Для заданного профиля предпочтения найти медиану Кемени.
Программа работы:
По исходному профилю предпочтения построить матрицу профиля.
Найти оптимальную перестановку с помощью алгоритма ветвей и границ, записывая все промежуточные частичные и полные решения в таблицу.
Найти приближенное решение задачи с помощью эвристического алгоритма, записываю последовательность действий в таблицу.
Сравнить полученные в пунктах 2 и 3 результаты.
Цель работы:
Для заданного профиля предпочтения найти медиану Кемени.
Программа работы:
Заданный профиль предпочтения:
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
Идея метода заключается в том, что проверяются неполные или частичные решения, используется операция ветвления и нахождения границ, тем самым стремимся к минимальному расстоянию до ранжирования. То есть вычисляется оценка расстояния 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.
Данный алгоритм находит решение, которое не является точным, хотя иногда оно может быть оптимальным.
Необходимо
найти оптимальную перестановку
Т*.
Расчеты приведены в таблице 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 =
Вычисляем наименьшее возможное расстояние:
Решения, полученные с помощью двух разных алгоритмов, полностью
совпадают.
Для полной достоверности правильности расчетов проведем процедуру улучшения эвристик.
Т* = {123}.
Пронумеруем перестановку:
ik | а1 > a2 > a3 | ||
i | 1 | 2 | 3 |
а) 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точн – точное решение алгоритма (алгоритм ветвей и границ).
При нахождении медианы Кемени с помощью алгоритма ветвей и границ и эвристического алгоритма, мы получили оптимальное решение Duвг=Duэвр=Dleast=6. Окончательные ранжирования в двух алгоритмах совпадают и имеют следующий вид:
S
*:= {123}.
Вывод:
в ходе работы было выявлено, что с помощью
метода ветвей и границ мы получаем абсолютно
точные решения, хотя и затрачиваем на
их нахождение не мало времени и усилий.
Этот метод надо использовать тогда, когда
требуется узнать оптимальное (идеальное
и единственно верное) решение. Этот способ
является достаточно надежным. Что касается
эвристического алгоритма, то следует
заметить, что он находит «хорошие», но
не обязательно точные решения. Его можно
быстрее и проще реализовать, чем любой
другой известный точный алгоритм. Его
результаты можно применять только как
приближенные, так как эвристический алгоритм
– это не гарант надежности.