Теория игр

Если обозначить  

yj = qj , j = 1, 2, …, n, (1.16) 

то получим  систему неравенств: 

a11 y1 + a12 y2 +…+ a1n yn 1, 

a21 y1 + a22 y2 +…+ a2n yn 1, (1.17) 

am1 y1 + am y2 +…+ amn yn 1. 

Переменные yj (j = 1, 2, …, n) удовлетворяют условию y1 + y2 +…+ yn = 1. 

Игра свелась  к следующей задаче. 

Определить значения переменных yj 0, j = 1, 2, …, n, которые удовлетворяют системе неравенств (1.17) и максимизируют линейную функцию 

Z' = y1 + y2 +…+ yn, (1.18) 

Решение задачи линейного программирования (1.16), (1.17) определяет оптимальную стратегию S* B = (q1*, q2*, …, qn*). При этом цена игры 

= 1/max Z' = 1/min Z. (1.19) 

Составив расширенные  матрицы для задач (1.13), (1.14) и (1.17), (1.18), убеждаемся, что одна матрица  получилась из другой транспортированием: 

a11 a21 … am1 1 

a12 a22 … am2 1 

... … … …  … 

a1n a2n … amn 1 

a11 a12 … a1n 1 

a21 a22 … a2n 1 

… … … …  … 

am1 am2 … amn 1 

Таким образом, задачи линейного программирования (1.13), (1.14) и (1.17), (1.18) являются взаимно - двойственными. Очевидно, при определении оптимальных  стратегий в конкретных задачах  следует выбрать ту из взаимно - двойственных задач, решение которой менее трудоёмко, а решение другой задачи найти с помощью теорем двойственности. 

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

4. Предприятие может выпускать три вида продукции (А1, А2 и А3), получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (В1, В2, В3 и В4). Дана матрица (табл. 4.), её элементы аij характеризуют прибыль, которую получит предприятие при выпуске i -ой продукции с j - ым состоянием спроса. 

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

Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платёжной матрицей (см. табл. 4). 

Таблица 4. 

В1 

В2 

В3 

В4  

А1 

3 

3 

6 

8  

А2 

9 

10 

4 

2  

А3 

7 

7 

5 

4  
 
 

Прежде чем  решать задачу, можно попытаться упростить  игру, проведя анализ платёжной матрицы и отбросив стратегии, заведомо не выгодные или дублирующие. Так, вторая стратегия (второй столбец матрицы (табл. 4)) является явно не выгодной для игрока В по сравнению с первой (элементы второго столбца больше элементов первого столбца), так как цель игрока В - уменьшить выигрыш игрока А. поэтому второй столбец можно отбросить. Получим матрицу P размера 3 3: 

3 6 8 

Р = 9 4 2  

7 5 4 

Таблица 5. 

Вид продукции 

Спрос 

В1 

В3 

В4 

?i  

А1 

3 

6 

8 

3  

А2 

9 

4 

2 

2  

А3 

7 

5 

4 

4  

?j 

9 

6 

8 

6 

4  
 
 

Определим нижнюю верхнюю цены игры в табл. 5. 

Так как , то седловая точка отсутствует, и оптимальное  решение следует искать в смешанных  стратегиях игроков: 

S* A = (р1, р2, р3) и  S* B = (q1, q2, q3). 

обозначив x1 = p1, i = 1, 2, 3 и yj = qj , j = 1, 2, 3, составив две взаимно - двойственные задачи линейного программирования (см. (1.13) - (1.14) и (1.17) - (1.18)). 

Задача 1 

3x1 + 9x2 + 7x3 1, 

6x1 + 4x2 + 5x3 1, 

8x1 + 2x2 + 4x3 1, 

xi 0, i = 1, 2, 3 

Задача 2 

3y1 + 6y2 + 8y3 1, 

9y1 + 4y2 + 2y3 1, 

7y1 + 5y2 + 4y3 1, 

yj 0, j = 1, 2, 3,Z = x1 + x2 + x3 min  

Z = y1 + y2 + y3 max 

Решаем симплексным  методом одну из задач, например, задачу 2, поскольку для неё первое базисное решение будет допустимым. Введём добавочные переменные и перейдём к уравнениям: 

3y1 + 6y2 + 8y3 + y4 = 1, 

9y1 + 4y2 + 2y3 + y5 = 1, 

7y1 + 5y2 + 4y3 + y6 = 1, 

yj 0, j = 1, 2, …, 6. 

I шаг. Основные  переменные - y4, y5, y6; неосновные переменные - y1, y2, y3. 

