Эвристический алгоритм поиска медианы Кемени

Пусть для исходных ранжирований матрица потерь определена. Процесс поиска итогового ранжирования состоит из 2 этапов.

На первом этапе строится предварительное ранжирование P_I.

1-я итерация. Подсчитаем суммы элементов строк матрицы потерь:

.

Найдем минимальную из них .

Альтернативу а_i1, ставим на первое место в искомом ранжировании. Вычеркивая в  строку и столбец с номером i₁, получаем матрицу , множество индексов строк и столбцов которой соответственно I⁽¹⁾= J⁽¹⁾={1, …, n}\ I₁.

k-я итерация. В матрице потерь  подсчитаем суммы элементов строк:

.

Найдем минимальную из них:

.

Альтернативу а _ik, ставим на k-тое место в искомом упорядочении. Вычеркивая в  строку и столбец с номером i_k, получаем матрицу , множество индексов строк и столбцов которой соответственно I^{( k)}= J^{( k)}={1, …, n}\{i₁, …, i_k}.

Алгоритм завершается после n-й итерации (I^{( k)}= J^{( k)} и равны пустому множеству). Искомое упорядочение

На втором этапе из найденного ранжирования P_I получают итоговое ранжирование P_II, при этом процесс перехода от ранжирования P_I к ранжированию P_II происходит следующим образом: для элементов ранжирования P_I последовательно проверяем справедливость соотношений (6.1).

(6.1)

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

 

Пример

Рассмотрим процесс построения итогового ранжирования на примере, рассмотренном ранее (исходные данные представлены в табл. 6.2).

1. Построим матрицы отношений для ранжирований экспертов:

	0	-1	-1	-1		0	-1	-1	-1
	1	0	-1	1		1	0	1	1
	1	1	0	1		1	-1	0	1
	1	-1	-1	0		1	-1	-1	0
	0	1	1	1		0	0	-1	-1
	-1	0	-1	-1		0	0	-1	-1
	-1	1	0	0		1	1	0	-1
	-1	1	0	0		1	1	1	0

Например, p₁₂⁽¹⁾=-1, так как r₁< r₂ (r₁=3, r₂=1), p₃₄⁽²⁾=0, так как r₃= r₄ (r₃=2, r₄=2).

 

2. Матрица потерь имеет следующий вид:

0	5	6	6
3	0	6	4
2	2	0	3
2	4	5	0

Например, r₁₂= d₁₂( P₁, P₃)+ d₁₂( P₂, P₃)+ d₁₂( P₄, P₃), так как P₃ – ранжирование, элемент матрицы отношений которого p₁₂⁽³⁾=1. Тогда r₁₂=| p₁₂⁽³⁾- p₁₂⁽¹⁾|+| p₁₂⁽²⁾- p₁₂⁽³⁾|+| p₁₂⁽³⁾- p₁₂⁽⁴⁾|=|1-(-1)|+ |1-(-1)|+ |1-0|=5.

 

3. Найдем предварительное ранжирование P_I (первый этап).

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

Минимум достигается на S₃⁽¹⁾. На первое место в ранжировании P_I помещается альтернатива a₃, и она из дальнейших рассмотрений исключается.

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

Минимум достигается на S₄⁽²⁾. На второе место в ранжировании P_I помещается альтернатива a₄, и она из дальнейших рассмотрений исключается.

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

Минимум достигается на S₂⁽³⁾. На третье место в ранжировании P_I помещается альтернатива a₂, и она из дальнейших рассмотрений исключается. Таким образом, ранжирование P_I имеет следующий вид:

4. Найдем ранжирование Р _II (второй этап).

Итак, i₁=3, i₂=4, i₃=2, i₄=1. Сравниваем  и  или r₂₁ и r₁₂, Так как r₂₁≤ r₁₂ (3≤ 5), то альтернативы не меняем местами, переходим к сравнению r₄₂ и r₂₄. Так как r₄₂≤ r₂₄ (4≤ 4), то переходим к сравнению r₃₄ и r₄₃.  Поскольку r₃₄< r₄₃ (3≤ 5), то найденное ранжирование

и является ранжированием Р _II, для которого соотношения (6.1) выполнены.

Итоговые ранжирования альтернатив по методу Борда и методу поиска медианы Кемени представлены в табл. 6.4.

 

Таблица 6.4

Результаты построения итогового ранжирования с помощью метода Борда и метода поиска медианы Кемени

Альтернатива	Место в итоговом ранжировании (Кемени)	Место в итоговом ранжировании (Борд)
a 1	4	3
a 2	2	4
a 3	1	1
a 4	3	2

 

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

 

Вопросы и задания

1. Приведите примеры групповых задач принятия решений.

