Литература
Петровский А. Б. Теория принятия решений — М.: Издательский центр «Академия», 2009 .— 398, [1] с.: ил.
Таха Х. Введение в исследование операций. — М.: Вильямс, 2005. — 912 с.
Эддоус М., Стэнсфилд Р. Методы принятия решений. — М.: Аудит, ЮНИТИ, 1997. — 590 с.
Лабораторная работа № 4
Принятие решений в условиях неопределенности
Общие сведения
Цель работы
Научиться находить рациональные решения в условиях неопределенности вызванной конфликтом интересов.
План выполнения
Изучить теоретическую часть;
Получить задание преподавателя;
Выполнить задание 1:
Определить по заданной матрице платежей нижнюю и верхнюю цены игры. Определить, существует ли в игре равновесие в чистых стратегиях?
Привести задачу теории матричных игр к задаче линейного программирования;
Решить задачу ЛП с помощью пакета MS Excel. Определить цену игры и оптимальные стратегии для каждого из игроков.
Выполнить задание 2:
Построить матрицу платежей.
Определить по заданной матрице платежей нижнюю и верхнюю цены игры. Определить, существует ли в игре равновесие в чистых стратегиях?
Привести задачу теории матричных игр к задаче линейного программирования.
Решить задачу линейного программирования с помощью пакета MS Excel и ответить на дополнительные вопросы задания.
Составить отчёт по лабораторной работе. Отчёт должен иметь следующую структуру:
Титульный лист, который должен содержать следующую информацию:
Название университета и кафедры, ответственной за дисциплину;
Заголовок — номер и название лабораторной работы;
Подзаголовок — номер варианта и номера задач;
ФИО и должности студента и преподавателя;
«г. Санкт-Петербург, 2012 год»;
Отчёт о решении задания 1, содержащий следующее информационное наполнение:
Формулировка индивидуального задания;
Решение задачи поиска минимальной и максимальной цен игры, поиска точки равновесия в чистых стратегиях;
Снимки экрана монитора, содержащие табличную модель задачи линейного программирования;
Решение задачи поиска цены игры в смешанных стратегиях игроков, поиска вероятностей использования стратегий;
Найденное решение и выводы;
Отчёт о решении задания 2, содержащий информационное наполнение, аналогичное отчёту о решении задания 1:
Формулировка индивидуального задания;
Результат построения матрицы игры с комментариями о выбранном решении;
Решение задачи поиска минимальной и максимальной цен игры, поиска точки равновесия в чистых стратегиях;
Снимки экрана монитора, содержащие табличную модель задачи линейного программирования;
Решение задачи поиска цены игры в смешанных стратегиях игроков, поиска вероятностей использования стратегий;
Найденное решение и выводы.
Теоретическая часть
Ситуации, связанные с принятием решений, в которых два или более разумных противника имеют конфликтующие цели, рассматриваются в теории игр. Само слово «игра» применяется для обозначения некоторого набора правил и соглашений, составляющих данный вид игры, например: футбол, карточная игра, шахматы. Эти ситуации принятия решений отличаются от рассмотренных ранее, где природа, хотя и могла находиться в различных состояниях, но не преследовала каких-либо целей и, следовательно, не рассматривалась в роли соперника.
Общие понятия матричных игр
В игре заинтересованные стороны называются игроками, каждый из которых имеет некоторое множество вариантов выбора (не меньше двух, иначе он фактически не участвует в игре, поскольку заранее известно, что он предпримет). В экономике модель поведения лиц в виде игры возникает, например, при попытке нескольких фирм завоевать наиболее выгодное место на конкурентном рынке, или, например, при желании нескольких лиц (кампаний) разделить некоторое количество продукта (ресурса, финансовых средств) между собой так, чтобы каждому досталось как можно больше. Игроками в конфликтных экономических ситуациях, моделируемых в виде игры, являются производственные и непроизводственные фирмы, банки, отдельные люди и другие экономические агенты. В военных приложениях модель игры используется, например, для наилучшего выбора средств (из имеющихся или потенциально возможных) поражения военных целей противника или защиты от его нападения.
Для игр характерна неопределенность результата. Причины или источники неопределенности относятся к трем группам:
Комбинаторные источники (например игра шахматы);
Случайные факторы (например игры кости, карточные игры, где случаен расклад);
Неопределенность имеет стратегическое происхождение: игрок не знает, какого рода образа действий придерживается его противник. Здесь неопределенность исходит от другого лица.
Далее будем рассматривать игровые модели конфликтов, в которых участвуют два противника, каждый из которых имеет конечное число вариантов выбора решений. С каждой парой решений связан платеж, который один из игроков выплачивает другому (т.е. выигрыш одного игрока равен проигрышу другого). Такие игры принято называть конечными играми двух лиц с нулевой суммой.
В игре принимают участие два игрока: A и B. В распоряжении каждого игрока имеется конечное множество вариантов выбора — стратегий. Пусть  — множество стратегий игрока A,  — множество стратегий игрока B. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Т.е., когда игрок А выбирает стратегию  (свою i-ю стратегию), а игрок В — стратегию  , то результатом такого выбора становится платеж  . Поскольку стратегий конечное число, то платежи образуют матрицу размерности n x m, называемую матрицей платежей (или матрицей игры). Строки этой матрицы соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В.
Пусть два игрока А и В играют в игру, основанную на подбрасывании монеты. Игроки одновременно и независимо друг от друга выбирают герб (Г) или решку (Р). Если результаты двух подбрасываний монеты совпадают (т.е. ГГ или РР), то игрок А получает один доллар от игрока В. Иначе игрок А платит один доллар игроку В.
Для каждого из игроков возможны 2 варианта результатов: выпадения герба или решки, следовательно матрица платежей имеет размерность 2 х 2 следующего вида:
Если результаты двух подбрасываний (т.е. подбрасываний монеты игроками А и В) совпадают, то платеж в 1 доллар получает игрок А. Будем строить матрицу игры, с точки зрения игрока А, т.е. его выигрыши оценивать как положительные, а проигрыши — как отрицательные (с точки зрения В все будет наоборот и мы вполне могли бы построить матрицы платежей, ориентируясь на его точку зрения).
Если результаты подбрасывания различаются, то доллар получает В, значит платеж А равняется –1 доллар. В игре с нулевой суммой выигрыш игрока B равносилен проигрышу игрока A и равен поэтому  .
Т.о., мы построили матрицу игры, описывающую заданную ситуацию. Предполагается, что матрица игры обоим игрокам известна.
Исход игры зависит от поведения обоих игроков, которое основывается на выборе правильных стратегий игры, т.е. таких вариантов, при которых так платеж данному игроку будет наибольшим. Однако, в отличие от методов оптимизации, в теории игр игрок не может просто стремиться к максимуму, он вынужден считаться с действиями соперника. Существенно, что ни один из партнеров не знает, какую стратегию применит его противник. Таким образом, имеет место ситуация полной неопределенности, при которой теория вероятности также не может помочь игрокам в выборе решения.
Решение игр в чистых стратегиях
Рассмотрим процесс принятия решений обеими сторонами, предполагая, что оба игрока будут действовать рационально. Если игрок А не знает, как поступит его противник, то, действуя наиболее целесообразно и не желая рисковать, он выберет такую стратегию, которая гарантирует ему наибольший из наименьших выигрышей при любой стратегии противника.
|
B1
|
B2
|
B3
|
A1
|
2
|
–3
|
4
|
A2
|
–3
|
4
|
–5
|
A3
|
4
|
–5
|
6
|
Т.е. А предполагает, что В умен и будет вести себя так, чтобы доставить противнику набольшие неприятности. Тогда, при выборе 1-й стратегии, А может рассчитывать лишь на худший для себя результат –3. При выборе 2-й и 3-й стратегий он может рассчитывать на –5. Из всех возможных стратегий целесообразнее выбрать ту, что принесет максимальный возможный доход (минимальные возможные убытки, как в нашем случае). В рассматриваемом случае это стратегия 1.
Принято говорить, что при таком образе действий игрок А руководствуется принципом максиминного выигрыша. Этот выигрыш определяется формулой:
Величина  называется нижней ценой игры, максиминным выигрышем, или сокращенно максимином. Это тот гарантированный минимум, который игрок А может себе обеспечить, придерживаясь наиболее осторожной стратегии.
Очевидно, аналогичное рассуждение можно провести и за игрока В. Так как он заинтересован в том, чтобы обратить выигрыш А в минимум, он должен просмотреть каждую свою стратегию с точки зрения максимального выигрыша при этой стратегии. Поэтому внизу матрицы выпишем максимальные значения по каждому столбцу:
Все эти максимумы хороши для А, но крайне неприятны для В. Поскольку противник также учитывает нашу разумность, то выбирает из этих вариантов наименьший:
— больше этой суммы игрок В точно не потеряет. Величина  называется верхней ценой игры, или минимаксом.
Принцип осторожности, который определяет выбор партнерами стратегий, соответствующих максиминному выигрышу или минимаксному проигрышу, часто называют принципом минимакса, а стратегии, вытекающие из этого принципа, — минимаксными стратегиями. Можно доказать, что всегда  , чем и объясняются названия «нижняя цена» и «верхняя цена».
|
B1
|
B2
|
B3
|
αi
|
A1
|
2
|
–3
|
4
|
-3
|
A2
|
–3
|
4
|
–5
|
-5
|
A3
|
4
|
–5
|
6
|
-5
|
βj
|
4
|
4
|
6
|
|
Матрица игры в общем виде:
|
B1
|
B2
|
…
|
Bm
|
αi
|
A1
|
a11
|
a12
|
…
|
a1m
|
α1
|
A2
|
a21
|
a22
|
…
|
a2m
|
α2
|
…
|
…
|
…
|
…
|
…
|
…
|
An
|
an1
|
an2
|
…
|
anm
|
αn
|
βj
|
β1
|
β1
|
…
|
βm
|
|
Нижняя цена игры α = – 3; верхняя цена игры β = 4. Наша максиминная стратегия есть А1; применяя ее систематически, мы можем твердо рассчитывать выиграть не менее –3 (проиграть не более 3). Минимаксная стратегия противника есть любая из стратегий В1 и В2, применяя их систематически, он, во всяком случае, может гарантировать, что проиграет не более 4. Если мы отступим от своей максиминной стратегии (например, выберем стратегию А2), противник может нас «наказать» за это, применив стратегию В3 и сведя наш выигрыш к — 5. Но если противник выберет стратегию B3, то мы в свою очередь можем выбрать A3 и он проиграет 6 и т.д. Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии противной стороны.
Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней:
α = β
Если нижняя цена игры равна верхней, то их общее значение называется ценой игры, и обозначают γ.
Например, в игре, матрица которой приведена ниже, верхняя и нижняя цены игры оказываются равными: α = β = γ = 0,6.
Элемент 0,6, выделенный в платежной матрице, является одновременно минимальным в своей строке и максимальным в своем столбце. В геометрии точку на поверхности, обладающую аналогичным свойством (одновременный минимум по одной координате и максимум по другой), называют седловой точкой. По аналогии этот термин применяется и в теории игр. Элемент матрицы, обладающий этим свойством, называется седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.
|
B1
|
B2
|
B3
|
B4
|
αi
|
A1
|
0,4
|
0,5
|
0,7
|
0,3
|
0,3
|
A2
|
0,8
|
0,4
|
0,3
|
0,7
|
0,3
|
A3
|
0,7
|
0,6
|
0,8
|
0,9
|
0,6
|
A4
|
0,7
|
0,2
|
0,4
|
0,6
|
0,2
|
βj
|
0,8
|
0,6
|
0,8
|
0,9
|
|
Для игр с седловой точкой решение игры обладает следующим свойством: если один из игроков (например А) придерживается своей оптимальной стратегии, а другой игрок (В) будет любым способом отклоняться от своей оптимальной стратегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным. Это утверждение легко проверить на примере рассматриваемой игры с седловой точкой.
В этом случае наличие у любого игрока сведений о том, что противник избрал свою оптимальную стратегию, не может изменить собственного поведения игрока: если он не хочет действовать против своих же интересов, он должен придерживаться своей оптимальной стратегии. Т.е. пара оптимальных стратегий в игре с седловой точкой является как бы положением равновесия.
Анализируя матрицу игры, можно прийти к заключению, что если каждому игроку предоставлен выбор одной-единственной стратегии, то в расчете на разумно действующего противника этот выбор должен определяться принципом минимакса. Придерживаясь этой стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене игры α.
Решение игр в смешанных стратегиях
Возникает естественный вопрос: нельзя ли гарантировать себе средний выигрыш, больший α, если применять не одну-единственную «чистую» стратегию, а чередовать случайным образом несколько стратегий? Такие комбинированные стратегии, состоящие в применении нескольких чистых стратегий, чередующихся по случайному закону с определенным соотношением частот, в теории игр называются смешанными стратегиями.
Для матричной игры n х m обозначим через  — смешанную стратегию игрока А, где  и  . Через  обозначим смешанную стратегию игрока В, где  и  . Здесь  — вероятности использования игроком А в смешанной стратегии своих чистых стратегий  , и  — вероятности использования игроком B в смешанной стратегии своих чистых стратегий  .
Математическое ожидание выигрыша игрока А запишется в виде:
Смешанная стратегия, которая гарантирует игроку наибольший возможный средний выигрыш (или наименьший возможный средний проигрыш), называется его оптимальной смешанной стратегией. Пусть P* — смешанная стратегия игрока А, Q* — смешанная стратегия игрока В. Пара смешанных стратегий (P*, Q*), при которой M(P,Q*) ≤ M(P*,Q*) ≤ M(P*,Q), называют седловой точкой игры, а математическое ожидание выигрыша γ = M(P*, Q*) — ценой игры, причем всегда α≤γ≤β.
Сведение матричной игры к задаче линейного программирования
Общим методом нахождения решения игры любой конечной размерности является ее сведение к задаче линейного программирования. Из основного положения теории игр следует, что при использовании смешанных стратегий такое оптимальное решение всегда существует и цена игры γ находится между верхним и нижним значениями игры (α≤γ≤β).
Допустим, что смешанная стратегия игрока А складывается из стратегий  с вероятностями  (некоторые из значений вероятностей могут быть равны нулю). Оптимальная смешанная стратегия игрока В складывается из стратегий  с вероятностями  . Условия игры определяются платежной матрицей с элементами  ,  ;  . Если игрок А применяет оптимальную смешанную стратегию, а игрок B — чистую стратегию , то средний выигрыш игрока А (математическое ожидание выигрыша) составит
 .
Игрок А стремится к тому, чтобы при любой стратегии игрока В его выигрыш был не меньше, чем цена игры γ, а сама цена игры была максимальной. Такое поведение игрока А описывается следующей задачей линейного программирования:
 (игрок А стремится максимизировать свой выигрыш)
Используя обозначения  и соотношение  , получим  . Отсюда
Эта задача всегда имеет решение  , получив которое (например, с помощью надстройки Поиск решения MS Excel) можно найти цену игры  и оптимальные значения вероятностей — оптимальную смешанную стратегию игрока А.
Требуется обратить внимание на то, что матрица игры представлена в неравенствах в транспонированном виде.
Поведению игрока B соответствует двойственная задача линейного программирования:
(эквивалентно  : игрок B стремится минимизировать свой средний проигрыш)
Здесь  .
Если в исходной платежной матрице имеется хотя бы один неположительный элемент, то первым шагом в процедуре сведения игры к задаче линейного программирования должно быть ее преобразование к матрице, все элементы которой строго положительны. Для этого достаточно увеличить все элементы исходной матрицы на одно и то же число
 ,  .
При таком преобразовании матрицы оптимальные стратегии игроков не изменятся. Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры, γ нужно уменьшить на d.
|
