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

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

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 24.10.2014
Размер файла 146,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

1. Элементы теории игр в задачах оптимального управления экономическими процессами

Предмет теории игр. Основные понятия

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

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

При этом ни одна из сторон не может полностью контролировать положение, т.к. обеим сторонам приходится принимать решение в условиях неопределенности.

Раздел математики, изучающий конфликтные ситуации на основе их математических моделей, называется теорией игр.

Отметим основные ее понятия:

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

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

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

теория игра оптимальное управление

партией называют каждый вариант реализации игры. В партии игроки совершают конкретные ходы;

ход - выбор и реализация игроком одного из допустимых вариантов поведения.

Целью теории игр является определение оптимальной стратегии для каждого игрока.

Игры можно классифицировать по разным признакам:

Например:

- по количеству стратегий игры делятся на конечные и бесконечные;

- по взаимоотношению участников на бескоалиционные (без права заключения соглашения), некооперативные, и коалиционные (кооперативные);

- по характеру выигрышей на игры с нулевой суммой (общий капитал игроков не меняется, а лишь перераспределяется в ходе игры, при этом сумма выигрышей равна 0, а проигрыш есть отрицательный выигрыш и с ненулевой суммой;

- по виду платежной функции на матричные и непрерывные;

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

Ограничимся изучением парных матричных игр с нулевой суммой, а именно таких игр, в которых у каждого из двух игроков А и В конечное число возможных ходов - чистых стратегий.

Решение матричных игр в чистых стратегиях

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

Платежную матрицу удобно также представить в виде таблицы

В ее строках расположены чистые стратегии игрока А, а в столбцах - чистые стратегии игрока В.

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

Число называют нижней ценой игры и является гарантированным выигрышем игрока А.

Очевидно, находится в одной из строк матрицы H, к примеру в строке . Тогда стратегию называют максиминной, т.к. .

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

Рассмотрим примеры нахождения и .

Пример 1. Пусть игра задана платежной матрицей :

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

Верхняя и нижняя цены игры совпали: .

Пример 2. Задана платежная матрица

Здесь .

Теорема 1. В любой матричной игре нижняя цена игры не превосходит верхней цены игры, т.е. .

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

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

Решение матричных игр в смешанных стратегиях

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

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

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

Рассмотрим матричную игру, заданную таблицей.

Через и обозначим соответственно вероятности (относительные частоты), согласно которым игроки А и В выбирают стратегии и . Очевидно, что , , , . Упорядоченные множества и полностью определяет характер игры игроков А и В и называются их смешанными стратегиями. Отметим, что любая их чистая стратегия и может быть описана как смешанная. Действительно, или . Пусть игроки А и В применяют смешанные стратегии p и q, выбирают их случайно. Тогда вероятность выбора комбинации будет равна .

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

Этой величиной является математическое ожидание выигрыша, которое определяется формулой:

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

, .

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

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

Сформулируем основную теорему теории игр.

Теорема (Нейман): Любая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Теорема 1. Для того чтобы смешанные стратегии и были оптимальными, необходимо и достаточно выполнение неравенств

,

Теорема 2. Пусть и - оптимальные смешанные стратегии и - цена игры.

Только те вероятности , отличны от нуля, для которых

.

Только те вероятности , отличны от нуля, для которых

.

Методы решения матричных игр в смешанных стратегиях.

В этой лекции рассматриваются матричные игры, не имеющие седловых точек: - игры. Рассмотрим игру с платежной матрицей

Пусть игрок A применяет набор своих оптимальных стратегий . По основной теореме теории игр это обеспечивает ему выигрыш при любых стратегиях игрока В, т.е. выполняются соотношения:

Дополняя их уравнением

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

, , ,

где .

Повторяя те же рассуждения для игрока В, получим систему линейных уравнений

Ее решениями будут

, , ,

Пример. Молокозавод поставляет в магазин молочную продукцию () и кисломолочную продукцию (). Согласно договора между ними продукция поступает в магазин два раза в день: с 10.00 до 11.00 (1-ый срок) и с 17.00 до 18.00 (2-ой срок). Если молокозавод соблюдает сроки поставок, то магазин выплачивает премии по следующей схеме: при поставке продукции в первый срок выплачивает 5 тыс. руб., во второй срок - 3 тыс. руб.; при поставке продукции в первый срок выплачивает 2 тыс. руб., во второй срок - 3 тыс. руб. Определить оптимальные стратегии поставок и получения продукции.

Решение. Примем молокозавод за игрока А, а магазин - за игрока В. Составим платежную матрицу игры:

Сроки

Продукция

1-ый срок

2-ой срок

5

1

2

3

или

Найдем

,

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

, , , ,

, ,

Оптимальные стратегии: , , цена игры .

Таким образом, молокозавод поставляет молочную продукцию с вероятностью , а кисломолочную продукцию - с вероятностью , а магазин получает продукцию в 1-ый срок с вероятностью , а во 2-ой срок - с вероятностью и выплачивает 2,6 тыс. руб. премии молокозаводу ежедневно.

Матричная игра допускает простую геометрическую интерпретацию. Нахождение цены игры и оптимальной стратегии для игрока А равносильно решению уравнения:

Для нахождения правой части (56) применим графический метод.

Пусть игрок А выбрал смешанную стратегию , , а игрок В - k-ую чистую стратегию, . Тогда средний выигрыш игрока А окажется равным

при стратегии

при стратегии

Очевидно, , которую называют нижней огибающей прямых I и II. Нетрудно видеть, что . Таким образом, верхняя точка нижней огибающей - определяет оптимальную стратегию игрока А: и цену игры . Проиллюстрируем описанный графичексий метод на рассмотренной выше игре с платежной матрицей

.

На плоскости pOz построим две прямые, описываемые уравнениями:

и или (I) и (II).

Решая систему уравнений

найдем , , .

Таким образом, имеем полученный выше ответ игры:

и .

Теперь покажем как графическим методом найти стратегии игрока В.

Пусть игрок В выбрал смешанную стратегию , , а игрок А - i-ую чистую стратегию, . Тогда средний выигрыш игрока В окажется равным

при стратегии

при стратегии

На плоскости qOz уравнения описывают прямые III и IV

Очевидно, , которую называют верхней огибающей прямых III и IV. Нетрудно видеть, что . Таким образом, нижняя точка верхней огибающей - определяет оптимальную стратегию игрока В: и цену игры . Для рассмотренной выше гры с матрицей H найдем стратегии игрока В. На плоскости qOz построим две прямые, описываемые уравнениями:

и или

(III) и (IV).

Решая систему уравнений

найдем , , .

Таким образом, имеем и .

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

или .

Для рассмотренного примера такими уравнениями будут

или

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

и - игры.

Решают такие игры графическим способом, описанным выше. Отличие от - игр заключается в следующем.

1) Нижняя (верхняя) огибающая семейства прямых

