Принятие решений с помощью языка бинарных отношений

Август 5, 2022

Главная
Информатика
Принятие решений с помощью языка бинарных отношений

Содержание

2. Содержание Текущий контроль Основные допущения Способы задания бинарных отношений Алгоритмы ранжирования объектов Классификация бинарных отношений Метод
3. Текущий контроль Три ученика заданы оценками по двум дисциплинам, приведенным в таблице 1. Требуется: Пользуясь DELTA-1
4. Допущения 1) Отсутствие количественных характеристик предпочтительности одной альтернативы по сравнению с другой; 2) Для каждой пары
5. способы задания бинарных отношений непосредственное перечисление пар; матричный способ; графовое задание: граф G(X,U) отражает непротиворечивые мнения
6. Алгоритм ранжирования объектов в порядке ухудшения Шаг 1. i = 1. Шаг 2. На множестве вершин
7. ПРИМЕР 1 Последовательное преобразование графа G(X,U) 1 5 3 2 2 6 5 1 4 3
8. САМОСТОЯТЕЛЬНО Дать пошаговое описание упорядочения вершин графа G(X,U), не содержащего контуров, в порядке «улучшения» вершин. Упорядочить
9. Программная реализация прямого и обратного упорядочений вершин
10. Классификация бинарных отношений В теории выбора используются три типа отношений: эквивалентности, порядка; доминирования.
11. Используемые термины Бинарное отношение R на множестве X нарывается: рефлексивным, если антирефлексивным, если симметричным, если асимметричным,
12. Используемые термины сильнотранзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно. Отношение эквивалентности (~) рефлексивно, симметрично
13. пример практического использования бинарных отношений Группы экспертов оценивают пары поданных на конкурс проектов, пользуясь отношениями эквивалентности
14. Избавление от противоречивых оценок Одним из подходов, позволяющим избавиться от противоречий, является отказ от мнений нескольких
15. Формальная постановка задачи где: A(G) - множество контуров на ориентированном графе G(X, U); U(a) – подмножество
16. Метод Делфи Четыре основных этапа метода Делфи: Раздача анкет, сбор оценок, их обобщение и определение разброса
17. Противоречивые мнения экспертов Наличие контуров на графе G(X,U) приводит к выводу о наличии противоречий во мнениях
18. Задача о разрыве контуров на бисвязном графе Формальная постановка Графическая задачи интерпретация на графе G(X,U) 1
19. Решение задачи о минимальном разрезе перебором 2 3 1 6 3 1 4 2 5 Rопт
20. Программа поиска минимального разреза на бисвязном взвешенном графе
22. Скачать презентацию

Слайд 2

Содержание
Текущий контроль
Основные допущения
Способы задания бинарных отношений
Алгоритмы ранжирования объектов
Классификация бинарных отношений
Метод Делфи
Принятие

решений при наличии противоречивых экспертных оценок.

Слайд 3

Текущий контроль
Три ученика заданы оценками по двум дисциплинам, приведенным в таблице

1. Требуется:
Пользуясь DELTA-1 разбить учеников по двум таксонам.
Пользуясь алгоритмом SKAT проверить устойчивость таксономии.

Слайд 4

Допущения
1) Отсутствие количественных характеристик предпочтительности одной альтернативы по сравнению с другой;
2)

Для каждой пары альтернатив (x, y) справедливо одно из трех:
одна из них предпочтительней другой;
альтернативы равноценны;
альтернативы несравнимы.
3) Отношения предпочтения для любой пары
(x, y) не зависят от остальных альтернатив, предложенных к выбору.

Слайд 5

способы задания бинарных отношений
непосредственное перечисление пар;
матричный способ;
графовое задание: граф G(X,U) отражает

непротиворечивые мнения
экспертов, если на нем
отсутствуют контуры.

Слайд 6

Алгоритм ранжирования объектов в порядке ухудшения

Шаг 1. i = 1.
Шаг 2.

На множестве вершин полученного графа
выбираем вершины источники. Если таковые
отсутствуют, перейти к шагу 7.
Шаг 3. Выбранные на предыдущем шаге вершины
считаем принадлежащими i-му ярусу.
Шаг 4. i = i + 1.
Шаг 5. Выбранные на шаге 2 последней итерации вершины удаляются из
графа.
Шаг 6. Перейти к шагу 2.
Шаг 7. Конец алгоритма.

Слайд 7

ПРИМЕР 1
Последовательное преобразование графа G(X,U)
1
5
3
2
2
6
5
1
4
3
6
3
1
2
5
а б
в
г
1
2
5
Перестановки: π₁= {4,6,3,1,2,5};

π₂ = {6,4,3,1,2,5}; π₃ = {4,6,3,5,1,2}.
Самостоятельно определить остальные упорядочения вершин графа.

Слайд 8

САМОСТОЯТЕЛЬНО
Дать пошаговое описание упорядочения вершин графа G(X,U), не содержащего контуров, в

порядке «улучшения» вершин.
Упорядочить этим алгоритмом вершины графа G(X,U), матрица смежности вершин которого М приведена ниже:
М =

