Летающий спутник

Летающий спутник

Заработок для студента

Заработок для студента

 Заказать диплом

Заказать диплом

 Cкачать контрольную

Cкачать контрольную

 Курсовые работы

Курсовые работы

Репетиторы онлайн по любым предметам

Репетиторы онлайн по любым предметам

Выполнение дипломных, курсовых, контрольных работ

Выполнение дипломных, курсовых, контрольных работ

Магазин студенческих работ

Магазин студенческих работ

Диссертации на заказ

Диссертации на заказ

Заказать курсовую работу или скачать?

Заказать курсовую работу или скачать?

Эссе на заказ

Эссе на заказ

Банк рефератов и курсовых

Банк рефератов и курсовых

Математическое решение экономических задач Элементы линейного программирования Транспортная задача Динамическое программирование Принятие решений и элементы планирования

Математическое решение экономических задач

Принятие решений и элементы планирования

Основные понятия теории игр

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

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

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

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

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

В игре участвуют первый и второй игроки, каждый из них может записать независимо от другого цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами, и, наоборот, если разность отрицательна, то выигрывает второй игрок. Если разность равна нулю, то игра заканчивается вничью.

У первого игрока три стратегии (варианта действия): А1 (записать 1), А2 (записать 2), А3 (записать 3); у второго игрока также три стратегии: B1, B2, В3 (табл. 33.1).

Задача первого игрока — максимизировать свой выигрыш. Задача второго игрока — минимизировать свой проигрыш или минимизировать выигрыш первого игрока.

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

Для данного примера платежная матрица имеет вид

В общем случае парную игру с нулевой суммой можно записать платежной матрицей

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

Найдем наилучшую стратегию первого игрока: минимальное число а„ в каждой строке обозначим αi (i = ),

Зная αi, т.е. минимальные выигрыши при различных стратегиях Аi, первый игрок выберет ту стратегию, для которой αi максимально. Обозначим это максимальное значение через α, тогда

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

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

где β — верхняя цена игры (минимакс).

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

Для матричной игры справедливо неравенство

Если α = β, то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий (Аiопт, Bjопт) — седловой точкой матрицы. В этом случае элемент αij = v называется ценой игры, является одновременно минимальным в i-й строке и j-м столбце. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Найдем решение игры рассмотренного выше примера:

Так как α = β = 0, матрица игры имеет седловую точку.

Оптимальная стратегия первого игрока — А3, второго — В3. Из табл. 31.1 видно, что отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш, а отклонение второго игрока от В3 увеличивает его проигрыш.

Если платежная матрица не имеет седловой точки, т.е. α < β, то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. Такая сложная стратегия называется смешанной.

В игре, матрица которой имеет размерность т х п, стратегии первого игрока задаются наборами вероятностей = (x1, x2,... ,xт), с которыми игрок применяет свои чистые стратегии. Эти наборы можно рассматривать как m-мерные векторы, для координат которых

Аналогично для второго игрока наборы вероятностей определяют n-мерные векторы   = (y1, y2, … , yп), для координат которых

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

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

Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры: a ≤ v ≤ b.

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

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

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

Откуда имеем

Все элементы А2 меньше A3, т.е. А3 заведомо невыгодна для первого игрока и А2 можно исключить. Все элементы А4 меньше А3, исключаем А4.

Для второго игрока: сравнивая В1 и B4, исключаем В1; сравнивая В2 и В4, исключаем В2; сравнивая B3 и В4, исключаем В3. В результате преобразований получим матрицу

 

Графическое решение игр вида (2 x n) и (m x 2)

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии. Рассмотрим игру (2 х п), см. табл. 31.2.

Предполагаем, что игра не имеет седловой точки.

Обозначим: х1 — вероятность применения первым игроком 1-й стратегии, x2 — вероятность применения первым игроком 2-й стратегии, причем х2 = 1 — x1; y1 — вероятность применения вторым игроком 1-й стратегии, у2 — вероятность применения вторым игроком 2-й стратегии и т.д., уn — вероятность применения вторым игроком п-й стратегии.

Ожидаемый выигрыш первого игрока при применении вторым 1-й стратегии составит

