Для решения матричной игры как задачи линейного программирования необходимо чтобы

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

В данном статье описано сведение матричной игры к задаче линейного программирования.
Алгоритм поиска решения матричной антагонистической игры, заданной платежной матрицей, имеющей размерность m×n при больших значениях m и n, сводится к алгоритму симплекс-метода решения пары взаимодвойственных задач линейного программирования. Покажем, как привести конечную матричную антагонистическую игру к двум взаимодвойственных задачам линейного программирования.
Пусть антагонистическая игра задана платёжной матрицей A, имеющей размерность m×n, и эта игра является не вполне определённой. Необходимо найти решение игры, т.е. определить оптимальные смешанные стратегии первого и второго игроков:
P * = (p₁ * , p₂ * , …, p_m * ), Q * = (q₁ * , q₂ * ,…, q_n * )
где P * и Q * — векторы, компоненты которых p_i * и p_j * характеризуют вероятности применения чистых стратегий i и j соответственно первым и вторым игроками и соответственно для них выполняются соотношения:
p₁ * + p₂ * + … + p_m * = 1, q₁ * + q₂ * + … + q_n * = 1

Найдём сначала оптимальную стратегию первого игрока P * . Эта стратегия должна обеспечить выигрыш первому игроку не меньше V, т.е. ≥V , при любом поведении второго игрока, и выигрыш, равный V , при его оптимальном поведении, т.е. при стратегии Q * .
Цена игры V нам пока неизвестна. Без ограничения общности, можно предположить её равной некоторому положительному числу V>0. Действительно, для того, чтобы выполнялось условие V > 0, достаточно, чтобы все элементы матрицы A были неотрицательными. Этого всегда можно добиться с помощью аффинных преобразований: прибавляя ко всем элементам матрицы A одну и ту же достаточно большую положительную константу М; при этом цена игры увеличится на М, а решение не изменится. Итак, будем считать V > 0.
Предположим, что первый игрок A применяет свою оптимальную стратегию P * , а второй игрок B свою чистую стратегию j -ю, тогда средний выигрыш (математическое ожидание) первого игрока A будет равен:

Оптимальная стратегия первого игрока (A ) обладает тем свойством, что при любом поведении второго игрока (B) обеспечивает выигрыш первому игроку, не меньший, чем цена игры V; значит, любое из чисел a_j не может быть меньше V (≥ V). Следовательно, при оптимальной стратегии, должна выполняться следующая система неравенств:
(1)
Разделим неравенства (1) на положительную величину V (правые части системы (1)) и введём обозначения:
(2)
y₁ ≥ 0, y₂ ≥ 0, . y_m ≥ 0, (3)
Тогда условия (1) запишутся в виде:
(4)
где y₁,y_2. y_m — неотрицательные переменные. В силу (2) и того, что p₁ * + p₂ * + … + p_m * = 1 переменные y₁, y₂ , . y_m удовлетворяют условию, которое обозначим через F:
(5)
Поскольку первый игрок свой гарантированный выигрыш (V) старается сделать максимально возможным (V→ max) , очевидно, при этом правая часть (5) — →min — принимает минимальное значение. Таким образом, задача решения антагонистической игры для первого игрока свелась к следующей математической задаче:
определить неотрицательные значения переменных y₁, ₂, . , y_n, чтобы они удовлетворяли системе функциональных линейных ограничений в виде неравенств (4), системе общих ограничений (3) и минимизировали целевую функцию F:
F = y₁ + y₂ + _. + y_m→ min
Это типичная задача линейного программирования (двойственная) и она может быть решена симплекс — методом. Таким образом, решая задачу линейного программирования, мы можем найти оптимальную стратегию P * = (p₁ * , p₂ * , …, p_m * ) игрока A.
Найдём теперь оптимальную стратегию Q * = (q₁ * , q₂ * ,…, q_n * )игрока B. Всё будет аналогично решению игры для игрока A, с той разницей, что игрок B стремиться не максимизировать, а минимизировать выигрыш (по сути дела его проигрыш), а значит, не минимизировать, а максимизировать величину , т.к. V →min. Вместо условий (4) должны выполняться условия:
(6)
где
(7)
x₁ ≥ 0, x₂ ≥ 0, . x_n ≥ 0 (8)
Требуется так выбрать переменные x₁, x₂, . x_n, чтобы они удовлетворяли условиям (6), (8) и обращали в максимум линейную функцию цели F / :