Слайд 9

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

Слайд 10

Классификация бинарных отношений
В теории выбора используются три типа отношений:
эквивалентности,
порядка;
доминирования.

Слайд 11

Используемые термины
Бинарное отношение R на множестве X нарывается:
рефлексивным, если
антирефлексивным, если

симметричным, если
асимметричным, если
антисимметричным, если
транзитивным, если
отрицательно транзитивным, если отношение транзитивно;

Слайд 12

Используемые термины
сильнотранзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно.
Отношение эквивалентности

(~) рефлексивно, симметрично и транзитивно.
Примеры отношения эквивалентности: "быть четным", "иметь одинаковый остаток от деления на 3", "быть одноклассником" и т.п.
Отношение нестрогого порядка (≤) рефлексивно, антисимметрично, транзитивно.
Отношение строгого порядка (<) антирефлексивно, асимметрично и транзитивно. Отношение "≤" эквивалентно объединению "<" и "~".
Отношение доминирования антирефлексивно и асимметрично.
Пример выявления отношений доминирования – разбиение графа на ярусы

Бинарное отношение R на множестве X нарывается:

Слайд 13

пример практического использования бинарных отношений
Группы экспертов оценивают пары поданных на конкурс

проектов, пользуясь отношениями эквивалентности и доминирования. Цель – выбрать проекты, претендующие на 1,2 и 3 места.
Результатом является граф, вершины которого отвечают проектам, направления дуг – отношениям доминирования различных групп экспертов, а вес r(i,j) каждой дуги – степени доверия соответствующей экспертной оценке .
Очевидно, что наличие контуров приводит к выводу о наличии противоречий во мнениях экспертов

Слайд 14

Избавление от противоречивых оценок
Одним из подходов, позволяющим избавиться от противоречий, является

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

Слайд 15

Формальная постановка задачи
где:
A(G) - множество контуров на ориентированном графе G(X, U);
U(a)

– подмножество дуг, отвечающих контуру «a»;
(i,j) – дуга, принадлежащая множеству U.

Слайд 16

Метод Делфи
Четыре основных этапа метода Делфи:
Раздача анкет, сбор оценок, их обобщение

и определение разброса мнений.
Сообщение итогов и запрос объяснений причин индивидуального отклонения от средней или медианной оценки первой итерации.
Сообщение всех объяснений и запрос контраргументов на них.
Сообщение возражений и запрос новых оценок альтернатив.
Самостоятельно прочитать стр. 65 -67.

Слайд 17

Противоречивые мнения экспертов
Наличие контуров на графе G(X,U) приводит к выводу о

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

Слайд 18

Задача о разрыве контуров на бисвязном графе
Формальная постановка Графическая задачи интерпретация

на графе G(X,U)

7
3 5
1
4 2

Возможные разрезы на G(X,U):
1) W₁ ={(1,2);(5,3)}; R(W₁)=11.
2) W₂ ={(4,5)};R(W₂)=2.

Слайд 19

Решение задачи о минимальном разрезе перебором
2
3
1
6 3
1 4
2
5
Rопт =

6; πопт = 3,1,2

Слайд 20

Принятие решений с помощью языка бинарных отношений

Содержание

Текущий контрольТри ученика заданы оценками по двум дисциплинам, приведенным в таблице

Допущения1) Отсутствие количественных характеристик предпочтительности одной альтернативы по сравнению с другой;2)

способы задания бинарных отношенийнепосредственное перечисление пар;матричный способ;графовое задание: граф G(X,U) отражает

Алгоритм ранжирования объектов в порядке ухудшения Шаг 1. i = 1.Шаг 2.

ПРИМЕР 1Последовательное преобразование графа G(X,U)153226514363125 а б вг125Перестановки: π₁= {4,6,3,1,2,5};

САМОСТОЯТЕЛЬНОДать пошаговое описание упорядочения вершин графа G(X,U), не содержащего контуров, в

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

Классификация бинарных отношенийВ теории выбора используются три типа отношений: эквивалентности, порядка;доминирования.

Используемые терминыБинарное отношение R на множестве X нарывается:рефлексивным, если антирефлексивным, если

Используемые терминысильнотранзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно.Отношение эквивалентности

пример практического использования бинарных отношенийГруппы экспертов оценивают пары поданных на конкурс

Избавление от противоречивых оценокОдним из подходов, позволяющим избавиться от противоречий, является

Формальная постановка задачигде:A(G) - множество контуров на ориентированном графе G(X, U);U(a)

Метод ДелфиЧетыре основных этапа метода Делфи:Раздача анкет, сбор оценок, их обобщение

Противоречивые мнения экспертовНаличие контуров на графе G(X,U) приводит к выводу о

Задача о разрыве контуров на бисвязном графеФормальная постановка Графическая задачи интерпретация

Решение задачи о минимальном разрезе перебором231 6 31 42 5Rопт =

Программа поиска минимального разреза на бисвязном взвешенном графе

Похожие презентации