Принципы и методы решения матричных игр

Набор стратегий, выбранных игроками, называется ситуацией.

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

Если оба игрока выбирают одинаковые стратегии, то первый игрок выигрывает у второго 1 руб., если разные – то второй такую же сумму выигрывает у второго.

Представим платежную матрицу для первого игрока.

Таблица 1 – Платежная матрица первого игрока в орлянку

Эта матрица может быть записана и в обычном для матриц виде:

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

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

Таблица 2 – Платежная матрица первого игрока в тройку, семерку и туз

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

Исходя из этого, первый игрок отдаст предпочтение ходу семеркой. В этом случае при любом ходе соперника он будет иметь выигрыш в размере не меньше 1 руб. При выборе стратегии "Тройка" он должен ожидать, что второй игрок тоже будет ходить с тройки, что приведет к потере первым игроком 2 руб. На стратегию первого игрока "Туз" второй игрок ответит стратегией "Семерка", что приведет к потере первым игроком 3 руб.

Рассуждая точно также, второй игрок не будет ходить тройкой (если в этом случае первый пойдет тузом, то это принесет первому игроку выигрыш, а второму, соответственно, проигрыш 3 руб.). Он не будет ходить и семеркой: первый игрок, пойдя тройкой, получит выигрыш 2 руб. Лучшим для второго игрока будет ход тузом: это минимализирует его максимальный проигрыш 1 рублем.

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

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

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

Какова же стратегия игроков при отсутствии седловой точки?

Пусть выигрыш первого игрока, определяемый по максиминной стратегии h₁(x) = α, выигрыш второго игрока, определяемый по минимаксной стратегии h₂(x) = β. В равновесных задачах с седловой точкой имеет место равенство α = β, в неравновесных задачах α < β. Тогда задача может быть сведена к "справедливому" дележу разности β – α . Математическая теория игр утверждает, что компромиссное разделение этой разности между игроками можно достичь путем применения ими случайного применения своих первоначальных чистых стратегий. Случайное применение стратегии обеспечивает ее максимальную скрытность для противника. При разумном построении механизма случайного выбора стратегий последние оказываются оптимальными. Случайные величины, значениями которых являются стратегии игрока, называются смешанными стратегиями.

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

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

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

Под оптимальным программированием понимают применение в экономике математического программирования. Оно включает комплекс методов разработки оптимальных планов и программ (оптимальное планирование), регулирования хозяйственной деятельности. Математическим программированием называют область математики, посвященную теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых некоторыми ограничениями, выраженными в виде равенств и неравенств. Если изучаемая функция линейна и задана на множестве, заданном линейными равенствами и неравенствами, то данный раздел математического программирования называется линейным программированием. Использование в названии рассматриваемой области знаний слова "программирование" объясняется тем, что отыскиваемые в результате решения задачи переменные в совокупности образуют программу работы некоторого экономического объекта.

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

В неком сельскохозяйственном предприятии возделывают две культуры – пшеницу и картофель.

Для этого хозяйство располагает следующими ресурсами:

площадь пашни – 4500 га;

ресурсы рабочего времени механизаторов – 15000 чел.-дней;

денежные ресурсы для проведения работ – 30000 тыс. руб.

Урожайность пшеницы составляет 20 ц/га, картофеля – 150 ц/га. Цена реализации 1 ц пшеницы – 350 руб., 1 ц картофеля – 400 руб. Следовательно, стоимость продукции, произведенной на 1 га пшеницы, составит 350*20=7000 руб., на 1 га картофеля – 400*150=60000 руб. Затраты труда на 1 га пшеницы и картофеля составляют соответственно 2 и 10 чел.-дней. Денежные затраты на 1 га этих же культур – 2,5 и 45 тыс. руб. Легко посчитать, что 1 га пшеницы может дать чистого дохода 7-2,5=4,5 тыс. руб., а 1 га картофеля – 60-45=15 тыс. руб. Однако занять всю площадь высокодоходным картофелем не удастся: для этого потребовалось бы 10*4500=45000 чел.-дней ресурсов рабочего времени механизаторов, а их имеется только 15000; денежных ресурсов при этом было бы необходимо потратить 45*4500= 202500 тыс.руб., что существенно превышает их наличие. Бессмысленно занимать всю площадь и пшеницей: в этом случае останутся неизрасходованными 30000-(2,5*4500)=30000-11250=18750 тыс. руб. денежных средств и 15000-2*4500=15000-9000=6000 чел.-часов труда механизаторов. Чистый доход при этом составит 4,5*4500=20250 тыс. руб. По-видимому, если часть пашни занять картофелем, а часть пшеницей, то результат деятельности предприятия (а он оценивается полученной величиной чистого дохода) можно улучшить. К примеру, если занять 4100 га пашни пшеницей, а 400 га – картофелем, то масса чистого дохода возрастет до 4,5*4100+25*400=
28450 тыс. руб. Имеющиеся ресурсы позволяют реализовать такой вариант. Трудовых ресурсов понадобится для этого 2*4100+10*400=12200 чел.-дней, денежных средств – 2,5*4100+45*400=28250 тыс.руб. Предложенный вариант является допустимым. Но является ли он оптимальным? Предложение найти оптимальный план методом перебора едва ли можно признать хорошей идеей: количество возможных комбинаций, не противоречащих наличию ресурсов, бесконечно. Даже если рационализировать такой поиск, все равно эта работа весьма трудоемка. Попытаемся решить задачу, пользуясь знаниями, полученными еще в средней школе на уроках алгебры.

Обозначим площадь посева пшеницы х₁, площадь картофеля х₂.

Теперь можно составить неравенство по площади посева:

.

Аналогично можно составить неравенства по трудовым и денежным ресурсам:

;

;

; .

Приведенные неравенства выражают условия задачи.

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

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

.

Это выражение отражает цель задачи и называется ее целевой функцией.