Таким образом, задача решения антагонистической игры для второго игрока свелась к следующей математической задаче:
определить неотрицательные значения переменных x₁, x₂, . x_n, чтобы они удовлетворяли системе функциональных линейных ограничений в виде неравенств (6), системе общих ограничений (8) и максимизировать целевую функцию F / :
F’ = x₁ + x₂ + .. + x_n → min
Это типичная задача линейного программирования (прямая) и она может быть решена симплекс — методом. Таким образом, решая прямую задачу линейного программирования, мы можем найти оптимальную стратегию Q * = (q₁ * , q₂ * ,…, q_n * ) игрока B.
Подведём итог.

Задача второго игрока минимизация проигрыша V	Задача первого игрока максимизация выигрыша V
Целевая функция
F / = x1+x2+x3+. +xn= → max	F = y1+y2+y3+. +ym= → min
Функциональные ограничения
Общие (прямые) ограничения
x1 ≥ 0, x2 ≥ 0, . xn≥ 0	y1 ≥ 0, y2 ≥ 0, . ym≥ 0

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

Примечание
Из сведения задачи решения конечной матричной антагонистической игры к задаче линейного программирования (ЗЛП) можно сделать заключение по поводу существования решения антагонистической игры m × n, не опираясь на теорему фон Неймана.
Пусть задача о нахождении оптимальной стратегии P * = (p₁ * , p₂ * , …, p_m * ) игрока A сведена к задаче линейного программирования с условиями неравенствами (4) и минимизируемой функцией (5). Всегда ли существует её решение? Известно, что решение задачи линейного программирования может и не существовать; оно отсутствует, если:
1. функциональные и общие условия — равенства или неравенства — вообще не имеют допустимых неотрицательных решений;
2. допустимые решения существуют, но среди них нет оптимального, так как минимизируемая функция не ограничена снизу.
Все преобразования можно получить через онлайн-калькулятор Решение матричной игры

Посмотрим, как обстоит дело в нашем случае. Допустимые решения ЗЛП в нашем случае всегда существуют. Действительно, с помощью аффинных преобразований сделаем элементы платёжной матрицы A строго положительными, например, прибавив достаточно большое положительное число М к каждому элементу платёжной матрицы, и обозначим наименьший элемент матрицы A через μ:
μ = min min a_ij
i j
Положим теперь y₁ = 1/μ, y₂ = y₃ = . = y_m = 0. Нетрудно видеть, что эта система значений переменных х₁, х_{2 ,} х_3. х_m представляют собой допустимое решение ЗЛП — все они неотрицательны, и их совокупность удовлетворяет условиям (4).
Теперь убедимся, что линейная функция (5) не может быть неограниченной снизу. Действительно, все y₁, y_{2 ,} y_3. y_m неотрицательны, а коэффициенты при них в в выражении (5) положительные (равные единицам), значит, функция F в формуле (5) тоже неотрицательна, значит, она ограничена снизу (нулём) и решение задачи линейного программирования (а следовательно, и игры m × n) существует.

Пример 1. Решить игру с матрицей:

1. В соответствии с алгоритмом определим, существуют ли в ней доминируемые стратегии, чтобы исключить их. Доминируемых стратегий нет.
2. Поскольку матрица содержит отрицательные числа, то нужно добиться, чтобы все её элементы были неотрицательны, прибавив ко всем её элементам число, равное модулю наименьшего числа матрицы. Минимальный элемент матрицы равен — 0,1, его модуль равен 0,1. Прибавим ко всем элементам платёжной матрицы число, равное 0,1 , в результате получим:

Умножим все элементы полученной матрицы на 10, чтобы удобнее проводить последующие вычисления.

Проведённые аффинные преобразования на оптимальных стратегиях не скажутся, а цену игры мы восстановим, сделав обратные преобразования (разделим полученную сумму на 10 и отнимем 0,1).
Припишем строкам вероятности p₁, p₂, p₃.

Тогда среднее значение (математическое ожидание) выигрыша игрока A при применении игроком B своей первой стратегии равен 1·p₁ + 7·p₂ + 5·p₃ (первый столбец поэлементно умножаем на вероятности p₁, p₂, p₃ и полученные произведения суммируем). Это выигрыш не может быть меньше гарантированной цены игры V: 1·p₁ + 7·p₂ + 5·p₃ ≥ V. Аналогично для других стратегий игрока B.
p₁+7p₂+5p₃≥V
4p₁+2p₂+3p₃≥V
6p₁+2p₃≥V
p_i≥0, i=1,2,3
Разделим обе части неравенства на V и введём обозначения y_i = p_i/V (i=1,2,3.):
y₁+7y₂+5y₃≥1
4y₁+2y₂+3y₃≥1
6y₁+2y₃≥1
y_i≥0, i=1,2,3

