V Международная студенческая научная конференция Студенческий научный форум - 2013

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

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

В практической деятельности нередко приходится рассматривать явления и ситуации, в которых участвуют две или более стороны, имеющие несовпадающие интересы и обладающие возможностями применять для достижения своих целей разнообразные действия. Подобные явления и ситуации принято называть конфликтными, или просто конфликтами. Матричные игры – направление математики, занимающиеся разработкой решений в условиях конфликта. В качестве конфликта может выступать определенная бизнес - ситуация. Игра – формализованная модель конфликта. Под стратегией понимают набор правил, которые определяют ход игрока. Стратегии бывают чистыми (неслучайные решения игроков) и смешанными (стратегия определяется как случайная величина). Основная задача теории игр состоит в нахождении оптимальной стратегии. Наиболее распространенной моделью матричной игр является игра с «нулевой суммой», то есть когда выигрыш одного игрока равен проигрышу другого.

Рассмотрим конечную игру двух игроков А и В, в которой игрок А может применить одну из m стратегий A₁, A₂, …A_mа игрок В – одну из n стратегий B₁, B₂, …Bn.

Будем предполагать везде далее, что игрок А выигрывает, а игрок B проигрывает

Пусть каждая из сторон выбрала стратегии A_i и B_j соответственно (i, j фиксированы, i=1,m;j=1,n).

Через a_ijобозначим исход игры (сумму выигрыша игрока А или, что то же, сумму проигрыша игрока В). Предположим, что нам известны значения a_ijпри всех, i=1,m;j=1,n. Эти значения записывают в виде платежной матрицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В:

Величина называется нижней чистой ценой игры или максимином,

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

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

В теории матричных игр доказывается, что α ≤ β. Решение матричной игры, т. е. нахождение наилучших способов её ведения, производится по разному, в зависимости от того, α=β или α < β. Рассмотрим эти случаи.

1. Если α= β, то величина v= α= β называется ценой игры. Подобные игры называются играми с седловой точкой, а элемент платёжной матрицы a_ij, соответствующий максиминной (Ai) и минимаксной (Bi) стратегиям игроков, называется седловым элементом (седловой элемент – это элемент платёжной матрицы, наименьший в своей строке и наибольший в своём столбце).

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

2. Решение матричной игры с α < β находят, используя так называемые смешанные стратегии игроков – случайное чередование отдельных чистых стратегий с определённой вероятностью.

Смешанную стратегию игрока А, состоящую из чистых стратегий A₁, A₂, …A_mс соответствующими вероятностями p₁, p₂, …p_m будем обозначать как вектор

Смешанную стратегию игрока В, состоящую из чистых стратегий B₁, B₂, …Bnс соответствующими вероятностями будем обозначать как вектор

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

и

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

Средняя величина выигрыша (проигрыша) является функцией от смешанных стратегий и имеет вид

Эта функция называется платёжной функцией игры с платёжной матрицей

Пусть − оптимальные смешанные стратегии игроков А и В соответственно. Справедливы неравенства:

которые означают, что применение игроком А оптимальной смешанной стратегии p* гарантирует ему выигрыш, не меньший, чем при применении им любой другой стратегии p в свою очередь, применение игроком В оптимальной смешанной стратегии q* гарантирует ему проигрыш, не больший, чем при применении им любой другой стратегии q. Величина v=f(p*, q*) в этом случае определяет цену игры.

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

Пример. Постановка и решение матричной задачи в банковской сфере

Банк "Московские кредитные системы" планирует разместить 10 или 20% своих акций на ММВБ вдобавок к 15% уже торгующихся на ней. Его основной конкурент, банк "Финансовый стандарт", тоже торгуется на бирже, и, узнав о планах МКС, руководство решило вбросить на рынок дополнительные 5,10, 15 или же 20% акций. Возможно, что это решение так и не будет принято вследствие активного сопротивления миноритарных акционеров, которым невыгодно краткосрочное снижение курса акций.

Увеличение количества ценных бумаг в обороте банка Финансовый стандарт, несомненно, негативно скажется на стоимости акций "Московские кредитные системы".

В настоящий момент эксперты одной из крупных аудиторских компаний сотрудничают с МКС и рассчитывают возможное изменение курса акций банка в зависимости от действий конкурента.

