2

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

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

ДИСЦИПЛИНА

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

(методическое пособие по выполнению курсовой работы)

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

Москва 2004 г.

УТВЕРЖДАЮ

Проректор по научной работе

__________________________

« » _______________2004 г.

АННОТАЦИЯ

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

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

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

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

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

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

«

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Формализация задачи. Дерево решений.

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

Имеется 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 ) и Р(В) определяется нашими исходными данными (при других исход­ных данных равенства, естественно, не будет).

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

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

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

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

Обработка «дерева целей» начинается с самых крайних пра­вых «ветвей» «дерева целей», которые соответствуют завершению возможных вариантов развития событий (игры), при этом каждому варианту поставлен в соответствие некоторый доход (цена игры). Все значения этих доходов обычно предварительно оцениваются и задаются в качестве исходных данных задачи. В нашей задаче эти значения соответственно равны (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

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

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

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

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

Пошаговая картина обработки «дерева целей», соответствую­щего варианту Е1 нашей задачи, представлена на рис.2. Полная обработка веток «дерева целей» для этого варианта дает оценку до­хода, составляющего 27.2 условных единиц.

Аналогичный анализ необходимо провести для всех остав­шихся вариантов рассматриваемой задачи Е0, Е2, ЕЗ. В результате получим следующие результаты:

Е0 - 28 условных единиц

El - 27.2 условных единиц

Е2 - 30.4 условных единиц

Е3 - 31.15 условных единиц.

На основании полученных результатов, проводя последнюю процедуру свертывания, следует выбрать вариант Е3.

Таким образом, человек, которому предлагается принять уча­стие в нашей игре, должен принять решение - играть по варианту Е3.