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

2.2 Решение матричных игр в чистых стратегиях

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет m стратегий i= 1,2,...,m, второй имеетn стратегий j= 1,2,...,n.Каждой паре стратегий (i,j) поставлено в соответствие числоаij,выражающеевыигрышигрока 1 за счёт игрока 2, если первый игрок примет своюi-ю стратегию, а 2 – своюj-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает своюi-ю стратегию (i=), 2 – своюj-ю стратегию (j=), после чего игрок 1 получает выигрышаijза счёт игрока 2 (еслиаij<0, то это значит, что игрок 1 платит второму сумму |аij| ). На этом игра заканчивается.

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

Если рассмотреть матрицу

А=

то проведение каждой партии матричной игры с матрицей Асводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.

Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2

аij (i=)

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

аij== (1).

Определение. Число, определённое по формуле (1) называетсянижней чистой ценойигрыи показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

аij , т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит своюj-ю чистую стратегию,

затем игрок 2 отыскивает такую своюj = j1стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij== (2).

Определение.Число, определяемое по формуле (2), называетсячистой верхней ценойигрыи показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

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

Определение.Если в игре с матрицей А =, то говорят, что эта игра имеетседловуюточкув чистых стратегиях ичистую ценуигры

u ==.

Седловая точка– это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство =. В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

гдеi, j– любые чистые стратегии соответственно игроков 1 и 2;(iо,jо)– стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждойстрокенаходят минимальный элемент и проверяют, является ли этот элемент максимальным в своёмстолбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий(iо,jо)игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом iоиjо называютсяоптимальными чистыми стратегиями соответственно игроков 1 и 2.

2.3 Решение матричных игр в смешанных стратегиях путём сведения к задаче линейного программирования

Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться навыигрышбольший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.

Определение.Смешанной стратегией игроканазывается полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m,то его смешанная стратегия x– это набор чисел x = (x1, ..., xm)удовлетворяющих соотношениям