y4 = 1 - 3y1 - 6y2 - 8y3, 

y5 = 1 - 9y1 - 4y2 - 2y3, 

y6 = 1 - 7y1 - 5y2 - 4y3, 

Z' = y1 + y2 + y3. 

Базисное решение Y1 = (0; 0; 0; 1; 1; 1) допустимое; переводим y2 в основные; y2 = min ;; =; переводим y4 в  неосновные переменные. 

II шаг. Основные  переменные - y2, y5, y6; неосновные переменные - y1, y3, y4. 

Получим после преобразований: 

y2 = - y1 - y3 - y4, 

y5 = - 7 y1 - y3 - y4, 

y6 = - y1 - y3 - y4, 

Z' = + y1 - y3 - y4. 

Базисное решение: Y2 = (0; ; 0; 0; ; ). Переводим y1 в основные; y1 = min ; ; = . Переводим y6 в неосновные переменные. 

III шаг. Основные переменные - y1, y2, y5; неосновные переменные - y3, y4, y6; 

y1 = - y3 + y4 - y6,  

y2 = - y3 - y4 + y6, 

y5 = + y3 - y4 + y6,  

Z' = - y3 - y4 - y6.  

Базисное решение Y3 = (;; 0; 0; ; 0). 

Так как отсутствуют  положительные коэффициенты при  неосновных переменных, то критерий оптимальности выполнен, max Z' = и базисное решение Y3 = (;; 0; 0; ; 0) является оптимальным. 

Установим соответствие между переменными взаимно - двойственных задач и определим оптимальное  базисное решение задачи 1 с помощью  теорем двойственности: 

x1 x2 x3 x4 x5 x6 
 

y4 y5 y6 y1 y2 y3 

0 0  

Оптимальное базисное решение задачи 1: (; 0; ; ; 0; ), при чём min Z = max Z' = . Из соотношений (1.19) находим  цену игры = = == = 5,4. оптимальную стратегию S* A = (р1*; р2*; р3*) находим, используя (1.12): рi* = xi , i = 1, 2, 3, т.е. 

р1* = 5,4= 0,4, р2* = 5,4 0 = 0, 

р3* = 5,4= 0,6; S* A = (0,4; 0; 0,6). 

Следовательно, предприятие должно выпустить 40% продукции  А1 и 60% продукции А3, а продукцию  А2 не выпускать. 

Оптимальная стратегия  спроса S* B определяется аналогично: qj* = yj, j = 1, 2, 3, т.е. S* B = (0,2; 0; 0,8; 0) (здесь учтено, что второй столбец исходной матрицы был отброшен как невыгодный). Таким образом, оптимальный спрос в 20% находится в состоянии В1 и в 80% - в состоянии В3. 

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

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

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

3. Если седловая  точка отсутствует, то решение  следует искать в смешанных  стратегиях. Для игр размера m n рекомендуется симплексный метод,  для игр размера 2 2, 2 n, n 2 возможно геометрическое решение. 

На практике реализация оптимального решения S* = А1 … Аm  

p1 … р2 
 

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

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

Рассмотрим ещё  одну экономическую задачу, сводящуюся к игровой модели. 

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

Потребитель может  приобрести продукцию: немедленно (стратегия  В1), в течение небольшого времени (В2), после длительного периода  времени (В3). 

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

Определить оптимальные  пропорции продукции для применения стратегий А1, А2, А3, руководствуясь «минимаксным критерием» (гарантированный средний уровень убытка) при матрице затрат, представленной в табл. 6. 

Таблица 6. 

Аj Bi 

B1 

B2 

B3  

А1 

2 

5 

8  

А2 

7 

6 

10  

А3 

12 

10 

8  
 
 

Решение. Получаем игру с платёжной матрицей 2 5 8 

Р = 7 6 10. 

12 10 8 

В этой матрице  первую строку можно отбросить как  невыгодную (её элементы меньше соответствующих  элементов второй строки). Матрица  примет вид 

7 6 10 

Р = 12 10 8. 

Элементы первого  столбца больше соответствующих  элементов второго столбца, поэтому  его можно отбросить. 

Игра упростилась: 

Р =6 10 

10 8. 

По формулам (1.7) и (1.8) находим: 

Р2* = = ; р3* = 1 - = ; 

= = = 8. 

Вывод: оптимальная  стратегия производителя продукции S* A = (0; ; ), т.е. стратегия А1 не применяется, продукции отправляется на склад (стратегия А2), продукции дополнительно обрабатывается (стратегия А3), при этом цена игры = 8.  

Заключение 
 

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

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