Нахождения оптимального решения игры двух лиц с нулевой суммой

курсовая работа

2.3 Контрольный пример

Рассмотрим игру с матрицей А=.

Итерация 0.1. Пусть игрок 1 выбрал свою 1-ю стратегию, т.е. А0= [0, 1, 2]. Тогда за начальные условия примем следующие: x0= (1, 0, 0) - приближение оптимальной стратегии игрока 1; c0=a1= (0, 1,2) - возможный выигрыш игрока 1.

Найдём множество индексов, на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: , значит множество индексов J0={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т.е. .

2. На этом шаге определим, пользуясь начальными значениями, компоненты векторов . Для этого рассмотрим подигру . Для этой подигры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.

Обозначим её через : = (0, 1, 0). Зная , можем вычислить =0а1+1а2+0а3=а2= (4, 2, 1).

3. Найдём 1. Для этого рассмотрим подыгру (23) с матрицей . Решая матрицу графическим способом, получаем, что 1=1/2.

4. Проведённые вычисления позволяют найти значения векторов x1, c1:

x1=1/2x0+1/2 =1/2 (1, 0, 0) +1/2 (0, 1, 0) = (1/2, 1/2, 0);

c1=1/2c0+1/2 =1/2 (0, 1,2) +1/2 (4, 2, 1) = (2, 3/2, 3/2).

Итерация 1. Так как 1 не равно 0, то процесс продолжается дальше. Теперь за начальные условия примем найденные значения векторов x1, c1. С их помощью вычисляем , которые с большей точностью будут близки к истинным оптимальным стратегиям игрока 1.

1. Итак, пусть x1= (1/2, 1/2, 0), c1= (2, 3/2, 3/2).

Найдём множество индексов , на которых игрок 1 может получить наименьший выигрыш: , значит, J1={2,3}. Для этих индексов выигрыш равен 3/2. Это есть значение нижней оценки цены игры, т.е. . Заметим, что .

2. Далее найдём компоненты векторов . Для этого рассмотрим подигру . В силу симметричности матрицы ее решением будет вектор (1/2, 1/2), т.е. 1/2a1+1/2a2+0a3=

= (4/2, 3/2, 3/2).

3. Вычислим коэффициент 2. Для этого решим подигру (23): . Стратегии игроков совпадают, поэтому 2=0. В этом случае цена игры совпадает со своим нижним значением, т.е. . Возвращаемся к предыдущему шагу.

Итак, оптимальной стратегией игрока 1 является стратегия x*=x1= (1/2, 1/2, 0) при стоимости игры .

Рис 2. Результаты контрольного расчета

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

Делись добром ;)