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

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

Рассмотрим игру, заданную платежной матрицей А:

а₁₁ а_{12 ….} а_1n

а₂₁ а_{22 ….} a_2n

A= ……………

а_m1 а_{m2 ….} a_mn

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

Если игрок В применяет свою чистую стратегию В_j, а игрок А – свою оптимальную стратегию, то средний выигрыш игрока равен:

g_j= а_1jp₁ + а_2jp₂+…+ а_mjp_m

(j=1…n)

Если игрок A применяет свою чистую стратегию A_i, а игрок B – свою оптимальную стратегию, то средний выигрыш игрока равен:

g_i= а_i1q₁ + а_i2q₂+…+ а_inq_n

(i=1…m)

Учитывая, что g_j не может быть меньше g для игрока А, а g_j не может быть больше g для игрока В.

Двойственную задачу можно записать следующим образом:

1) для игрока А:

_m

S а_ijp_i> =g (g>0) (j=1…n)

ⁱ⁼¹

_m

Sp_i=1

ⁱ⁼¹

2) для игрока В:

_n

S а_ijq_j< =g (g>0) (i=1…m)

^j=1

_n

Sq_i=1

^j=1

Разделив левую и правую части неравенств на g>0, получим:

_m

S а_ijp_i/g> =1 (j=1…n)

ⁱ⁼¹

_n

S а_iiq_j/g< =1 (i=1…n)

^j=1

Введем обозначения:

x_i= p_i/g (x_i>=0)

y_j= q_j/g (y_j>=0)

Из выше написанных выражений переменные x_i и y_j удовлетворяют условиям:

_m

S x_i =1/g

ⁱ⁼¹

_n

S y_j =1/g

^j=1

Учитывая, что игрок А стремиться максимизировать g, а игрок В стремиться минимизировать g, переменные x_i и y_j должны быть выбраны так, чтобы целевые функции F(x) и Ф(х)

_m

F(x) =S x_i àmin

ⁱ⁼¹

_m

S а_ijx_i> =1 (j=1…n)

ⁱ⁼¹

_n

Ф(x)= S y_jàmax

^j=1

_n

S а_ijy_i< =1 (i=1…m)

^j=1

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

_m

g =1/S x_i

ⁱ⁼¹

или _n

g =1/S y_j

^j=1

_m

p_i = x_i /S x_i (i=1…m)

ⁱ⁼¹

_n

q_j =y_j./S y_j (j=1…n)

^j=1

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

Что Вы должны знать:

(вопросы для самоконтроля)

1. Каковы основные термины и определения теории игр?

2. Что из себя представляет платежная матрица?

3. Какая пара стратегий определяет седловую точку7

4. Каков принцип минимакса?

5.

Пример для закрепления:

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

	В1	В2	В3	В4	В5
А1
А2
А3
А4
А5
А6

ЛИТЕРАТУРА

1. Г.П. Фомин «Математические методы и модели в коммерческой деятельности»-М. Финансы и статистика, 2001.

2. Е.С. Венцель «Исследование операций. Задачи, принципы, методология».-М. Наука, 1980.

3. А.В. Крячков, И.В. Сухинина, В.К. Томшин «Программирование на С и С++» –М. Горячая линия-Телеком, 2000.

4. И.А.Акулич, «Математическое программирование в примерах и задачах», Высшая школа, 1986.

5. Р. Шеннон, «Имитационное моделирование систем - искусство и наука», М.,Мир, 1978.

6. А.И. Карасев, Н.Ш. Кремер, Т.И. Савельева «Математические методы и модели в планировании».- М. Экономика,1987.

7. А.С. Шапкин, Н.П. Мазаева «Математические методы и модели исследования операций», учебник, - М, Дашков и К^о, 2004