2. Всегда ли можно найти лучшую альтернативу, используя правило большинства и принцип Кондорсе?

3. В чем принципиальные различие между методом Борда и методом поиска медианы Кемени?

 

Список литературы

1. Ларичев, О. И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах: учебник. – М.: Логос, 2000. – 296 с.

2. Розен, В. В. Математические модели принятия решений в экономике: Учебное пособие. – М.: Книжный дом «Университет», Высшая школа, 2002. – 228 с.

3. Теория прогнозирования и принятия решений/ под ред.
С. А. Саркисяна. – М.: Высшая школа, 1977. – 351 с.

4. Парето-оптимальные решения многокритериальных задач.
В. В. Подиновский, В. Д. Ногин – М.: Наука. Главная редакция физико-математической литературы, 1982. – 256 с.

5. Домарев, В. В. Безопасность информационных технологий. Методология создания систем защиты – К.: ООО ТИД «ДС», 2002 – 688 с.

6. Мухин О. И. Компьютерное моделирование [Электронный ресурс]/ – Режим доступа: http: //www.twirpx.com/file/415646/

7. Шолохова, Надежда Владимировна. Система поддержки принятия решений при управлении депозитным портфелем физических лиц коммерческого банка: автореферат дис.... кандидата технических наук: 05.13.10 / Шолохова Надежда Владимировна; [Место защиты: Уфим. гос. авиац.-техн. ун-т].- Уфа, 2012.- 16 с.: ил. РГБ ОД, 9 12-5/3994.

8. Рябинин, И. А. Надежность и безопасность структурно-сложных систем. – СПб.: Политехника, 2000. – 248 с.

9. Соложенцев, Е. Д. Сценарное логико-вероятностное управление риском в бизнесе и технике. – СПб.: Бизнес-Пресса, 2004. – 432 с.

10. Матричные антагонистические игры. Методические указания для самостоятельной работы студентов / Уфимск. гос. авиац. техн. ун-т; Сост.: Р. П. Абдрахманова, А. Ф. Валеева. – Уфа, 2004.– 42 c.

11. Балдин, К. В. Математические методы в экономике. Теория, примерные варианты контрольных работ: Учеб. пособие /
К. В. Балдин, О. Ф. Быстров – М.: Издательство Московского психологического социального института; Воронеж: Издательство НПО «МОДЭК», 2003. – 54 с.

12. Munda G. Social multi-criteria evaluation for a sustainable economy. Berlin: Springer Verlag, 2008.

13. Kř ehlí k T. Unorthodox measures of economic performance. Prague, 2011. Bachelor’s thesis, Charles University, Faculty of Social Sciences, Institute of Economic Studies.

14. MCDA. Novel Approach to Imprecise Assessment and Decision Environments (NAIADE) [Электронный ресурс]/ – Режим доступа: http: //www.aegean.gr/environment/energy/mcda/Frames/Steps/Step7.htm

15. Кини, Р. Л. Принятие решений при многих критериях: предпочтения и замещения / Р. Л. Кини, Х. Райфа: пер. с англ. / под ред. И. Ф. Шахнова. – М.: Радио и связь, 1981. – 560 с.

16. Андрейчиков, А. В. Анализ, синтез, планирование решений в экономике / А. В. Андрейчиков, О. Н. Андрейчикова. – М.: Финансы и статистика, 2001. – 368 с.

17. Шелобаев, С. И. Математические методы и модели в экономике, финансах, бизнесе: Учебное пособие для вузов / С. И. Шелобаев. – М.: ЮНИТИ-ДАНА, 2000. – 367 с.

18. Представление знаний и использование знаний/ под ред. Х. Уэно, М. Исидзука и др. – М.: Мир, 1989. – 220 с.

19. Литвак, Б. Г. Экспертная информация: методы получения и анализа. – М.: Радио и связь, 1982. – 184 с.

Приложение 1

Лингвистические переменные

Значение лингвистической переменной	Функция принадлежности
1	2
Отлично
Очень хорошо
Хорошо
Более или менее хорошо

 

Продолжение приложения 1

1	2
Умеренно
Более или менее плохо
Плохо

Продолжение приложения 1

1	2
Очень плохо
Крайне плохо

                                                                                          

Приложение 2

Нечеткие переменные

Вид функции принадлежности	Функция принадлежности
1	2
Гауссова	где l, m, u, k − некоторые числовые параметры, k≥ 0.
Flat	где l, u, m 1, m 2, b 1, b 2 − некоторые числовые параметры,

 

Продолжение приложения 2

1	2
Left-right general	где l, u, m, b 1, b 2 − некоторые числовые параметры,
Symmetrical	где l, u, b 1, b 2 − некоторые числовые параметры,

 

⇐ Предыдущая567891011121314

Поделиться: