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

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

 

Рассмотрим игру, матрица А которой имеет размерность т ´ п:

Матрица не содержит седловой точки, поэтому решение игры представ­лено в смешанных стратегиях: При оптимальной стратегии игрока А выполняется условие (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).