Классификация задач принятия решения

Классификационный признак	Разновидность задачи принятия решения
Новизна задачи (алгоритм решения, наличие аналога).	Задача имеется в базе знаний (есть алгоритм решения), задачи нет в базе знаний, но есть аналоги, задача не имеет аналогов.
Тип исхода (информационная среда задачи, уровень информации).	Детерминированный исход (в условиях определенности), случайный исход (в условиях риска, в условиях неопределенности), нечеткий исход (в условиях нечеткости).
Вид проблемной ситуации.	Необходимость решения новой задачи, изменение условий функционирования системы, появление новой информации.
Метод описания	Декларативный, процедурный, комбинированный (сочетание нескольких методов).
Метод поиска решений.	Полный перебор, имплицитный перебор, эвристический поиск.

Таблица 1.4 Меры информации в различной информационной среде

Среда решения	Измеряемая характеристика	Мера информации
Детерминированная.	Степень отличия поведения системы от заданного.	Точность достижения заданного состояния.
Случайная.	Вероятность, ожидаемая полезность.	Количество, ценность.
Нечеткая.	Степень удовлетворения рассматриваемому свойству.	Степень принадлежности.

2. ФОРМАЛИЗАЦИЯ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ

На практике задачи системного анализа и принятия решений обладают слабой структурированностью.

Для существования задачи ПР необходимо иметь хотя бы две альтернативы. Альтернативы, присутствующие в задачах принятия решений могут быть:

1. Независимыми. Независимымиявляются альтернативы, любые действия с которыми не оказывают влияние на качество других альтернатив;

2. Зависимыми. При зависимых альтернативах решение по одним из них оказывает влияние на качество других;

3. Заранее заданными. Особенностью таких задач является замкнутое и нерасширяющееся множество альтернатив;

4. Конструируемымив процессе принятия решений. Часто на основе существующих альтернатив в процессе выбора возникают либо новые альтернативы, либо совокупность требований к существующим альтернативам.

Критерии — это способ описания альтернативных вариантов решений, способ выражения различий между ними с точки зрения предпочтений ЛПР (вероятность и полезность, эффективность и стоимость и т. д.).

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

Для любых двух множеств XиY(различных или нет) существует единственное множество, состоящее из всех упорядоченных пар (x, y),,. Обозначаетсяи называетсядекартовым произведением(или просто произведением)XиY.обозначается как.

Бинарным отношением на множестве Xбудем называть произвольное подмножествоRмножества, т. е.R(R). Если:Rи,,, илито отношение можно отобразить графически (рис. 2.1).

Рис. 2.1. Графическое отображение бинарных отношений

Получившиеся фигуры будем называть ориентированным

графом, или графом, узлы — вершинами графа. Задание бинарного отношения интерпретируется как введение некоторой системы предпочтений, т. е. если,,, то подразумевается, что в определенном смысле элемент «лучше» или не «хуже» элемента.

Рассмотрим некоторые свойства бинарного отношения:

1. Отношение называется рефлексивным, если для.

2. Отношение называется антирефлексивным, если из .

3. Отношение называется симметричным (эквивалентным ), еслииз. Эквивалентное отношение рефлексивно и транзитивно.

4. Отношение называется полным (связным), если ,, или (и).

5. Отношение не являющееся полным называется частичнымилинесвязным.

6. Отношение называется асимметричным, если из двух соотношенийи, по меньшей мере, одно не выполняется. Если отношение асимметрично, то оно и антирефлексивно.

7. Отношение называется антисимметричным, если изи.

8. Отношение называется транзитивным, если таких, чтои.

9. Отношение Rназываетсяквазипорядком, еслиR— рефлексивно и транзитивно.

10. Антисимметричный квазипорядок называется порядком.

11. Отношение Rназываетсялинейным квазипорядком, еслиR— рефлексивно, транзитивно и связно.

12. Отношение Pназывается отношениемстрогого предпочтения, если оно — антисимметрично и связно.

13. Отношение Iназывается отношениембезразличия, если оно — симметрично, транзитивно и связно.

14. Инвариантным относительно линейного положительного преобразования, если для любых трех элементов, a,b,c∈Aи произвольного положительного числаαиз соотношения,A.

15. Пусть R,. ОтношениеR_B= {(a,b)∈R  a,b∈B} будем называтьсужениемRнаB.

Совокупность {A_j} непустых подмножеств множестваAбудем называть его разбиением, если они попарно не пересекаются (A_jA_i=приij) и.будем называтьклассамиразбиения.

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

Наиболее распространенным подходом к решению задач ПР является построение скалярной функции ценности(полезности)U(x) со следующими свойствами:UU(), если;UU(),если.

Если функция ценности существует, то она определяет линейный квазипорядок на множестве X. Верно и обратное, если на множествеXпостроен линейный квазипорядок, то возможно построение функции ценности (например, путем сопоставления альтернативам множестваX, расположенных в порядке убывания их предпочтительности натуральных чисел; одинаково предпочтительным альтернативам (эквивалентным) будут присвоены одинаковые числа).

Если задано X— множество сравниваемых альтернатив (объектов),R— бинарное отношение на множествеX. Тогда пару будем называтьмоделью выбора.

Определим, что будем понимать под решением задачи выбора .

Элемент будем называтьнаилучшимпоRвX, если, справедливо для всех, .Т. е..«не хуже» или не менее предпочтителен, чем любой другой элемент изXотличный от.

Пример. X = {a,b,c}, R = {(a,c), (b,b)},(рис. 2.2).

Рис. 2.2. Графическое отображение бинарного отношения

Существованию наилучшего элемента соответствует вершина, соединенная исходящими из нее стрелками со всеми остальными вершинами графа. На данном графе наилучший элемент отсутствует. Понятие «наилучшего» элемента недостаточно универсально.

Элемент будем называтьмаксимальнымпоRвX(максимальным в модели), если из . Будем обозначать множество всех максимальных элементов в через.

Граф отношения, имеющего максимальные элементы, содержит вершины, в которых каждой входящей стрелке соответствует «компенсирующая» выходящая, направленная в вершину, из которой исходит указанная входящая.

Под задачей ПР будем понимать задачу выделения множества максимальных элементов из Xпо некоторому бинарному отношениюR:.

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

Определим матрицу парных сравнений как матрицу содержащую в качестве элементов результаты сравнений элементов с номерамиi и j множества вариантов Х.

Такая матрица отражает возникающее бинарное отношение предпочтения (безразличия) на множестве. Элементы иматрицы парных сравнений размерадолжны быть равными, если соответствующие объектыиравноценны, т. е.. Если же, тои наоборот. На элементы матрицыможно наложить дополнительные калибровочные ограничения, однозначно связывающие попарно альтернативыи.

Калибровки позволяют придать оценкам различный смысл (таблица 2.1).

Рассмотрим содержание отдельных вариантов калибровок.

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

Для турнирной калибровки соответствует числу очков, набранных игрокомво встречах с игроком,const — это количество встреч.

Для степенной калибровки превосходит в парном сравнениивраз.

Для кососимметричной калибровки превосходит в парном сравнениина.

Таблица 2.1