Теория принятия решений
ЛПР, управляющий своими стратегиями (ходами) А1, А2, …, Аn, и его противник, управляющий стратегиями (ходами) В1, В2, …, Вn в данной ситуации называются игроками.
Элементы матрицы аij , заданной в условии, называются выигрышами (платежами) игрока А. А вся матрица называется матрицей платежей.
Далее возможны два случая. Если в матричной игре задана одна платежная матрица, то естественно предположить, что выигрыши первого игрока будут являться проигрышами второго игрока. Такая антагонистическая ситуация называется матричной игрой с нулевой суммой. Цель игры для первого игрока (ЛПР) – побольше выиграть, а для второго игрока – поменьше проиграть. Иными словами, целью игры является определение оптимальной стратегии для каждого игрока – такой стратегии, при которой выигрыш первого игрока будет максимальным, а проигрыш второго игрока будет минимальным.
Однако, такая ситуация бывает не всегда. Зачастую в жизни ваш противник преследует сугубо свои цели, определенные своими выигрышами. В этом случае матричная игра задается двумя платежными матрицами. Или для краткости элементы одной платежной матрицы состоят из двух чисел: (аij, bij). Такая ситуация называется матричной игрой с ненулевой суммой. И для первого и для второго игроков цель игры – побольше выиграть.
Очевидно, что рассмотренная матричная игра предполагает, что каждый игрок делает только по одному ходу. Естественно, что многие конфликтные ситуации предполагают по нескольку ходов каждого игрока. Такие игры рассматриваются пошагово и решаются методами динамического программирования. На каждом отдельном шаге такая игра рассматривается как игра с одним ходом.
Матричные игры для двух игроков с нулевой и ненулевой суммой достаточно хорошо изучены и для них разработана теория оптимального поведения игроков.
Однако в жизненной практике в конфликтных ситуациях зачастую участвуют более чем две стороны. Чем больше игроков – тем больше проблем. Такие игры менее изучены и здесь есть просторное поле для новых фундаментальных научных исследований.
Несмотря на несколько легкомысленное звучание основных терминов, теория игр является строго научной дисциплиной с точными математическими выкладками.
На протяжении всего своего исторического пути развития человечество ежедневно сталкивается с конфликтными ситуациями: политическими, военными, экономическими, социальными и прочими, которые проявляются как в глобальных, так и в малых (вплоть до личных) формах. И если бы Человеку хватило бы ума в конфликтных ситуациях пользоваться не силой, не надеждой на "авось", а математикой, то жизнь наверняка была бы другой. Будем надеяться, что новое поколение, усвоив курс "Исследование операций" J, изменит жизнь к лучшему!
Итак, рассмотрим игру, в которой ЛПР противостоит "думающий" противник.
Возможны такие случаи:
Ходы игроками делаются одновременно.
Первым ходит игрок 2 – противник, но игрок 1 – ЛПР, не имеет информации о ходе противника.
Первым ходит игрок 2 – противник, но игрок 1 – ЛПР, знает о ходе противника.
Первым ходит игрок 1, но игрок 2 не имеет информации о ходе противника.
Первым ходит игрок 1, но игрок 2 знает о ходе противника.
Очевидно, что случаи 1), 2) и 4) идентичны – никто из игроков не знает о ходе противника ничего.
Рассмотрим случай 3). Так как ЛПР имеет полную информацию о ходе противника, то мы имеем ситуацию принятия решения в условиях полной определенности. Как уже отмечалось выше, такими задачами занимается математическое программирование.
Рассмотрим случай 5). Так как ЛПР ходит первым, то его противник наверняка выберет самую худшую для ЛПР стратегию. Поэтому в такой ситуации ЛПР необходимо принимать решение о своем ходе согласно принципу наибольшей осторожности, т.е. согласно принципу максимина. Это утверждение однозначно, легко математически доказывается и не должно подвергаться сомнению ни в каких жизненных ситуациях.
Итак, содержательны по своей сути только случаи 1), 2) и 4), которые сводятся к одному случаю. Это как мы видим, принятие решения в условиях неопределенности.
4.2 Матричные игры, разрешимые в чистых стратегиях
Рассмотрим парную конечную антагонистическую игру. Пусть игрок А располагает m личными стратегиями, которые обозначим А1, а2 ..., Аm. Пусть у игрока В имеется n личных стратегий, обозначим их В1, В2, ,.., Вn. Говорят, что игра имеет размерность m х n . В результате выбора игроками любой пары стратегий Аi и Вj (i = 1,2 …, m; j = 1,2, …, n).
Однозначно определяется исход игры, т.е. выигрыш аij игрока А (положительный или отрицательный) и проигрыш (-аij) игрока В . Предположим, что значения аij известны для любой пары стратегий (Аi Вj). Значения этих выигрышей заданы в платежной матрице
Строки этой таблицы соответствуют стратегиям игрока А , а столбцы – стратегиям игрока В .
С помощью хорошо нам знакомого принципа максимина найдем гарантированный наибольший выигрыш для игрока А:
![]()
Найденное число a называется нижней ценой игры.
Стратегия, соответствующая максимину, называется максиминной стратегией – она будет оптимальной стратегией игрока А.
Посмотрим на эту ситуацию с точки зрения второго игрока: ему необходимо уменьшить свои потери. В таком случае критерию максимина превратится в минимаксный и гарантированный наименьший проигрыш для игрока В будет таким:
![]()
Найденное число в называется верхней ценой игры
Стратегия, соответствующая минимаксу, называется минимаксной стратегией – она будет оптимальной стратегией игрока В.
Причем, для нижней и верхней цены игры всегда справедливо неравенство:
![]()
Если нижняя и верхняя цены игры совпадают, то общее значение верхней и нижней цены игры a = в = n называется чистой ценой игры, или ценой игры. Элемент платежной матрицы, в котором достигается чистая цена игры, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз – в другом). Найденные оптимальные стратегии игроков А и В в данном случае называются чистыми стратегиями.
Матричная игра с платежной матрицей, имеющей седловую точку, называется игрой, разрешимой в чистых стратегиях. При этом очевидно, что решение игры обладает устойчивостью, т.е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии. Оба игрока находятся в "положении равновесия", из которого не выгодно выходить каждому.
Рассмотрим числовой пример.
Пусть имеем игру с платежной матрицей:

