|
|
| Пример №3. Теория игр. Решение матричной игры в смешанных стратегиях. |
Данное решение является образцом работы программы, представленной на сайте.
| Введенная Вами матрица показывает выигрыш игрока А, в зависимости от выбранного им действия и от ответного действия игрока В. Данная матрица называется платежной матрицей.
Мы рассматриваем игру двух игроков, в которой выигрыш одного из них равен проигрышу другого. Внешние факторы отсутствуют. Оба игрока обладают конечным числом действий и логикой, которая определят их действия (рассмотрим ниже).
Строки матрицы являются возможными действиями игрока А, столбцы матрицы - возможными действиями игрока В. Возможные действия игроков называются чистыми стратегиями. |
| В нашем случае, количество чистых стратегий игрока А равно 5 . Количество чистых стратегий игрока В равно 6 . |
| Если я выберу стратегию A1 ,то при любом действии игрока B, я гарантирую себе выигрыш -2 ,т.е. потеряю не более 2 ден.ед. |
| Если я выберу стратегию A2 ,то при любом действии игрока B, я гарантирую себе выигрыш 0 ,т.е. получу не менее 0 ден.ед. |
| Если я выберу стратегию A3 ,то при любом действии игрока B, я гарантирую себе выигрыш 1 ,т.е. получу не менее 1 ден.ед. |
| Если я выберу стратегию A4 ,то при любом действии игрока B, я гарантирую себе выигрыш 0 ,т.е. получу не менее 0 ден.ед. |
| Если я выберу стратегию A5 ,то при любом действии игрока B, я гарантирую себе выигрыш 1 ,т.е. получу не менее 1 ден.ед. |
| |
|
Стратегии игрока B |
Минимальный элемент в строке |
| B1 | B2 | B3 | B4 | B5 | B6 | | Стратегии игрока A | A1 | 4 | -2 | 5 | 1 | 2 | 7 | -2 | | A2 | 1 | 2 | 4 | 3 | 0 | 10 | 0 | | A3 | 3 | 5 | 6 | 7 | 1 | 9 | 1 | | A4 | 1 | 2 | 4 | 3 | 0 | 10 | 0 | | A5 | 2 | 1 | 3 | 6 | 5 | 4 | 1 |
Игрок А использует логику, которая гарантирует ему максимальный выигрыш вне зависимости от поведения игрока В.
Свой выбор, игрок А остановит на стратегии A3, которая обеспечит ему выигрыш 1, т.е. доход не менее 1 ден.ед.
Значение равное 1, называется нижней ценой игры.
|
| Если я выберу стратегию B1 ,то при любом действии игрока A, я гарантирую себе проигрыш 4 ,т.е. потеряю не более 4 ден.ед. |
| Если я выберу стратегию B2 ,то при любом действии игрока A, я гарантирую себе проигрыш 5 ,т.е. потеряю не более 5 ден.ед. |
| Если я выберу стратегию B3 ,то при любом действии игрока A, я гарантирую себе проигрыш 6 ,т.е. потеряю не более 6 ден.ед. |
| Если я выберу стратегию B4 ,то при любом действии игрока A, я гарантирую себе проигрыш 7 ,т.е. потеряю не более 7 ден.ед. |
| Если я выберу стратегию B5 ,то при любом действии игрока A, я гарантирую себе проигрыш 5 ,т.е. потеряю не более 5 ден.ед. |
| Если я выберу стратегию B6 ,то при любом действии игрока A, я гарантирую себе проигрыш 10 ,т.е. потеряю не более 10 ден.ед. |
| |
|
Стратегии игрока B |
Минимальный элемент в строке |
| B1 | B2 | B3 | B4 | B5 | B6 | | Стратегии игрока A | A1 | 4 | -2 | 5 | 1 | 2 | 7 | -2 | | A2 | 1 | 2 | 4 | 3 | 0 | 10 | 0 | | A3 | 3 | 5 | 6 | 7 | 1 | 9 | 1 | | A4 | 1 | 2 | 4 | 3 | 0 | 10 | 0 | | A5 | 2 | 1 | 3 | 6 | 5 | 4 | 1 | | Максимальный элемент в столбце | | 4 | 5 | 6 | 7 | 5 | 10 | |
Игрок В использует логику, которая гарантирует ему минимальный проигрыш вне зависимости от поведения игрока А.
Свой выбор, игрок В остановит на стратегии В1, которая обеспечит ему проигрыш 4, т.е. потерю не более 4 ден.ед.
Значение равное 4, называется верхней ценой игры.
|
| В случае, если верхняя цена игры равна нижней цене игры - мы нашли оптимальное решение, которое устраивает обоих игроков, исходя из их логики.
В нашей задаче, если игроки пользуются только чистыми стратегиями, оптимальное решение не найдено.
Но, всегда есть решение в смешанных стратегиях. |
| Смешанной стратегией игрока А называется применение чистых стратегий A1 , A2 , A3 , A4 , A5 c вероятностями p1 , p2 , p3 , p4 , p5 . |
Смешанную стратегию первого игрока обозначают как вектор:
P = ( p1 , p2 , p3 , p4 , p5 ) , где p1 + p2 + p3 + p4 + p5 = 1 и p1 , p2 , p3 , p4 , p5  0 |
| Смешанной стратегией игрока B называется применение чистых стратегий B1 , B2 , B3 , B4 , B5 , B6 c вероятностями q1 , q2 , q3 , q4 , q5 , q6 . |
Смешанную стратегию второго игрока обозначают как вектор:
Q = ( q1 , q2 , q3 , q4 , q5 , q6 ) , где q1 + q2 + q3 + q4 + q5 + q6 = 1 и q1 , q2 , q3 , q4 , q5 , q6 0 |
| Оптимальное решение игры (или просто - решение игры) - это пара оптимальных смешанных стратегий |
| P* ( p*1 , p*2 , p*3 , p*4 , p*5 ) и Q* ( q*1 , q*2 , q*3 , q*4 , q*5 , q*6 ) |
| обладающих следующим свойством: |
| если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. |
| Выигрыш игрока А равный проигрышу игрока В , соответствующий оптимальному решению, называется ценой игры v. |
| Цена игры больше либо равна нижней цены игры и меньше или равна верхней цены игры. |
В нашем случае :
1  v 4. |
| |
|
Стратегии игрока B |
| B1 | B2 | B3 | B4 | B5 | B6 | | Стратегии игрока A | A1 | 4 | -2 | 5 | 1 | 2 | 7 | | A2 | 1 | 2 | 4 | 3 | 0 | 10 | | A3 | 3 | 5 | 6 | 7 | 1 | 9 | | A4 | 1 | 2 | 4 | 3 | 0 | 10 | | A5 | 2 | 1 | 3 | 6 | 5 | 4 |
| Исключим стратегии, которыми заведомо не выгодно пользоваться игрокам. |
| Стратегия A4 является доминирующей над стратегией A2 , т.к. каждый элемент строки 4 больше или равен соответствующего элемента строки 2. Игроку А заведомо не выгодно пользоваться стратегией A2. Удаляем стратегию A2 из рассмотрения . |
| |
|
Стратегии игрока B |
| B1 | B2 | B3 | B4 | B5 | B6 | | Стратегии игрока A | A1 | 4 | -2 | 5 | 1 | 2 | 7 | | A3 | 3 | 5 | 6 | 7 | 1 | 9 | | A4 | 1 | 2 | 4 | 3 | 0 | 10 | | A5 | 2 | 1 | 3 | 6 | 5 | 4 |
| Стратегия B1 является доминирующей над стратегией B3 , т.к. каждый элемент столбца 1 меньше или равен соответствующего элемента столбца 3. Игроку B заведомо не выгодно пользоваться стратегией B3. Удаляем стратегию B3 из рассмотрения . |
| |
|
Стратегии игрока B |
| B1 | B2 | B4 | B5 | B6 | | Стратегии игрока A | A1 | 4 | -2 | 1 | 2 | 7 | | A3 | 3 | 5 | 7 | 1 | 9 | | A4 | 1 | 2 | 3 | 0 | 10 | | A5 | 2 | 1 | 6 | 5 | 4 |
| Стратегия B1 является доминирующей над стратегией B6 , т.к. каждый элемент столбца 1 меньше или равен соответствующего элемента столбца 5. Игроку B заведомо не выгодно пользоваться стратегией B6. Удаляем стратегию B6 из рассмотрения . |
| |
|
Стратегии игрока B |
| B1 | B2 | B4 | B5 | | Стратегии игрока A | A1 | 4 | -2 | 1 | 2 | | A3 | 3 | 5 | 7 | 1 | | A4 | 1 | 2 | 3 | 0 | | A5 | 2 | 1 | 6 | 5 |
| Стратегия B2 является доминирующей над стратегией B4 , т.к. каждый элемент столбца 2 меньше или равен соответствующего элемента столбца 3. Игроку B заведомо не выгодно пользоваться стратегией B4. Удаляем стратегию B4 из рассмотрения . |
| |
|
Стратегии игрока B |
| B1 | B2 | B5 | | Стратегии игрока A | A1 | 4 | -2 | 2 | | A3 | 3 | 5 | 1 | | A4 | 1 | 2 | 0 | | A5 | 2 | 1 | 5 |
| Стратегия A3 является доминирующей над стратегией A4 , т.к. каждый элемент строки 2 больше или равен соответствующему элементу строки 3. Игроку А заведомо не выгодно пользоваться стратегией A4. Удаляем стратегию A4 из рассмотрения . |
| |
|
Стратегии игрока B |
| B1 | B2 | B5 | | Стратегии игрока A | A1 | 4 | -2 | 2 | | A3 | 3 | 5 | 1 | | A5 | 2 | 1 | 5 |
После преобразований платежной матрицы, оптимальное решение будем искать в виде :
P* = ( p*1 , 0 , p*3 , 0 , p*5 ) ,
Q* = ( q*1 , q*2 , 0 , 0 , q*5 , 0 ). |
| Если P* = ( p*1 , 0 , p*3 , 0 , p*5 ) и Q* = ( q*1 , q*2 , 0 , 0 , q*5 , 0 ) являются оптимальным решением, то должны выполняться две следующие системы неравенств : |
 | 4 p*1 | + 3 p*3 | + 2 p*5 | | v | | -2 p*1 | + 5 p*3 | + p*5 | | v | | 2 p*1 | + p*3 | + 5 p*5 | | v |