Игрок A стремиться повысить цену игры (V→ max). Поэтому F→ min.
Получили задачу линейного программирования:
F = y₁ + y₂ + y₃ → min
y₁+7y₂+5y₃≥1
4y₁+2y₂+3y₃≥1
6y₁+2y₃≥1
y_i≥0, i=1,2,3
Аналогично припишем столбцам вероятности q₁, q₂, q₃.

Тогда средний проигрыш игрока B при применении игроком A его первой стратегии равен 1·q₁ + 4·q₂ + 6·q₃ (1-ю строку поэлементно умножаем на вероятности q₁,q₂, q₃ и полученные произведения суммируем). Этот проигрыш не может быть больше цены игры V: 1·q₁ + 4·q₂ + 6·q₃ ≤ V. Аналогично для других стратегий игрока A.
q₁+4q₂+6q₃≤V
7q₁+2q₂≤V
5q₁+3q₂+2q₃≤V
q_i≥0, i=1,2,3

Игрок B стремится понизить цену игры (V→min), поэтому F / → max.
Получили задачу линейного программирования:
F’ = x₁ + x₂ + x₃ → max
x₁+4x₂+6x₃≤1
7x₁+2x₂≤1
5x₁+3x₂+2x₃≤1
x_i≥0, i=1,2,3
Полученные задачи являются взаимно двойственными задачами линейного программирования. Решим любую из них симплекс-методом. Окончательный результат — таблица имеет следующий вид:

у1	3/28	p1=	3/8
у2	0	p2=	0
у3	5/28	p3=	5/8
F /	2/7	V=	3 1/2

х1	1/7	q1=	1/2
х2	0	q2=	0
х3	1/7	q3=	1/2
F	2/7	V=	3 1/2

Итак, оптимальные стратегии:
Р * =(3/8; 0; 5/8), Q * =(1/2; 0; 1/2),
цена игры:
для модифицированной задачи V= 3.5, а для исходной задачи V / = 3.5/10-0.1 = 0.25.

Пример решения матричной игры методом линейного программирования

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

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	5	-8	7	-6	0	-8
A2	8	-5	9	-3	2	-5
A3	-2	7	-3	6	-4	-4
b = max(Bi )	8	7	9	6	2	0

Решение находим с помощью калькулятора.
Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.
Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называют выбором стратегии игрока.
Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.
Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	B4	B5	a = min(Ai)
A1	5	-8	7	-6	0	-8
A2	8	-5	9	-3	2	-5
A3	-2	7	-3	6	-4	-4
b = max(Bi)	8	7	9	6	2

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = -4, которая указывает на максимальную чистую стратегию A₃.
Верхняя цена игры b = min(b_j) = 2.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах -4 ≤ y ≤ 2. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если a_ij ≥ a_kj для всех j Э N и хотя бы для одного j a_ij > a_kj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M a_ij ≤ a_il и хотя бы для одного i a_ij < a_il. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
Стратегия A₂ доминирует над стратегией A₁ (все элементы строки 2 больше или равны значениям 1-ой строки), следовательно, исключаем 1-ую строку матрицы. Вероятность p₁ = 0.

8	-5	9	-3	2
-2	7	-3	6	-4

С позиции проигрышей игрока В стратегия B₅ доминирует над стратегией B₁ (все элементы столбца 5 меньше элементов столбца 1), следовательно, исключаем 1-й столбец матрицы. Вероятность q₁ = 0.
С позиции проигрышей игрока В стратегия B₅ доминирует над стратегией B₃ (все элементы столбца 5 меньше элементов столбца 3), следовательно, исключаем 3-й столбец матрицы. Вероятность q₃ = 0.

Мы свели игру 3 x 5 к игре 2 x 3.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (5). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях (для игрока II):
12x₂ ≥ 1
2x₁+11x₂ ≥ 1
7x₁+x₂ ≥ 1
F(x) = x₁+x₂ > min
найти максимум функции Z(y) при ограничениях (для игрока I):
2y₂+7y₃ ≤ 1
12y₁+11y₂+y₃ ≤ 1
Z(y) = y₁+y₂+y₃ > max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции Z(Y) = y₁+y₂+y₃ при следующих условиях-ограничений.
2y₂+7y₃≤1
12y₁+11y₂+y₃≤1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2y₂+7y₃+y₄ = 1
12y₁+11y₂+y₃+y₅ = 1
Решим систему уравнений относительно базисных переменных: y₄, y₅
Полагая, что свободные переменные равны 0, получим первый опорный план:
Y0 = (0,0,0,1,1)

