Использование теории игр в задачах линейного программирования

Рассмотрим игру т×п, определяемую матрицей

 

 

Согласно теореме 3, для оптимальной стратегии первого игрока U*= ( , ,…, ) и цены игры υ выполняется неравенство . Предположим для определенности, что υ>0. Это всегда может быть достигнуто благодаря тому, что прибавление ко всем элементам матрицы А одного и того же постоянного числа С не приводит к изменению оптимальных стра­тегий, а только лишь увеличивает цену игры на С.

Разделив теперь обе части последнего неравенства на υ, по­лучим

Положим / υ = тогда

; ≥ 0 (i= ),

 

Используя введенное обозначение, перепишем условие в виде .

 

Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине l/ υ. С уче­том этого, определение оптимальной стратегии первого игрока сводится к нахождению минимального значения функции F*= при условиях ; ≥ 0 (i= )

Аналогичные рассуждения показывают, что определение оптимальной стратегии второго игрока сводится к нахождению максимального значения функции F= при условиях ; ≥ 0 (j= ). Здесь x_j = z_j/ υ.

 

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

 

Прямая задача: найти максимальное значение функции F= при условиях ; ≥ 0 (j= ).

Двойственная задача: найти минимальное значение функции F*= при условиях ; ≥ 0 (i= ).

Используя решение пары двойственных задач, получаем фор­мулы для определения стратегий и цены игры:

Итак, процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы:

1. Составляют пару двойственных задач линейного програм­мирования, эквивалентных данной матричной игре.

2. Определяют оптимальные планы пары двойственных за­дач.

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

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

 

Решение. Составим двойственную пару задач линейного программирования: прямая задача: найти максимум функции F = x₁ + x₂ + x₃

 

при условиях

x₁, x₂, x₃ ≥ 0;

 

Двойственная задача: найти минимум функции F* = y₁+y₂+y₃ при условиях

y₁, y₂, y₃ ≥ 0;

 

Находим оптимальные планы прямой и двойственной задач (табл. 5).

 

Из табл. 5 видно, что исходная задача имеет оптималь­ный план Х*= (0; 1/2; 1), а двойственная задача — оптималь­ный план Y*= (1/2; 1; 0).

Следовательно, цена игры υ= ,

а оптимальные стратегии игроков U*= (1/3; 2/3; 0); Z*=(0; 1/3; 2/3).

 

Таблица 5

i	Базис	C6	P0
Р1	P2	P3	P4	Р5	P6
	P4
	Р5
	Р6
				-1	-1	-1
	P4
	Р3
	Р6
					-1
	P2		1/2	1/2			1/2
	Р3
	Р6		1/2	3/2			-1/2
			3/2	1/2			1/2

 

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

Пусть задана симметричная пара двойственных задач: пря­мая задача: F=CX, AХ≤В, Х≥О; двойственная задача: F* = BY, YA≥C, Y≥0. Тогда этой симметричной паре двойственных задач можно поставить в соответствие игру, определяемую матрицей

где индекс ^т означает операцию транспонирования.

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

Задача 2.Построить игру, определяемую следующей парой двой­ственных задач:

прямая задача:

2х₁ + 3х₂→mах;

 

двойственная задача:

 

10y₁+ 12y₂→min;

Решение:Здесь

 

 

B^т = (10; 12); С = (2; 3), С^т =

 

Следовательно, исходной симметричной паре двойственных задач можно поставить в соответствие матричную игру, определяемую матрицей

Контрольные вопросы и упражнения

1. Что называется игрой?

2. Какая игра называется парной?

a. Какая игра называется множественной?

3. Что понимается под партией игры?

4. Что такое ход и стратегия?

5. Чем отличается личный ход от случайного хода?

6. Какая игра является игрой с полной и неполной информацией? Приведите примеры.

7. Опишите одноходовую игру двух лиц с нулевой суммой.

8. Что значит решить игру?

9. Какая стратегия называется оптимальной?

10. Что такое цена игры?

11. Каким принципом лучше всего руководствоваться при выборе оптимальных стратегий?

12. Как определить нижнюю и верхнюю цены игры и какое соотношение существует между ними?

13. Что называется седловой точкой платежной матрицы?

15. Что такое смешанная стратегия?

16. Какие чистые стратегии называются активными?

17. Сформулируйте основную теорему теории игр.

18. Как решаются игры, не имеющие седловой точки?

1. задачах 1-4 найдите решение игр, определяемых следую­щими матрицами:

1.

.

3.

 

 

20. Постройте для симметричных пар двойствен­ных задач определяемые ими матричные игры.

5. F = 3x₁+4x₂ + х₃→max;

F'*= 12y₁ + 14y₂+ 14y₃→min;

 

 

Рекомендуемая литература

1. Т.Л. Партыка, И.И. Попов «Математические методы», М., ФОРУМ-ИНФРА-М, 2007

2. Л.Э. Хазанова «Математические методы в экономике» М., Волтерс Клувер, 2005

3. М.С. Красс, Б.П. Чупрынов « Математика в экономике. Математические методы и модели», М., Финансы и статистика, 2007

4. Кундышева Е.С. «Математическое моделирование в экономике», М.,Дашков и К⁰, 2007

5. В.В. Покровский «Математические методы в бизнесе и менеджменте», М., «Бином. Лаборатория знаний», 2008