Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
»и максимином.
А соответствующая стратегия - максиминной.
Также можно рассуждать и в отношении 2-го игрока. Только в А указаны его проигрыши, которые он стремится минимизировать. Например, стратегия y1 может принести 2-му игроку проигрыш 7, 2 или 3. Но уже больше 7 он не проиграет. Следовательно, число 7, являющееся максимальным элементом стратегии y1, есть гарантированный проигрыш2-го игрока при y1. Определим все гарантированные проигрыши - В(y). Каким же проигрышем может ограничиться 2-й игрок ?
Числоназывается верхней ценой игры или минимаксом.
А соответствующая стратегия - минимаксной.
. Теоремы теории игр
Теорема 1. (основная теорема теории игр).
Всякая конечная игра имеет цену и у каждого игрока существует по меньшей мере одна оптимальная стратегия.
Терема 2. Нижняя цена игры всегда не превосходит верхней цены игры, .
Рассмотрим два случая.
. Пусть .
Игра, для которой, , называется игрой с седловой точкой. Если , то С является ценой игры, а стратегии игроков, обеспечивающие им выигрыш или проигрыш, равный С, являются оптимальными. Если игра с седловой точкой имеет С=0, то она является справедливой, если С0, - несправедливой.
. Пусть. В этом случае трудно определить цену игры и оптимальные стратегии игроков. Вернемся к рассмотренному примеру. = 3, а = 5. Значит, первый игрок может гарантировать себе выигрыш, равный 3, а второй - ограничить свой проигрыш 5. Область между и является как бы ничейной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы в этом случае оптимальные стратегии игроков? Если каждый игрок будет применять стратегию, соответствующую его максимальному гарантированному выигрышу или проигрышу, противник может догадаться о его намерениях и улучшить свой результат. Например, первый игрок использует х3, а второй - y2. Второй игрок заметил, что первый все время применяет x3, и решил применить y1, сведя свой проигрыш к меньшему числу. Таким образом, чтобы иметь успех, каждый игрок должен хранить свой выбор в секрете. Это трудно сделать, если игра повторяется многократно.
Секретность можно сохранить, если каждый раз выбирать стратегию случайным образом (бросая монету, кость и т.п.). При этом выигрыш и проигрыш будут случайными величинами. Результат можно оценить средней величиной проигрыша или выигрыша. Так, в нашем случае, если второй игрок использует свои стратегии y1, y2, y3 случайным образом, например, с вероятностями 1/3; 1/3; 1/3, соответственно, то среднее значение его проигрыша может быть:
если первый использует х1:
Сср = 1/3 а11 + 1/3 а12 + 1/3 а13 = 7/3 + 2/3 + 5/3 = 14/3;
если первый использует х2:
Сср = 1/3 а21 + 1/3 а22 + 1/3 а23 = 2/3 + 2/3 + 3/3 = 7/3;
если первый использует х3:
Сср = 1/3 а31 + 1/3 а32 + 1/3 а33 = 3/3 + 5/3 + 4/3 = 4. Таким образом, второй игрок может ограничить свой проигрыш уже не 5, а 14/3, независимо от стратегии первого игрока. Следовательно, в ряде случаев оказывается целесообразным не намечать заранее стратегии, а выбирать ту или иную случайным образом. Стратегия, основанная на случайном выборе, называется смешанной стратегией.
Вектор, каждая компонента которого показывает относительную частоту (вероятность) использования игроком соответствующих чистых стратегий, называется смешанной стратегией.
Пусть u=(u1,...,um) и z=(z1,...,zn), соответственно, вероятности отдельных исходов механизма случайного выбора 1-го и 2-го игроков.
Из теории вероятностей должно быть известно, что
1) ui 0, i=; zj . 0, j=; (т.к. 0 р 1);
) и (т.к. р(U) = 1, U- достоверное событие). Если u* - оптимальная стратегия 1-го игрока, z* - оптимальная стратегия 2-го игрока, то число является ценой игры.
Определение оптимальных стратегий и цены игры составляет процесс решения игры.
Теорема 3 (о цене игры).
Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях. Для того, чтобы число С было ценой игры, а u* и z* - оптимальными стратегиями игроков, необходимо и достаточно выполнения неравенств:
и .
Теорема дает ответ на вопрос о существовании решения игры и определяет путь решения.
В частном случае, когда по крайней мере у одного из игроков имеется только 2 стратегии, справедлива теорема.
Теорема 4. Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш или проигрыш равен цене игры вне зависимости от того, с какими частотами (вероятностями) будет применять другой игрок свои стратегии, вошедшие в оптимальную.
3. Способы решения задач теории игр.
4. Методы принятия решений: в условиях определенности; в условиях риска; в условиях неопределенности.
До сих пор рассматривались игры, в которых участвовали два, как бы равноправные, противника, преследовавшие противоположные цели. Каждый стремился так выбрать свою стратегию, чтобы получить для себя наибольшую выгоду и свести до минимума выгоду противника.
Однако, во многих практических ситуациях приходится сталкиваться со случаями, когда один из противников оказывается нейтральным, т.е. таким, который не стремится извлечь для себя максимальную выгоду, а, следовательно, не стремится обратить в свою пользу ошибки, совершаемые противником. К таким играм относят игры, в которых в качестве одного из игроков выступает "природа".
Здесь в понятие "природа" входит вся совокупность внешних обстоятельств, в которых приходится принимать решение. Любая хозяйственная деятельность человека может быть представлена как игра с "природой".
Чел