Решение игр вида 2хn и mх2

Графо-аналитический метод.

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

Решение.

	1	4	7	1
	6	3	2	2
	6	4	7	2 4

a = 2, b=4, , поэтому игра не имеет седловой точки, и решение должно быть в смешанных стратегиях.
1. Строим графическое изображение игры.

Если игрок B применяет стратегию В₁, то выигрыш игрока A при применении стратегии А₁ равен а₁₁ = 1, а при использовании А₂ выигрыш равен а₂₁ = 6, поэтому откладываем отрезки А₁В₁ = 1, А₂В₁^′ = 6 на перпендикулярах в А₁ и А₂ и соединяем их отрезком. Аналогично для стратегий В₂ и В₃ строим отрезки В₂ В₂^′ и В₃ В₃^′.
2. Выделяем нижнюю границу выигрыша В₁М N В₃^′ и находим наибольшую ординату этой нижней границы, ординату точки М, которая равна цене игрыγ.
3. Определяем пару стратегий, пересекающихся в точке оптимума М.
В этой точке пересекаются отрезки В₂В₂^′ и В₁В₁^′, соответствующие стратегиям В₁ и В₂ игрока B. Следовательно, стратегию В₃ ему применять невыгодно. Исключаем из матрицы третий столбец и решаем игру 2 x 2 аналитически:

; ; .
Ответ: γ = 7/2; P_A = (1/2; 1/2); Q_B = (1/6; 5/6; 0).

Стохастическое программирование. Основные алгоритмы решения вероятностных задач.

Стохасти́ческое программи́рование — это подход, позволяющий учитывать неопределённость в оптимизационных моделях.

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

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

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

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

Поиск по сайту: