ПРАКТИЧЕСКАЯ РАБОТА №3

Модели теории игр

Понятие об игровых моделях

Теория игр занимается разработкой различного рода рекомендаций по принятию решений в условиях конфликтной ситуации. Формируя конфликтные ситуации математически, их можно представить как игру двух, трёх и более игроков, каждый из которых преследует цель максимизации своего выигрыша за счет другого игрока. Математическая модель конфликтной ситуации называется игрой , стороны, участвующие в конфликте, – игроками , а исход конфликта – выигрышем . Для каждой формализованной игры вводятся правила , т.е. система условий, определяющая:

1. варианты действий игроков;

2. объем информации каждого игрока о поведении партнеров;

3. выигрыш, к которому приводит каждая совокупность действий.

Как правило, выигрыш может быть задан количественно (например, проигрыш – 0, выигрыш – 1, ничья – ½). Игра называется парной , если в ней участвуют два игрока, и множественной , если число игроков больше двух. Игра называется игрой с нулевой суммой , если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – сознательный выбор игроком одного из возможных действий (ход в шахматной игре), случайный ход – случайно выбранное действие (выбор карты из перетасованной колоды).

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

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

Платежная матрица. Нижняя и верхняя цена игры

Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим А 1 , А 2 ,…,А m . Пусть у игрока B имеется n личных стратегий, обозначим их B 1 , B 2 ,…,B n . Говорят, что игра имеет размерность m ´ n . В результате выбора игроками любой пары стратегий А i и B j однозначно определяется исход игры, т.е. выигрыш a ij игрока А (положительный или отрицательный) и проигрыш (-a ij ) игрока В . Матрица Р=(a ij) , элементами которой являются выигрыши, соответствующие стратегиям А i и B j , называется платежной матрицей или матрицей игры .

Пример – игра «Поиск»

Игрок А может спрятаться в убежище 1 – обозначим эту стратегию за А 1 или в убежище 2 – стратегия А 2 . Игрок В может искать первого игрока в убежище 1 –стратегия В 1 , либо в убежище 2 – стратегия В 2 . Если игрок А находится в убежище 1 и его там обнаруживает игрок В , т.е. осуществляется пара стратегий (А 1 ,В 1) , то игрок А платит штраф, т.е. a 11 =–1. Аналогично получаем a 22 =–1. Очевидно, что стратегии (А 1 ,В 2) и (А 2 ,В 1) дают игроку А выигрыш 1, поэтому a 12 =a 21 =1. Таким образом, получаем платежную матрицу

Рассмотрим игру m ´ n с матрицей Р=(a ij) и определим наилучшую среди стратегий игрока А . Выбирая стратегию А i , игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий В j , для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А ).

Обозначим через a i наименьший выигрыш игрока А при выборе им стратегии А i для всех возможных стратегий игрока В (наименьшее число в i -й строке платежной матрицы), т.е. .

Среди всех чисел a i выберем наибольшее: . Назовем a нижней ценой игры , или максимальным выигрышем (максимином ). Это гарантированный выигрыш игрока А при любой стратегии игрока В . Следовательно, .

Стратегия, соответствующая максимину, называется максиминной стратегией . Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А ; выбирая стратегию B j , он учитывает максимально возможный при этом выигрыш для A. Обозначим .

Среди всех чисел выберем наименьшее иназовем b верхней ценой игры , или минимаксным выигрышем (минимаксом ). Это гарантированный проигрыш игрока В при любой стратегии игрока А . Следовательно, .

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

Статистические игры

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

Задача

После нескольких лет эксплуатации промышленное оборудование оказывается в одном из следующих состояний: В 1 – оборудование может использоваться в очередном году после профилактического ремонта; В 2 – для безаварийной работы оборудования в дальнейшем следует заменить отдельные его детали и узлы; В 3 – оборудование требует капитального ремонта или замены.

В зависимости от сложившейся ситуации В 1 ,В 2 ,В 3 руководство предприятия может принять такие решения: А 1 – отремонтировать оборудование силами заводских специалистов, что требует соответствующих затрат а 1 =6, а 2 =10, а 3 =15 ден.ед; А 2 – вызвать специальную бригаду ремонтников, расходы в этом случае составят b 1 =15, b 2 =9, b 3 =18 ден.ед; А 3 – заменить оборудование новым, реализовав устаревшее оборудование по его остаточной стоимости. Совокупные затраты в результаты этого мероприятия будут равны соответственно с 1 =13, с 2 =24, с 3 =12 ден.ед.

Задание

1. Придав описанной ситуации игровую схему, выявить ее участников, указать возможные чистые стратегии сторон.

2. Составить платежную матрицу, пояснив смысл элементов a ij матрицы (почему они отрицательные?).

3. Выяснить, какое решение о работе оборудования в предстоящем году целесообразно рекомендовать руководству предприятия, чтобы минимизировать потери при следующих предположениях: а) накопленный на предприятии опыт эксплуатации аналогичного оборудования показывает, что вероятности указанных состояний оборудования равны соответственно q 1 =0,15; q 2 =0,55; q 3 =0,3 (примените критерий Байеса); б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны (примените критерий Лапласа); в) о вероятности оборудования ничего определенного сказать нельзя (примените критерии Вальда, Сэвиджа, Гурвица). Значение параметра g=0,8 в критерии Гурвица задано.

Решение

1) Описанная ситуация представляет собой статистическую игру.

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

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

2) Составим платежную матрицу игры:

Элемент платежной матрицы а ij показывает затраты руководства предприятия, если при выбранной стратегии А i оборудование окажется в состоянии В j . Элементы платежной матрицы отрицательны, так как при любой выбранной стратегии руководству предприятия придется нести расходы.

а) накопленный на предприятии опыт эксплуатации аналогично оборудования показывает, что вероятности состояний оборудования равны q 1 =0,15; q 2 =0,55; q 3 =0,3.

Платежную матрицу представим в виде:

где , (i=1,3)

По критерию Байеса за оптимальную принимается та чистая стратегия А i , при которой максимизируется средний выигрыш статистика, т.е. обеспечивается =max .

Оптимальной стратегией по Байесу является стратегия А 1 .

б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны, т.е. = 1/3.

Средние выигрыши равны:

1/3*(-6-10-15) = -31/3 » -10,33;

1/3*(-15-9-18) = -42/3 = -14;

1/3*(-13-24-12) = -49/3 » -16,33.

Оптимальной стратегией по Лапласу является стратегия А 1 .

в) о вероятностях оборудования нельзя сказать ничего определенного.

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

.

= max (-15, -18, -24) = -15.

Таким образом, оптимальной является стратегия А 1 .

Построим матрицу рисков , где .

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

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

Описание алгоритма:

1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Представим алгоритм решения матричной игры графически.

Рисунок - Схема решения матричной игры.

Методы решения матричной игры в смешанных стратегиях

1. Решение игры через систему уравнений.
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2 , то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом.
   В случаях, когда n=2 или m=2 , матричную игру можно решить графически .
3. Решение матричной игры симплекс-методом.
   В этом случае матричная игра сводится к

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

По словам Н. Пола Лумбы: ʼʼПлатеж представляет собой денежное вознаграждение или полезность, являющиеся следствием конкретной стратегии в сочетании с конкретными обстоятельствами. В случае если платежи представить в форме таблицы (или матрицы), мы получаем платежную матрицуʼʼ, как показано на рис. 8.4. Слова ʼʼв сочетании с конкретными обстоятельствамиʼʼ очень важны, чтобы понять, когда можно использовать платежную матрицу и оценить, когда решение, принятое на ее основе, скорее всœего будет надежным. В самом общем виде матрица означает, что платеж зависит от определœенных событий, которые фактически свершаются. В случае если такое событие или состояние природы не случается на делœе, платеж неизбежно будет иным.

В целом платежная матрица полезна, когда:

1. Имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.

2. То, что может случиться, с полной определœенностью не известно.

3. Результаты принятого решения зависят от того, какая именно выбрана альтернатива и какие события в действительности имеют место.

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

В случае если вероятность не была принята в расчет, решение всœегда будет соскальзывать в направлении наиболее оптимистических последствий. К примеру, в случае если исходить из того, что инвесторы на удачной кинокартинœе могут иметь 500% на инвестированный капитал, а при вложении в торговую сеть - в самом благоприятном варианте всœего 20%, то решение всœегда должно быть в пользу кинопроизводства. При этом если взять в расчет, что вероятность большого успеха кинофильма весьма невысока, капиталовложения в магазины становятся более привлекательными, поскольку вероятность получения указанных 20% очень значительна. В случае если взять более простой пример, то выплаты при ставках в заезде на длинную дистанцию на скачках выше, поскольку выше вероятность, что не выиграешь вообще ничего.

Вероятность прямо влияет на определœение ожидаемого значения - центральной концепции платежной матрицы. Ожидаемое значение альтернативы или варианта стратегии - это сумма возможных значений, умноженных на соответствующие вероятности. К примеру, в случае если вы считаете, что вложение средств (как стратегия действий) в киоск для торговли мороженым с вероятностью 0,5 обеспечит вам годовую прибыль 5000 долл., с вероятностью 0,2 - 10 000 долл. и с вероятностью 0,3 - 3000 долл., то ожидаемое значение составит:

5000 (0,5) + 10 000 (0,2) + 3000 (0,3) = 5400 долл.

Определив ожидаемое значение каждой альтернативы и расположив результаты в виде матрицы, руководитель без труда может установить, какой выбор наиболее привлекателœен при заданных критериях. Он будет, конечно, соответствовать наивысшему ожидаемому значению. Исследования показывают: когда установлены точные значения вероятности, методы дерева решений и платежной матрицы обеспечивают принятие более качественных решений, чем традиционные подходы.

Рис. 8.5.Дерево решений.

Платежная матрица - понятие и виды. Классификация и особенности категории "Платежная матрица" 2017, 2018.

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

В целом платежная матрица полезна, когда :

1. Имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.

2. То, что может случиться, с полной определенностью не известно.

3. Результаты принятого решения зависят от того, какая именно выбрана альтернатива и какие события в действительности имеют место.

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

Подходы:

а) без учета численных значений вероятностей исходов

б) с учетом численных значений вероятностей исходов

После построения матрицы выбирается вариант действий, обеспечивает оптимальное значение критерия.

а) – Правила при выборе вариантов действий:

1)максимальное решение – максимизация максимума критерия. В качестве критерия прибыль или доход

2)максимальное решение – максимизация минимума критерия (критерий – прибыль или доход)

3)минимаксное решение – минимизация максимума критерия.

Минимаксное решение– средний по степени риска подход.

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

Подходы:

1)максимизация критериев

2)минимизация критериев

Платежная матрица с учетом вероятности исходов событий:

– вероятность i – того варианта исхода событий

– математическое ожидание критерия при выборе i – того варианта альтернатив действий

Алгоритм выбора решений:

1)Максимизация наиболее вероятных значений критерия

2)На основе правила максимальной вероятности минимизации наиболее вероятных значений критерия

3)На основе правила максимизации математического ожидания

4)На основе правила минимизации математического ожидания критерия.

35.Существование метода «Дерево решений».

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

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

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

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

Два вида «ветвей»:

Пунктирные линии, выходящие из квадратов возможных решений, движение по ним зависит от принятия решений. На соответствующей пунктирной «ветви» проставляются все расходы, вызванные решением.

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

Квадрат – узел принятия решения.

Круг – узел ветвления вариантов исходов событий.

Пунктир – ветви, движение по которым зависит от принимаемого решения

Линия – ветви, движение по которым зависит от исхода событий.

3 этапа поиска решений:

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

2.Вычисляется и проставляется на соответствующих «ветвях» вероятности каждого исхода.

3.Справа налево рассчитываются и проставляются денежные исходы каждого из узлов. Любые возникающие расходы вычитаются из ожидаемых доходов.

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

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

36.Особенности метода «Ранжирования решений» .

Данный метод предполагает 3 варианта стратегий: 1. осторожное (пессимистичное), 2. оптимистичное, 3.рациональное (рассчитано на среднее условие)

Известно, что метод платежной матрицы, без учета вероятности исхода, так же предполагает 3 варианта действий с точки зрения их рискованности.

Оптимистичной стратегией в методе платежной матрицы можно считать максимизационный подход, пессимистической - максимальный, а рациональный – минимаксный.

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

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

Пример алгоритма выбора решения по критерию пессимизма .

Мы имеем n-вариантов действий, Aj и m – вариантов, Si – (события?).

Определен.ранги bij, для каждого из решения Aj (j=1+n).

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

Коэф.важности Kj соответствует максимальному АО абсолютной величине значению ранга решения по всем ситуациям (наихудшая оценка). Kj=max bij по i.

Выбирается оптимальное решение, которое соответствует минимальному, по абсолютной величине, значению Kj всех решений (наилучшая оценка). А пессим.=min Kj по j.

Оптимистичной стратегии соответствует критерий оптимизма. В этом случае ЛПР должно рассчитывать на лучшее.

Оптимальное, по критерию оптимизма, решение определяется путем нахождения для каждого решения наилучшей оценки по всем ситуациям и последующим выборам наилучших из них (наилучшее решение). Правило выбора оптимального решения в дан.случае имеет вид: Kj=min bij по i, A =min Kj по j.

Рациональная стратегия реализации по критерию максимума среднего выигрыша.

ЛПР должно рассчитывать решение на наибольшую вероятность условия. Для реализации рациональной стратегии требуется знание вероятностей Pi исходов, событий Si.

Коэффициент важности в дан.случае представляет собой средний выигрыш, который получается при каждом решении по всем ситуациям.

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

По определению Шеннона: «МОДЕЛЬ - это представление объекта, системы или идеи в некоторой форме, отличной от самой целостности». Схема организации, к примеру, это и есть модель, представляющая ее структуру.

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

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

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

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

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

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

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

Таблица 1. Платежная матрица

В целом платежная матрица полезна, когда:

Имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.

То, что может случиться, с полной определенностью не известно.

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

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