Линейно программный способ решения матричной игры. Решение матричных игр методами линейного программирования

Пусть дана т х п- игра, заданная своей т х п- матрицей А для первого игрока, А = [а^], г Е I = {1,..., ?n}, j € J = = {1,..., ?г}. Будем предполагать, что ау ^ О . В этом случае цена игры v > 0. Предположим также, что в матрице А нс имеется идентичных строк и столбцов (если они имеются, то надо исключить лишнее). Наконец, предполагаем, что в матрице нет лишних стратегий, т.е. уже исключены столбцы (строки), элементы которых ^ (^) соответствующих элементов других столбцов (строк) для первого игрока, который играет на максимум (соответственно для второго игрока, который играет на минимум).

Учитывая эти обозначения, перепишем ограничения:

Чтобы найти максимум v для v 9 надо найти минимум для

Если ввести функцию z = - = Х4, то оказывается, что

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

Аналогичным образом, чтобы найти оптимальные стратегии для второго игрока (М(Р. Q ) ^ ?;), надо решить задачу линейного программирования:

Замечаем, что элементы а! п ^ a" i2 , г = 1,3. Следовательно, можно исключить первый столбец.(стратегию В так как командир (В) играет на минимум. Замечаем также, что элементы а" 3 ^ а[ 4 , г = 1,3. Поэтому можно исключить четвертый столбец (стратегию В 4 ). Матрица игры становится

Наконец, замечаем, что элементы a”j ^ а 2 р j = 1,2. Поэтому можно исключить вторую строку (стратегию Л 2), так как командир (Л) играет на максимум. Матрица игры становится

Чтобы решить эту последнюю игру, применим линейное программирование. Имеются двойственные задачи (1.30) и

Решим эти задачи с помощью геометрического метода (рис. 1.5).

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

Рис. 1.5.

Программа {х = х 2 = 1/2} даст минимум экономической функции z, z - Z m i n = 1.

Координаты точки С дают также оптимальную программу для двойственной задачи. Программа {у = у 2 = 1/2} даст максимум экономической функции w, w = = 1.

Так как z = 1 = -, то Т/ = - = 1 => Цена v = v"-l = 0.

Получаем оптимальные стратегии для командира (Л):

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

Оптимальные стратегии для командира (В):

т.с. надо охранять один вход двумя солдатами, а другой - одним. ?

Замечание 6. Если нс уменьшить размеры матрицы А! до второго порядка, то для решения игры надо применить симплекс-метод к двойственной задаче (1.31), которую надо представить в стандартной форме:

Заполним три симплекс-таблицы.

Таблица 1



				2 *

к = 2 Т

Разрешающий элемент - 2*.

к! = 3 Т

Таблица 2

Разрешающий элемент - 2*.

Таблица 3

Значения всех критериев Aj ^ 0, (У в ^ 0). Следовательно, программа {у 2 = 1/2; ?у 3 = 1/2; щ = 1; ?yi = 1М = 2У5 = 2У7 =

0} дает максимум экономической функции ги, zD = w max =

Так как тй = - = 1, то Т/ = 1 v = Т/ - 1 = 0 (потому

что у" = v+1). Получаем оптимальные стратегии командира (В ), который охраняет объект:

Чтобы найти оптимальную программу первичной задачи (1.30), применим теорему Неймана (с. 34), согласно которой

Min = Wmax- СлСДОВаТСЛЬНО, МИНИМуМ ЭКОНОМИЧССКОЙ фуНК- ции 2 первоначальной задачи равен z - z m n = 1.

Соответствие между переменными Х{ и yj определяется соотношением (1.24) (с. 34). Следовательно,

Из таблицы 3 находим оптимальную программу первоначальной задачи:

откуда получаем оптимальные стратегии командира (Л):

Этот результат ранее был получен при решении задачи геометрическим методом. ?

гозтземргим

Это пособие набрано с помощью пакета Scientific Workplace, состоящего из трех частей. Часть Scientific Word служит для набора и форматирования текстов. Вторая часть Maple V или MuPAD позволяет производить математические вычисления в символьном виде или с применением численных методов и строить графики в R 2 или R 3 . Третья часть Exam Builder служит для организации проверки уровня знаний.

В качестве примера решим с помощью Scientific Work- Place задачу линейного программирования:

Р е ш с н и е. С помощью клавиатуры, главного меню и панелей инструментов заполним 8 х 1 -матрицу:

и в главном меню применим команду Compute + Simplex + Maximize. Вместо заполнения пяти симплекс-таблиц получаем ответ: Maximum is at: {23 = 0, ?’1 = О.Х 2 = 40}.

Если существуют atj

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

Пусть задано матричную декабря m X n платежной матрицей (13.1).

Преобразуем систему (13.2), поделив все члены на v, v> 0 и введя обозначения

Преобразуем систему (13.6), поделив все члены на v, v> 0 и введя обозначения

Задача (13.8), (13.9) является задачей линейного программирования, решив которую получим оптимальное решение матричной игры.

Проанализировал полученные задачи линейного программирования (13.4), (13.5) и (13.8), (13.9) можно сделать вывод, что они составляют пару взаимно двойственных задач линейного программирования. Очевидно, что при нахождении оптимальных стратегий в конкретных задачах следует решать ту из взаимно двойственных задач, решение которой менее трудоемко, а решение второй найти с помощью теорем двойственности.

Последовательность действий при решении матричной игры размером m X n

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

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

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

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

Выписка решение матричной игры в смешанных стратегиях.

Пример 13.1. Фирма может выпускать три вида продукции А1, А2, А3, получая при этом прибыль, зависит от спроса, который может принимать один из четырех состояний В1, В2, В3, В4. Прибыль, которую получит фирма при выпуске и го вида продукции

Определить оптимальные пропорции выпуска продукции.

Решение. Сократить размерность платежной матрицы игры невозможно, так как она не содержит заранее невыгодных стратегий.

Определим верхнюю и нижнюю цены игры по алгоритму нахождения максимина (минимакса)

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

Задача линейного программирования, соответствует определению оптимальной стратегии игрока А, имеет вид:

Задача линейного программирования, соответствует определению оптимальной стратегии игрока В, имеет вид:

Из анализа пары взаемнодвоистих задач линейного программирования (13.10), (13.11) и (13.12), (13.13) следует, что решать симплексным методом целесообразно задачу (13.12), 13.13), поскольку она не требует введения искусственных переменных.

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

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

Симплекс-метод основывается на свойствах ЗЛП:

1. Если есть экстремум, то он единственный.

2. Множество всех планов ЗЛП выпуклая.

3. Целевая функция достигает своего оптимального значения в вершине многоугольника решений. Если она принимает свое оптимальное значение больше чем в одной из вершин, то она достигает того же значения в каждой точке, которая является линейной комбинацией этих точек.

4. Каждой вершине многоугольника решений соответствует опорный план ЗЛП.

Если нужно максимизировать целевую функцию, то можно перейти к минимуму max Ly = min (-Ly).

Сведем задачу (13.12), (13.13) к каноническому виду путем введения дополнительных переменных - y5, y6, y7.

Если неравенство в системе ограничений ЗЛП имеет знак "≤", то дополнительную переменную вводят со знаком "+"; если неравенство имеет знак "≥", то дополнительную переменную вводят со знаком "-".

ЗЛП (13.12), (13.13) в канонической форме имеет следующий вид

Переменные x1, x2, х3, х4, являются основными, х5, х6, х7 - дополнительными. Векторы р5, р, р7 образуют единичный базис и называются базисными, причем р5 - первый базисный вектор.

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

если дополнительная переменная имеет знак минус, то в это уравнение вводят искусственную переменную со знаком плюс;

если дополнительная переменная имеет знак плюс, то в это уравнение искусственную переменную вводить не нужно.

Искусственные переменные одновременно вводят в целевую функцию с неизвестным положительным коэффициентом М.

В нашем случае искусственные переменные вводить не следует.

Заполним первую симплекс-таблицу. Начальная симплекс-таблица заполняется следующим образом. В первой строке записывают коэффициенты целевой функции. В столбец "Базис" записывают базовые векторы. В столбце "С" записывают коэффициенты целевой функции при базисных векторах. В столбцах "р0", "р1", "Р2", "р3", "р4", "р5", "р6", "р7" записывают компоненты соответствующих векторов.

Для заполнения клеток таблицы, которые находятся в двух последних строках нужно элементы столбца "С" умножить на соответствующие элементы столбца, рассчитываемого и вычесть число, стоит в первой строке (за исключением столбца "р0»). Например, для заполнения клеток столбца "р2" умножим элементы столбца "С" на соответствующие элементы столбца "р2" и вычтем число - 1: 0 * 3 + 0 * 4 + 0 * 5 - (- 1) = 1.

Таблица 13.1. Первая симплексная таблица

Последняя строка симплекс-таблицы называется индексным. В нем, начиная с столбца "р1", содержатся оценки оптимальности, с помощью которых проверяют оптимальность опорного плана, соответствующего данной таблицы. Значение составляющих опорного плана расположены в столбце "р0", причем небазисные переменным присваивают нулевые значения.

Оптимальность опорного плана проверяют по индексным строкой с помощью критерия оптимальности. Критерий оптимальности опорного плана:

Если в индексной строке среди оценок оптимальности есть хотя бы одна, положительная, то опорный план не является оптимальным.

Если в индексной строке все оценки оптимальности для небазисных переменных являются отрицательными числами, то опорный план является оптимальным и единственным.

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

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

Для перехода к следующей симплекс-таблицы в индексной строке выбирают самую положительную оценку, начиная с столбца

В нашем случае есть четыре крупнейших положительных оценок, которые совпадают, поэтому среди них выберем любую, например это число 1 в столбце "р3".

Столбец, соответствующий самой положительной оценке, называется решающих. Он показывает вектор следует ввести в базис.

В нашем случае вектор "р3" следует ввести в базис.

Найдем симплексная отношение оптимальности вQo: элементы столбца "р0" поделим на положительные элементы решающих столбца. Строка, соответствует наименьшему отношению оптимальности вQo, называется решающих. Он показывает вектор следует вывести из базиса.

Генеральный элемент - это элемент, который расположен на пересечении решающих столбца и решающих строки. В нашем случае это число 6.

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

Решающих столбец дополнить нулями. Если в решающих строке есть нули, то соответствующие столбцы переписать без изменений.

Таким образом, вторая симплекс-таблица имеет вид:

Таблица 13.2. Вторая симплексная таблица

Он не является оптимальным, поскольку в индексной строке есть положительные оценки.

По правилам, которые описаны выше, перейдем к третьей симплексной таблице:

Таблица 13.3. Третья симплексная таблица

Он является не оптимальным, поскольку в индексной строке есть положительные оценки.

Перейдем к четвертой симплексной таблице:

Таблица 13.4. Четвертая симплексная таблица

Симплекс-таблицы 13.4 соответствует опорный план:

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

Таким образом, фирме (игроку А) следует выпускать 50% продукции А, 50% продукции А3, продукцию А1 не выпускать. Это позволит фирме получить гарантированную среднюю величину прибыли,

По состояний спроса можно сделать вывод, что оптимальный спрос в 75% находится в состоянии В1 и в 25% - в состоянии В4.

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

Разработан сравнительно простой метод, заключающийся в сведении матричной игры к задаче линейного программирования, которая, в свою очередь, может быть решена хорошо известными методами (например, симплекс-методом) или с помощью многочисленных инструментов компьютерного моделирования (например, с помощью модуля «Поиск решения» MS Excel).

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

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

где X > 0, а р - любое вещественное число, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а цены игр удовлетворяют следующему условию: v B = Xv A + р.

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

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

Из определения оптимальной смешанной стратегии следует, что первый игрок, придерживающийся своей оптимальной смешанной стратегии, выиграет не меньше о при любых стратегиях второго игрока (в том числе чистых), а второй игрок, придерживающийся своей оптимальной смешанной стратегии, проиграет не больше о при любых стратегиях первого игрока (в том числе чистых). Из этого следует, что смешанные стратегии х = = (x v х т), у = (y v ..., у п) соответственно первого и второго игроков и цена игры о должны удовлетворять соотношениям

Разделим все уравнения и неравенства в данных системах на и (это можно сделать, так как по предположению о > 0) и введем обозначения:

Тогда получаем

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

Поскольку второй игрок стремится найти такие значения у } и, следовательно, q y чтобы цена игры и была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений q jy j = 1, ..., п у при которых

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

Решив эти задачи, получим значения р®, i = 1,т у q® y j = 1,..., п.

Тогда значение цены игры о определяется из условия

Оптимальные смешанные стратегии, т.е. х® и г/?, получаются по формулам

Пример 4.7. Рассмотрим вариант игры «Борьба за рынки». Две конкурирующие компании А и Б принимают решение о финансировании трех инновационных технических проектов. Каждая из компаний может инвестировать 100 дсн. ед. Компания Б пытается занять рынок, на котором традиционно компания А лидирует. В случае разработки и развития одних и тех же проектов компания А получит прибыль, тогда как компания Б понесет убытки. Если инвестиции направляются в разные проекты, компания А понесет убытки, связанные с перераспределением рынка, а прибыль предприятия Б будет соответствовать убытку предприятия А. Необходимо найти оптимальные стратегии предприятий. Прибыль предприятия А при разных стратегических ситуациях представлена в таблице:

		Стратегии предприятия Б

Стратегии предприятия А

Решение в MS Excel

Решим задачу с помощью программы MS Excel. В таблицу MS Excel вводятся элементы платежной матрицы игры и с помощью функций МИН() и МАКС() определяются минимальные и максимальные значения по строкам и столбцам соответственно, затем с помощью этих же функций находятся максимин и ми- нимакс (табл. 4.2). Поскольку эти значения не совпадают, седловой точки в игре нет, г.е. в чистых стратегиях она не решается. Значение цены игры должно лежать в диапазоне (-5; 10).

Таблица 4.2

Проверка наличия седловой точки в игре

Для использования алгоритма решения игры путем ее сведения к задаче линейного программирования применим аффинное правило. С помощью функции МИН() находим минимальное значение элементов платежной матрицы (-20). Модуль этого числа определяется как ABS(MHH(...)). С помощью аффинного преобразования с параметрами X = 1 и р = 20 получим новую платежную матрица (табл. 4.3).

Таблица 4.3

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

Справа от платежной матрицы произвольно указываются искомые переменные р. (на этом этапе могут указываться любые значения). В ячейках под платежной матрицей с помощью функции СУММПРОИЗВ() определяются значения

которые будут использоваться в ограничениях задачи ЛИ. Эти значения для произвольно выбранных p t приведены в табл. 4.3.

В ячейке, обозначенной как «Целевая функция», вводится формула СУММ(...), соответствующая выражению для целевой функции

В ячейке, обозначенной как «Цена игры», вводится формула для определения цены игры через значение целевой функции:

В ячейках, обозначенных как x it вводятся формулы для обратного преобразования переменных и нахождения искомых элементов смешанной стратегии первого игрока x i = u Pj.

Формулировка первой задачи линейного программирования: найти значе-

ни я Р" У обеспечивающие минимум функции YjPi * пип при условиях ^ a ij p i > 1,

Решение задачи линейного программирования осуществляется с помощью модуля «Поиск решения» программы MS Excel (применение этого модуля уже рассматривалось в гл. 2). В поле «Установить целевую ячейку» указывается адрес ячейки, содержащей значение целевой функции; выбирается режим «Равной: минимальному значению». В поле «Изменяя ячейки» указывается массив искомых переменных р г Нажатием кнопки «Добавить» и выбором массива, соответствующего ограничениям задачи, в поле «Ограничения» устанавливается соответствующее условие. Нажатием кнопки «Параметры» осуществляется переход в диалоговое окно «Параметры поиска решения», в котором выбираются параметры «Линейная модель» и «Неотрицательные значения»; значения остальных параметров остаются без изменений. После закрытия окна «Параметры поиска решения» (кнопкой ОК) нажатием кнопки «Выполнить» в окне «Поиск решения» осуществляется запуск итерационного процесса поиска решения задачи ЛП.

По окончании этого процесса появляется окно «Результаты поиска решения». Если все условия задачи были сформулированы правильно, все данные, формулы и параметры введены корректно, то в окне будет указано «Решение найдено. Все ограничения и условия оптимальности выполнены». В этом случае для сохранения решения нужно нажать ОК. Результаты расчетов представлены в табл. 4.4.

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

обеспечивающие максимум функции? Я) * тах П Р И условиях ^ a i} q- q } > 0.

