Теория игр. 
Методы динамического программирования

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

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

Математический аппарат теории игр, особенно антагонистических, разработан весьма подробно. Создана важная и содержательная теория построения модели и её анализа.

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

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

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

v1 + v2 + … + vi + … + vn = 0 (1).

Число v1 может быть положительным, отрицательным и равным нулю. При v1 > 0 — выигрыш, v1 < 0 — проигрыш и v1 = 0 — ничейный исход.

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

Развитие игры во времени сводится к ряду последовательных действий или вариантов принятия решений. Выбор одного из предусмотренных правилами игры вариантов называется ходом. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор одним из игроков из возможных в данной ситуации ходов и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не игроком, а каким-либо механизмов случайного выбора. Игры могут состоять из личных, случайных и смешанных ходом.

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

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

В общем виде постановка задачи парной игры с нулевой суммой сводится к следующему: если два игрока P1 и P2 играют в какую-либо игру, то как должен вести партию каждый из этих игроков, чтобы достигнуть наиболее благоприятного исхода для себя. При случайных ходах (действиях) этих игроков естественной оценкой благоприятного исхода (выигрыша) является его среднее значение, которое обозначается символом aij. Если известны значения aij выигрыша, то парную игру можно записать в виде прямоугольной таблицы, которая называется матрицей выигрышей или платежной матрицей. Она имеет такой вид:

В матрице x1 обозначают ходы игрока Р1, а yj — ходы игрока Р2.

В любой игре важное значение имеет стратегия, под которой понимается совокупность правил, определяющих выбор при каждом личном ходе игрока, в зависимости от ситуации, сложившейся в процессе игры. В матричных играх применяются чистые и смешанные стратегии. Стратегии с компонентом, равным единице, называются чистыми стратегиями. Они обозначаются для игрока Р1 через = (0,…, 0,1,0, …, 0), где единица стоит на i-м месте (i= 1,2, …, m), и аналогично для игрока Р2 = (0, …, 0,1,0, …, 0), где единица стоит на j-м месте (j=1,2, …, n). Стратегии с отличными от единицы компонентами, представляющими вероятные её доли, называются смешанными. Если игра ведется в смешанных стратегиях, то игрок Р1 из своих m чистых стратегий может их выбирать с частотами x1, x2, …, xm, а игрок Р2 имеющий n чистых стратегий, может их выбрать с частотами y1, y2, …, yn. Набор смешанных стратегий, используемых в игре, должен отвечать требованиям (2) и (3) :

для игрока Р1.

x1+x2+…+xm=1(2).

x1>=0, x2>=0, …, xm>=0.

для игрока Р2.

y1+y2+…+yn=1(3).

y1>=0, y2 >=0, …, yn >=0.

Как видно, чистая стратегия является частным случаем смешанной стратегии, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а одна применяется с частотой 1. (2).