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

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

В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем.

По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной . Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называетсябесконечной .

По характеру взаимодействия игры делятся на:

бескоалиционные : игроки не имеют права вступать в соглашения, образовывать коалиции;

коалиционные (кооперативные)–могут вступать в коалиции.

В кооперативных играх коалиции наперёд определены.

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

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

Определение . Если в игре с матрицей А=(нижняя чистая цена равна верхней чистой цене), то говорят, что эта игра имеетседловую точку в чистых стратегиях ичистую цену игры==.

Седловая точка –это пара чистых стратегий(i о , j о ) соответственно игроков 1 и 2, при которых достигается равенство=.Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:, гдеi , j –любые чистые стратегии соответственно игроков 1 и 2;(i о , j о ) –стратегии, образующие седловую точку.

Таким образом, седловой элемент является минимальным вi о -й строке и максимальным вj о -м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждойстроке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своёмстолбце . Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий(i о , j о ) игроков 1 и 2, образующая седловую точку и седловой элемент, называетсярешением игры . При этомi о иj о называютсяоптимальными чистыми стратегиями соответственно игроков 1 и 2.

Свойства седловых точек:

1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.

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

13.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях.

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

Для каждого игрока можно задать следующие компоненты:

P ia – вероятность применения i-ой стратегии со стороны А.

Если подобрать такой набор P ia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {p 1 a , p 2 a , …, p ma } = S A и будет называться смешанной стратегией.

S * A = {p * 1 a , p * 2 a , …, p * ma } – оптимальная смешанная стратегия.

{ S A } – множество смешанных стратегий со стороны А, из которых нужно выбрать оптимальную.

Игра 2*2 в смешанных стратегиях.

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

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

Определение 4. Парная игра, в которой сумма выигрышей игроков равна нулю (выигрыш первого игрока равен проигрышу второго игрока) называется парной игрой с нулевой суммой или антагонистической игрой .

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

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

Построим оптимальные стратегии игроков в антагонистической игре.

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

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

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

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

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

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

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

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

Теорема 1. Для произвольной прямоугольной матрицы всегда выполняется неравенство или

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

Определение 8. Значение называется ценой игры (чистой ценой игры ) .

Определение 9. Элемент матрицы называется седловым элементом матрицы .

Замечание. Седловой элемент матрицы одновременно является минимальным в своей строке и максимальным в своём столбце, то есть

Определение 10. Пару чистых стратегий и , соответствующих и , называют седловой точкой игры .

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

Определение 11. Тройка называется решением игры .

Пример 2.4 . В игре участвуют два игрока. Каждый из них может записать независимо от другого цифры 1, 2 и 3. если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами. Если разность отрицательна, то выигрывает второй игрок. Если разность нулевая, то игра заканчивается вничью. Составить платёжную матрицу и найти цену игры.

Решение. У игрока А есть 3 стратегии:

У игрока В также есть три стратегии:

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

Вычислим возможные выигрыши первого игрока:

Тогда платёжная матрица первого игрока примет вид:

Найдём оптимальную стратегию первого игрока. Для этого найдём минимальный выигрыш при каждой его стратегии (минимальный элемент в каждой строке):

Найдём нижнюю цену игры (выберем из минимальных элементов наибольший):

Таким образом, оптимальная стратегия первого игрока:

Найдём оптимальную стратегию второго игрока. Для этого найдём максимальный выигрыш первого игрока при каждой стратегии второго игрока (максимальный элемент в каждом столбце):

Найдём верхнюю цену игры (выберем из максимальных элементов наименьший):

Таким образом, оптимальная стратегия второго игрока:

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

Рассмотрим игру m × n с матрицей P = (a ij ), i = 1, 2, ..., m; j = 1, 2, ..., n и определим наилучшую среди стратегий A 1 , A 2 , ..., A m . Выбирая стратегию A i игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий B j , для которой выигрыш для игрока А минимален (игрок В стремится "навредить" игроку А ). Обозначим через α i , наименьший выигрыш игрока А при выборе им стратегии A i для всех возможных стратегий игрока В (наименьшее число в i -й строке платежной матрицы), т.е.

Среди всех чисел α i (i = 1, 2, ..., m) выберем наибольшее: . Назовем α нижней ценой игры , или максимальным выигрышем (максимином ). Это гарантированный выигрыш игрока А при любой стратегии игрока В . Следовательно,

13. Седловая точка.

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

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

Если в игре с матрицей А нижнее и верхнее, чистые цены игры совпадают т.е. , то говорят, что эта игра имеет седловую точку, в чистых выражениях и чистую цену игры:

Седловая точка - это пара чистых стратегий (i 0 , j 0) первого и второго игрока, при котором достигается равенство .

