Создание и использование программы для статистического анализа сведенных задач теории игр в экономической интерпретации к задачам линейного программирования | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 6 апреля, печатный экземпляр отправим 10 апреля.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №14 (200) апрель 2018 г.

Дата публикации: 05.04.2018

Статья просмотрена: 1135 раз

Библиографическое описание:

Жигульский, В. Е. Создание и использование программы для статистического анализа сведенных задач теории игр в экономической интерпретации к задачам линейного программирования / В. Е. Жигульский, О. Ю. Рудзейт. — Текст : непосредственный // Молодой ученый. — 2018. — № 14 (200). — С. 14-18. — URL: https://moluch.ru/archive/200/48862/ (дата обращения: 29.03.2024).



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

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

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

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

6800

28400

26000

6800

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

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

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

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

Таблица 4

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

Размерность матрицы

Диапазон значений

3*3

6*6

9*9

3

27

8

6

7

25

5

4

10

21

0

2

15

20

1

0

20

14

2

0

30

13

0

0

40

18

1

0

Рис. 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с.
Основные термины (генерируются автоматически): прикладная программа, прохладная погода, стратегия, теплая погода, цена игры, игрок, платежная матрица, решение, решение игры, теория игр.


Похожие статьи

Теория игр: основные понятия, типы игр, примеры

стратегия, игра, игрок, матричная игра, цена игры, решение игры, нулевая сумма, участник, верхняя цена игры, платежная матрица.

Поиск решения как средство решения задач оптимизации...

Матричные игры в чистых стратегиях определенной размерности можно автоматизировать в табличном процессоре MS EXCEL. При этом используются встроенные функции: МАКС, МИН, ЕСЛИ и ПОИСК РЕШЕНИЯ.

Решение игровых задач с нулевой суммой с помощью Microsoft...

Найдем решение игры, заданной матрицей .

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

Актуальность применения теории игр в процессе конкурсного...

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

Математическое моделирование оптимальных стратегий...

С помощью теории игр для двух бескоалиционных противников определяются стратегии, которые приведут если не к

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

Философско-методологические проблемы классической теории игр

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

Принятие решений при реализации стратегии взаимодействия...

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

Теоретико-игровая модель конкурентной борьбы за рынки сбыта...

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

Похожие статьи

Теория игр: основные понятия, типы игр, примеры

стратегия, игра, игрок, матричная игра, цена игры, решение игры, нулевая сумма, участник, верхняя цена игры, платежная матрица.

Поиск решения как средство решения задач оптимизации...

Матричные игры в чистых стратегиях определенной размерности можно автоматизировать в табличном процессоре MS EXCEL. При этом используются встроенные функции: МАКС, МИН, ЕСЛИ и ПОИСК РЕШЕНИЯ.

Решение игровых задач с нулевой суммой с помощью Microsoft...

Найдем решение игры, заданной матрицей .

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

Актуальность применения теории игр в процессе конкурсного...

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

Математическое моделирование оптимальных стратегий...

С помощью теории игр для двух бескоалиционных противников определяются стратегии, которые приведут если не к

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

Философско-методологические проблемы классической теории игр

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

Принятие решений при реализации стратегии взаимодействия...

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

Теоретико-игровая модель конкурентной борьбы за рынки сбыта...

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

Задать вопрос