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

Критерий Лапласа

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

q₁ = q₂ = … = q_n = 1/n.

q_i = 1/3.

Выбираем из (2; 6.33; -18.33; 3.33) максимальный элемент max=6.33.

Вывод: выбираем стратегию N=2.

Критерий Вальда.

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

a = max (min a_ij).

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

Выбираем из (0; 2;; 1) максимальный элемент max=2.

Вывод: выбираем стратегию N=2.

Критерий Севиджа.

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

a = min (max r_ij).

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

Находим матрицу рисков.

Риск — мера несоответствия между разными возможными результатами принятия определенных стратегий. Максимальный выигрыш в j-м столбце b_j = max (a_ij) характеризует благоприятность состояния природы.

1. Рассчитываем 1-й столбец матрицы рисков.

r₁₁ = 5 — 5 = 0; r₂₁ = 5 — 2 = 3; r₃₁ = 5 — 1 = 4; r₄₁ = 5 — 1 = 4;

2. Рассчитываем 2-й столбец матрицы рисков.

r₁₂ = 9 — 1 = 8; r₂₂ = 9 — 9 = 0; r₃₂ = 9 — = 9; r₄₂ = 9 — 7 = 2;

3. Рассчитываем 3-й столбец матрицы рисков.

r₁₃ = 8 — 0 = 8; r₂₃ = 8 — 8 = 0; r₃₃ = 8 — (-56) = 64; r₄₃ = 8 — 2 = 6;

Результаты вычислений оформим в виде таблицы.

Выбираем из (8; 3; 64; 6) минимальный элемент min=3.

Вывод: выбираем стратегию N=2.

Критерий Гурвица.

Критерий Гурвица является критерием пессимизма — оптимизма. За оптимальную принимается та стратегия, для которой выполняется соотношение:

max (s_i).

где s_i = y min (a_ij) + (1-y)max (a_ij).

При y = 1 получим критерий Вальде, при y = 0 получим — оптимистический критерий (максимакс).

Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.

Рассчитываем s_i.

s₁ = 0.5*0+(1−0.5)*5 = 2.5.

s₂ = 0.5*2+(1−0.5)*9 = 5.5.

s₃ = 0.5*+(1−0.5)*1 = 0.5.

s₄ = 0.5*1+(1−0.5)*7 = 4.

Выбираем из (2.5; 5.5; 0.5; 4) максимальный элемент max=5.5.

Вывод: выбираем стратегию N=2.

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

Задание 2

Решить игру симплекс-методом:

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

Определим максимальное значение целевой функции F (X) = 2x₁ + 2x₂ + 3x₃ + x₄+1 при следующих условиях-ограничений.

При вычислениях значение Fc = 1 временно не учитываем.

• 2x₁ + 2x₂ + 3x₃ + x₄?1
• — x₁ + 8x₂ + 6x₃ + 3x₄?1
• 5x₁ + 7x₂ + 4x₃ + 6x₄?1
• 3x₁ + 2x₂ + 4x₃?1

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

• 2x₁ + 2x₂ + 3x₃ + 1x₄-1x₅ + 0x₆ + 0x₇ + 0x₈ = 1
• -1x₁ + 8x₂ + 6x₃ + 3x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ = 1
• 5x₁ + 7x₂ + 4x₃ + 6x₄ + 0x₅ + 0x₆-1x₇ + 0x₈ = 1
• 3x₁ + 2x₂ + 4x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇-1x₈ = 1

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

x₀ = 0−2(-x₁)-2(-x₂)-3(-x₃)-1(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₁ = 0−1(-x₁)+0(-x₂)+0(-x₃)+0(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₂ = 0+0(-x₁)-1(-x₂)+0(-x₃)+0(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₃ = 0+0(-x₁)+0(-x₂)-1(-x₃)+0(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₄ = 0+0(-x₁)+0(-x₂)+0(-x₃)-1(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₅ = 0+0(-x₁)+0(-x₂)+0(-x₃)+0(-x₄)-1(-x₅)+0(-x₆)+0(-x₇)+0(-x₈).

x₆ = 0+0(-x₁)+0(-x₂)+0(-x₃)+0(-x₄)+0(-x₅)-1(-x₆)+0(-x₇)+0(-x₈).

x₇ = 0+0(-x₁)+0(-x₂)+0(-x₃)+0(-x₄)+0(-x₅)+0(-x₆)-1(-x₇)+0(-x₈).

x₈ = 0+0(-x₁)+0(-x₂)+0(-x₃)+0(-x₄)+0(-x₅)+0(-x₆)+0(-x₇)-1(-x₈).

Данной системе соответствует таблица T⁰.

В качестве начальной допустимой базы можно взять B⁰ = .

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

Окончательный вариант таблицы:

F (X) = 1.

Необходимо найти минимальное значение целевой функции F = x₁+9x₂ > min, при системе ограничений:

x1−2×2?1 (1).

• 4x1+6×2?1 (2)
• 7x1+9×2?1 (3)

x1?0 (4).

x2?0 (5).

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

Или.

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = x₁+9x₂ > min.

Построим прямую, отвечающую значению функции F = 0: F = x₁+9x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб.

Область допустимых решений представляет собой многоугольник.

Прямая F (x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых(4) и (1), то ее координаты удовлетворяют уравнениям этих прямых:

x₂=0.

x₁-2x₂?1.

Решив систему уравнений, получим: x₁ = 1, x₂ = 0.

Откуда найдем минимальное значение целевой функции:

F (X) = 1*1 + 9*0 = 1.

Задание 3

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max (ai) = 1, которая указывает на максимальную чистую стратегию A1.

Верхняя цена игры b = min (bj) = 3.

Что свидетельствует об отсутствии седловой точки, так как a? b, тогда цена игры находится в пределах 1 <= y <= 3. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии) В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (3). Такая замена не изменит решения игры, изменится только ее цена (по теореме фон Неймана).

Решим задачу геометрическим методом, который включает в себя следующие этапы:

• 1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B₁, правый — стратегии B₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁, p₂).
• 2. На левой оси ординат откладываются выигрыши стратегии B₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B₂.

Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.

Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A₁A₁ и A₂A₂, для которых можно записать следующую систему уравнений: лаплас севидж выигрыш симплексный.

y = 5 + (4 — 5) q₂

y = 3 + (6 — 3) q₂

Откуда.

q₁ = ¹/₂

q₂ = ¹/₂

Цена игры, y = 4¹/₂

Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A₃, которая дает явно больший проигрыш игроку A, и, следовательно, p₃ = 0.

• 5p₁+3p₂ = y
• 4p₁+6p₂ = y

p₁+p₂ = 1.

или.

• 5p₁+3p₂ = 4¹/₂
• 4p₁+6p₂ = 4¹/₂

p₁+p₂ = 1.

находим:

p₁ = ³/₄

p₂ = ¹/₄

Поскольку ранее к элементам матрицы было прибавлено число (3), то вычтем это число из цены игры.

Цена игры: y = 4¹/₂ — 3 = 1¹/₂

Задание 4

• 0 — 67
• 2 3 9

А= 1 — 56.

1 6 2.

Решение анижняя цена игры, а = * ajJ.

в — верхняя цена игры.

в= * ajJ.

Если верхняя и нижняя граница совпадают значит общее значение является седловой точкой.

min max.

• 0 -67 -67 -0
• 2 3 9 2
• 1 -56 -56
• 1 6 2 1

max 2 6 — 67.

min -67.

в = -67 0? -67 значит седловой точки нет.

a= 0.