Проверим, имеет ли наша матричная игра седловую точку? Для этого используем принцип максимина.
Дополним исходную матрицу справа еще одним столбцом, а снизу – еще одной строкой. В них будем заносить значения минимальных элементов каждой строки и значения максимальных элементов каждого столбца соответственно:
Найдем нижнюю цену игры. Выигрыш игрока А:
a =
= 4он достигается
в третьей строке.
Найдем верхнюю цену игры. Выигрыш игрока В:
в =
= 4 он достигается
во втором столбце.
Как видим, выигрыши игроков совпадают: a = в = n = 4 , значит у матрицы имеется седловая точка. А значит, у данной матричной игры имеется пара оптимальных чистых стратегий А3В2 . Цена игры n = 4.
Но такое бывает далеко не всегда.
4.2 Матричные игры, разрешимые в смешанных стратегиях
4.2.1 Постановка задачи
Если
платежная
матрица не
имеет седловой
точки, то
. А значит
. Такая игра в
чистых стратегиях
не разрешима.
Первый игрок
в таком случае
будет стремиться
увеличить свой
выигрыш, а второй
– уменьшить
свой проигрыш.
Поиск такого
решения приводит
к применению
сложной стратегии,
состоящей в
случайном
применении
двух и более
чистых стратегий
с определенными
вероятностями:
PA = (p1, p2, …, pm) где pi – это вероятности применения чистых стратегий игроком А;
QB = (q1, q2, …, qn) где qj – это вероятности применения чистых стратегий игроком B;
при этом
и
.
Такие наборы вероятностей применения чистых стратегий игроками А и В называются смешанными стратегиями.
Заметим, что чистые стратегии – это частный случай смешанных стратегий. Например, чистая стратегия первого игрока – это смешанная стратегия, у которой все вероятности pi = 0 , кроме соответствующего номера k чистой стратегии: pk = 1 .
Основная теорема теории игр (Теорема фон-Неймана): любая конечная игра двух лиц с нулевой суммой разрешима в смешанных стратегиях.
Как же искать смешанные стратегии? Их можно найти точно – алгебраическим способом (в частности, с помощью симплекс-метода) или графическим способом (для игры размерности 2 х n или m х 2 ).
Для того чтобы точно найти решение матричной игры в смешанных стратегиях, нужно представить заданную матричную игру в виде задачи линейного программирования и решить её симплекс-методом.
Рассмотрим матричную игру, не разрешимую в чистых стратегиях, в общем виде:
Заметим, что в матричной игре, разрешимой в чистых стратегиях, элементы платежной матрицы могут быть как положительными, так и отрицательными. Для симплекс-метода, которым будем решать игру, не разрешимую в чистых стратегиях, необходимо, чтобы элементы платежной матрицы были неотрицательными. Для этого, если в платежной матрице будут отрицательные элементы, нужно ко всем элементам платежной матрицы прибавить достаточно большое число с . При этом решение задачи не изменится, а цена игры увеличится на с.#
PA = (p1, p2, …, pm)– это оптимальная смешанная стратегия первого игрока. Её применение гарантирует первому игроку выигрыш не меньший, чем цена игры n . Если при этом второй игрок выберет стратегию В1, математически все вышесказанное будет иметь вид:
а11р1 + а21р2 + … + am1pm ≥ n
Таких неравенств будет столько, сколько есть возможных альтернатив у второго игрока, т.е. столбцов платежной матрицы – n штук:
а11р1 + а21р2 + … + am1pm ≥ n
а12р1 + а22р2 + … + am2pm ≥ n
а1nр1 + а2nр2 + … + amnpm ≥ n
Разделив все неравенства на n , получим (в общем виде):
а1j
+ а2j
+ … + amj
≥ 1
Обозначим:
= xi, . С помощью
таких новых
переменных
вышеуказанные
неравенства
запишутся в
виде:
а11 x1 + а21 x2 + … + am1 xm ≥ 1
а12 x1 + а22 x2 + … + am2 xm ≥ 1
а1n x1 + а2n x2 + … + amn xm ≥ 1
Просуммируем новые переменные:
= x1 + x2 + … + xm =
+
+ … +
=
=
![]()
PA = (p1,
p2, …, pm)–
это оптимальная
смешанная
стратегия
первого игрока.
То есть нужно
так подобрать
(p1, p2, …,
pm) , чтобы n
была как можно
большей. Или
же, что то же
самое, чтобы
была как можно
меньшей.
Таким образом, используя новые переменные и учитывая всё вышесказанное, исходную матричную игру можно представить в виде задачи линейного программирования:
найти вектор переменных Х = {x1, x2, … , xm}, такой что:
целевая
функция f
=
min
при множестве ограничений:
АТХ ≥ Е
гдеА – матрица коэффициентов (платежная матрица), заданная в условии;
Е – единичный вектор
Х – вектор
неизвестных
переменных,
такой что xi
=
;
n – это цена
игры:n =
=
;
рi – это коэффициенты вектора смешанной стратегии первого игрока.
4.2.2 Решение задачи симплекс-методом
Рассмотрим числовой пример.
Пусть имеем игру с платежной матрицей:

