§ 5.6. Блок-схема алгоритма «Ядро»

В предыдущих параграфах этой главы было получено строгое решение задачи построения множества допустимых групповых решений в пространствах и 90 и предложен эвристический метод решения этой задачи для случая, когда исходные данные принадлежат пространству Поскольку решение последней задачи включает решение первой, то при разработке алгоритма естественно рассматривать более общий случай, когда исходные данные принадлежат и в этом же пространстве ищутся допустимые групповые решения.

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

текущий индекс эксперта, через ранжирование, полученное от эксперта, где ранг объекта, присвоенный ему экспертом.

Рис. 5.3. (см. скан)

Таким образом, входными данными являются: Блок-схема на рис. 5.3 описывает работу алгоритма.

Пояснения к блок-схеме будут сопровождаться примерами на трех объектах и с.

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

Пусть , т. е. эксперт считает, что Матрица отношения предпочтения эксперта в пространстве имеет вид

Переносим исходные данные из в в соответствии с формулой

Для выписанной в матрицы отношений в пространстве имеем матрицу

а сама точка Р в графическом представлении имеет вид

3. Выписываем минимальное отношение по условию

Так, для трех отношений в 90

имеем

4. Выписываем максимальное отношение в пространстве по правилу

Для отношений из имеем

5. Для каждой из точек в пространстве теперь нужно найти соответствующую ей максимальную ближайшую точку Обозначим

5а) Цикл по Выход в

56) Для каждой точки находим матрицу «добавок», т. е. матрицу тех добавление которых к по описанному ниже правилу позволит найти соответствующий максимальный элемент

Для примера из для имеем

5в) Цикл Выход в п. 5д.

Из матрицы выбираем единичный элемент добавляем его получаем отношение

Проверяем полученную матрицу на транзитивность, для чего возводим в квадрат и проверяем включение . Если включение выполняется, то переходим к если же — нет, то продолжаем перебор добавок Для нашего примера

5г) Полагаем Повторяем вычисления пункта 56 с той лишь разницей, что вместо матрицы отношения вычитаем из Р матрицу полученного транзитивного отношения

5д) Если ни одно добавление к не «привело к новой транзитивной точке т. е. отношение уже само есть максимальная точка, то в массив максимальных точек записываем и продолжаем цикл по , п. 5а. В противном случае в массив заносим матрицу найденного максимального отношения и возвращаемся к п. 5а.

6. К этому моменту сформирован массив максимальных точек Выписываем ядерное отношение по условию

Точки определяют ядро в пространстве 90 и представляют собой два допустимых групповых решения в 90, удовлетворяющих (принципу Парето. Все остальные решения заполняют линейный сегмент между Перейдем теперь к построению линейного сегмента. Обозначим множество точек линейного сегмента через

7. Выписываем матрицу

где

8. Построим массив адресов-индексов тех элементов матрицы которые равны 1. Например, для матрицы

этот массив будет иметь вид

Далее будем перебирать все возможные комбинации «добавок» из к отношению следующим образом. Пусть где через обозначено число элементов в равных 1. Теперь будем к Т прибавлять единицу по модулю 2. Если в получаемых таким образом числах номера позиций, занимаемых единицами, отождествлять с номерами адресов в массиве то таким образом мы переберем все возможные комбинации «добавок». Объединяя с этими комбинациями и проверяя полученное объединение на транзитивность, мы построим все точки линейного сегмента между и и, следовательно, все допустимые групповые решения в пространстве 90.

9. Если по условиям задачи допустимые групповые решения нужно получить в пространстве частичных порядков 90, то массив нужно вывести на печать.

В качестве дополнительных характеристик полученного множества допустимых групповых решений в 90 можно подсчитать нормированное расстояние между «крайними» мнениями из ядра по формуле

и коэффициент согласия Кендалла для этих же точек [19]:

10. Если групповые решения ищутся в пространстве линейных квазипорядков то перенос точек ядра в пространство

производится по формуле

где есть матрица группового предпочтения в а

Каждая полученная матрица проверяется на транзитивность.

11. Если множество допустимых групповых решений в пространстве пусто, то за групповое решение принимается транзитивное замыкание отношения

12. Работа алгоритма после выполнения п. 11 заканчивается восстановлением по матрицам групповых решений рангов соответствующих ранжирований.