2

МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ И УПРАВЛЕНИЯ (ИТ-7)

ДИСЦИПЛИНА

«Теория принятия решений»

Специальность 22.02.00 «Автоматизированные системы обработки информации и управления»

Москва 2000 г.

УТВЕРЖДАЮ

Проректор по УР

__________________________

« » _______________2004 г.

АННОТАЦИЯ

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

Автор: доц. Косолапов О.И.

Научный редактор: проф. Петров О.М.

Рецензент: доц. Правоторова Н.А.

Рассмотрено и одобрено на заседании кафедры ИТ-7

«____» мая 2000 г. Зав. кафедрой ______________ О.М.Петров

«

Ответственный от кафедры за выпуск учебно-методических материалов доц. Правоторова Н.А.

Введение в курс

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

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

Можно считать, что математические методы принятия реше­ний сформировались в самостоятельный раздел математики, назы­ваемый «исследование операций», в 20 - ые годы 20 века в свя­зи с необходимостью решать сложные организационные, техниче­ские, тактические задачи, а во время второй мировой войны и от­ветственные военные задачи.

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

При этом после формализации задача принятия решений име­ет, как правило, следующие общие черты:

• в каждой задаче речь идет о некотором мероприятии, пре­следующем определенную цель

• задаются некоторые условия, влияющие на выполнение ме­роприятия, изменять которые мы не можем (ограничения)

• требуется принять решение, т.е. выбрать значения каких-то параметров управления, чтобы мероприятие в определенном смыс­ле было наиболее выгодным.

Следует договориться об определениях некоторых понятий, которые нам придется употреблять:

• операция - некоторое мероприятие (система действий), объединенное единым замыслом для достижения определенной цели. Операция всегда управляется, т.е. имеется возможность выбрать какие-то параметры, характеризую­щие способ ее организации (в широком смысле слова)

• решение - любой выбор параметров, зависящих от челове­ка, принимающего решение

• решение будет оптимальным, если оно по некоторым со­ображениям лучше всех других

• особенность рассматриваемой предметной области в том, что в конце концов решение принимается ответственным лицом (группой лиц) неформально, при этом принимаются во внимание результаты математических выкладок, а так­же соображения, не учтенные математической моделью из-за их сложности

• эффективность операции - степень ее приспособленности к выполнению стоящей задачи

• целевая функция - некоторая количественная оценка эф­фективности операции, позволяющая сравнивать различ­ные варианты организации операции (мероприятия). Целе­вая функция зависит от приложения (для задачи организа­ции промышленного предприятия целевая функция - при­быль, для задачи обеспечения надежности ЭВМ - среднее время наработки на отказ, и т.д.)

• математическая модель – формализованное, математически точное описание задачи с указанием всех сделанных упрощающих предположений.

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

В общем случае создание математической модели, которая адекватно отражает существо задачи и может быть решена сущест­вующими математическими средствами - это искусство.

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

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

1. Задачи принятия решений в условиях неопределенности

1.1. Постановка задачи

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

Прежде всего рассмотрим типовой пример задачи на принятие решений, которая может быть решена этим методом.

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

При этом заранее неизвестны некоторые обстоятельства: стоимость бурения, запасы нефти на которые можно рассчитывать (в частности, результат может быть нулевым), стоимость эксплуатации скважины и т.д.

Для принятия решения можно заказать различную информа­цию, позволяющую принять решение более обоснованно: результат сейсмической разведки (это стоит достаточно дорого), заказать кар­ту данной местности из космоса (это стоит еще дороже) и т.д. В простейшем случае можно принять решение без использования до­полнительной информации.

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

Если рассмотреть несколько подобных разных задач, можно, не вникая в содержательные особенности, выделить несколько об­щих этапов их решения:

• определение в рамках содержательной постановки задачи перечня (группы) событий, которые могут произойти

• составление списка доступных возможностей сбора инфор­мации, постановки эксперимента