Таблица 4.4

Результаты решения задачи ЛП для первого игрока

Результаты решения задачи ЛП для второго игрока

Таблица 4.5

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

Результаты показывают, что оптимальной стратегией компании А является распределение средств, предполагаемых к инвестированию, в пропорции 29, 60 и 11%, т.е. 29, 60 и 11 ден. ед. При этом компания А получит прибыль не менее 0,5 ден. ед. Минимальное значение прибыли (0,5 ден. ед.) компания А получит при условии, что компания Б будет придерживаться своей оптимальной стратегии инвестирования проектов, а именно 39, 25, 36%, т.е. инвестировать в проекты 39, 25 и 36 ден. ед. соответственно. Если компания Б будет отклоняться от этой стратегии (придерживаться другой схемы инвестирования), прибыль компании А будет расти.

Анализ решения показывает, что для компании Б данная игра невыгодна (ожидаемый убыток составляет приблизительно 0,5 ден. ед.). Однако если компания Б считает этот убыток сравнительно незначительным по сравнению с достижением поставленной цели - вхождением на рынок, традиционно контролируемый компанией А, то, придерживаясь своей оптимальной стратегии распределения инвестиций, компания Б потеряет не больше 0,5 ден. ед. Если компания А будет вести себя нерационально, то потери компании Б будут уменьшаться.

