Элементы теории принятия решений

Итак. Эта статья посвящена теории принятия решений без нейросетей и больших блоков условий. Материал я постараюсь изложить в наиболее понятной форме, будет понятно даже десятикласснику.


Сперва определения:
Проблемой называется блокада привычного действия. К примеру: Вы видите, что закончился хлеб и привычно идете в булочную. Подходите и видите, что она закрыта.
Вот это и является блокадой привычного действия. Вот здесь Вы уже ставите задачу и её решаете. Хотя вы не задумываетесь, а такой процесс происходит. Представленная далее схема нужна при программировании программы, принимающей решения.
Процесс принятия решения проходит так:
1) Идентификация проблемы
2) Разработка альтернативных способов её решения
3) Выбор оптимального альтернативного решения на основе некоторого субъективного критерия.

В примере с булочной, альтернативы будут следующими:
Пойти домой ничего не купив; Пойти в другую булочную.
А субъективные критерии:
Пойти в булочную, где хлеб повкуснее.
Пойти в булочную, где хлеб дешевле.
Пойти в булочную, которая ближе всех.
Ну вы сами можете придумать еще.

А вот процесс принятия решения уже происходит в условиях, не зависящих от субъекта(от Вас). В объективных условиях.
Таких условий три вида:
1) Условие полной определенности
2) Условие риска
3) Условие полной неопределенности

Разъяснения:
Условие полной определенности- это когда Вы знаете все возможные последствия, которые могут произойти при принятии альтернативного решения.
Например: Если пойти в булочную, где хлеб вкуснее, то надо платить 7 рублей за проезд. Если в ту, где хлеб дешевле, то ничего не потеряете. Ит.д.

Условие риска- когда не все последствия известны и могут происходить с некоторой вероятностью.
К примеру вы решили ехать в булочную, где хлеб вкуснее и не платите за проезд. Тогда с какой-то вероятностью может войти контролер и оштрафовать вас. Этот пример будет рассмотрен далее.

Условие полной неопределенности- понятно из названия, сто нам ничего не известно о последствиях, которые произойдут при принятии одного из альтернативных решений. И опять наша булочная: Мы хотим пойти в альтернативную булочную, но совсем не знаем, открыта ли она?

Дерево решения

Обозначения:
-Альтернативные способы решения: A1, A2, A3… An.
-Объективные условия, влияющие на результат: O1, O2, O3,… On
-Вероятности каждого условия(если они нужны в задаче): P(O1), P(O2),… P(On)
-Результат применения альтернативы Ai в условиях Oо : Ci,j
- Полезность Ci,j (числовое выражение исхода): b(i,j)

Корень дерева обозначается решеткой «#»
Общее дерево решений выглядит так:


В узлах дерева(которые отмечены жирными точками) может ставиться вероятность условия, содержащегося в данном узле.

Анализ дерева решений в условии риска

Разберем процесс принятия решения в условиях риска на бытовом примере: проезд в транспорте. Внимание, данный пример не является пособием к действиям

Допустим, мы каждое утро катаемся в универ на трамвае. Так как мы ездим каждый день, то вполне можем наблюдать, сколько раз в неделю появляется контролер и можем сосчитать, с какой вероятностью он появляется на неделе.
Самое простое- появляется один раз в неделю.
Значит вероятность его появления равна 1/5 (мы пять раз в неделю ездим).
Очевидно, что вероятность его не-появления равна 1- 1/5 = 4/5

Вводим обозначения:
O1- контролер есть. P(O1)= 1/5
O2- контролера нет. P(O2)= 4/5
Альтернативы:
A1- платить за проезд.
A2- не платить за проезд.

Строим дерево.


Теперь расскажу:
Решаем платить(A1). Согласитесь, при любом исходе(есть контроль или его нет) мы теряем семь рублей.
А вот во втором случае(Не платим за проезд) мы сидим и боимся, будет контроль или нет.
Случай один: контроль есть. Ну вот. Платим штраф в 20 рублей.
Случай два: контроля нет. Сэкономили семь рублей. Некоторые при построении дерева пишут вместо нуля семерку. Так это что получается, нам за то, что мы не платили, еще и денег дали? Нет. Ноль- это мы ничего не теряем.