Базис	B	y1	y2	y3	y4	y5
y4	1	0	2	7	1	0
y5	1	12	11	1	0	1
Z(Y0)	0	-1	-1	-1	0	0

Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₃, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3
и из них выберем наименьшее:
min (1 : 7 , 1 : 1 ) = 1 /₇
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	y5	min
y4	1	0	2	7	1	0	1 /7
y5	1	12	11	1	0	1	1
Z(Y1)	0	-1	-1	-1	0	0

Формируем следующую часть симплексной таблицы. Вместо переменной y₄ в план 1 войдет переменная y₃.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4	y5
y3	1 /7	0	2 /7	1	1 /7	0
y5	6 /7	12	75 /7	0	-1 /7	1
Z(Y1)	1 /7	-1	-5 /7	0	1 /7	0

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y₁, так как это наибольший коэффициент по модулю.
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1
и из них выберем наименьшее:
min (- , 6 /₇ : 12 ) = 1 /₁₄
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (12) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	y1	y2	y3	y4	y5	min
y3	1 /7	0	2 /7	1	1 /7	0	—
y5	6 /7	12	75 /7	0	-1 /7	1	1 /14
Z(Y2)	1 /7	-1	-5 /7	0	1 /7	0

Формируем следующую часть симплексной таблицы. Вместо переменной y₅ в план 2 войдет переменная y₁.

Получаем новую симплекс-таблицу:

Базис	B	y1	y2	y3	y4	y5
y3	1 /7	0	2 /7	1	1 /7	0
y1	1 /14	1	25 /28	0	-1 /84	1 /12
Z(Y2)	3 /14	0	5 /28	0	11 /84	1 /12

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

Базис	B	y1	y2	y3	y4	y5
y3	1 /7	0	2 /7	1	1 /7	0
y1	1 /14	1	25 /28	0	-1 /84	1 /12
Z(Y3)	3 /14	0	5 /28	0	11 /84	1 /12

Оптимальный план можно записать так:
y₁ = 1 /₁₄, y₂ = 0, y₃ = 1 /₇
Z(Y) = 1* 1 /₁₄ + 1*0 + 1* 1 /₇ = 3 /₁₄
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
x₁= 11 /₈₄, x₂= 1 /₁₂
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что X = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А -1 через алгебраические дополнения, получим:

1 /7	0
-1 /84	1 /12

Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных.
Тогда X = C*A -1 =

1 /7	0
-1 /84	1 /12

Оптимальный план двойственной задачи равен:
x₁ = 11 /₈₄, x₂ = 1 /₁₂
F(X) = 1* 11 /₈₄+1* 1 /₁₂ = 3 /₁₄
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
q_i = g*y_i; p_i = g*x_i.
Цена игры: g = 1 : 3 /₁₄ = 14 /₃
p₁ = 14 /₃* 11 /₈₄ = 11 /₁₈
p₂ = 14 /₃* 1 /₁₂ = 7 /₁₈
Оптимальная смешанная стратегия игрока I: P = ( 11 /₁₈; 7 /₁₈)
q₁ = 14 /₃* 1 /₁₄ = 1 /₃
q₂ = 14 /₃*0 = 0
q₃ = 14 /₃* 1 /₇ = 2 /₃
Оптимальная смешанная стратегия игрока II: Q = ( 1 /₃; 0; 2 /₃)
Поскольку ранее к элементам матрицы было прибавлено число (5), то вычтем это число из цены игры.
4 2 /₃ — 5 = -1 /₃
Цена игры: v= -1 /₃
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑a_ijq_j ≤ v
∑a_ijp_i ≥ v
M(P₁;Q) = (-5* 1 /₃) + (-3*0) + (2* 2 /₃) = -0.333 = v
M(P₂;Q) = (7* 1 /₃) + (6*0) + (-4* 2 /₃) = -0.333 = v
M(P;Q₁) = (-5* 11 /₁₈) + (7* 7 /₁₈) = -0.333 = v
M(P;Q₂) = (-3* 11 /₁₈) + (6* 7 /₁₈) = 0.5 ≥ v
M(P;Q₃) = (2* 11 /₁₈) + (-4* 7 /₁₈) = -0.333 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Поскольку из исходной матрицы были удалены строки и столбцы, то найденные векторы вероятности можно записать в виде:
P(0, 11 /₁₈, 7 /₁₈)
Q(0, 1 /₃,0,0, 2 /₃)