Проверим, имеет ли наша матричная игра седловую точку? Для этого используем принцип максимина.
Выигрыш
игрока А:a =
= 2 он достигается
в первой строке.
Выигрыш
игрока В:в =
= 3 он достигается
в четвертом
столбце.
Как видим, выигрыши игроков не совпадают, значит у матрицы нет седловой точки. Значит, нужно искать смешанные стратегии.
В данном конкретном случае в множестве ограничений будет четыре неравенства (т.к. в условии задачи четыре столбца). Пересчитывать симплекс- таблицы с четырьмя строками не очень сильно хочется, поэтому удобнее решить двойственную задачу (для коэффициентов вектора смешанной стратегии второго игрока), в которой будет всего две строки (т.к. в условии задачи две строки):
найти вектор двойственных переменных Y = {y1, y2, … yn}, такой что:
целевая
функция g
=
max
при множестве ограничений:АY ≤ Е
Для нашего примера задача линейного программирования будет такой:
найти вектор Y = {y1, y2, y3, y4}, такой что:
целевая
функция g
=
max
при множестве ограничений:

Далее нужно вспомнить методику применения симплекс-метода и использовать её для нашей задачи.
Однако, как показывает многолетняя практика, студенты обладают так называемой "краткосрочной памятью", которая работает только до сдачи необходимого экзамена. Поэтому вспомнить сейчас методику применения симплекс-метода вряд ли кто-то сможет. Для этого нужно сходить в библиотеку, найти специальную литературу и умело ей воспользоваться. Осмелимся заметить, что и этого половина студентов сделать поленится и благополучно завалит данную тему J . #
Поэтому для всеобщего блага приведем здесь методику применения симплекс-метода (пройденного и успешно сданного в математическом программировании) для нашей конкретной задачи.
1 этап – приведение задачи линейного программирования к каноническому виду.
Неравенства во множестве ограничений нужно превратить в равенства с помощью добавления искусственных переменных. Для того чтобы неравенства превратить в равенства, надо в каждое неравенство добавить (или отнять – в зависимости от знака неравенства) искусственную переменную:

