Курсовая работа: Линейное программирование

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y– это набор чисел

y = (y1, ..., yn), yj>= 0, (j= 1,n), = 1.

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

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либоi-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И этаi-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Определение. Средний выигрыш игрока 1 в матричной игре с матрицейАвыражается в виде математического ожидания его выигрышей

E(A, x, y) ==x A yT

Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрышЕ(А, х, y), а второй – за счёт своих смешанных стратегий стремится сделатьЕ(А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры

Е(А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е(А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборыхо, уо соответственно, которые удовлетворяют равенству

Е(А, х, y) =Е(А, х, y) =Е(А, хо, уо).

ВеличинаЕ(А, хо ,уо) называется при этомценой игрыи обозначается через u.

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

Е(А, х, уо)<= Е(А, хо, уо)<= Е(А, хо, у)

Оптимальные смешанные стратегии и цена игры называютсярешением матричной игры.

Основная теорема матричных игр имеет вид :

Теорема(о минимаксе).Для матричной игры с любой матрицейАвеличины

Е(А, х, y) и Е(А, х, y) существуют и равны между собой.

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования.

Пусть игра m × n задана платежной матрицей p = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В — стратегиями B₁ , B₂ , ..., B_m . Необходимо определить оптимальные стратегии S*_A = ( p*₁ , p*₂ , ..., p*_m ) и S*_B = ( q*₁ , q*₂ , ..., q*_n ), где p*_i , q*_j — вероятности применения соответствующих чистых стратегий A_i , B_j , p*₁ + p*₂ +...+ p*_m =1, q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = ( p*₁ , p