Пример №2 . Решить матричную игру методом линейного программирования.

Решение находим через сервис матричная игра.

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 5, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 7.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 5 Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
6x₁+10x₂+13x₃+7x₄ >= 1
5x₁+4x₂+10x₃+11x₄ >= 1
7x₁+7x₂+4x₃+5x₄ >= 1
F(x) = x₁+x₂+x₃+x₄ = min
найти максимум функции Ф(y) при ограничениях:
6y₁+5y₂+7y₃ 10y₁+4y₂+7y₃ 13y₁+10y₂+4y₃ 7y₁+11y₂+5y₃ Ф(y) = y₁+y₂+y₃ = max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = x₁ + x₂ + x₃ + x₄ при следующих условиях-ограничений.
6x₁ + 10x₂ + 13x₃ + 7x₄≥1
5x₁ + 4x₂ + 10x₃ + 11x₄≥1
7x₁ + 7x₂ + 4x₃ + 5x₄≥1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
6x₁ + 10x₂ + 13x₃ + 7x₄-1x₅ + 0x₆ + 0x₇ = 1
5x₁ + 4x₂ + 10x₃ + 11x₄ + 0x₅-1x₆ + 0x₇ = 1
7x₁ + 7x₂ + 4x₃ + 5x₄ + 0x₅ + 0x₆-1x₇ = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
-6x₁-10x₂-13x₃-7x₄ + 1x₅ + 0x₆ + 0x₇ = -1
-5x₁-4x₂-10x₃-11x₄ + 0x₅ + 1x₆ + 0x₇ = -1
-7x₁-7x₂-4x₃-5x₄ + 0x₅ + 0x₆ + 1x₇ = -1
Решим систему уравнений относительно базисных переменных: x₅, x₆, x₇,
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,-1,-1,-1)

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

Посмотреть все итерации
Конец итераций: индексная строка не содержит отрицательных элементов — найден оптимальный план
Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так: x₁ = 24 /₂₂₇, x₄ = 9 /₂₂₇, x₂ = 2 /₂₂₇
F(X) = 1• 24 /₂₂₇ + 1• 2 /₂₂₇ = 35 /₂₂₇
Составим двойственную задачу к прямой задаче.
6y₁ + 5y₂ + 7y₃≤1
10y₁ + 4y₂ + 7y₃≤1
13y₁ + 10y₂ + 4y₃≤1
7y₁ + 11y₂ + 5y₃≤1
y₁ + y₂ + y₃ → max
y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0
Данную двойственную задачу можно решить двумя способами – используя снова прямой симплексный метод и воспользовавшись теоремой двойственности.

Первый способ нахождений двойственной задачи

Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = x₁ + x₂ + x₃ при следующих условиях-ограничений.
6x₁ + 5x₂ + 7x₃≤1
10x₁ + 4x₂ + 7x₃≤1
13x₁ + 10x₂ + 4x₃≤1
7x₁ + 11x₂ + 5x₃=1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
6x₁ + 5x₂ + 7x₃ + 1x₄ + 0x₅ + 0x₆ = 1
10x₁ + 4x₂ + 7x₃ + 0x₄ + 1x₅ + 0x₆ = 1
13x₁ + 10x₂ + 4x₃ + 0x₄ + 0x₅ + 1x₆ = 1
7x₁ + 11x₂ + 5x₃ + 0x₄ + 0x₅ + 0x₆ = 1
Введем искусственные переменные x.
6x₁ + 5x₂ + 7x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇= 1
10x₁ + 4x₂ + 7x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇= 1
13x₁ + 10x₂ + 4x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇= 1
7x₁ + 11x₂ + 5x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇= 1
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = x₁+x₂+x₃ — Mx₇ => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x₇ = 1-7x₁-11x₂-5x₃
которые подставим в целевую функцию:
F(X) = x₁ + x₂ + x₃ — M(1-7x₁-11x₂-5x₃) => max
или
F(X) = (1+7M)x₁+(1+11M)x₂+(1+5M)x₃+(-1M) => max

Второй способ нахождений двойственной задачи

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А -1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда

Решение матричной игры симплексным методом

Найти решение матричной игры. Решить матричные игры симплексным методом.
Задание. Свести задачу, заданную платежной матрицей, к задаче линейного программирования (предварительно упростив задачу, убрав строго доминируемые стратегии, если это возможно) и решить симплекс методом.