Целевая функция при этом будет выглядеть так:g = y1 + y2 + y3 + y4 + 0y5 + 0y6
2 этап – определение начального опорного плана.
В полученном случае начальный опорный план будут составлять искусственные переменные, входящие в ограничения с коэффициентами +1 :{ y5 ; y6 }. Новых искусственных переменных для данной задачи вводить не требуется.
3 этап – заполнение исходной симплекс-таблицы.
Исходная симплекс-таблица для нашей двойственной задачи будет иметь вид:
В
столбец "текущий
базис" ставим
переменные,
начального
опорного плана
: { y5 ; y6 }.
В столбец "сi" ставим их коэффициенты в целевой функции.
В столбец "А0" ставим вектор ограничений Е : а10 = 1 ;а20 = 1 .
В самую верхнюю строку таблицы ставим коэффициенты cj при соответствующих переменных в целевой функции:c1 = 1 ; c2 = 1 ; c3 = 1 ; c4 = 1 ; c5 = 0 ; c6 = 0 .
В столбцы "А1", ...., "А6" ставим соответствующие коэффициенты матрицы ограничений А.
Вычисляем оценки по формулам
–
и ставим их в самую нижнюю строку симплекс-таблицы (строку оценок) :
–––
–––
–––
–––
––
––
4 этап – пересчет симплекс-таблицы.
Если j і 0 для всех j = 1, 2, .... , n , то данный план (в столбце "текущий базис") – оптимален. В нашем случае это условие не выполняется, значит, текущий базис можно улучшить.
Если имеются
k < 0 и в столбце
Аk все элементы
aik
0 , то целевая
функция не
ограничена
сверху на допустимом
множестве и
данная задача
не имеет смысла.
В нашем случае
видим, что целевая
функция сверху
ограничена.
Если имеются j < 0 и в столбцах Аj , соответствующих этим оценкам, существует хотя бы один элемент aik > 0, то возможен переход к новому лучшему плану, связанному с большим значением целевой функции. У нас так и есть.
Переменная хk, которую необходимо ввести в базис, для улучшения плана соответствует наименьшей отрицательной оценке j. Столбец Ak, содержащий эту оценку называется ведущим. В нашем случае все оценки одинаковы. Поэтому в качестве ведущего столбца выберем любую оценку, например, третью: k = 3.
Ищем min{ ai0 / ai1 } = min{ 1/8 ; 1/1 } = 1/8– этот минимум достигается при i = 1. Значит, r = 1первая строка – ведущая. (на рисунке помечена стрелкой)
Ведущий элементark = a13 = 8 (на рисунке выделен)
Заполняем новую симплекс-таблицу.
В столбец "текущий базис" вместо переменной у5 ставим переменную у3 .
В столбец "сi" ставим коэффициент переменной у3 в целевой функции.
Самая верхняя строка таблицы всегда остаётся неизменной.
Пересчитываем
ведущую строку
по формуле
:







После этого пересчитываем остальные строки по формуле
:
вторая строка (i = 2)







Пересчитываем и заполняем строку оценок:
–
––![]()
–
––
––
–