Таким образом, решение любой матричной игры может быть осуществлено приведением игры к двум задачам линейного программирования. Однако это требует большого объема вычислений, который растет с увеличением числа чистых стратегий игроков. Поэтому в первую очередь следует, по возможности используя метод исключения доминируемых стратегий, уменьшить число чистых стратегий игроков. Исключение слабо доминируемых стратегий может привести к потере некоторых решений. Если же исключаются только сильно доминируемые стратегии, то множество решений игры не изменится. Затем следует во всех случаях проверить наличие седловой точки, т.е. выполнение условия шах min а- = min ma ха...

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

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

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

Удаляем, если они есть, доминируемые строки и доминирующие столбцы. На их месте в оптимальных стратегиях игроков соответствующие компоненты будут равны нулю.

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

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

Пример индивидуального решения.

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

Прежде всего, проверим, имеет ли матрица седловую точку. Наименьший элемент -3 первой строки не является наибольшим в третьем столбце; наименьший элемент -1 второй строки не является наибольшим в первом столбце; наконец, наименьший элемент 2 третьей строки является одновременно наибольшим в третьем столбце. Следовательно, матрица имеет седловую точку (3, 3), в которой расположен элемент а зз = 2. Значит, игра имеет решение в чистых стратегиях, а именно:

- оптимальная стратегия первого игрока;