Аналогично найдем ожидаемые выигрыши первого игрока при применении вторым игроком 2, 3, ..., n-й стратегий. Полученные данные поместим в табл. 31.3.

Из таблицы видно, что ожидаемый выигрыш первого игрока линейно зависит от x1. На оси X1 построим выражения ожидаемых выигрышей первого игрока.

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

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

Пример 1. Рассмотрим представленную выше игру, заданную платежной матрицей

Найти оптимальные стратегии игроков и цену игры.

Решение. Обозначим: x1 — вероятность применения первым игроком 1-й стратегии, х2, х3, х4 — вероятность использования первым игроком 2, 3, 4-й стратегий соответственно, причем х1 + x2 + x3 + x4 = 1; y1 — вероятность применения вторым игроком 1-й стратегии, у2, у3, y4, y5 — вероятность использования вторым игроком 2, 3, 4, 5-й стратегий соответственно, причем y1 + у2 + у3 + y4 + y5 = 1.

Платежная матрица была упрощена путем вычеркивания дублирующих, заведомо невыгодных стратегий. Поэтому x2 = x4 = y1 = y2 = y3 = 0 и матрица имеет вид

Найдем решение игры (табл. 31.4) графическим методом (рис. 31.1). На оси Х1 разместим точки х1 = 0 и х1 = 1, через которые проведем прямые, перпендикулярные оси Х1. Подставляя х1 = 0 и x1 = 1 в выражение х1 +3, найдем значения, которые отложим на соответствующих перпендикулярных прямых. Соединив эти точки, получим прямую.

Аналогично рассмотрим выражение –3x1 + 5.

Оптимальная стратегия первого игрока определится из равенства выражений х1 + 3 и -3х1 + 5:

Цена игры v = x1 + 3 = 1/2 + 3 = 7/2.

Оптимальная стратегия первого игрока:

Найдем оптимальную стратегию для второго игрока (табл. 31.5).

Имеем

Оптимальная стратегия второго игрока (рис. 31.2):

Пример 2. Найдем решение игры вида (2 х n), заданной платежной матрицей (табл. 31.6)

Решение. Находим

α = mах (-1,2) = 2, β = min (4, 3, 3, 6) = 3, 2 ≤ v ≤ 3.

Тогда

Оптимальное решение первого игрока:

опт = (1/2, 1/2), при этом цена игры составляет v = 5/2.

Найдем оптимальное решение второго игрока (табл. 31.7).

Из рис. 31.3 следует, что оптимальная стратегия первого игрока определяется из равенства выражений –x1 + 3 и х1 + 2, соответствующих 2-й и 3-й чистым стратегиям второго игрока (см. табл. 31.5), поэтому y1 = y4 = 0, а у3 = 1 – y2.

Имеем

откуда

Оптимальное решение второго игрока (рис. 31.4):

опт = (0,1 / 2,1 / 2,0), при этом цена игры v = 5/2.

Ответ.

опт = (1/2, 1/2), опт = (0,1 / 2,1 / 2,0), v = 5/2.

Пример 3. Найдем решение игры вида (т х 2), заданной платежной матрицей (табл. 31.8)

Решение. Находим α = mах (2, 2, 2, -2) = 2, β = min (3, 6) = 3, 2 ≤ v ≤ 3. Пусть y1 и у2 (причем y2 = l —y1) — смешанные стратегии второго игрока; x1, x2, x3, x4 — смешанные стратегии первого игрока.

Находим

Оптимальное решение второго игрока (рис. 31.5):

опт = (2/3, 1/3), при этом цена игры v = 8/3.

Прямые, пересекающиеся в минимаксной точке, соответствуют 1-й и 3-й чистым стратегиям первого игрока. Это означает, что х2= х4 = 0. Следовательно, х1 = 1 — x3. Найдем оптимальную стратегию 1-го игрока (табл. 31.9, рис. 31.6).

Имеем

Оптимальное решение первого игрока:

опт = (1/3, 0, 2/3, 0), при этом цена игры v = 8/3.

Ответ.

опт = (1/3, 0, 2/3, 0), опт = (2/3, 1/3), v = 8/3.


Экономический анализ транспортных задач