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

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

А=(a_ij)=.

Для оптимальной стратегии первого игрока U*=(u₁*, u₂*, ...u_m*) и цены игры v выполняется неравенство (j=1...n). Предположим для определенности, что v>0. Это всегда может быть достигнуто благодаря тому, что прибавление ко всем элементам матрицы А одного и того же числа С не приводит к изменению оптимальных стратегий, а только увеличивает цену игры на С.

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

(j=1...n).

Положим u_i*/v=y_i*, тогда

(j=1...n); (i=1...m).

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

=1 в виде =1/v.

Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине 1/v. С учетом этого, определение оптимальной стратегии первого игрока сводится к нахождению минимального значения функции

F*=

при условиях

(j=1...n); (i=1...m).

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

F=

при условиях

(i=1...m); x_i0 (j=1...n).

Здесь x_j=z_j/v.

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

Прямая задача: найти максимальное значение функции F= при условиях

(i=1...m); x_i0 (j=1...n).

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

(j=1...n); y_i0 (i=1...m).

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

определения стратегий и цены игры:

==v, ==v,

v==; (i=1...m; j=1...n).

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

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

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

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

П р и м е р 1. Найти решение игры, заданной матрицей

4	3	4	2
3	4	6	5
2	5	1	3

Р е ш е н и е. Запишем две системы ограничений, соответствующие задачам отыскания оптимальной стратегии игроков А и В.

Для игрока А:

Для игрока В:

Введем замены: t_i=x_i/v, u_j=y_j/v.

Для определения оптимальной стратегии игрока А имеем следующую ЗЛП: найти

min Z=t₁+t₂+t₃

при ограничениях

Двойственная задача для определения оптимальной стратегии игрока В формулируется так: найти max W=u₁+u₂+u₃+u₄ при ограничениях

Рассмотрим решение двойственной задачи симплекс-методом.

Предварительно, с помощью неотрицательных переменных u₅, u₆ и u₇ преобразуем неравенства в уравнения.

Первоначальный базис образуют единичные векторы А₅, А₆ и А₇.

			0	1	1	1	1	0	0	0
N	Базис	Сб	A0	A1	A2	A3	A4	A5	A6	A7
1	A5	0	1	4	3	4	2	1	0	0
2	A6	0	1	3	4	6	5	0	1	0
3	A7	0	1	2	5	1	3	0	0	1
	Wj-Cj		0	-1	-1	-1	-1	0	0	0

			0	1	1	1	1	0	0	0
N	Базис	Сб	A0	A1	A2	A3	A4	A5	A6	A7
1	A1	1	1/4	1	3/4	1	1/2	1/4	0	0
2	A6	0	1/4	0	7/4	3	7/2	-3/4	1	0
3	A7	0	1/2	0	7/2	-1	2	-1/2	0	1
	Wj-Cj		1/4	0	-1/4	0	-1/2	-1/4	0	0

На третьей итерации получаем оптимальный план задачи.

			0	1	1	1	1	0	0	0
N	Базис	Сб	A0	A1	A2	A3	A4	A5	A6	A7
1	A1	1	3/14	1	1/2	4/7	0	5/14	-1/7	0
2	A4	1	1/14	0	1/2	6/7	1	-3/14	2/7	0
3	A7	0	5/14	0	5/2	-19/7	0	-1/14	-4/7	1
	Wj-Cj		2/7	0	0	3/7	0	0	1/7	0

Он имеет вид:

U=(3/14; 0; 0; 1/14), max W=1/v=2/7, v=7/2.

Учитывая соотношения между u_j и y_j, получаем, используя последней итерации, находящиеся в столбцах А₅, А₆ и А₇: t₁=1/7+0=1/7, t₂=1/7+0=1/7, t₃=0+0=0. Таким образом, Т=(1/7; 1/7; 0), следовательно, X=(1/2; 1/2; 0).