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

Различают стратегии чистые и смешанные. Чистая стратегия
первого игрока (чистая стратегия
второго игрока) – это возможный ход первого (второго) игрока, выбранный им с вероятностью, равной 1.

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

,

.

Теорема : В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т. е.
.

Определение: Если для чистых стратегий ,игроковA и В соответственно имеет место равенство
, то пару чистых стратегий (,) называют седловой точкой матричной игры, элементматрицы, стоящий на пересеченииi-й строки и j-го столбца – седловым элементом платежной матрицы, а число
- чистой ценой игры.

Пример: Найти нижнюю и верхнюю чистые цены, установить наличие седловых точек матричной игры

.

Определим нижние и верхние чистые цены игры: , ,
.

В данном случае имеем одну седловую точку (А 1 ; В 2), а седловой элемент равен 5. Этот элемент является наименьшим в 1-й строке и наибольшим во 2-м столбце. Отклонение игрока А от максиминной стратегии А 1 ведет к уменьшению его выигрыша, а отклонение игрока В от минимаксной стратегии В 2 ведет к увеличению его проигрыша. Иными словами, если в матричной игре имеется седловой элемент, то наилучшими для игроков являются их минимаксные стратегии. И эти чистые стратегии, образующие седловую точку и выделяющие в матрице игры седловой элемент a 12 =5, есть оптимальные чистые стратегии исоответственно игроков А и В.

Если же матричная игра не имеет седловой точки, то решение игры затрудняется. В этих играх
. Применение минимаксных стратегий в таких играх приводит к тому, что для каждого из игроков выигрыш не превышает , а проигрыш - не меньше . Для каждого игрока возникает вопрос увеличения выигрыша (уменьшение проигрыша). Решение находят, применяя смешанные стратегии.

Определение: Смешанной стратегией первого (второго) игрока называется вектор
, где
и
(
, где
и
).

Вектор p(q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).

Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией от смешанных стратегий р, q:

.

Определение: Функция f(р, q) называется платежной функцией игры с матрицей
.

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

Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р; второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.

Совокупность оптимальных стратегий и цены игры составляет решение игры.

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

Процесс биматричной игры состоит в независимом выборе игроком I числа а игроком II - числа , после чего игрок I получает выигрыш , а игрок II - выигрыш .

Номера строк матриц и назовем чистыми стратегиями игрока I, а номера столбцов этих матриц – чистыми стратегиями игрока II. Тогда пары вида будут являться ситуациями в чистых стратегиях биматричной игры , а числа и - выигрышами I и II игроков в ситуации . Соответственно, распределение вероятностей применения чистых стратегий игрока I - и игрока II - будем называть смешанными стратегиями . Тогда пары вида представляют ситуации биматричной игры в смешанных стратегиях , а числа и являются математическими ожиданиями выигрыша I и II игроков.

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

(8.2)

где - математическое ожидание выигрыша игрока I;

Математическое ожидание выигрыша игрока II;

Оптимальная смешанная стратегия игрока I;

Оптимальная смешанная стратегия игрока II.

Задача

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

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

В подобной конфликтной ситуации одним из игроков является противолодочная подводная лодка , а другим - противолодочная подводная лодка .Очевидно, ракетная подводная лодка не может быть игроком, так как она имеет только один способ действий, заключающийся в скрытом маневрировании и выполнении уклонения с обнаружением сигналов гидролокаторов.

Характерным здесь является то, что каждый из игроков преследует разные, но не противоположные цели. Действительно, целью противолодочной подводной лодки является обнаружение ракетной подводной лодки, а целью противолодочной подводной лодки - обнаружение противолодочной подводной лодки . Поэтому для оценки достижения цели каждым из игроков в зависимости от выбранных способов действий (стратегий) необходимо иметь два критерия эффективности и соответственно две функции выигрыша. Тогда моделью подобной конфликтной ситуации будет конечная игра с ненулевой суммой, описываемая двумя матрицами одинаковой формы и , называемая биматричной.

Примем за критерий эффективности противолодочной подводной лодки (игрок I) вероятность обнаружения ракетной подводной лодки , а за критерий эффективности противолодочной подводной лодки (игрок II) – вероятность обнаружения противолодочной подводной лодки . Тогда биматричная игра будет задана матрицей (рисунок 9.a) и матрицей (рисунок 9.b).

Где - использование активного режима;

Использование пассивного режима.

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

Определение. В антагонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

Рассмотрим матричную игру G (3х4)

В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.

Оказывается, что в этом случае максиминные стратегии А 2 и В 2 будут устойчивыми по отношению к информации о поведении противника.

Действительно, пусть игрок А узнал, что противник применяет стратегию В 2 . Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А 2 , потому что любое отступление от стратегии А 2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В , не заставит его отступить от своей стратегии В 2 .

Пара стратегий А 2 и В 2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.

Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.

Стратегии А i и В j (в рассматриваемом примере А 2 , В 2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.

Величина называется ценой игры.

Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.

Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.

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

Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).

Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.

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

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

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

Будем обозначать смешанные стратегии игроков А и В соответственно

S A =||p 1 , p 2 , ..., p m ||,

S B =||q 1 , q 2 , ..., q n ||,

где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .

В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными p i и q j .

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

Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением

Естественно, что ожидаемый проигрыш игрока В равен такой же величине.

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

Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.