- оптимальная стратегия второго игрока;

v = 2 - цена игры.

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

В матрице нет седловой точки, следовательно, игра имеет решение в смешанных стратегиях.

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

Прибавив ко всем элементам матрицы А", например, число с = 3, получим матрицу

все элементы которой неотрицательны, а элементы второй строки строго положительны.

Составим пару симметричных двойственных задач, так чтобы исходная задача была стандартной задачей максимизации, матрица коэффициентов этой задачи совпадала с платежной матрицей А", ·а коэффициенты при неизвестных в целевой функции и свободные члeны неравенств были бы равны единице.

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем её к основной при помощи дополнительных неизвестных x 4 ≥0, x 5 ≥0. В результате получим следующую задачу.

x j ≥ 0 (j = 1,…,5),

f (X ) = x 1 + x 2 + x 3 → тах.

Задача - каноническая и, применив к ней алгоритм симплекс-метода, получим симплексные таблицы вида

Из столбца базисных переменных, и индексной строки выпишем оптимальные планы пары двойственных задач, а именно:

f(X*) = g(Y*) =

Из решений двойственных задач получим цену игры и оптимальные стратегии игроков в игре с матрицей А":

v" = = ;

= v" = = ;

= v" = =

Игра с матрицей А" будет иметь те же оптимальные стратегии и , что и игра с матрицей А", причем цена игры