• определение упорядоченной во времени последовательно­сти событий, в исходах которых можно получить определенную информацию, и последовательности действий, которые мы можем предпринять

• оценка полезности доступных действий

• определение вероятности каждого неопределенного (имеющего вероятностную природу) события

В качестве основного формального математического инстру­мента рассматриваемого метода используется так называемое «дерево решений» (диаграмма решений).

«Дерево решений» - это граф, содержащий вершины двух ти­пов. К первому типу относятся вершины, которые соответствуют моментам принятия некоторых частных решений человеком (эти вершины будем обозначать квадратиками), к другому типу - вер­шины, соответствующие проявлению случайной природы некоторых событий (эти вершины будем обозначать кружочками).

Можно использовать другое определение, дополняющее пер­вое. «Дерево целей» - это структура задачи в виде хронологически увязанных выборов (моментов принятия решений), которые должен делать человек, решающий задачу на принятие решений, и выбо­ров, определяемых случаем (случайным механизмом).

Продемонстрировать использование рассматриваемого метода и его основного рабочего инструмента - «дерево целей» можно на примере типовой задачи, сформулированной в терминологии урн (терминология, привычная в теории вероятностей).

Имеется N урн, каждая из которых может быть одного из двух типов - Q1 или Q2. Известно, что 80% урн принадлежат к ти­пу Q1, и 20% урн - к типу Q2.

В каждой урне находятся 10 шаров (красные и черные). Рас­пределение красных и черных шаров различно в зависимости от типа урны - в урнах типа Q1 4 красных и 6 черных шаров, в урнах типа Q2 9 красных и 1 черный шар.

Человеку предлагается сыграть в игру. Он случайным образом выбирает одну из N урн, и должен решить, к какому типу принад­лежит выбранная им урна.

Если человек угадывает тип урны, то он выигрывает некото­рую сумму денег, если не угадывает - проигрывает.

У участника игры имеются варианты получить некоторую ин­формацию перед тем, как определить тип урны. За дополнительную плату (8 единиц) можно случайным образом вынуть 1 шар из выбранной урны. За дополнительную плату в 12 единиц можно вы­нуть 2 шара из выбранной урны. За дополнительную плату в 9 еди­ниц можно вынуть 1 шар и решить вынуть ли ещё один шар за 4.5 единиц. При этом шар, вынутый первым, может быть возвращен в урну или нет (возможны варианты) и т.д.

В результате человек может принимать решение, выбирая из следующих вариантов:

• отказаться от игры

• без дополнительной информации определить тип урны (решение ЕО)

• вынуть один шар из выбранной урны и после этого опре­делить тип урны (решение Е1)

• вынуть два шара из выбранной урны и после этого опреде­лить тип урны (решение Е2)

• вынуть один шар из выбранной урны и решить, выбирать ли ещё один шар. После получения необходимой инфор­мации определить тип урны (решение ЕЗ).

Если участник игры определяет тип урны Q1, то он выигры­вает 40 единиц в случае «истинности», и проигрывает 20 единиц в случае «ложности» утверждения.

Если участник игры определяет тип урны Q2, то он выигры­вает 100 единиц в случае истинности, и проигрывает 5 единиц в случае «ложности» утверждения.

На рис. 1 представлена ветвь «дерева целей» задачи для вари­анта решения Е1.

На этой «веточке» некоторые узлы дерева изображены кру­жочками, что соответствует действию вероятностного механизма. Для использования дерева в решении, в таких «узлах» необходимо определить распределение вероятностей для возможных вариантов развития событий. Некоторые распределения вероятностей задаются в условиях задачи. Например, в нашей задаче задаются:

P(Q1) - вероятность выбора урны типа Q1, (P(Q1) = 0.8)

P(Q2) - вероятность выбора урны типа Q2, (P(Q2) = 0.2)

P(R/Q1) - вероятность выбрать красный шар при условии вы­бора урны типа Q1 (P(R/Q1) = 0.4)