Решение проводим с помощью калькулятора.

Игроки	B1	B2	B3	a = min(Ai)
A1	0	3	1	0
A2	3	0	5	0
A3	2	1	1	1
b = max(Bi )	3	3	5	0

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = 1, которая указывает на максимальную чистую стратегию A₃.
Верхняя цена игры b = min(b_j) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0x₁ + 3x₂ + 2x₃-1x₄ + 0x₅ + 0x₆ = 1
3x₁ + 0x₂ + 1x₃ + 0x₄-1x₅ + 0x₆ = 1
1x₁ + 5x₂ + 1x₃ + 0x₄ + 0x₅-1x₆ = 1

Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
0x₁-3x₂-2x₃ + 1x₄ + 0x₅ + 0x₆ = -1
-3x₁ + 0x₂-1x₃ + 0x₄ + 1x₅ + 0x₆ = -1
-1x₁-5x₂-1x₃ + 0x₄ + 0x₅ + 1x₆ = -1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆,
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,-1,-1,-1)

План	Базис	B	x1	x2	x3	x4	x5	x6
0	x4	-1	0	-3	-2	1	0	0
x5	-1	-3	0	-1	0	1	0
x6	-1	-1	-5	-1	0	0	1
Индексная строка	F(X0)	0	1	1	1	0	0	0

Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A -1 .
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А -1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A -1 =

Оптимальный план двойственной задачи равен:
y₁ = 1 /₃, y₂ = 1 /₃, y₃ = 0
Z(Y) = 1* 1 /₃+1* 1 /₃+1*0 = 2 /₃
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 2 /₃ = 1 1 /₂

Оптимальная стратегия игрока А: P( 1 /₂ ; 1 /₂; 0)
Оптимальная стратегия игрока B: Q( 1 /₂; 1 /₂; 0)

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

Игроки	B1	B2	B3	a = min(Ai)
A1	2	3	2	2
A2	4	2	1	1
A3	1	3	3	1
b = max(Bi )	4	3	3	0

Решение матричной игры находим через сервис решение матричной игры.
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 3.
Что свидетельствует об отсутствии седловой точки, так как a<>b, тогда цена игры находится в пределах 2 Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
2x₁+4x₂+x₃ >= 1
3x₁+2x₂+3x₃ >= 1
2x₁+x₂+3x₃ >= 1
F(x) = x₁+x₂+x₃ = min
найти максимум функции Ф(y) при ограничениях:
2y₁+3y₂+2y₃ 4y₁+2y₂+y₃ y₁+3y₂+3y₃ Ф(y) = y₁+y₂+y₃ = max
Решаем эти системы симплекс-методом.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = x₁ + x₂ + x₃ при следующих условиях-ограничений.
2x₁ + 4x₂ + x₃≥1
3x₁ + 2x₂ + 3x₃≥1
2x₁ + x₂ + 3x₃≥1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x₁ + 4x₂ + 1x₃-1x₄ + 0x₅ + 0x₆ = 1
3x₁ + 2x₂ + 3x₃ + 0x₄-1x₅ + 0x₆ = 1
2x₁ + 1x₂ + 3x₃ + 0x₄ + 0x₅-1x₆ = 1
Поскольку задача решается на минимум и элементы единичной матрицы отрицательны, сведем задачу к нахождению максимума. Для этого умножим все строки на (-1) и будем искать первоначальный опорный план.
-2x₁-4x₂-1x₃ + 1x₄ + 0x₅ + 0x₆ = -1
-3x₁-2x₂-3x₃ + 0x₄ + 1x₅ + 0x₆ = -1
-2x₁-1x₂-3x₃ + 0x₄ + 0x₅ + 1x₆ = -1

Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 5 /₁₁ = 2 1 /₅
p1 = 2 1 /₅•0 = 0
p2 = 2 1 /₅• 2 /₁₁ = 2 /₅
p3 = 2 1 /₅• 3 /₁₁ = 3 /₅
q1 = 2 1 /₅• 2 /₁₁ = 2 /₅
q2 = 2 1 /₅•0 = 0
q3 = 2 1 /₅• 3 /₁₁ = 3 /₅

Оптимальная стратегия игрока А: P( 0; 2 /₅; 3 /₅)
Оптимальная стратегия игрока B: Q( 2 /₅;0; 3 /₅)

Решение матричной игры путем ее сведения к задачам линейного программирования

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

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

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

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