В понятии седловой точки вложен следующий смысл:

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

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

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

Седловой элемент - является минимальным элементом строки и максимальным элементом в столбце.

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

14. Оптимальные стратегии .

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

В то же время при удачном выборе стратегии i = i* первый игрок может получить максимальный выигрыш из минимальных:

Второй игрок рассуждает сходным образом. При выборе стратегии j его максимальный проигрыш из двух возможных а1 j, а2 j равен

Если выбор стратегии j = j* оказался удачным, то он может рассчитывать на минимальный проигрыш из максимальных:

Формулы (5.2), (5.3) определяют наилучшие гарантированные выигрыши игроков. Если они совпадают, то их общее значение можно считать приемлемым для игроков компромиссом, а соответствующие стратегии i*, j* - оптимальными стратегиями.

Непосредственные вычисления по формулам (5.2), (5.3) с использованием (5.1) дают

Здесь наилучшие гарантированные выигрыши не равны и оптимальных стратегий не существует.

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

По характеру взаимодействия игры делятся на:

1) бескоалиционные : игроки не имеют права вступать в соглашения, образовывать коалиции;

2) коалиционные (кооперативные) – могут вступать в коалиции.

В кооперативных играх коалиции наперёд определены.

Определение . Если в игре с матрицей А = (нижняя чистая цена равна верхней чистой цене), то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры u = = .

Седловая точка – это пара чистых стратегий (i о,j о) соответственно игроков 1 и 2, при которых достигается равенство = .Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе: , где i, j – любые чистые стратегии соответственно игроков 1 и 2; (i о,j о) – стратегии, образующие седловую точку.

Таким образом, седловой элемент является минимальным в i о -й строке и максимальным в j о -м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце . Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (i о,j о) игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры . При этом i о и j о называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

Свойства седловых точек:

1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.

13.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях.

Для каждого игрока можно задать следующие компоненты:

Pia – вероятность применения i-ой стратегии со стороны А.

Если подобрать такой набор Pia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {p 1 a , p 2 a , …, p ma } = S A и будет называться смешанной стратегией.

S * A = {p * 1 a , p * 2 a , …, p * ma } – оптимальная смешанная стратегия.

{ S A } – множество смешанных стратегий со стороны А, из которых нужно выбрать оптимальную.

Игра 2*2 в смешанных стратегиях.

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

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

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица .

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

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

Составим платёжную матрицу:

Если первый игрок выбирает i -ю чистую стратегию, а второй игрок - j -ю чистую стратегию, то выигрыш первого игрока составит a ij единиц, а проигрыш второго игрока - также a ij единиц.

Так как a ij + (- a ij ) = 0 , то описанная игра является матричной игрой с нулевой суммой.

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

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

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

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

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

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

При решении задач на цену игры и определение стратегии для определения этих величин у второго игрока следует поступать следующим образом. Из каждого столбца выписать значение максимального элемента и уже из них выбрать минимальный. Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название - минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует "минимакс", то независимо от выбора стратегии первым игроком, он проиграет не более v 2 единиц.

Пример 1.

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

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

Итак, гарантированный выигрыш первого игрока:

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

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

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

Ещё пример из этой же серии.

Пример 2. Дана матричная игра с платёжной матрицей

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

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

Седловая точка в матричных играх

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

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

В этом случае матричная игра имеет решение в чистых стратегиях .

Пример 3. Дана матричная игра с платёжной матрицей

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

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

Пример 4. Дана матричная игра с платёжной матрицей

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

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

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

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

Если первый игрок использует чистые стратегии с вероятностями , то вектор называется смешанной стратегией первого игрока. Иначе говоря, это "смесь" чистых стратегий. При этом сумма этих вероятностей равна единице:

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

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

Пример 5. Дана матричная игра с платёжной матрицей

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

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

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

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

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

В таком случае для функции E существует седловая точка , что означает равенство .

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

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

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

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

Система ограничений в прямой задаче линейного программирования:

Функция цели в двойственной задаче:

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

В соответствии определениям предыдущего параграфа и координатами оптимальных планов, в силе следующие смешанные стратегии первого и второго игроков:

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

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

Нам, практикам, остаётся лишь использовать эту формулу для решения матричных игр в смешанных стратегиях. Как и формулы для нахождения оптимальных смешанных стратегий соответственно первого и второго игроков:

в которых вторые сомножители - векторы. Оптимальные смешанные стратегии также, как мы уже определили в предыдущем параграфе, являются векторами. Поэтому, умножив число (цену игры) на вектор (с координатами оптимальных планов) получим также вектор.

Пример 6. Дана матричная игра с платёжной матрицей

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

Находим линейную форму оптимальных планов как сумму найденных координат.