Контрольные, курсовые, рефераты, тесты – готовые и на заказ!
 Гарантия качества, доступные цены, индивидуальный подход
 Работы выполняют высококвалифицированные специалисты
Войти      Регистрация
 тел. 8-912-388-82-05
  std72@mail.ru
> 20 лет успешной работы
> 50000 выполненных заказов
Отзывы/вопросы

Форма входа



Главная » Учебно-методические материалы » ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ » Математические методы. Попова Н.В.

Тема 3.5.Приведение матричной игры к задаче линейного программирования
22.12.2011, 14:32

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть игра m × n задана платежной матрицей p = (aij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A, A, ..., A, игрок В — стратегиями B, B, ..., B. Необходимо определить оптимальные стратегии S*A = ( p*,  p*2 , ... ,  p*m ) иS*B = ( q*, q*2 , ... ,  q*n ), где p*iq*j — вероятности применения соответствующих чистых стратегий Ai , Bj  p* + p*2 +...+ p*m =1q*+ q*2 +...+ q*n = 1.

Оптимальная стратегия S*A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы aij ≥ 0. Если игрок А применяет смешанную стратегию S*A = ( p*,  p*2 , ... ,  p*m ) против любой чистой стратегии Bигрока В, то он получает средний выигрыш, или математическое ожидание выигрыша aj = a1j p1 + a2j p2 +...+ am j pm , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A, A, ..., Am и результаты складываются).

Для оптимальной стратегии S*A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

(3.11)

Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:

x1 =  p1/v, x2 = p2/v , ...,  pm/v 
(3.12)

Тогда система (11) примет вид:

(3.13)

Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v
Разделив на v ≠ 0 равенство p1 + p2 + ...+ pm = 1 , получаем, что переменные x1 (i = 1, 2, ..., m) удовлетворяют условию: x1 + x2 + ...+ xm = 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных xi ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция

Z = x1 + x2 + ...+ xm,
(3.14)

обращалась в минимум. Это задача линейного программирования. Решая задачу (3.13)—(3.14), получаем оптимальное решение p*1 + p*2 + ...+ p*m и оптимальную стратегию SA 
Для определения оптимальной стратегии S*B = (q*1 + q*2 + ...+ q*n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Переменные q, q2 , ..., qn удовлетворяют неравенствам:

(3.15)

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

yj =  qj/v, j = 1, 2, ..., n,  
(3.16)

то получим систему неравенств:

(3.17)

Переменные yj (1, 2, ..., n) удовлетворяют условию 
Игра свелась к следующей задаче 
Определить значения переменных yj ≥ 0, j = 1, 2, ..., n,  которые удовлетворяют системе неравенств (3.17) и максимизируют линейную функцию

Z' = y1 + y2 + ...+ yn,
(3.18)

Решение задачи линейного программирования (3.16), (3.17) определяет оптимальную стратегию S*B = (q*1 + q*2 + ...+ q*n) . При этом цена игры

v =  1 / max, Z' = 1 / min Z 
(3.19)

Составив расширенные матрицы для задач (3.13), (3.14) и (3.17), (3.18), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (3.13), (3.14) и (3.17), (3.18) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности. Приведем примеры экономических задач, которые описываются игровыми моделями т х п и могут быть решены методами линейного программирования.

Пример 3.5.1.

Обозначив xi =  pi/v, i = 1, 2, 3 и yj = qj/v , j = 1, 2, 3, составим две взаимно-двойственные задачи линейного программирования (см. (3.13)-(3.14) и (3.17)-(3.18)).

Пример 3.5.2

При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы:

  1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
  2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.
  3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × n рекомендуется симплексный метод, для игр размера 2×22×nn×2 возможно геометрическое решение.

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

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

Пример 3.5.3.


http://matmetod-popova.narod.ru/




БАНКОВСКОЕ ДЕЛО
БУХГАЛТЕРСКИЙ, УПР. И ФИН. УЧЕТ
БЮДЖЕТ И БЮДЖЕТНАЯ СИСТЕМА РФ
ВЫСШАЯ МАТЕМАТИКА, ТВ и МС, МАТ. МЕТОДЫ
ГУМАНИТАРНЫЕ НАУКИ
ДОКУМЕНТОВЕДЕНИЕ И ДЕЛОПРОИЗВОДСТВО
ИНВЕСТИЦИИ
ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ
ИССЛЕДОВАНИЕ СИСТЕМ УПРАВЛЕНИЯ
МАРКЕТИНГ
МЕНЕДЖМЕНТ
МЕТ. РЕКОМЕНДАЦИИ, ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
МИРОВАЯ ЭКОНОМИКА И МЭО
НАЛОГИ И НАЛОГООБЛОЖЕНИЕ
ПЛАНИРОВАНИЕ И ПРОГНОЗИРОВАНИЕ
ПРАВОВЕДЕНИЕ
РАЗРАБОТКА УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
РЫНОК ЦЕННЫХ БУМАГ
СТАТИСТИКА
УПРАВЛЕНИЕ ПЕРСОНАЛОМ
УЧЕБНИКИ, ЛЕКЦИИ, ШПАРГАЛКИ (СКАЧАТЬ)
ФИНАНСОВЫЙ МЕНЕДЖМЕНТ
ФИНАНСЫ, ДЕНЕЖНОЕ ОБРАЩЕНИЕ И КРЕДИТ
ЦЕНЫ И ЦЕНООБРАЗОВАНИЕ
ЭКОНОМИКА
ЭКОНОМИКА, ОРГ-ЦИЯ И УПР-НИЕ ПРЕДПРИЯТИЕМ
ЭКОНОМИКА И СОЦИОЛОГИЯ ТРУДА
ЭКОНОМИЧЕСКАЯ ТЕОРИЯ (МИКРО-, МАКРО)
ЭКОНОМИЧЕСКИЙ АНАЛИЗ
ЭКОНОМЕТРИКА
Оформить заказ
Ваше имя *
Ваш e-mail *
Контактный телефон
Город *
Учебное заведение *
Предмет *
Тип работы *
Тема работы/вариант *
Кол-во страниц
Срок выполнения *
Прикрепить файл
Дополнительные условия


Статистика
Онлайн всего: 22
Гостей: 22
Пользователей: 0