| | 4 q*1 | -2 q*2 | + 2 q*5 | | v | | 3 q*1 | + 5 q*2 | + q*5 | | v | | 2 q*1 | + q*2 | + 5 q*5 | | v |
| Рассмотрим первую систему. |
| Разделим почленно первую систему на v (цену игры). |
| Т.к. цена игры положительная, то знаки в неравенствах системы не изменятся. |
| Введем новые обозначения: |
| y1 = p*1 / v , y2 = p*3 / v , y3 = p*5 / v |
| y1 + y2 + y3 = p*1 / v + p*3 / v + p*5 / v = 1/v * ( p*1 + p*3 + p*5 ) = 1/v |
| Т.к игрок A старается увеличить свой выигрыш, т.е. цену игры v, то выражение 1/v будет стремиться к минимуму. |
| Мы получили задачу линейного программирования. |
| Требуется найти мминимум линейной функции F = y1 + y2 + y3 при следующей системе ограничений : |
| | 4 y1 | + 3 y2 | + 2 y3 | | 1 | | -2 y1 | + 5 y2 | + y3 | | 1 | | 2 y1 | + y2 | + 5 y3 | | 1 |
| Рассмотрим вторую систему. |
| Разделим почленно вторую систему на v (цену игры). |
| Т.к. цена игры положительная, то знаки в неравенствах системы не изменятся. |
| Введем новые обозначения: |
| x1 = q*1 / v , x2 = q*2 / v , x3 = q*5 / v |
| x1 + x2 + x3 = q*1 / v + q*2 / v + q*5 / v = 1/v * ( q*1 + q*2 + q*5 ) = 1/v |
| Т.к игрок B старается уменьшить свой проигрыш, т.е. цену игры v, то выражение 1/v будет стремиться к максимуму. |
| Мы получили задачу линейного программирования. |
| Требуется найти максимум линейной функции L = x1 + x2 + x3 при следующей системе ограничений : |
| | 4 x1 | -2 x2 | + 2 x3 | | 1 | | 3 x1 | + 5 x2 | + x3 | | 1 | | 2 x1 | + x2 | + 5 x3 | | 1 |
| Полученные задачи являются парой симметричных взаимно двойственных задач. |
| Решив одну из них, мы автоматически получим решение второй. |
Удобнее решить вторую задачу. Решим ее симплекс методом.
|
Система ограничений должна быть приведена к каноническому виду. |
| К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x4 , тем самым мы преобразуем неравенство 1 в равенство. |
| К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x5 , тем самым мы преобразуем неравенство 2 в равенство. |
| К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6 , тем самым мы преобразуем неравенство 3 в равенство. |
| | 4 x1 | -2 x2 | + 2 x3 | + x4 | | | = | 1 | | 3 x1 | + 5 x2 | + x3 | | + x5 | | = | 1 | | 2 x1 | + x2 | + 5 x3 | | | + x6 | = | 1 |
| Система ограничений приведена к каноническому виду, т.е.. все условия системы представляют собой уравнения. |
Определимся с начальным опорным решением. |
| Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее: |
| Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная. |
| Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная. |
| Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x6 - базисная переменная. |
| Переменные , которые не являются базисными, называются свободными переменными. Приравняв свободные переменные нулю, в получившийся системе ограничений, мы получим начальное опорное решение. |
X нач = ( 0 , 0 , 0 , 1 , 1 , 1 )| Значение функции для начального решения: L (X нач) = 0 |
Обратите внимание:
При составлении исходной симплекс таблицы, коэффициенты при переменных функции L записываются с противоположными знаками, а свободный член со своим знаком. |
| За ведущий выберем столбец 1 , так как -1 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем. |
| За ведущую выберем строку 1, так как отношение свободного члена к соответствующему элементу выбранного столбца для 1 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x4 | 4 | - 2 | 2 | 1 | 0 | 0 | 1 | | | x5 | 3 | 5 | 1 | 0 | 1 | 0 | 1 | | | x6 | 2 | 1 | 5 | 0 | 0 | 1 | 1 | | | L | - 1 | - 1 | - 1 | 0 | 0 | 0 | 0 | - |
| Разделим элементы строки 1 на 4. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x4 | 1 | | | | 0 | 0 | | | | x5 | 3 | 5 | 1 | 0 | 1 | 0 | 1 | | | x6 | 2 | 1 | 5 | 0 | 0 | 1 | 1 | | | L | - 1 | - 1 | - 1 | 0 | 0 | 0 | 0 | - |
| От элементов строки 2 отнимает соответствующие элементы строки 1 умноженные на 3. |
| От элементов строки 3 отнимает соответствующие элементы строки 1 умноженные на 2. |
| От элементов строки L отнимает соответствующие элементы строки 1 умноженные на -1. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | | | | 0 | 0 | | - | | x5 | 0 | | | | 1 | 0 | | - | | x6 | 0 | 2 | 4 | | 0 | 1 | | - | | L | 0 | | | | 0 | 0 | | - |
X 1 = ( 1/4 , 0 , 0 , 0 , 1/4 , 1/2 )| Значение функции L для данного решения: L (X 1) = 1/4 |
| За ведущий выберем столбец 2 , так как -3/2 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем. |
| За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для 2 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 2. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | | | | 0 | 0 | | - | | x5 | 0 | | | | 1 | 0 | | | | x6 | 0 | 2 | 4 | | 0 | 1 | | | | L | 0 | | | | 0 | 0 | | - |
| Разделим элементы строки 2 на 13/2. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | | | | 0 | 0 | | - | | x5 | 0 | 1 | | | | 0 | | | | x6 | 0 | 2 | 4 | | 0 | 1 | | | | L | 0 | | | | 0 | 0 | | - |
| От элементов строки 1 отнимает соответствующие элементы строки 2 умноженные на -1/2. |
| От элементов строки 3 отнимает соответствующие элементы строки 2 умноженные на 2. |
| От элементов строки L отнимает соответствующие элементы строки 2 умноженные на -3/2. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | 0 | | | | 0 | | - | | x2 | 0 | 1 | | | | 0 | | - | | x6 | 0 | 0 | | | | 1 | | - | | L | 0 | 0 | | | | 0 | | - |
X 2 = ( 7/26 , 1/26 , 0 , 0 , 0 , 11/26 )| Значение функции L для данного решения: L (X 2) = 4/13 |
| За ведущий выберем столбец 3 , так как -8/13 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем. |
| За ведущую выберем строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 3. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | 0 | | | | 0 | | | | x2 | 0 | 1 | | | | 0 | | - | | x6 | 0 | 0 | | | | 1 | | | | L | 0 | 0 | | | | 0 | | - |
| Разделим элементы строки 3 на 54/13. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | 0 | | | | 0 | | | | x2 | 0 | 1 | | | | 0 | | - | | x6 | 0 | 0 | 1 | | | | | | | L | 0 | 0 | | | | 0 | | - |
| От элементов строки 1 отнимает соответствующие элементы строки 3 умноженные на 6/13. |
| От элементов строки 2 отнимает соответствующие элементы строки 3 умноженные на -1/13. |
| От элементов строки L отнимает соответствующие элементы строки 3 умноженные на -8/13. |
базисные
переменные | x1 | x2 | x3 | x4 | x5 | x6 | свободные
члены | отношение | | x1 | 1 | 0 | 0 | | | | | - | | x2 | 0 | 1 | 0 | | | | | - | | x3 | 0 | 0 | 1 | | | | | - | | L | 0 | 0 | 0 | | | | | - |
X 3 = ( 2/9 , 5/108 , 11/108 , 0 , 0 , 0 )| Значение функции L для данного решения: L (X 3) = 10/27 |
| L = | 10/27 | -1/27 x4 | -5/27 x5 | -4/27 x6 |
| Учитывая, что все x i0 по условию задачи, наибольшее значение функции равно свободному члену 10/27. |
| Учитывая правило формирования ответа симметричной двойственной задачи, запишем ее решение, на основании все той же последней симплекс таблицы. |
| Максимальное значение функции прямой задачи равно минимальному значению функции двойственной задачи. |
| Lmax = 10/27 , Fmin = 10/27 |
| v = 1 / Fmax = 1 / Lmin = 27/10 |
| Теперь, мы можем найти оптимальное решение нашей игры. |
| p*1 = y1 * v = 1/27 * 27/10 = 1/10 |
| p*3 = y2 * v = 5/27 * 27/10 = 1/2 |
| p*5 = y3 * v = 4/27 * 27/10 = 2/5 |
| q*1 = x1 * v = 2/9 * 27/10 = 3/5 |
| q*2 = x2 * v = 5/108 * 27/10 = 1/8 |
| q*5 = x3 * v = 11/108 * 27/10 = 11/40 |
| P* = ( 1/10 , 0 , 1/2 , 0 , 2/5 ) |
| Q* = ( 3/5 , 1/8 , 0 , 0 , 11/40 , 0 ) |
| Дадим объяснение полученному ответу. |
| Выигрыш игрока А составит 27/10 ден.ед. |
| Проигрыш игрока В составит 27/10 ден.ед. |
| использует стратегию A1 на 10 % |
| использует стратегию A2 на 0 % |
| использует стратегию A3 на 50 % |
| использует стратегию A4 на 0 % |
| использует стратегию A5 на 40 % |
| использует стратегию B1 на 60 % |
| использует стратегию B2 на 12.5 % |
| использует стратегию B3 на 0 % |
| использует стратегию B4 на 0 % |
| использует стратегию B5 на 27.5 % |
| использует стратегию B6 на 0 % |
|
