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

ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ ЛЕКЦИЯ 3: Принятие решений с помощью языка бинарных отношений

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

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

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

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

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

ПРИМЕР 1 Последовательное преобразование графа G(X,U)

САМОСТОЯТЕЛЬНО Дать пошаговое описание упорядочения вершин графа G(X,U), не содержащего контуров, в порядке «улучшения» вершин. Упорядочить этим алгоритмом вершины графа G(X,U), матрица смежности вершин которого М приведена ниже: М =

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

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

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

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

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

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

Формальная постановка задачи где: A(G) - множество контуров на ориентированном графе G(X, U); U(a) – подмножество дуг, отвечающих контуру «a»; (i,j) – дуга, принадлежащая множеству U.

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

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

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

Решение задачи о минимальном разрезе перебором

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

Алгоритм упорядочения объектов Постановка задачи (содержательная и формальная). Проведение экспертизы (метод Дельфи). Построение графа доминирования объектов. Проверка (тест) графа на наличие бикомпонент. Если таковые есть, то переход к шагу 5, нет – к шагу 8. Определение весовых оценок для экспертных заключений и постановка задачи о минимальном разрезе. Решение задачи о минимальном разрезе на графе доминирования объектов. Удаление на графе доминирования объектов дуг, отвечающих минимальному разрезу. Разбиение вершин полученного графа на слои последовательным отбрасыванием вершин – источников (стоков). Если полученное упорядочение объектов отличается от хранящегося в памяти на допустимую величину, то перейти к шагу 10, в противном случае ранее хранившееся упорядочение забывается, новое запоминается, после чего осуществляется переход к шагу 2. Конец алгоритма. Полученное на последней итерации упорядочение объектов является оптимальным.