рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Матричные игры

Реферат Курсовая Конспект

Выберите учебное заведение

Матричные игры

Матричные игры - раздел Образование, методы ОПТИМАлЬНЫХ РЕШЕНИЙ Пусть Игрок А Имеет M Чистых Стратегий А1,...

Пусть игрок А имеет m чистых стратегий А₁, А₂, … А_i,…А_m, а игрок В имеет n чистых стратегий B₁, B₂, … B_j,…B_n. Такая игра называется игрой m ´ n. Если игрок А пользуется стратегией А_i, а игрок В пользуется стратегией В_j, то обозначим через а_ij выигрыш игрока А, если а_ij > 0, или проигрыш игрока А, если а_ij < 0. Очевидно, что – это одновременно проигрыш игрока В, если а_ij > 0, и выигрыш игрока В, если а_ij < 0.

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

	В₁	В₂	…	В_j	…	В_n
А₁	а₁₁	а₁₂	…	а₁_j	…	а_1n
…	…	…	…	…	…	…	(7.1)
А_i	а_i₁	а_i2…	…	а_ij	…	а_in
…	…	…	…	…	…	…
А_m	а_m₁	а_m₂	…	а_mj	…	а_m_n

Каждая строка этой матрицы соответствует некоторой стратегии игрока А, а каждый столбец – некоторой стратегии игрока В.

Пример игры. Два игрока выкидывают на пальцах числа, причем четное число пальцев – это выигрыш игрока А, нечетное – проигрыш игрока А. Для простоты введем ограничение – игроки выкидывают от 1 до 3 пальцев.

Составим платежную таблицу:

	В₁	В₂	В₃
А₁		-3		-3
А₂	-3		-5	-5
А₃		-5		-5

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

a_i = а_ij.

В нашем примере a₁ = -3; a₂ = -5; a₃ = -5. Далее, среди полученных значений l_i-х определим максимальное

a =a_i = а_ij.

В нашем примере a = -3, т.е. игрок А проигрывает 3 очка. Это число a называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А₁ максиминная, т.е. из всех наихудших ситуаций выбирают наилучшую. Эта величина (a) – гарантированный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В. Меньше нижней цены игры игрок А никогда не «выиграет», если будет придерживаться правил игры.

Игрок В старается максимально уменьшить свой проигрыш. Для этого определяется верхняя цена игры

b =b_j = а_ij.

Соответствующая стратегия называется минимаксной. В нашем примере будет две минимаксных стратегии В₁ и В₂. При этом игрок В проигрывает 4 очка.

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

Игра с седловой точкой

Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число u = a = b называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.

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

В₁

В₂

В₃

В₄

a_i

- лучшая стратегия для игрока А – (А₃)

А₁

А₂

А₃

А₄

b_j

цена игры u = a = b = 4

min max - лучшая стратегия для игрока В – (В₂)

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

методы ОПТИМАлЬНЫХ РЕШЕНИЙ

С В Амелин... методы оПТИМАлЬНЫХ РЕШЕНИЙ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Матричные игры

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Построение графика Ганта
Сетевой график дает чёткое представление о порядке следования работ, а для того, чтобы определить, какие работы должны выполняться в каждый конкретный момент времени, строят масштабный сетевой граф

Расчет временных параметров событий
Введем обозначения (рис. 11): i, j – номер события; I - исходное событие; J - завершающее событие; tPi, tPj - ранний срок свершения события; tП

Поздний срок свершения завершающего события
tПJ = tPJ = tКР. (1.5) Резерв времени события показывает, на какой допустимый период времени можно задержать наступление данног

Сетевое планирование в условиях неопределённости
В случаях, когда время выполнения работ точно не известно, то есть продолжительность работы является случайной (стохастической) величиной, характеризующейся законом β-распредел

Расчёт показателей качества функционирования систем массового обслуживания
Чтобы улучшить работу СМО путем изменения ее организации, необходимо рассчитать показатели качества её функционирования при существующем варианте организации и при других возможных вариантах и на о

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

Основные балансовые соотношения
Первое балансовое соотношение выражает связь между первым и вторым разделами балансовой модели + yi = Xi, i =

Баланса. Модель Леонтьева
Запишем первую систему балансовых соотношений, характеризующих распределение продукции отраслей материального производства: + y

Методы отыскания вектора валовых выпусков
Для решения первой задачи существует два метода: точный и приближенный. а) Точный метод отыскания вектора валовых выпусков Х. Запишем модель Леонтьева в матричном виде &n

Коэффициенты косвенных затрат
Косвенные затраты относятся к предшествующим стадиям производства и входят в продукт не непосредственно, а через затраты сопряженных отраслей (рис. 55).

Тема 4. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Раздел математических методов, в котором рассматриваются способы решения задач на нахождение экстремума функции цели при ограничении области допустимых значений в форме уравнений ил

Фирма выпускает четыре вида персональных компьютеров
Таблица 4.1 Цех Затраты времени на единицу продукции, ч Общий фонд времени, ч/мес a b

Выражения (4.1), (4.2) и (4.3) составляют экономико-математическую модель задачи линейного программирования.
Для представления задачи в символьном виде введем обозначения: Хj – количество выпускаемых изделий j-го типа, j = ;

Условия неотрицательности получаемого решения
xj ³ 0, (j = ). 3. Задача оптимального распределения заданий по

Условие неотрицательности решения
xj ³ 0, (j = ). 4. Задача составления оптимальной смеси (задача диеты) Для производ

Условие неотрицательности решения
xj ³ 0, (j = ). 5. Распределительная задача: о размещении парка оборудования по

Представление задачи линейного программирования в канонической форме
Пусть требуется найти неотрицательные значения переменных Х1, Х2, …, Хn, для которых функция цели принимает максимальное значение f(x) = C1 Х

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

Экономическая интерпретация двойственных задач
Пример. Для производства трех видов изделий А, В и С используются три различных вида сырья, запасы которого составляют соответственно 180, 210 и 244 кг. Нормы затрат сырья на единицу продукц

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

Нахождение первоначального опорного плана
Для определения первоначального опорного плана существуют несколько различных методов. Это – метод северо-западного угла, метод минимального элемента, или минимальной стоимости, и другие.

Циклы пересчёта
Переход от одного опорного плана к другому в транспортной задаче сводится к тому, что, как и в симплекс-методе, надо ввести в базис новый вектор вместо выведенного базисного вектора. Это способству

Задач, имеющих дополнительные условия
1. Если по каким-либо причинам перевозки грузов из некоторого пункта отправления Аi в некоторый пункт назначения Вj не могут быть осуществлены, тогда для определения оптимальн

Транспортной задачи
Пусть дан некоторый опорный план. Для каждой свободной клетки таблицы перевозок вычислим алгебраические суммы стоимостей в вершинах цикла Dij. Так, для клетки (4,1) получим D

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

Тема 8. ЭЛЕМЕНТЫ ТЕОРИИ СТАТИСТИЧЕСКИХ ИГР.
ИГРЫ С «ПРИРОДОЙ» В рассмотренных случаях оба игрока действовали наилучшим для себя способом. Однако встречаются конфликтные ситуации, в которых одна из ст

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

ЗАКЛЮЧЕНИЕ
Современные сложные производственные системы являются крайне чувствительными к ошибкам в принятии управленческих решений. Интуиции, личного опыта руководителей уже не достаточно для успешного функц

Библиографический Список
1. Амелин С.В. Методы и модели в экономике: конспект лекций. / С.В. Амелин. - Воронеж: Воронежский государственный технический университет, 2001, 90 с. 2. Амелин С.В. Метод