v" = v" - с = - 3 = .

И, наконец, исходная игра с матрицей А имеет оптимальные стратегии

Р*= и Q*=

и цену игры v = v" = .

Оптимальные стратегии Р* и Q * мы получили из оптимальных стратегий и , приписав нули на месте удаленных строк и столбцов.

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства M(P i , Q*) ≤ v≤ М(Р*, Q j) следует подставить компоненты найденных оптимальных стратегий Р* и Q*, компоненты чистых стратегий Р i (i = 1, 2, 3) и Q j (j = 1, 2, 3, 4, 5)

и цену игры v = .

Заметим, что сводить задачу теории игр к паре двойственных задач ЛП следует только тогда, когда все элементы хотя бы одной строки платежной матрицы строго положительны . В этом случае обе задачи будут иметь оптимальные планы, из которых можно получить оптимальные стратегии игроков. В противном случае в исходной задаче целевая функция может оказаться неограниченной, а в двойственной задаче не будет ни одного плана. Так, в после примере, если составить пару двойственных задач в игре с матрицей

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

Оптимальная смешанная стратегия первого игрока (игрока A ) имеет вид

оптимальная смешанная стратегия второго игрока (игрока B ) имеет вид:

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

Решение игр графическим методом.

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Пример1.

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

Нижней границей выигрыша для игрока А является ломаная В 3 КВ 4 ,. Стратегии В 3 , и В 4 являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В 1 и В 2 , у 1 = у 2 = 0. Решение игры сводится к решению игры с матрицей (2х2).

