Сведение матричной игры к задаче
линейного программирования
Рассмотрим игру, матрица А которой имеет размерность т ´ п:

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

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

где ![]()
Из условия
следует, что
![]()
Решение игры должно максимизировать значение v, значит, функция
должна принимать
минимальное значение. Таким образом, получена задача линейного
программирования:
при ограничениях
(4.14) и дополнительных
условиях неотрицательности переменных
. Решая ее, находим значение
и величину
, затем отыскиваем
значения
.
Для определения стратегии игрока В запишем следующие условия:

Разделив
все члены неравенств на v,
получим

где
Переменные
должны быть выбраны
так, чтобы выполнялись условия (4.17) и достигался максимум функции
![]()
Таким образом, для решения игры имеем пару двойственных симметричных
задач линейного программирования. Используя свойство симметричности, можно
решить одну из. них,
требующую меньших вычислений, а решение второй задачи найти на основании оптимального
плана двойственной.
Покажем теперь, что существуют решения заданных
двойственных задач, а значит, и решение игры. Рассмотрим задачу, ограничения которой
заданы в системе (4.14), дополнив их условием неотрицательности переменных
. При заданных ограничениях необходимо минимизировать
функцию
.
Докажем, что задача имеет решение, т. е. существуют опорные
планы задачи и минимизируемая функция ограничена
снизу.
При построении системы (4.13), из которой получена система
(4.14), предполагалось, что платежная матрица преобразована так, что все ее элементы
положительны. Обозначим наименьший элемент матрицы через
m, тогда
![]()
Покажем, что план
является опорным. Действительно,
подставив указанные значения переменных в (4.14), убеждаемся в том, что они
удовлетворяют заданной системе ограничений.
Ограниченность целевой функции снизу следует из
неотрицательности переменных
и положительности
коэффициентов при них в выражении Z. Следовательно, значение функции Z ограничено снизу нулем.
Таким образом, существует решение рассмотренной задачи
линейного программирования, а значит, имеют решение, двойственная ей задача и
соответствующая им матричная игра.
Пример. Найти решение игры, заданной матрицей

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

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

В табл. 4.1. приведено решение задачи для игрока В. Предварительно,
с помощью дополнительных неотрицательных переменных ![]()
Таблица
4.1.
|
i |
Базис |
С базиса |
В1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
В2 |
В2 |
В3 |
В4 |
В5 |
В6 |
В7 |
|||||
|
1 2 3 |
В5 В6 В7 |
0 0 0 |
1 1 1 0 |
4 3 2 -1 |
3 4 5 -1 |
4 6 1 -1 |
2 5 3 -1 |
1 0 0 0 |
0 1 0 0 |
0 0 1 0 |
|
|
m+1 |
Wj – Cj |
||||||||||
|
1 2 3 |
В1 В6 В7 |
1 0 0 |
¼ ¼ ½ ¼ |
1 0 0 0 |
3/4 7/4 7/2 -1/4 |
1 3 -1 0 |
1/2 7/2 2 -1/2 |
1/4 -3/4 -1/2 -1/4 |
0 1 0 0 |
0 0 1 0 |
|
|
m+1 |
Wj – Cj |
||||||||||
|
1 2 3 |
В1 В4 В7 |
1 1 0 |
3/14 1/14 5/14 |
1 0 0 |
1/2 1/2 5/2 |
4/7 6/7 -19/7 |
0 1 0 |
5/14 -3/14 -1/14 |
-1/7 2/7 -4/7 |
0 0 1 |
|
|
m+1 |
Wj – Cj |
2/7 |
0 |
0 |
3/7 |
0 |
1/7 |
1/7 |
0 |
||
и
неравенства были
преобразованы в уравнения. Первоначальный базнс
образуют единичные векторы B5, B6 и В7.
Оптимальный план задачи имеет вид
![]()
Учитывая соотношения между
и
, получаем оптимальную стратегию игрока В: ![]()
Оптимальный план задачи (4.19) получим, используя оценки
-й строки последней
итерации, находящиеся в столбцах В5,
В6 и В7:
![]()
Таким образом,
следовательно, X = (1/2; 1/2; 0).