- •1.1. Методы искусственного интеллекта в прикладных системах и системах принятии решений
- •1.2. Интеллектуальные информационные технологии в прикладных системах и системах принятия решений
- •1.3. Типология задач интеллектуализации систем
- •Лекция 2. Представление знаний в интеллектуальных системах
- •2.1. Модели представления знаний
- •2.2. Системы, основанные на правилах
- •2.3. Системы, основанные на автоматическом доказательстве теорем
- •2.4. Системы, основанные на автоматическом порождении (выдвижении) гипотез
- •Лекция 3. Структура и основные компоненты прикладных интеллектуальных систем
- •3.1. Прикладные системы, основанные на знаниях
- •3.2. Структура системы управления, основанной на знаниях
- •3.3. Структура интеллектуальных систем поддержки принятия решения
- •3.4. Обобщенная структура экспертной системы
- •Лекция 4. Классификация прикладных интеллектуальных систем
- •4.1. Классификация экспертных систем
- •4.2. Примеры прикладных интеллектуальных систем
- •Лекция 5. Основные понятия и определения теории принятия решений
- •5.1. Роли людей в процессе принятия решений
- •5.2. Альтернативы
- •5.3. Критерии
- •5.4. Основные этапы процесса принятия решений
- •5.5. Математические методы теории принятия решений
- •Лекция 6. Принятие решений с помощью статистической проверки гипотез
- •6.1. Статистические решения
- •6.2. Основные задачи статистических решений
- •6.3. Статистическая проверка гипотез
- •6.4. Ошибки решения
- •6.5. Решающее правило при проверке гипотез
- •Лекция 7. Байесовская и последовательная процедуры принятия решения.
- •7.1. Байесовские процедуры принятия решения
- •7.1.1. Байесовская процедура при проверке простой гипотезы
- •7.1.2. Байесовские процедуры в задаче классификации
- •7.2. Принятие решения с помощью последовательной процедуры Вальда
- •Лекция 8. Принятие решения методом дискриминантнного анализа
- •8.1. Классификация в случае, когда распределения классов определены полностью
- •8.1.1. Модель двух нормальных распределений с общей ковариационной матрицей (модель Фишера)
- •8.1.2. Модель двух нормальных распределений с разными ковариационными матрицами
- •8.1.3. Модель нескольких нормальных распределений с общей ковариационной матрицей
- •8.2. Классификация при наличии обучающих выборок
- •8.2.1. Подстановочный алгоритм в модели Фишера
- •8.2.3. Правила классификации
- •8.3. Ошибка решающего правила
- •Лекция 9. Древообразные классификаторы
- •9.1. Назначение древообразных классификаторов
- •9.1. Структура дерева классификации
- •9.3. Вычислительные задачи древообразных классификаторов
- •9.3.1. Определение качества предсказания
- •9.3.2. Выбор разбиений
- •9.3.3. Определение правила прекращения разбиения
- •Лекция 10. Деревья решений
- •9.1. Характеристики дерева решений
- •9.2. Построение дерева решений
- •Лекция 11. Методы прогнозирования
- •11.1. Анализ временных рядов
- •11.1.1. Модель временного ряда
- •11.1.2. Тренд, сезонная и циклическая компоненты
- •11.1.3. Декомпозиция временного ряда
- •11.1.4. Экспоненциальное сглаживание
- •11.2. Каузальные методы прогнозирования
- •11.3. Качественные методы прогнозирования
- •Лекция 12. Основная задача линейного программирования
- •12.1. Математическая модель основной задачи линейного программирования
- •12.2. Задача линейного программирования с ограничениями-неравенствами
- •12.3. Примеры задач линейного программирования
- •12.3.1. Транспортная задача
- •12.3.2. Задача о назначениях
- •Лекция 13. Симплекс-метода решения задачи линейного программирования
- •13.1. Характеристика симплекс–метода
- •13.2. Табличный алгоритм замены базисных переменных
- •13.3. Отыскание опорного решения основной задачи линейного программирования
- •13.4. Отыскание оптимального решения основной задачи линейного программирования
- •Лекция 14. Многокритериальные методы принятия решений при объективных моделях
- •14.1. Объединение критериев
- •14.2. Метод главного критерия
- •14.3. Метод последовательных уступок
- •14.4. Метод целевого программирования
- •14.5. Метод, использующий принцип гарантированного результата
- •14.6. Метод равных наименьших относительных отклонений
- •14.7. Процедура STEM поиска удовлетворительных значений критериев
- •Лекция 15. Выбор Парето–оптимальных решений
- •15.1. Основные определения
- •15.2. Графическая интерпретация
- •15.3. Постановка задачи
- •Лекция 16. Оценка многокритериальных альтернатив с помощью теории полезности
- •16.1. Теория полезности
- •16.2. Принятие решения на основе значения ожидаемой полезности
- •16.3. Многокритериальная теория полезности (MAUT)
- •Лекция 17. Сравнение альтернатив методом аналитической иерархии
- •17.1. Основные этапы метода аналитической иерархии
- •17.2. Декомпозиция задачи
- •17.3. Попарное сравнение критериев и альтернатив
- •17.4. Свойства идеальной матрицы сравнений
- •Лекция 18. Приоритеты для критериев и альтернатив и выбор наилучшей альтернативы в методе анализа иерархий
- •18.1. Вычисление собственных характеристик обратно симметричной матрицы
- •18.2. Вычисление величины приоритетов
- •18.3. Определение наилучшей альтернативы
- •18.4. Проверка согласованности
- •18.5. Пример применения метода анализа иерархий
- •Лекция 19. Оценка многокритериальных альтернатив методами ELECTRE
- •19.1. Этапы подхода, направленного на разработку индексов попарного сравнения альтернатив
- •19.2. Свойства бинарных отношений
- •19.3. Метод ELECTRE I
- •19.4. Метод ELECTRE II
- •19.5. Метод ELECTRE III
- •Лекция 20. Основные понятия и математическая модель игровых методов обоснования решений
- •20.1. Основные понятия теории игр
- •20.2. Математическая модель игры
- •20.3. Нижняя и верхняя цена игры. Принцип минимакса
- •Лекция 21. Методы решения игр
- •21.1. Решение игры в чистых стратегиях
- •21.2. Решение игры в смешанных стратегиях
- •21.3. Упрощение игр
- •21.4. Решение игры 2х2
- •21.5. Графический метод решения (2х2)-игр
- •Лекция 22. Игры 2 х п
- •Лекция 23. Решение игр т х 2 и т х п
- •23.1. Решение игр т х 2
- •23.2. Решение игр т х п
- •Лекция 24. Критерии принятия решений в условиях риска и неопределенности
- •24.1. Основные понятия. Математическая модель
- •24.3. Максиминный критерий Вальда
- •24.4. Критерий минимаксного риска Сэвиджа
- •24.5. Критерий пессимизма-оптимизма Гурвица
- •Литература
Лекция 16. Оценка многокритериальных альтернатив с помощью теории полезности
16.1. Теория полезности
Теория полезности – это раздел теории принятия решений, который связан с задачей измерения величины выигрыша лицом, принимающим решения. Полезность – это цена результата, величина, которую в процессе выбора максимизирует личность.
Задачи принятия решений с применением полезностей и вероятностей состоят в следующем: человек выбирает какие-то действия в условиях, когда на получаемый результат (исход) действия влияют случайные события. Имея некоторые знания о вероятностях этих событий, человек может рассчитать наиболее выгодный для себя вариант действий.
Известно, что в условиях рационального выбора, имеющего аксиоматическое обоснование, существует числовая функция полезности U, определенная на множестве исходов и имеющая следующие свойства [12]:
1)исход х предпочтительнее исхода у тогда и только тогда, когда U(x) ≥ U(y);
2)U(x, p, y) = р U(x) + (1 – р) U(y), р – вероятность исхода.
Отсюда следует, что нужно выбирать вариант (действие) с наибольшей полезностью.
16.2. Принятие решения на основе значения ожидаемой полезности
Рассмотрим задачу принятия решения на основе значения ожидаемой полезности. Исходные данные для задачи приведены в табл. 16.1. Лицу, принимающему решения, необходимо выбрать один из вариантов капиталовложений (А, В, не делать капиталовложений) при различных состояниях фондовой биржи: 1) индекс Доу–Джонса растет, 2) индекс Доу–Джонса падает, 3) индекс Доу–Джонса остается без изменений. Каждому из состояний фондовой биржи соответствуют вероятности 0,2; 0,3 и 0,5. В табл. 16.1 указаны значения выигрыша ЛПР при выборе любого из вариантов действия (знак минус означает проигрыш).
Таблица 16.1 Варианты капиталовложений при различных состояниях фондовой биржи
Возможные |
|
Состояния фондовой биржи |
||
альтернативы |
Рост |
|
Падение |
Без изменений |
|
(р = 0,2) |
|
(р = 0,3) |
(р = 0,5) |
Капиталовложения А |
100000 |
|
– 40000 |
5000 |
Капиталовложения В |
90000 |
|
– 50000 |
45000 |
Не делать капитало- |
0 |
|
0 |
0 |
вложений |
|
|
|
|
Используя платежную таблицу 16.1, припишем значения полезности наибольшему выигрышу (100000) и наибольшему проигрышу (– 50000). Абсолютная величина полезности не имеет значения, важно лишь то, чтобы наибольшему выигрышу соответствовала наибольшая величина полезности, а наименьшему выигрышу – наименьшая. Для простоты установим U(100000) = 10, U(–50000) = 0. Теперь мы можем определить величину полезности для каждого выигрыша в таблице. Для этого мы должны узнать у ЛПР, какой вариант из двух он предпочтет:
1.Гарантированный выигрыш 90000.
2.Лотерею с выигрышем 100000 с вероятностью р, либо проигрышем –50000 с вероятностью 1 – р. Лотереей называется игра с двумя исходами: исходом х, получаемым с вероятностью р, и исходом у, получаемым с вероятностью 1 – р.
80
Если р = 1, то ЛПР предпочтет лотерею, т.е. предпочтет выигрыш в 100000 выигрышу в 90000. Будем уменьшать величину р, пока не наступит состояние безразличия между двумя возможностями выбора. Поскольку вероятность р выиграть 100000 падает, а вероятность (1– р) проигрыша растет, то лотерея начинает выглядеть менее привлекательно. Наконец, будет достигнуто некоторое значение вероятности, при которой ЛПР больше не будет отдавать предпочтение лотерее и будет оставаться безразличным при выборе между двумя
вариантами действия. Это значение называется вероятностью безразличия Р .
Допустим, что ЛПР стало безразличным при Р = 0,95. Это означает, что ЛПР безразлично между гарантированным выигрышем 90000 и 95%-ным шансом выиграть
100000 (55%-ным шансом потерять 50000).
Теперь выберем следующий по величине выигрыш 45000 и повторим опыт. Зададим вопрос ЛПР, что он предпочтет: гарантированный выигрыш 45000 или лотерею с установленной вероятностью выигрыша 100000. Далее будем поступать, как в рассмотренном выше шаге, пока не наступит состояние безразличия. Пусть вероятность безразличия для 45000 равна 0,84.
Повторим эти действия для всех выигрышей табл. 16.1, устанавливая значение вероятности безразличия в каждом случае. Задав эти вероятности, мы можем определить величину полезности всех выигрышей. Полезность выигрыша U для наилучшего и наихудшего случая определится как
U(Выигрыша) = Р · U(100000) + (1 – Р )·U(–50000).
Полезность U(45000), которой соответствует вероятность безразличия 0,84, равна
U(45000) = 0,84·10 + (1 – 0,84) · 0 = 8,4.
Все вычисленные величины полезностей приведены в табл. 16.2.
Таблица 16.2
Значения полезностей и вероятностей безразличия
Выигрыш |
Вероятность |
Полезность |
|
безразличия |
|
100000 |
– |
10,0 |
90000 |
0,95 |
9,5 |
45000 |
0,84 |
8,4 |
5000 |
0,79 |
7,9 |
0 |
0,72 |
7,2 |
–40000 |
0,22 |
2,2 |
–50000 |
– |
0 |
Подставляя эти значения полезностей в табл.16.1, получим табл. 16.3.
|
Полезность выигрышей |
Таблица 16.3 |
|||
|
|
|
|||
|
|
|
|
|
|
Возможные |
|
Состояния фондовой биржи |
|||
альтернативы |
Рост |
|
Падение |
Без изменений |
|
|
(р = 0,2) |
|
(р = 0,3) |
(р = 0,5) |
|
Капиталовложения А |
10 |
|
2.2 |
7,9 |
|
Капиталовложения В |
9,5 |
|
0 |
8,4 |
|
Не делать капитало- |
7,2 |
|
7,2 |
7,2 |
|
вложений С |
|
|
|
|
|
Теперь можно рассчитать ожидаемую полезность ЕU(·) каждого из вариантов капиталовложений:
81
ЕU(А) = 0,2 · 10 + 0,3 · 2,2 + 0,5 · 7,9 = 6,61, ЕU(В) = 0,2 · 9,5 + 0,3 · 0 + 0,5 · 8,4= 6,1, ЕU(С) = 0,2 · 7,2 + 0,3 · 7,2 + 0,5 · 7,2 = 7,2.
На основании этих значений ожидаемой полезности ЛПР может выбрать подходящую альтернативу, так как функция полезности является мерой относительного предпочтения для ЛПР.
На рис. 16.1 показаны функции полезности для трех типов ЛПР: 1) ЛПР, которое согласно рисковать, 2) ЛПР, которое избегает риска, 3) лицо, принимающее решения с нейтральным риском.
Полезность
|
1 |
3 |
2 |
Выигрыш
Рис. 16.1. Функция полезности: 1 – для ЛПР, которое согласно рисковать, 2 – ЛПР, которое избегает риска, 3 – лицо, принимающее решения с нейтральным риском.
Кривая 1 имеет плоский участок, указывающий, что полезность не растет слишком быстро при высоких денежных значениях. Для кривой 2 (случай, когда ЛПР идет на рискованное предприятие) полезность возрастает, когда рискуют большими суммами. Для линейной функции полезности 3 доказано, что максимизация ожидаемого денежного выигрыша дает такое же решение, как и максимизация ожидаемой полезности. Если размер возможного выигрыша в задаче принятия решения на слишком большой, довольно часто используется линеаризация функции полезности вида 1 или 2, а затем применяется критерий Байеса (см. лекц. 24).
16.3. Многокритериальная теория полезности (MAUT)
Многокритериальная теория полезности MAUT (Multi-Attribute Utility Theory) представляет собой дальнейшее развитие теории полезности и позволяет решить следующие задачи [12]:
•построить функцию полезности, имеющую математическое обоснование;
•проверить в диалоге с ЛПР некоторые условия, определяющие форму этой функции;
•упорядочить по качеству все возможные альтернативы и произвести их оценку на основании найденного решающего правила.
Наиболее целесообразно применять методы MAUT для задач с большим числом альтернатив.
Основные этапы подхода MAUT. Перечислим этапы решения задачи с помощью многокритериальной теории полезности.
1.Разработать перечень критериев.
2.Построить функции полезности по каждому из критериев.
82
3.Проверить некоторые условия, определяющие общий вид функции полезности.
4.Построить зависимость между оценками альтернатив по критериям и общим качеством альтернативы.
5.Оценить все имеющиеся альтернативы и выбрать наилучшую.
Аксиоматическое обоснование [12]. Так же, как и классическая теория полезности, многокритериальная теория полезности имеет аксиоматическое обоснование. Условия, которым должна удовлетворять функция полезности, формулируются в виде аксиом. Если условия удовлетворяются, дается доказательство существования функции полезности. В MAUT эти условия можно разделить на две группы: 1) аксиомы общего характера, которые использовались в теории полезности и 2) аксиомы независимости, специфичные для MAUT.
Рассмотрим аксиомы первой группы.
1.Аксиома полноты, утверждающая, что может быть установлено отношение между полезностями любых альтернатив: либо одна из них превосходит другую, либо они равны.
2.Аксиома транзитивности: из превосходства полезности альтернативы А над полезностью альтернативы В и превосходства полезности В над полезностью С следует превосходство полезности альтернативы А над полезностью альтернативы С.
3.Для соотношений между полезностями альтернатив А, В, С, имеющими вид
U(А) > U(В) > U(С), 0 ≤ α ≤ 1; 0 ≤ β ≤ 1,
можно найти такие числа, что:
αU(А) + (1 – α) U(С) = U(В),
(1 – β) U(А) + β U(В) > U(В).
Аксиома 3 основана на предположении, что функция полезности непрерывна и что можно использовать любые малые части полезностей альтернатив.
Приведем несколько условий независимости, относящихся к аксиомам второй группы. 1. Независимость по разности. Предпочтения между двумя альтернативами, отличающимися лишь оценками по порядковой шкале одного критерия С1, не зависят от
одинаковых оценок по другим критериям С2, …, Ст.
2. Независимость по полезности. Критерий С1 называется независимым по полезности от критериев С2, …, Ст, если порядок предпочтения лотерей, в которых меняются лишь уровни критерия С1, не зависит от фиксированных значений по другим критериям.
3. Независимость по предпочтению. Два критерия С1 и С2 независимы по предпочтению от других критериев С3, …, Ст, если предпочтения между альтернативами, различающимися лишь оценками по С1, С2 не зависят от фиксированных значений по другим критериям.
Первые два условия независимости относились к независимости одного критерия от остальных, третье условие – к независимости пары критериев от прочих.
Основная теорема. Если аксиомы первой группы и некоторые условия независимости выполнены, то из этого следует строгий вывод о существовании многокритериальной функции полезности в определенном виде.
Можно сформулировать теорему, на которой основаны практические методы оценки альтернатив: если условия независимости по полезности и независимости по предпочтению выполнены, то функция полезности является аддитивной
m |
m |
U(х) = ∑wiUi (x) при |
∑wi = 1 |
i=1 |
i=1 |
либо мультипликативной |
|
m |
m |
1 + k U(х) =∏(1+ kwiwjUi (x)) при ∑wi ≠ 1, |
|
i+1 |
i=1 |
83