Математика (3 сем-р) (стр. 5 )

Пара чистых стратегий (Аi, Bj) даёт оптимальное решение, когда соответствующий элемент aij является наибольшим в своём столбце и наименьшим в строке. Элемент aij называется седловой точкой. А сама игра называется игрой с седловой точкой.

Пример 2. У нас 3 вида вооружения А1, А2, А3. У противника 3 вида самолётов В1, В2, В3. Наша задача – поразить самолёт, противника – сохранить. Наш личный ход – выбор вооружения, у противника – выбор самолёта. Вооружением А1 самолёты В1, В2, В3 поражаются с вероятностями 0,5; 0,6; 0,8 соответственно. Вооружением А2 с вероятностями: 0,9; 0,7; 0,8. А3: 0.7; 0,5; 0,6.

Найти нижнюю и верхнюю чистые цены матричной игры с матрицей:

Решение. Платёжная матрица игры имеет вид: .

Нижняя цена игры . Верхняя цена . Таким образом, в данном случае . Нижняя и верхняя чистые цены матричной игры совпадают, и они равны чистой цене игры. Максиминная стратегия А2 и минимаксная стратегия В2 являются в данном случае оптимальными стратегиями, и отступать от них невыгодно ни одному из игроков.

Элемент является седловым элементом матрицы игры (он является одновременно минимальным в своей строке и максимальным в своем столбце), а сама игра – игрой с седловой точкой.

Ответ: оптимальное решение игры (А2; В2), цена игры =0,7.

Пример 3. Найти нижнюю и верхнюю чистые цены матричной игры с матрицей:

.

Решение. Чистая цена игры . Таким образом, , и в игре отсутствует седловая точка. Решение такой игры затруднено. Поясним эту мысль. Стратегия гарантирует первому игроку выигрыш не менее 4 единиц в худшем случае, когда второй игрок выбирает стратегию . Аналогично стратегия гарантирует второму игроку проигрыш не более 7 единиц в худшем случае, когда первый игрок выбирает стратегию . Первому игроку можно избрать стратегию , чтобы выиграть 9 единиц, но второй игрок выберет стратегию .

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

В.3. Решение игр в смешанных стратегиях

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

Смешанной стратегией первого (второго ) игрока называется применение чистых стратегий A1, A2,…,Am (B1, B2,…, Bn) с вероятностями р1, р2,…,рm.(q1, q2,…,qn):

.

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

Исходя из рассмотренных определений, можно сделать следующие выводы:

1.  Игра приобретает случайный характер.

2.  Случайной становится величина выигрыша (проигрыша).

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

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

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

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

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

Теорема фон Неймана (основная теорема теории матричных игр): Любая матричная игра имеет по крайней мере одно оптимальное решение в смешанных стратегиях – две оптимальные стратегии и соответствующую им цену: .

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

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

В.4. Упрощение игр

Если игра m×n не имеет седловой точки, то найти её решение, особенно при больших m и n, трудно. Иногда эту задачу можно упростить, сократив число стратегий, вычёркивая некоторые лишние: дублирующие и заведомо невыгодные.

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

Рассмотрим две стратегии первого игрока – i – ю и k – ю. При этом пусть для всех элементов соответствующих строк матрицы выполняются условия: . В этом случае говорят, что i – я стратегия первого игрока доминирует над его j – й стратегией. Если каждое неравенство выполняется как строгое, то говорят, что одна стратегия строго доминирует над другой. В любом случае из двух стратегий первый игрок предпочтет доминирующую, поскольку при использовании доминируемой стратегии его выигрыш по меньшей мере не увеличится. В этом случае можно принять .

Аналогично рассмотрим две стратегии второго игрока - j - ю и l – ю, и при этом для элементов соответствующих столбцов матрицы выполняются условия: . Для второго игрока, как известно, более выгодной является стратегия, дающая меньший проигрыш, поэтому говорят, что j - я стратегия доминирует над l - й. Если попарные неравенства являются строгими, то говорят, что одна стратегия строго доминирует над другой. При этом, естественно, .

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

Пример 4. Упростить игру, заданную матрицей: .

Решение. Начнём упрощение с игрока А. Стратегия А3 «дублирует» А1 (А3 = А1). Следовательно, любую из них можно вычеркнуть (например, А3). Далее сравнивая А1 и А2, видим, что элементы А2 меньше или равны А1 (А2 ≤ А1). Т. е. стратегия А2 для игрока А желающего выиграть как можно больше, невыгодна. Т. о. Получаем матрицу .

