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

Ключевые слова: теория игр, экономические задачи, линейное программирование, математическая статистика.

1 Теория игр. Экономическая интерпретация.

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

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

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

2 Общая теория матричных игр. Алгоритм.

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

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

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

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

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

При условии, что седловая точка не была найдена, решение ищется в смешанных стратегиях. Смешанной стратегией первого игрока называется вектор , где m — количество строк, все и . При этом – вероятность, с которой первый игрок выбирает свою i-ю стратегию. Аналогично определяется смешанная стратегия второго игрока. Чистая стратегия также подпадает под определение смешанной — в этом случае все вероятности равны нулю, кроме одной, равной единице.

Таблица 1

Платежная матрица

Для начала определяется седловая точка. Считаем, что первый игрок выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а второй игрок выбирает свою стратегию так, чтобы минимизировать выигрыш первого игрока. Находим гарантированный выигрыш, определяемый нижней ценой игры . Верхняя цена игры . Точка является седловой, если . Если такая точка была найдена, то выписывается решение в чистых стратегиях. Иначе цена игры находится в промежутке и решение игры находится в смешанных стратегиях.

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

Цена игры v неизвестна, однако можно считать, что . Последнее условие выполняется всегда, если все элементы ПМ неотрицательны, а этого можно достигнуть, прибавив ко всем элементам матрицы минимальный элемент в ней. Будем считать, что .

Таблица 2

Преобразованная платежная матрица

Целевая функция имеет вид: (1)

Ограничения ЗПЛ определяются по формулам:

(2)

Преобразуем систему ограничений 2, разделив все члены неравенства на v.

(3)

где

По условию , разделим обе части на v и получим новую целевую функцию: (4)

Оптимальная стратегия игрока 2 должна минимизировать величину v, следовательно, функция должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (4) при ограничениях (3).

Решаем задачу симплекс-методом и получаем значения . Цена игры находится по формуле: , а вероятности использования тактик игроком 2 по формуле: .

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

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

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

4 Прикладная программа

Данная программа была написана в интегрированной среде разработки MS Visual Studio 2017 с использованием языка c# и платформы.NET Framework, выполняющая 9 различных функций. Интерфейс и пример решения показан на рис. 1.

Рис. 1. Демонстрация интерфейса и решения с помощью прикладной программы

Рассмотрим пример решения задачи: швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. Но данным прошлых наблюдений предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составили для костюмов 27 руб., для платьев 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб.

Предприятие располагает в этих условиях двумя стратегиями: стратегия — в расчете на теплую погоду и стратегия — в расчете на холодную погоду. Природу будим рассматривать как второго игрока также с двумя стратегиями: прохладная погода () и теплая погода ().

Если предприятие выберет стратегию , то в случае прохладной погоды () доход составит: 6 800 руб., а в случае теплой погоды () доход равен 28 400 руб.

Если предприятие выберет стратегию , то реализация продукции в условиях прохладной погоды даст доход 26 000 руб., а в условиях теплой погоды 6 800.

Таблица 3

Условие задачи. Платежная матрица

Внесем условие задачи в прикладную программу и найдем решение (рис. 2).

Рис. 2. Решение задачи

Таким образом получаем, что с вероятностью 53 % будет прохладная погода, а 47 % — тёплая. Таким образом швейному предприятию стоит выпускать 47 % продукции в расчете на теплую погоду, а 53 % продукции — с расчетом на прохладную погоду, от общего количества реализованной продукции за период, чтобы получить среднюю прибыль в размере 16964руб.

Найдем решения случайно заполненных платежных матриц при разных значениях размерности и диапазона значений случайного заполнения.

Таблица 4

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

Рис. 3. Графики зависимости частоты присутствия седловой точки от диапазона случайного заполнения

Данные из таблицы 4 и рис. 3 наглядно демонстрируют, что данную прикладную программу можно использовать в целях сбора статистических данных о проведении ряда экспериментов со случайными значениями. Так, например, в матрице размерностью 3*3 за 7 экспериментов средний процент присутствия седловой сточки составляет 39,4 %. Также можно заметит, что процент присутствия седловой точки уменьшается с увеличением диапазона допустимых значений. В итоге для задач, где количество допустимых стратегий игроков меньше, соответственно больший шанс выбора единственно верной тактики.

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

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

Литература:

1. Д. Кнут «Искусство программирования. Том 1. Основные алгоритмы» 2015г. 720стр. Издательство: Вильямс.
2. Романьков, В А Введение В Теорию Игр: Учебное Пособие / Романьков В А. — Москва: ИЛ, 2016. — 834 cтр.
3. Рейзлин В. И. Численные методы оптимизации: Учебное пособие / Погребной В. К. — Томск: НИ ПТУ, 2013. — 103стр.
4. Ашманов С. А. Линейное программирование. М.: Наука. 1981.
5. Орлов А. И. Теория принятия решений Учебное пособие. — М.: Издательство «Март», 2004.
6. Зиборов, В. В. Visual C# 2012 на примерах / В. В. Зиборов. — М.: БХВ-Петербург, 2013. — 480с.