А вот сейчас начинается самое интересное- упрощение дерева!
В условиях риска- это самая простая опреация:
Для каждого An считаем её математическое ожидание(обозначается MX). Для тех кто не знает, что это такое- прошу в книги по теории вероятностей. А формулу я приведу:
MX=P(O при С(1,1))*b(1,1) + P(O при С(1,2))*b(1,2) + … + P(O при С(n,m))*b(n,m)

В нашем дереве:
Математическое ожидание для A1 равно
MX= 1/5*(-7) + 4/5*(-7) = -7
Для A2
MX= 1/5(-20) + 4/5*(0)= -4

Строим упрощенное дерево по полученным результатам:
Вместо O, C, B для каждого A запишем его математическое ожидание.
Получилось следующее:


А теперь выбираем максимальное математическое ожидание и выбираем действие с этим ожиданием.
В нашем случае это A2, так как его ожидание (-4)

Итог: Просто так цифры сложились. При штрафе больше 35 рублей лучше за проезд заплатить. Сами посчитайте.

Анализ дерева решений в условии полной неопределенности

Это условие, при котором нам неизвестны вероятности.
Разберем на простом примере:
Фирма «Ф» разоряется.
Способы решения проблемы:
A1- выпустить новый товар
A2- модернизировать старый
При этом
O1- сотрудничать с фирмой 1
O2- сотрудничать с фирмой 2
Аналитики компании вывели, что одна из фирм будет точно с нами сотрудничать. А еще они вычислили результаты сотрудничества с каждой из фирм.
Все. Снова строим дерево решений:


Начинаем это самое дерево упрощать:
Существует четыре критерия:
1) Критерий Гурвица (критерий полного оптимизма (идиотизма))
Суть в том, что выбираем максимальное значение из С в каждом A.
Возможен так же коэффициент осторожности, который имеет смысл при значении больше ?. Но этот случай мы не будем рассматривать.
Упрощенное дерево выглядит так:

Выбираем максимальное значение исхода. Это A1.

2) Критерий Вальда (критерий полного пессимизма)
Соответственно, если в критерии Гурвица мы выбирали максимальное С, то здесь мы выбираем минимальное. Коэффициент риска возможен, но мы его не рассматриваем.
Строим дерево из которого видно, что A1 наиболее оптимальное решение.


3) Критерий Сэвиджа (критерий сожаления)
Суть этого критерия довольно туманна.
Пример:
Выбираем A1. Реализуется событие O1. Если бы мы выбрали A2, то доход был бы меньше. Поэтому сожаление равно нулю.
Выбираем A1. Реализуется O2. Если бы мы выбрали A2, то доход был бы меньше. И снова сожаление равно нулю.
Выбираем A2. Реализуется O1. Если бы выбрали A1, то доход был бы больше. Сожаление в данном случае считается по формуле: Исход события, которое принесло бы большую прибыль минус исход реализовавшегося условия.
Т.е. это 50-25=25.
Выбираем A2. Реализуется O2. Могли бы и больше прибыли получить, если бы выбрали A1. Сожаление равно 30-10=20.
Для каждого A выбираем наибольшее сожаление.
Получающееся дерево:


4) Критерий Лапласа.
Если нельзя считать вероятности событий точно или приблизительно, то все события принимают равновероятными. Итак, вероятность каждого события будет равна 1/n.
И тогда задача превращается в задачу в условиях риска. Математическое ожидание в данной задаче будет просто средним арифметическим исходов/полезностей(в зависимости от задачи). Выбираем то решение, при котором ожидание максимально.
Историческая справка: Лаплас, в отличие от предыдущих ученых работал в 18 веке.

Вот основные четыре критерия для упрощения деревьев.

Заключение.
Вот и все. Все написанное поможет при решении проблем с принятием решения.
Эта тема связана с теорией вероятностей, поэтому более полно об этом можно прочитать в книгах о теории вероятностей, о теории игр.

