РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ

Стафеев А. А., Воронова Л.И.

Национальный исследовательский университет – Высшая школа экономики

Москва, Россия

SOFTWARE SYSTEM DEVELOPMENT FOR SOLVING LINEAR OPTIMIZATION

PROBLEMS

Stafeev A. A., Voronova L.I.

National Research University - Higher School of Economics

Moscow, Russia

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

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

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

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

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

Рассмотрим конечную игру двух игроков А и В, в которой игрок А может применить одну из m стратегий A1, A2, …Am а игрок В – одну из n стратегий B1, B2, …Bn.

Будем предполагать везде далее, что игрок А выигрывает, а игрок B проигрывает Пусть каждая из сторон выбрала стратегии Ai и Bj соответственно (i, j фиксированы, i=1,m;

j=1,n).

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

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

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

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

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

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

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

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

Смешанную стратегию игрока А, состоящую из чистых стратегий A1, A2, …Am с соответствующими вероятностями p1, p2, …pm будем обозначать как вектор Смешанную стратегию игрока В, состоящую из чистых стратегий B1, B2, …Bn с соответствующими вероятностями будем обозначать как вектор При этом, по свойствам вероятности случайного события, необходимо учитывать, что и Применение игроком А отдельной чистой стратегии Ai ( ) можно рассматривать как частный случай смешанной стратегии, в которой вероятность применения им стратегии Ai равна единице, а вероятности применения других стратегий равны нулю. Следовательно, величина выигрыша игрока А (проигрыша игрока В) является случайной величиной с возможными значениями aij элементов платёжной матрицы.

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

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

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

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

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

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

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

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

Рис.1. График нижней огибающей, полученный в программном комплексе В данной задаче банку оптимально придерживаться первой стратегии (она будет более эффективна с вероятностью 0,71) Пример 2. Транспортная задача Транспортная задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида. Транспортная задача может быть записана в виде прямоугольной таблицы.

Пример подобной таблицы приведен ниже1:

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

http://cyclowiki.org/wiki/Транспортная_задача В программной реализации использовался метод потенциалов с дальнейшим перераспределением цепи поставок. Следует обратить внимание на рекурсивный метод реализации (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]);

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]);

Index1.RemoveAt(Index1.Count - 1);

Index2.RemoveAt(Index2.Count - 1);

Symbol.RemoveAt(Symbol.Count - 1);

--number;

return false;

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

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

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

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