Для игрока В, который стремится как можно меньше проиграть, В3 невыгодна по сравнению с В4 (В3 > В4). Вычёркиваем В3. Т. о. игра 4×4 свелась к игре 2×3: .

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

Теорема. Оптимальные смешанные стратегии соответственно 1 – го и 2 – го игроков в матричной игре с ценой v будут оптимальными и в матричной игре с ценой , где .

Пример 5. В матричной игре с платежной матрицей примем b=10, C=-6 . Применим преобразование bA+c, тогда получим игру с теми же оптимальными стратегиями, но с другой эквивалентной матрицей: .

В.5. Методы решения матричных игр

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

Рассмотрим некоторые частные случаи решаемых матричных игр.

5.1. Игра, имеющая седловой элемент в платежной матрице (игра с седловой точкой)

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

5.2.Игра с платежной матрицей 2 на 2, не имеющей седлового элемента.

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

Пусть дана платежная матрица

(вокруг матрицы записаны смешанные стратегии игроков). Запишем для первого игрока два уравнения: первое – для случая применения вторым игроком только его первой стратегии, и тогда используются только элементы первого столбца матрицы, второе – для случая применения вторым игроком только своей второй стратегии, и тогда используются только элементы второго столбца матрицы. Левые части этих уравнений вычисляют математическое ожидание выигрыша первого игрока, которое равно цене игры. Эти два уравнения содержат сразу три неизвестные - , и сами уравнения при этом являются однородными, поэтому для однозначной разрешимости системы необходимо третье уравнение со свободным членом. Этим добавочным и очень важным уравнением является условие нормировки, согласно которому сумма вероятностей всех событий должна равняться единице. Таким образом, окончательно система уравнений для первого игрока выглядит так:

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

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

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

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

, решение которых даёт

Таким образом, запишем решение игры в виде:

5.3.  Графическое решение игры два на два.

1 B2

Снова рассмотрим пример 6. Отложим на оси абсцисс отрезок единичной длины. На концах этого отрезка нарисуем вертикальные оси I-I и II-II. Отложим на оси I-I значения выигрышей первого игрока при использовании им первой стратегии. На оси II-II отложим выигрыши первого игрока при использовании им второй стратегии. Соединим точки отрезками прямых. Ломаная B1 KB2 - нижняя граница выигрыша. На этой границе лежит минимальный выигрыш игрока А при любой его смешанной стратегии. Точка К, в которой этот выигрыш достигает максимума, определяет решение и цену игры. Для смешанной стратегии второго игрока можем также записать:

или .

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

5.4. Решение игр и m×2.

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

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

Пример 7. Решить игру со следующей платежной матрицей:

Решение. Эта игра имеет 2 стратегии со стороны первого игрока и три стратегии со стороны второго. Поэтому графическим способом определим одну из стратегий второго игрока, которая является неактивной. Построим график относительно стратегий первого игрока.

Из графика видно, что для второго игрока явно невыгодной является первая стратегия, которая является неактивной. Таким образом, из матрицы игры исключаем первый столбец и приходим к матрице размерности два на два следующего вида: . Для этой матрицы запишем систему уравнений - для первого игрока, и систему: - для второго игрока. Решение этих систем дает следующий результат: .

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

Пример 8. Решить матричную игру со следующей матрицей: .

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

Из графика видно, что вторая стратегия для первого игрока является невыгодной, поскольку при её применении выигрыш первого игрока (и, соответственно, проигрыш второго) будет меньше. Таким образом, активными стратегиями первого игрока будут первая и третья. Соответственно запишем системы уравнений для смешанных стратегий игроков:

Решение системы:

Решением системы будут значения Таким образом, решение игры выглядит так: .

5.5. Решение игр . Эквивалентность матричной игры паре двойственных ЗЛП

Рассмотрим матричную игру размером ().

Сведем её к задаче линейного программирования в общем виде. Имеем:

Будем считать, что . Это всегда можно сделать по теореме об эквивалентном преобразовании платежной матрицы, следовательно, можно считать цену игры положительным числом, v>0.

Для первого игрока имеем систему неравенств (с учетом того, что первый игрок стремится как можно больше выиграть, цена игры для него будет превышать v):

Введем новые переменные делением на цену игры: , тогда получим ЗЛП.

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

Аналогично имеем для второго игрока систему неравенств:

