Методы принятия решения Лекции, страница 2

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

1.3. Метод решения. Процедура свертывания.

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

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

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

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

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

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

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

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

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

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

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

2. Игровые методы обоснования решений

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

Методы решения таких задач достаточно сложны и рассмат­риваются в специальном разделе математики - Теория игр.

Считаем необходимым в рамках нашего курса познакомиться с основными идеями и подходами к решению задач такого типа.

Введем некоторые понятия и определения:

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

Правила игры регламентируют:

• возможные варианты действия игроков

• объем информации каждой стороны о поведении другой стороны

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

Игра развивается во времени, т.е. имеется последовательность действий игроков (игроки делают свои ходы).

Ход - выбор одного из предусмотренных правилами игры дей­ствий и его осуществление.

Различают личные и случайные ходы.

Личный ход - сознательный выбор одного из возможных дей­ствий и его осуществление.

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

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

Если число стратегий конечное, то считается, что игра - ко­нечная.

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

2.1. Платежная матрица

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

Рассмотрим конечную игру, в которой участвуют два игрока А и В. Игрок А имеет m стратегий (Al, A2, ..., Am), а игрок В - n стратегий (Bl, B2, ..., Вn).

Предположим, что при выборе игроком А стратегии Ai и иг­роком В стратегии Bj игрок А получает выигрыш aij. Тогда можно составить платежную матрицу, в которой строки соответствуют стратегиям игрока А, столбцы - стратегиям игрока В, а элементы матрицы - соответствующим выигрышам игрока А.

Рассмотрим простой пример (Игра «поиск»).

Игрок А - прячется, игрок В - ищет игрока А. В распоряжении иг­рока А есть два убежища. Если игрок В «находит» игрока А (с од­ной попытки), то игрок А платит ему 1 руб. Если Игрок В не «находит» игрока А, то он платит игроку А 1руб. Платежная матрица для такой игры будет иметь вид:

Анализ этой простой игры показывает, что, используя пла­тежную матрицу, можно получить далеко нетривиальные выводы:

• если играть только один раз, то вообще нельзя говорить об оптимальной стратегии

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

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

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

Пример 2 (Игра «Пальцы»).

Игроки А и В «выбрасывают» одновременно до 3-х (1, 2 или 3) пальцев. Игрок А выигрывает (величина выигрыша равна сумме «выброшенных» пальцев), если сумма четная и соответственно проигрывает, если сумма - нечетная. Для данной игры платежная матрица имеет вид:

Анализ этой платежной матрицы позволяет заключить:

• для каждой стратегии игрока А у игрока В есть лучшая страте­гия (для A1 - В2, для A2 - ВЗ, для A3 - В2)

• аналогично у игрока А есть лучшая стратегия игры против игро­ка В

• игрокам А и В необходимо пользоваться «смешанными страте­гиями»

2.2. Нижняя и верхняя цена игры. Принцип минимакса

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

Дополним платежную матрицу столбцом с элементами ₁, ₂, …, _m, где _i = min _ij (минимизация по j) и строкой с элементами ₁, ₂, …, _n, где _j = max _ij.минимизация по I).

 = max _i  = max min _ij.

- нижняя цена игры - так называемый максимин.

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

Аналогичные рассуждения можно провести для игрока В и ввести  = min _j и  = min max _ij

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

Принцип, определяющий игрокам выбор максиминной и ми­нимаксной стратегий, называется принципом минимакса.

Рассмотрим игру, характеризующуюся «платежной матрицей»:

Для этой игры  = -3,  = 4.

Максиминная стратегия игрока А гарантирует, что игрок А проиграет не более 3 руб., минимаксная стратегия игрока В гаран­тирует, что он проиграет не больше 4 руб.

Для рассматриваемой игры минимаксные стратегии неустой­чивы.

Действительно, пусть Игрок В выбрал стратегию В1, тогда, поняв это, игрок А выберет A3 и будет выигрывать 4 руб. На это игрок В может ответить стратегией В2 и будет выигрывать 5 руб. На это игрок А ответит стратегией А2 и будет выигрывать 4 руб. И т.д.

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

Однако, существуют игры, для которых значения максимина и минимакса совпадают. При этом минимаксные стратегии игроков А и В («чистые стратегии») являются устойчивыми стратегиями.

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

Для игры с «седловой точкой» минимаксные стратегии игро­ков А и В являются оптимальными стратегиями, т.е. если один игрок придерживается своей минимаксной стратегии, то для другого игрока не может быть выгодным отклоняться от своей минимаксной стратегии.

Для игры с «седловой точкой» минимаксные стратегии обла­дают устойчивостью.

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