Принятие решений в условиях неопределённости и риска. Классификация оптимизационных задач

Тема 5. Принятие решений в условиях неопределённости и риска Лекция 12 2 Классификация оптимизационных задач Проблема принятия решения нет Одно лицо да Одна цель да нет нет Многокритериальная оптимизация Определенность Принятие решения в условиях неопределенности и риска да Линейность нет Нелинейное программирование да нет Целочисленность Теория игр Линейное программирование 3 да Целочисленное программирование Теория принятия решений — часть теории управления, изучающая способы анализа, выработки образа действий в зависимости от целевой установки и условий, в которых осуществляется деятельность, располагаемых ресурсов, состава исполнителей. 4 Теория принятия решений  область исследования, вовлекающая понятия и методы математики, статистики, менеджмента и психологии;  изучает закономерности выбора людьми путей решения разного рода задач;  исследует способы поиска наиболее выгодных из возможных решений. 5 Классификация процесса принятия решений  Принятие решений в условиях определенности (ЗЛП, ЦЧП, ЗНЛП)  Принятие решений в условиях риска (исходные данные могут быть описаны с помощью вероятностных распределений)  Принятие решений в условиях неопределенности  Принятие решений в условиях конфликта (теория игр) 6 Задачи принятия решений в условиях риска (УР) – это задачи принятия решений, в которых исходные данные (стоимости альтернатив) могут быть описаны с помощью вероятностных распределений Решения ЛПР d1 d2 … dm 7 Состояния среды s1 s2 … sn Исходные данные в задаче принятия решений в условиях риска Исход:  di , s j  Решения ЛПР Состояния среды s1 s2 … sn d1 d2 h(d1,s1) h(d1,s2) … h(d1,sn) h(d2,s1) h(d2,s2) … h(d2,sn) … … h(dm,s1) … h(dm,s2) … … … h(dm,sn) dm ℎ(𝑑𝑖 , 𝑠𝑗 ) – полезность принятого решения 𝑑𝑖 , 𝑖 = 1, … , 𝑚, 8 при реализации состояния 𝑠𝑗 , 𝑗 = 1, … , 𝑛. Исходные данные в задаче принятия решений в УР Решения ЛПР Состояния среды s1 s2 … sn d1 d2 h(d1,s1) h(d1,s2) … h(d1,sn) h(d2,s1) h(d2,s2) … h(d2,sn) … … … … … dm h(dm,s1) h(dm,s2) … h(dm,sn) Вероятности p(s1) p(s2) … p(sn) 𝑝(𝑠𝑗 ) – вероятность реализации состояния 𝑠𝑗 , 𝑗 = 1, … , 𝑛. 9 Задачи принятия решений в условиях риска (УР). Пример Брать зонт? Состояния среды Решения ЛПР 10 Идёт дождь Нет дождя Взять зонт Не брать зонт 10 5 10 5 Прогноз погоды 0,3 0,7 Полезность и риск принятого решения ℎ 𝑑𝑖 , 𝑠𝑗 – полезность исхода 𝑑𝑖 , 𝑠𝑗 , 𝑖 = 1, … , 𝑚; 𝑗 = 1, … , 𝑛. Математическое ожидание полезности решения 𝑑𝑖 (в случае дискретной 𝑠): n H (di )   h(di , s j ) p ( s j ), i  1,..., m Ожидаемая полезность j 1 Дисперсия решения 𝑑𝑖 (в случае дискретной 𝑠): D(di )    h(di , s j )  H (di )  p( s j ), i  1,..., m n 11 j 1 2 Риск Задача принятия решений в УР – постановка 1 n H (di )   h(di , s j ) p ( s j )  max j 1 D(di )    h(di , s j )  H (di )  p( s j )  min n 2 j 1 Двухкритериальная задача (если ЛПР учитывает риск) 12 Задача принятия решений в УР – постановка 2 n H (di )   h(di , s j ) p(s j )  max j 1 Однокритериальная задача (ЗЛП или ЗНЛП) (если ЛПР не учитывает риск) Задача принятия решения в условиях риска – это задача максимизации решения. 13 ожидаемой полезности принятого Пример 1 100 урн Урна типа I Урна типа II 2 5 10 5 70 штук ? 14 10 8 30 штук – Урна типа I или типа II? Пример 2 Альтернативы Состояние среды s2 d1 d2 d3 $500 -$200 -$150 $1000 $0 $0 Вероятности состояния среды 0,7 0,3 𝑑1 – «урна I типа» 𝑑2 – «урна II типа» 𝑑3 – «отказ от игры» 15 s1 Ожидаемая полезность 𝑠1 – «урна I типа» 𝑠2 – «урна II типа» Пример 1 n H (di )   h(di , s j ) p ( s j )  max j 1 H  d1   500  0, 7  (200)  0,3  290 H  d 2   (150)  0, 7  1000  0,3  195 H  d3   0  0, 7  0  0,3  0 16 Оптимальное решение: 𝒅𝟏 – «урна I типа» Пример 1 D(di )    h(di , s j )  H (di )  p( s j )  min n 2 j 1 D  d1   (500  290) 2  0, 7  (200  290) 2  0,3  102900 D  d 2   (150  195) 2  0, 7  (1000  195) 2  0,3  277725 Оптимальное решение: 𝒅𝟑 – «отказ от игры» 17 Пример 2 100 урн Урна типа I Урна типа II 2 5 10 5 70 штук ? 18 10 8 30 штук Достать один шар? – $50! – Урна типа I или типа II? Дерево решений  Дерево решений – это ориентированный граф, исходящий из одной вершины (основание дерева), соответствующий исходной точке процесса принятия решения.  Граф – это математический объект, определяемый двумя множествами: множеством узлов 𝑁 = 𝑥 , 𝑁 = 𝑛, и множеством рёбер 𝐺 = 𝑁 × 𝑁 = (𝑥, 𝑦) 𝑥 ∈ 𝑁, 𝑦 ∈ 𝑁 .  Граф называется ориентированным, если все его рёбра имеют направление (ориентированы). 19 Вершины дерева принятия решений  Терминальные (концевые) вершины: никакие рёбра не выходят; количественные оценки варианта решения. $100  Вершины принятия решения: выходят рёбра, d1 соответствующие возможным альтернативам.  Случайные вершины: выходят вероятностные 20 рёбра, соответствующие исходам случайных событий; указываются вероятности данных исходов. d2 0,2 0,1 0, 7 Этапы решения (1) 1. Выписывается дерево решений слева направо (в направлении принятия решения). При этом на граф наносятся все известные числовые характеристики. 2. Оценивается дерево решений последовательно по шагам в обратном направлении, т.е., начиная с терминальных вершин.  Для случайных вершин – последовательно вычисляются математические ожидания выигрышей.  Для вершин принятия решения – последовательно 21 вычисляются оценки лучших альтернатив. Этапы решения (2) 3. Последний этап – это определение оптимального решения. Для нахождения оптимального решения дерево еще раз просматривается в прямом направлении, отмечая наилучшие альтернативы в точках принятия решения. Метод тройной прогонки 22 Дерево решений 1 23 Дерево решений 2 24 Теорема 1. (Формула полной вероятности) 25 Теорема 2. (Формула Байеса) 26 Вероятности для Дерева 2. Вершина 2 W = «достали белый шар» B = «достали чёрный шар» P W / s1   0,5 P W / s2   0, 2 P  B / s1   0,5 P  B / s2   0,8 P W   P W / s1   P  s1   P W / s2   P  s2   0,5  0, 7  0, 2  0,3  0, 41 P  B   P  B / s1   P  s1   P  B / s2   P  s2   0,5  0, 7  0,8  0,3  0,59 27 Вероятности для Дерева 2. Вершины 9, 10 W = «достали белый шар» B = «достали чёрный шар» P W / s1   0,5 P W / s2   0, 2 P  B / s1   0,5 P  B / s2   0,8 P W   0, 41 P  B   0,59 P W / s1   P  s1  P  s1 / W   P W  28 P  s2 / W   P W / s2   P  s2  P W  0,5  0, 7   0,854 0, 41  0, 2  0,3  0,146 0, 41 Вероятности для Дерева 2. Вершины 12, 13 W = «достали белый шар» B = «достали чёрный шар» P W / s1   0,5 P W / s2   0, 2 P  B / s1   0,5 P  B / s2   0,8 P W   0, 41 P  B   0,59 P  B / s1   P  s1  P  s1 / B   P  B 29 P  s2 / B   P  B / s2   P  s 2  P  B 0,5  0, 7   0,593 0,59  0,8  0,3  0, 407 0,59 Выигрыши для Дерева 2. Терминальные вершины 19 : $500  $50  $450 20 : $200  $50  $250 21: $150  $50  $200 $50 22 : $1000  $50  $950 23 : $500  $50  $450 24 : $200  $50  $250 25 : $150  $50  $200 $50 30 26 : $1000  $50  $950 Оценка Дерева 2 9 : $450  0,854  ($250)  0,146  $347,8 10 : $200  0,854  $950  0,146  $32,1 12 : $450  0,593  ($250)  0, 407  $165,1 13 : $200  0,593  $950  0, 407  $268, 05 2 : $347,8  0, 41  $268, 05  0,59  $300, 75 31 Оптимальное решение. Пример 2 В узле 1 игрок должен выбрать альтернативу «Эксперимент». 2. Если игрок достал белый шар, то он выбирает альтернативу «урна I типа». 1. Если игрок достал чёрный шар, то он выбирает альтернативу «урна типа II». Математическое ожидание выигрыша составит $300,75 33 Домашнее задание № 5 Решите задачу с помощью дерева решений. (Таблицу строить НЕ надо!) СРОК: 19.05.2020 34