x 1 = 2/5, х 2 = 3/5; y 3 = 3/5, у 4 = 2/5; v = 11/5.

Ответ.

X (2/5, 3/5) и Y (0, 0,3/5, 2/5), цена игры составляет v = 11/5.

если первый игрок с вероятностью 2/5 будет применять первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;

если второй игрок с вероятностью 3/5 будет применять третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 11/5.

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

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

Верхней границей проигрыша для игрока В является ломаная А 1 КА 4 . Стратегии А 1 и А 2 являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А 3 и А 4 , поэтому вероятность их применения равна нулю, т.е. х 2 = х 3 = 0. Решение игры сводится к решению игры с матрицей (2х2)

По формулам (1)(3) находим оптимальные стратегии и цену игры:

х 1 = 7/8, х 4 = 1/8; у 1 = 3/8, у 2 = 5/8; v = 27/8.

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

X (7/8, 0, 0, 1/8) и Y (3/8, 5/8), цена игры составляет v = 27/8.

Данный ответ означает следующее:

если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.

Использование компьютерных технологий при изучении темы: «Антагонистические игры».

Для графического решения матричной игры используется Microsoft Word и Microsoft Excel, а для решения матричной игры методами линейного программирования используется Microsoft Excel опция «Поиск решения». Также для расчётов возможно использование программы MATLAB, которая представляет собой высокоуровневый технический вычислительный язык и интерактивную среду для разработки алгоритмов, визуализации и анализа данных, числовых расчетов.

Варианты заданий для самостоятельной работы.

Найти оптимальные стратегии и цену игры, заданной платежной матрицей А.

План.

14.1. Связь матричных игр и линейного программирования.

14.2. Алгоритм решения матричных игр с помощью линейного программирования.

Связь матричных игр и линейного программирования

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

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

, . (14.1)

Эта задача может быть сформулирована в виде задачи линейного программирования. Пусть

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

(14.2)

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

Для второго игрока задача записывается в виде

, .

Промежуточное соотношение:

Тогда задача примет вид

(14.3)

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

Задача для второго игрока (14.3) является двойственной к задаче для первого игрока (14.2). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока – двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков.

Математическую модель задачи (14.2) можно упростить, разделив все (n + 1) ограничения на v . Это возможно при v ¹ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сменить знаки неравенств.

Полагая v > 0, систему ограничений можно записать:

Полагая X i = x i / v и если v ® max, то 1/v ® min, получим задачу линейного программирования вида

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

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

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

где S (Y ) max = L (X ) min = 1/v , Y j = y j /n .