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

Рассмотрим игру 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. Найти решение игры, заданной матрицей

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

Для игрока А:

Для игрока В:

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

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

min Z=t₁+t₂+t₃

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

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

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

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

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

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

Он имеет вид:

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).