По результатам экспертных оценок о предполагаемой стоимости акций МКС необходимо найти оптимальные стратегии банков-конкурентов и наиболее вероятное изменение стоимости ценных бумаг МКС в результате размещения.

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

Стратегии	B1 (ФС 0%)	B1 (ФС 5%)	B1 (ФС 10%)	B1 (ФС 15%)	B1 (ФС 20%)
A1 (МКС 10%)	4	3	1	-1	0
A2 (МКС 20%)	-1	1	0	5	4

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

Рис.1. График нижней огибающей, полученный в программном комплексе

В данной задаче банку оптимально придерживаться первой стратегии (она будет более эффективна с вероятностью 0,71)

Пример 2. Транспортная задача

Транспортная задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы. Пример подобной таблицы приведен ниже¹:

	Потребитель B1, потребность 20 кг	Потребитель B2, потребность 30 кг	Потребитель B3, потребность 30 кг	Потребитель B4, потребность 10 кг
Поставщик A1, запас 30 кг	С11=2 руб./кг	С12=3 руб./кг	С13=2 руб./кг	С14=4 руб./кг
Поставщик A2, запас 40 кг	С21=3 руб./кг	С22=2 руб./кг	С23=5 руб./кг	С24=1 руб./кг
Поставщик A3, запас 20 кг	С31=4 руб./кг	С32=3 руб./кг	С33=2 руб./кг	С34=6 руб./кг

Цена перевозки (например, в рублях за 1 килограмм груза) C_ij записывается в ячейки таблицы на пересечении соответствующего потребителя и поставщика (цена может быть и отрицательной — в этом случае она представляет собой прибыль). Неизвестной (искомой) величиной в задаче являются такие объемы перевозки x_ij от поставщиков к потребителям, чтобы минимизировать общие затраты на транспортировку. В табличной записи цены отделяют от объемов перевозки косой чертой или квадратным уголком, в этой статье из соображений лучшей доходчивости они подписаны. При решении транспортной задачи единственными необходимыми арифметическими действиями являются сложение и вычитание. Для поиска начального решения применяют метод северо-западного угла, метод минимальных тарифов или метод Фогеля, а для окончательной оптимизации — метод потенциалов. В то же время, транспортная задача является подмножеством задач линейного программирования и может решаться симплекс-методом.

В программной реализации использовался метод потенциалов с дальнейшим перераспределением цепи поставок. Следует обратить внимание на рекурсивный метод реализации (C#) метода потенциалов; p1,p2-начальные координаты:

private bool buildpos(int p1, int p2)

{

if (number >= 4 && p1 == k1 && p2 == k2) return true;

int income = fill_row(p1, p2);

if (cycle)

{Index1 = CopyInt(Index1, income); Index2 = CopyInt(Index2, income); return true;}

if (income!=0)

{int q = Index1.Count - 1; for (int i = q; i > q -income; i--)

{ bool f; f = buildpos(Index1[i], Index2[i]);

if (f == true) { return true;}

else { }

}

}

income = fill_column(p1, p2);

if (cycle)

{Index1 = CopyInt(Index1, income); Index2 = CopyInt(Index2, income); return true;}

if (income!=0)

{ int q = Index1.Count - 1; for (int i = Index1.Count - 1; i>q-income; i--)

{ bool f; f = buildpos(Index1[i], Index2[i]);

if (f == true)

{ return true; }

else { }

}

}

Index1.RemoveAt(Index1.Count - 1);

Index2.RemoveAt(Index2.Count - 1);

Symbol.RemoveAt(Symbol.Count - 1);

--number;

return false;

}

Выводы

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

Список литературы

1.  
   1.  

      1. Шикин Е.В., Шикина Г.В. Исследование операций: учебник/ Е.В.Шикин, Г.В. Шикина. - Проспект. : М,, 2006. - 278 с.

      2. Шилдт Г. Полный справочник по С#: учебник/ Г.Шилдт. - СПб. : Питер, 2002. - 576 с.

      3. Фролов А.В., Фролов Г.В. Визуальное проектирование приложений С#: учебник/ А.В.Фролов, Г.В. Фролов. - СПб. : Питер, 2004. - 482 с.

1^ http://cyclowiki.org/wiki/Транспортная_задача

 

5

 

Код для цитирования: Скопировать