где X > 0, а р — любое вещественное число, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а цены игр удовлетворяют следующему условию: v_B = Xv_A + р.

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

Будем считать, что цена игры с платежной матрицей А_тХп положительна (и > 0). Если это не так, то согласно аффинному правилу всегда можно подобрать такое число р, прибавление которого ко всем элементам платежной матрицы дает матрицу с положительными элементами и, следовательно, обеспечивает положительное значение цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.

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

Разделим все уравнения и неравенства в данных системах на и (это можно сделать, так как по предположению о > 0) и введем обозначения:

Поскольку первый игрок стремится максимизировать цену игры о выбором значений х_[у то обратная величина 1/о должна минимизироваться выбором р_г Таким образом, решение первой задачи сводится к нахождению таких неотрицательных значений р., 2=1. т_у при которых

Поскольку второй игрок стремится найти такие значения у_> и, следовательно, q_y чтобы цена игры и была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений q_jy j = 1, . п_у при которых

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

Решив эти задачи, получим значения р®, i = 1,т_у q®_yj = 1. п.

Тогда значение цены игры о определяется из условия

Оптимальные смешанные стратегии, т.е. х® и г/?, получаются по формулам

Пример 4.7. Рассмотрим вариант игры «Борьба за рынки». Две конкурирующие компании А и Б принимают решение о финансировании трех инновационных технических проектов. Каждая из компаний может инвестировать 100 дсн. ед. Компания Б пытается занять рынок, на котором традиционно компания А лидирует. В случае разработки и развития одних и тех же проектов компания А получит прибыль, тогда как компания Б понесет убытки. Если инвестиции направляются в разные проекты, компания А понесет убытки, связанные с перераспределением рынка, а прибыль предприятия Б будет соответствовать убытку предприятия А. Необходимо найти оптимальные стратегии предприятий. Прибыль предприятия А при разных стратегических ситуациях представлена в таблице:

Стратегии предприятия Б

Стратегии предприятия А

Решение в MS Excel

Решим задачу с помощью программы MS Excel. В таблицу MS Excel вводятся элементы платежной матрицы игры и с помощью функций МИН() и МАКС() определяются минимальные и максимальные значения по строкам и столбцам соответственно, затем с помощью этих же функций находятся максимин и ми- нимакс (табл. 4.2). Поскольку эти значения не совпадают, седловой точки в игре нет, г.е. в чистых стратегиях она не решается. Значение цены игры должно лежать в диапазоне (-5; 10).

Проверка наличия седловой точки в игре

Для использования алгоритма решения игры путем ее сведения к задаче линейного программирования применим аффинное правило. С помощью функции МИН() находим минимальное значение элементов платежной матрицы (-20). Модуль этого числа определяется как ABS(MHH(. )). С помощью аффинного преобразования с параметрами X = 1 и р = 20 получим новую платежную матрица (табл. 4.3).

Сведение игры к задаче линейного программирования

Справа от платежной матрицы произвольно указываются искомые переменные р. (на этом этапе могут указываться любые значения). В ячейках под платежной матрицей с помощью функции СУММПРОИЗВ() определяются значения

которые будут использоваться в ограничениях задачи ЛИ. Эти значения для произвольно выбранных p_t приведены в табл. 4.3.

В ячейке, обозначенной как «Целевая функция», вводится формула СУММ(. ), соответствующая выражению для целевой функции

В ячейке, обозначенной как «Цена игры», вводится формула для определения цены игры через значение целевой функции:

В ячейках, обозначенных как x_it вводятся формулы для обратного преобразования переменных и нахождения искомых элементов смешанной стратегии первого игрока x_i = u Pj.

Формулировка первой задачи линейного программирования: найти значе-

ни я Р’_У обеспечивающие минимум функции YjPi * пип при условиях ^ a_ijp_i > 1,

Решение задачи линейного программирования осуществляется с помощью модуля «Поиск решения» программы MS Excel (применение этого модуля уже рассматривалось в гл. 2). В поле «Установить целевую ячейку» указывается адрес ячейки, содержащей значение целевой функции; выбирается режим «Равной: минимальному значению». В поле «Изменяя ячейки» указывается массив искомых переменных р_г Нажатием кнопки «Добавить» и выбором массива, соответствующего ограничениям задачи, в поле «Ограничения» устанавливается соответствующее условие. Нажатием кнопки «Параметры» осуществляется переход в диалоговое окно «Параметры поиска решения», в котором выбираются параметры «Линейная модель» и «Неотрицательные значения»; значения остальных параметров остаются без изменений. После закрытия окна «Параметры поиска решения» (кнопкой ОК) нажатием кнопки «Выполнить» в окне «Поиск решения» осуществляется запуск итерационного процесса поиска решения задачи ЛП.

По окончании этого процесса появляется окно «Результаты поиска решения». Если все условия задачи были сформулированы правильно, все данные, формулы и параметры введены корректно, то в окне будет указано «Решение найдено. Все ограничения и условия оптимальности выполнены». В этом случае для сохранения решения нужно нажать ОК. Результаты расчетов представлены в табл. 4.4.

Аналогично решается задача ЛП для второго игрока (табл. 4.5). Обратите внимание, что в данном случае для технического удобства массив искомых переменных расположен в строку (поскольку стратегии второго игрока соответствуют столбцам платежной матрицы), а ячейки с ограничениями — в столбец. Задача решается на максимум и формулируется так: найти значения q_jt

обеспечивающие максимум функции ? Я) * тах П Р И условиях ^ a_i>q- 0.