Статья в формате doc и картинки в присоединенном архиве.


Присоединённый файл ( Кол-во скачиваний: 12 )
 teoria.zip 32,52 Kb

Если статья твоя, резместил бы её на Вики как авторскую. В разделе алгоритмов (если он там есть, не помню, нет -- создать нужно).

Хотел бы немного покритиковать, не в обиду, а в конструктив. Хорошо?


Назвал бы "Определение множества решений". По канонам русского языка альтернатив может быть только две, хотя даже в самых хороших книгах по ТПР используют термин альтернатива, но иногда указывают на канон все же. Я тоже буду придерживаться общепринятой терминологии альтернатив.
"Разработка способа решения", считаю, звучит несколько не к месту. Ведь в ТПР занимаются выбором решения, или исследованием операций, но редко нахождением самих решений. ТПР выбирает, а не создаёт решения. Ты ведь сам придумал эти решения, творчески часто, не формально. Все же в некоторых курсах рассказывают и про это, что считаю даже правильным. Здесь это просто замечание такое.


Не совсем. Не могут, а обязательно произойдут. При полной определенности мы совершенно точно знаем, какой исход будет соответствовать каждой альтернативе. Все исходы мы знаем. Разные альтернативы могут приводить к одному и тому же исходу.


Эти связи: вкуснее -- 7 рублей, дешевле -- та же цена, совершенно точные, незыблемые.


Все исходы мы знаем. Но выбор альтернативы определяет некоторую плотность распределения вероятностей на множестве исходов. Мы знаем, с какой вероятностью может наступить каждый исход при выборе каждой альтернативы.


Здесь ты просто немного дополнил задачу. Это хорошо. Можно было сказать, например, что при походе в булочную с вкусным хлебом мы с вероятностью 0,7 заплатим за него 7 рублей (по каким прчинам так -- неважно, например, маркетинговые фичи) и с вер. 0,3 заплатим обычную цену.


Вот теперь абсолютно точно. Привел бы: вкусный хлеб может стоить столько же, а может стоить 7 рублей (дороже). Неизвестно, бабушка шепнула, неизвестная булочная и прочее.

Критерий Лапласа (Байеса--Лапласа) работает только для задач в условиях риска. Когда ничего не известно -- критерий (принцип) недостаточного основания Бернулли. Смысл тот же, вероятности одинаковые, но просто так не говорят. Сводится к простому суммированию всеъх исходов для каждой альтернативы.

Такие задачи лучше всего представлять в матричном виде. По строкам -- альтернативы, по столбцам -- состояния среды, в асмих клетках -- значимость, или полезность, исхода. В условиях риска кадый столбей будет иметь еще и свою вероятность наступления.

Критерй Сэвиджа сводится к постороению из заданной матрицы матрицы сожаления, а потом применением минимаксного критерия.

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

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

Из хорошо написанных книг рекомендую И.Г. Черноруцкого "Методы принятия решений".
Добавлено @ 23:11
Добавлю про контролера. Если решить задачу в общих числах по тому же методу, то решение таково: если вероятность появления контролера меньше отношения цена билета/штраф, то покупать билет не стоит, если больше это отношения, то стоит.
Замечу, что вы останитесь в выигрыше только в случае регулярной процедуры, а не единичного проезда. В среднем, катайся вы все 5-6 лет, при такой стратегии останитесь в выигрыше. По Питеру скажу: отношение 12/100, а контролер появляется два раза в месяц. И того платить не выгодно. Это не мой совет, а ответ ТПР.

Благодарю за комментарии. Исправлю, выложу на Вики.
Статья действительно моя. Нам читали этот курс в универе, поэтму я писал так, чтобы было понятно. Ибо там нам так прочитали, что все вскипели.

Пока вопрос с разделом Алгоритмы решается, я направил запрос Cheba, администратору Вики.

пока закрепил (на время обсуждения)

Cheba дал добро. Я уже создал заготовку. Осваивай и не бойся, если че -- подправим форматирование и прочее. Удачи.

открепляю...