содержит большее число отрезков.

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

, , , , где q - решение уравнения

или

3) Пусть в игре в нижней точке верхней огибающей пересекаются прямые и . Тогда при нахождении оптимальной смешанной стратегии игрока А согласно Теореме 2 полагают, что , , , , где p - решение уравнения

или .

- игры.

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

Правило доминировнаия. Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;

б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.

Например, рассмотрим игру с матрицей

Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой. Следовательно, стратегии и невыгодные и могут быть отброшены. Матрица игры преобразуется к матрице

Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-го столбца не меньше соответствующих элементов 1-го столбца, а элементы 3-го столбца не меньше соответствующих элементов 4-го столбца, т.е. стратегии и также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

.

Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут и , где и - оптимальные стратегии игры с матрицей . Аффинное правило.

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

В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП. Изучению этого вопроса посвящена следующая лекция.

Размещено на Allbest.ru

...

Подобные документы

  • Определение матричных игр в чистых стратегиях. Смешанные стратегии и их свойства. Решения игр матричным методом. Метод последовательного приближения цены игры. Отыскание седлового элемента. Антагонистические игры как первый класс математических моделей.

    контрольная работа [855,7 K], добавлен 01.06.2014

  • Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

    дипломная работа [81,0 K], добавлен 08.08.2007

  • Основные определения теории биматричных игр. Пример биматричной игры "Студент-Преподаватель". Смешанные стратегии в биматричных играх. Поиск "равновесной ситуации". 2x2 биматричные игры и формулы для случая, когда у каждого игрока имеется две стратегии.

    реферат [84,2 K], добавлен 13.02.2011

  • Принятие решений как особый вид человеческой деятельности. Рациональное представление матрицы игры. Примеры матричных игр в чистой и смешанной стратегиях. Исследование операций: взаимосвязь задач линейного программирования с теоретико-игровой моделью.

    курсовая работа [326,4 K], добавлен 05.05.2010

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

    контрольная работа [157,5 K], добавлен 04.02.2012

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

    реферат [368,2 K], добавлен 13.06.2011

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

    курсовая работа [390,2 K], добавлен 18.10.2015

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

    реферат [46,6 K], добавлен 06.05.2010

  • Содержание математики как системы математических моделей и инструментов для их создания. Возникновение "теории идей". Натуральные числа, множество целых чисел, рациональное число, вещественное или действительное число. Существующая теория чисел.

    реферат [81,7 K], добавлен 13.01.2011

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

    курсовая работа [1,8 M], добавлен 18.01.2013

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

    дипломная работа [92,2 K], добавлен 08.08.2007

  • Сущность математической теории скалярных и векторных полей, ее основные понятия и определения. Характерные черты и отличительные признаки скалярных и векторных полей, доказательства их главных теорем.

    лекция [121,6 K], добавлен 11.02.2010

  • Описание случайных ошибок методами теории вероятностей. Непрерывные случайные величины. Числовые характеристики случайных величин. Нормальный закон распределения. Понятие функции случайной величины. Центральная предельная теорема. Закон больших чисел.

    реферат [146,5 K], добавлен 19.08.2015

  • Возникновение и развитие теории групп. Проблема интегрирования дифференциальных уравнений. Алгебраические конструкции в теории автоматов. Появление понятия перестановок. Группы и классификация голограмм. Применение теории групп в квантовой механике.

    реферат [457,3 K], добавлен 08.02.2013

  • Теория вероятности как математическая наука, изучающая закономерность в массовых однородных случаях, явлениях и процессах, предмет, основные понятия и элементарные события. Определение вероятности события. Анализ основных теорем теории вероятностей.

    шпаргалка [777,8 K], добавлен 24.12.2010

  • Функциональные и степенные ряды. Разложение функций в ряды Тейлора и Макларена. Теорема Дерихле. Основные понятия в теории вероятностей. Теорема умножения и сложения вероятностей независимых событий. Формулы Бейеса, Бернулли. Локальная теорема Лапласа.

    методичка [96,6 K], добавлен 25.12.2010

  • Вклад А. Колмогорова в теорию вероятностей: публикации по проблемам дескриптивной и метрической теории функций; его глубокий интерес к философии математики. Разработка метода моментов Чебышевым. Исправление учеником Чебышева Марковым его теоремы.

    презентация [424,5 K], добавлен 28.04.2013

  • Базовые действия над матрицами. Решение матричных уравнений с помощью обратной матрицы и с помощью элементарных преобразований. Понятия обратной и транспонированной матриц. Решение матричных уравнений различных видов: АХ=В, ХА=В, АХВ=С, АХ+ХВ=С, АХ=ХА.

    курсовая работа [172,0 K], добавлен 09.09.2013

  • Роль математики в современном мире. Основные этапы развития математики. Аксиоматический метод построения научной теории. Начала Евклида как образец аксиоматического построения научной теории. История создания неевклидовой геометрии. Стили мышления.

    реферат [25,8 K], добавлен 08.02.2009

  • Теория вероятности как наука убеждения, что в основе массовых случайных событий лежат детерминированные закономерности. Математические доказательства теории. Аксиоматика теории вероятности: определения, вероятность пространства, условная вероятность.

    лекция [287,5 K], добавлен 02.04.2008

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.