P(B/Q1) - вероятность выбрать черный шар при условии вы­бора урны типа Q1 (P(B/Q1) = 0/6)

P(R/Q2) - вероятность выбрать красный шар при условии вы­бора урны типа Q2 (P(R/Q2) = 0.9)

P(B/Q2) - вероятность выбрать черный шар при условии вы­бора урны типа Q2 (P(B/Q2) = 0.1)

Нам необходимо определить ещё четыре величины:

P(Q1/R), P(Q1/B), P(Q2/R), P(Q2/B), соответственно вероятно­сти выбора урны типа Ql (Q2) при условии, что был вынут крас­ный (черный) шар. Эти вероятности не заданы, их можно найти с помощью известной формулы Байеса.

P(Q1/R) = P(Q1)*P(R/Q1) / (P(Q1)*P(R/Q1)+P(Q2)*P(R/Q2)) =

= 0.8*0.4 / (0.8*0.4 + 0.2*0.9) = 0.64

P(Q1/B) = P(Q1)*P(B/Q1) / (P(Q1)*P(B/Q1)+P(Q2)*P(B/Q2) =

= 0.8*0.6 / (0.8*0.6 + 0.2*0.1) = 0.96

P(Q2/R) = P(Q2)*P(R/Q2) / (P(Q1)*P(R/Q1)+P(Q2)*P(R/Q2)) =

= 0.2*0.9 / 0.5 = 0.36

P(Q2/B) = P(Q2)*P(B/Q2) / (P(Q1)*P(B/Q1)+P(Q2)*P(B/Q2)) =

= 0.2*0.1 / 0.5 = 0.04

По известной формуле полной вероятности определим значе­ние безусловной вероятности достать красный (черный) шар:

P(R ) = P(Q1)*P(R/Q1) + P(Q2)*P(R/Q2) =

= 0.8*0.4 + 0.2*0.9 = 0.5

P(B) = 0.5

Следует иметь в виду, что равенство вероятностей P(R ) и Р(В) определяется нашими исходными данными (при других исход­ных данных равенства, естественно, не будет).

Теперь мы знаем значения всех используемых в «дереве це­лей» переменных, и можно провести необходимый анализ по рас­сматриваемой методике.

1.2. Метод решения. Усреднение и свертывание.

Согласно рассматриваемой методике обработка «дерева це­лей» ведется справа налево, т.е. в первую очередь обрабатываются ветки «дерева целей», завершающие временную траекторию вариан­тов принятия решений. Потом, двигаясь справа налево от узла к уз­лу на всех ветках «дерева целей», придем к единственной (крайней слева) вершине «дерева», разветвления в которой соответствуют глобальному выбору вариантов (принятию решений), который дела­ет человек, принимающий решение.

Процедура усреднения применяется в узлах «дерева целей», в которых действует вероятностный механизм (эти узлы изображают­ся в виде «кружочков»).

Обработка «дерева целей» начинается с самых крайних пра­вых «ветвей» «дерева целей», которые соответствуют завершению возможных вариантов развития событий (игры), при этом каждому варианту поставлен в соответствие некоторый доход (цена игры). Все значения этих доходов обычно предварительно оцениваются и задаются в качестве исходных данных задачи. В нашей задаче эти значения соответственно равны (40, -20, 100, -5) условных единиц.

Процедура усреднения сводится к расчету математического ожидания случайной величины эффекта (дохода) от рассматривае­мого варианта развития ситуации, связанной с принятием решений (в нашем примере - это игра).

Например, для ветки Е1 для самых крайних правых «кружков» «дерева целей» получим соответственно:

40 * 0.64 + (-20) * 0.36= 18.4

(-5) * 0.64 + 100 * 0.36 = 32.8

40 * 0.96 + (-20) * 0.04 = 37.6

(-5) * 0.96 + 100 * 0.04 = - 0.8

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