Результаты решения задачи ЛП для первого игрока

X = 1

Результаты решения задачи ЛП для второго игрока

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

Результаты показывают, что оптимальной стратегией компании А является распределение средств, предполагаемых к инвестированию, в пропорции 29, 60 и 11%, т.е. 29, 60 и 11 ден. ед. При этом компания А получит прибыль не менее 0,5 ден. ед. Минимальное значение прибыли (0,5 ден. ед.) компания А получит при условии, что компания Б будет придерживаться своей оптимальной стратегии инвестирования проектов, а именно 39, 25, 36%, т.е. инвестировать в проекты 39, 25 и 36 ден. ед. соответственно. Если компания Б будет отклоняться от этой стратегии (придерживаться другой схемы инвестирования), прибыль компании А будет расти.

Анализ решения показывает, что для компании Б данная игра невыгодна (ожидаемый убыток составляет приблизительно 0,5 ден. ед.). Однако если компания Б считает этот убыток сравнительно незначительным по сравнению с достижением поставленной цели — вхождением на рынок, традиционно контролируемый компанией А, то, придерживаясь своей оптимальной стратегии распределения инвестиций, компания Б потеряет не больше 0,5 ден. ед. Если компания А будет вести себя нерационально, то потери компании Б будут уменьшаться.

Таким образом, решение любой матричной игры может быть осуществлено приведением игры к двум задачам линейного программирования. Однако это требует большого объема вычислений, который растет с увеличением числа чистых стратегий игроков. Поэтому в первую очередь следует, по возможности используя метод исключения доминируемых стратегий, уменьшить число чистых стратегий игроков. Исключение слабо доминируемых стратегий может привести к потере некоторых решений. Если же исключаются только сильно доминируемые стратегии, то множество решений игры не изменится. Затем следует во всех случаях проверить наличие седловой точки, т.е. выполнение условия шах min а- = min ma ха.

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

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

Для решения матричной игры как задачи линейного программирования необходимо чтобы

Сведение матричной игры к задаче

линейного программирования

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

Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей

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

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

По условию x ₁ + x ₂ + … + x _m = 1. Разделим обе части этого равенства на v .

Оптимальная стратегия ( x ₁ , x ₂ , . x_m ) игрока А должна максимизировать величину v , следовательно, функция

должна принимать минимальное значение.

Таким образом, получена задача линейного программирования: найти минимум целевой функции (3) при ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения , и величину 1/ v , затем отыскиваются значения x _i = vt _i .

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

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

Преобразуем систему ограничений, разделив все члены неравенств на v .

По условию y ₁ + y ₂ + … + y _n = 1. Разделим обе части этого равенства на v .

Оптимальная стратегия ( y ₁ , y ₂ , . y_n ) игрока В должна минимизировать величину v , следовательно, функция

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

Пример. Найти решение игры, заданной матрицей

a = max (2, 3, 1) = 3, b = min (4, 5, 6, 5) = 4, a ¹ b , .

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

Для определения оптимальной стратегии игрока А имеем следующую задачу линейного программирования:

Для нахождения оптимальной стратегии игрока В имеем следующую задачу линейного программирования:

Оптимальные решения пары двойственных задач имеют вид

Учитывая соотношения между x _i и t _i , y _j и s_j , а также равенство

можно найти оптимальные стратегии игроков и цену игры:

(1/2, 1/2, 0), (3/4, 0, 0, 1/4), v =7/2.