Разделив на цену игры и введя новые переменные , получим ЗЛП для второго игрока:

Здесь целевая функция задана на максимум, т. к. цена игры для второго игрока минимизируется.

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

Пример 9. Построить пару двойственных ЗЛП, эквивалентных игре, заданной платёжной матрицей: .

В.6. Игры с природой (статистические игры)

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

Природа безразлична к выигрышу.

Пусть статистик имеет m стратегий ; природа может реализовать n различных состояний .

Такие игры, в основном бывают 2-х типов: когда известны вероятности реализации состояний природы и когда неизвестны.

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

	П1	П2	…	Пn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…
Am	am1	am2	…	amn
pj	P1	P2	…	Pn

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

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

При решении опираются как на платежную матрицу, так и на матрицу рисков.

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

Матрица рисков имеет ту же размерность, что и платежная матрица:

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

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

1-й случай. Вероятности состояний природы неизвестны:

1. Критерий максимума математического ожидания выигрыша.

Критерий Лапласа: все состояния считаются равновероятными:

Тогда средний выигрыш по каждой стратегии рассчитывается как среднее арифметическое выигрышей по всем возможным состояниям природы: .

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

2. Критерий наименьшего среднего риска заключатся в подборе стратегии, обеспечивающей наименьший средний риск статистика: .

3. Максиминный критерий Вальда: Оптимальной считается стратегия Аi, при которой наименьший выигрыш статистика будет максимальным.

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

.

4. Критерий Сэвиджа: оптимальной считается стратегия, которая минимизирует величину максимального риска, т. е. из каждой строки матрицы рисков выбирается максимальный элемент, а затем среди этих элементов выбирается строка, в которой находится минимальный элемент:

5. Критерий пессимизма-оптимизма Гурвица: Оптимальной считается стратегия, найденная из условия: ,

где - «коэффициент пессимизма-оптимизма». При χ = 1 имеем критерий Вальда, или критерий крайнего пессимизма, при χ = 0 – критерий «крайнего оптимизма». Рекомендуется выбирать χ между нулем и единицей, из субъективных соображений. (Чем сложнее ситуация, тем ближе χ к единице).

II случай. Вероятности состояний природы известны.

1. Критерий максимума математического ожидания выигрыша.

Критерий Байеса: Если вероятности состояний природы известны, выбирается стратегия:

.

2. Критерий наименьшего среднего риска: Средний риск вычисляется по формуле:

,

а затем выбирается минимальный средний риск .

3. Максиминный критерий Вальда: аналогично случаю, когда вероятности состояний неизвестны.

4. Критерий Сэвиджа: также аналогично случаю 1.

5. Критерий пессимизма-оптимизма Гурвица: «коэффициент пессимизма-оптимизма» χ=0,5.

Пример 10. Торговое предприятие разработало несколько вариантов плана продажи товаров на предстоящей ярмарке с учётом меняющейся конъюнктуры рынка и спроса покупателей. Получающиеся от их возможных сочетаний величины прибыли представлены в виде матрицы выигрышей. Определить оптимальный план продажи товаров. (χ =0,6).

Величины прибыли
План продажи	Состояние спроса
П1	П2	П3	П4
А1	150	150	150	150
А2	100	300	300	300
А3	50	250	450	450
А4	0	200	400	600

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

Накопленный опыт свидетельствует о том, что вероятности этих состояний равны 0,3; 0,6 и 0,1. В зависимости от сложившейся ситуации руководство предприятия может принять такие решения:

1) провести ремонт своими силами, что потребует затрат, равных 2; 6 или 10 ед. в зависимости от состояния оборудования;

2) провести ремонт с помощью специалистов с затратами 10, 4 или 8 ед.;

3) заменить оборудование новым, на что будет израсходовано соответственно 14, 12 или 6 ед.

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

12. Для отопления помещения необходимо приобрести топливо. Расход топлива и цены на него зависят от погоды в зимнее время (мягкая, нормальная или суровая зима).

Погода	Мягкая	Нормальная	Суровая
Расход (т.)	5	10	18
Цена (руб/т.)	10	16	20

В настоящее время уголь может быть приобретен по минимальной цене (10 р/т), а излишек неиспользованного угля можно реализовать по цене 5 р/т.

Можно избрать одну из трёх стратегий в закупке угля: 5 т., 10 т. или 18 т. Предполагая, что подобных помещений имеется 100, определить оптимальную стратегию в образовании запасов.