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

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

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

Итак, пусть дана матричная игра с матрицей А порядка M х N. Согласно свойству 7 оптимальные смешанные стратегии Х = (Х1, ..., хM), Y = (Y1, ..., Yn) соответственно игроков 1 и 2 и цена игры U должны удовлетворять соотношениям.

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

, ,

Тогда (1) и (2) перепишется в виде :

, , , ,

, , , .

Поскольку первый игрок стремится найти такие значения ХI и, следовательно, Pi , чтобы цена игры U была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений Pi , при которых

, .

Поскольку второй игрок стремится найти такие значения Yj и, следовательно, Qj, чтобы цена игры U Была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений Qj, , при которых

, .

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения Pi , Qj и U.Тогда смешанные стратегии, т. е. Xi и Yj Получаются по формулам :

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

Решение. При решении этой игры к каждому элементу матрицы А прибавим 1 и получим следующую матрицу

Составим теперь пару взаимно-двойственных задач :

Решим вторую из них

Из оптимальной симплекс-таблицы следует, что

(q1, q2, q3) = (0;; 1),

А из соотношений двойственности следует, что

( p1, p2, p3) = (; 1; 0).

Следовательно, цена игры с платёжной матрицей А1 равна

. ,

А игры с платёжной матрицей А :

.

При этом оптимальные стратегии игроков имеют вид:

Х = (х1, х2, х3) = (uр1; uр2; uр3) = =

Y = (y1, y2, y3) = (uq1; uq2; uq3) = = .

< Предыдущая		Следующая >