Содержание
-
Стратегические игры
-
ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ1. ОПЕРАЦИЯ. ЭФФЕКТИВНОСТЬ ОПЕРАЦИИ
Под эффективностью операции подразумевается степень ее приспособленности к выполнению стоящей перед ней задачи. Чем лучше организована операция, тем она эффективнее. 2 Под операцией мы будем понимать любое мероприятие (или систему действий), объединенное единым замыслом и направленное к достижению определенной цели. Основная задача исследования операций—предварительное количественное обоснование оптимальных решений. Рассмотрим отдельную операцию О. Показатель эффективности операции -W.
-
3 , 2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПЕРАЦИИ Математические модели, применяемые в настоящее время в задачах исследования операций, можно грубо подразделить на два класса: аналитические и статистические. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИИ. ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ Пусть имеется некоторая операция 0 Эффективность операции характеризуется каким-то численным критерием или показателем W. Рассмотрим сначала наиболее простой случай: все факторы, от которых зависит успех операции, делятся на две группы: — заданные, заранее известные факторы (условия проведения операции) al, а2..., на которые мы влиять не можем; — зависящие от нас факторы (элементы решения) xl, х2, ..., которые мы, в известных пределах, можем выбирать по своему усмотрению. W=W(al, a2,... xl, х2,...). (3.1) При заданных условиях al, a2, ... найти такие элементы решения xl, x2, ..., которые обращают показатель W в максимум.
-
4 Эффективность операции зависит уже не от двух, а от трех категорий факторов: условия выполнения операции al, а2, ..., которые известны заранее и изменены быть не могут; неизвестные условия или факторы Yl, Y2, ... ; элементы решения xl, х2, ..., которые нам предстоит выбрать. Пусть эффективность операции характеризуется некоторым показателем W, зависящим от всех трех групп факторов. Запишем это в виде общей формулы: W=W(a1, a2,...; Y1, Y2,...; х1, х2,...). 4. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИИ. ОПТИМИЗАЦИЯ РЕШЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ При заданных условиях а1, а2,..., с учетом неизвестных факторов Y1, Y2, ... найти такие элементы решения х1, х2, ..., которые по возможности обращали бы в максимум показатель эффективности W Это — уже другая, не чисто математическая задача (недаром в ее формулировке сделана оговорка «по возможности»). Наличие неизвестных факторов Yl, Y2, ... переводит нашу задачу в другую категорию, она превращается в задачу о выборе решения в условиях неопределенности.
-
5 «Исследование операций представляет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами». Т. Л. Саати «Математические методы исследования операций» В случае, когда неизвестные факторы, фигурирующие в операции — Y1, Y2,.... — являются обычными случайными величинами (или случайными функциями), распределение которых, хотя бы ориентировочно, известно, для оптимизации решения может быть применен один из двух приемов: — искусственное сведение к детерминированной схеме; — «оптимизация в среднем». Первый прием применяется по преимуществу в грубых, ориентировочных расчетах, когда диапазон случайных изменений величин Yl, Y2,.... сравнительно мал, т. е. они без большой натяжки могут рассматриваться как не случайные. Заметим, что тот же прием замены случайных величин их математическими ожиданиями может успешно применяться и в случаях, когда величины Yl, Y2,.... обладают большим разбросом, но показатель эффективности Wзависит от них линейно (или почти линейно).
-
6 W=M[W}= W(a1, а2,...;У1,у2,...;х1,х2...) (У1,у2,...) dy1dy2.... Во втором случае нужно выбирать такое решение XI, Х2, ... , при котором обращается в максимум математическое ожидание показателя эффективности: d(Yl),dY2),...).плотность распределенияслучайных величин Yl, Y2,..... Наиболее трудным для исследования является тот случай неопределенности, когда неизвестные факторы Yl, Y2,... не могут быть изучены и описаны с помощью статистических методов: их законы распределения или не могут быть получены (соответствующие статистические данные отсутствуют), или, что еще хуже, таких законов распределения вовсе не существует. Это бывает, когда явление, о котором идет речь, не обладает свойством статистической устойчивости
-
7 Эффективность операции W зависит, помимо заданных условий al,a2, ... и элементов решения xl, х2,..., еще и от ряда неизвестных факторов Yl, Y2,... нестатистической природы, о которых определенных сведений нет, а можно делать только предположения. Попробуем все же решить задачу. Зафиксируем мысленно параметры Yl, Y2,..., придадим им вполне определенные значения Yl=yl, Y2=y2,..., и переведем тем самым в категорию заданных условий al, a2, .... Для этих условий мы в принципе можем решить задачу исследования операций и найти соответствующее оптимальное решение xl, х2, ... Его элементы, кроме заданных условий al, a2, ..., очевидно, будут зависеть еще и от того, какие частные значения мы придали условиям Yl, Y2,...: xl =xl (al, a2,...; yl, у2, ...); х2 =x2(al, а2,...; yl, у2,...). Такое решение, оптимальное для данной совокупности условий yl, у2,... (и только для нее), называется локально-оптимальным.
-
8 Вопросы. 1. В чем заключается смысл понятия « операция»? 2. Приведите примеры , когда к событиям Вашей повседневной жизни может быть применено понятие «операция». 3. Почему при исследовании операций можно ограничиться лишь задачей максимизации критерия эффективности? 4 .Какие виды ситуаций рассматриваются в теории исследования операций? 5. Какие виды решения задач исследования операций могут использоваться в детерминированных ситуациях? 6. Почему в условиях неопределенности задачу исследования операций решают как задачу оптимизации в среднем?
-
9 ОСНОВЫ ТЕОРИИ СТРАТЕГИЧЕСКИХ ИГР Типичный конфликт характеризуется тремя основными составляющими: заинтересованными сторонами; интересами этих сторон; их возможными действиями. ТЕОРИЯ ИГР- это математическая теория конфликтов. Протекание конфликта состоит в выборе каждым игроком своей стратегии и в получении им в сложившейся ситуации выигрыша из некоторого источника. На этом пути создается теория игр с выигрышами. Однако оценка игроком ситуации путем предположения о своем выигрыше, вообще говоря, не всегда возможна практически и даже не всегда имеет смысл. В подобных случаях иногда удается вместо прямых численных оценок ситуаций указывать на их сравнительную предпочтительность для отдельных игроков. На этом пути создается теория игр с предпочтениями, включающая в себя теорию игр с выигрышами как частный случай. В дальнейшем мы ограничимся рассмотрением только игр с выигрышами.
-
10 Мы будем стремиться: • к выработке принципов оптимальности, т.е. того критерия, по которому поведение игроков следует считать оптимальным (разумным, целесообразным); • выяснению реализуемости этих принципов, т.е. установлению существования оптимальных в выработанном смысле ситуаций и отысканию этих реализаций. Оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш. Количество стратегий у каждого игрока может быть конечным или бесконечным, в зависимости от этого игры подразделяются на конечные и бесконечные.
-
11 Матричные игры Полученная матрица имеет размеры m x n и называется матрицей игры или платежной матрицей (отсюда и название игры – матричная). Пусть игрок A выбрал стратегию i, а игрок B – стратегию k. Будем считать, что выбор игрокамистратегий и однозначно определяет исход игры – выигрыш игрока A и выигрыш игрока B, причем эти Предположим что игрок А имеет m стратегий, а игрок B имеет n стратегий. выигрыши связаны равенством: (отрицательный выигрыш обычно называют проигрышем).
-
12 Матричные игры относятся к разряду так называемых антагонистических игр, т.е. игр, в которых интересы игроков прямо противоположны. Рассматриваемая модель называется антагонистической игрой двух лиц с нулевой суммой (имеются два участника, и выигрыш одного равен проигрышу другого. Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков. Первый игрок имеет m стратегий i= 1,2,...,n, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 - свою j-ю стратегию. Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=1, 2…m),2-й свою j-ю стратегию (j=1,2,…), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij
-
13 Определение. Число чистой ценойигры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2. (1). , определённое по формуле (1) называется нижней (2). Определение. Число , определяемое по формуле (2 ), называется чистой верхней ценойигры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе обеспечить игрок 1. Верхнею цену игры можно интерпретировать и как максимальный проигрыш, который может гарантировать себе второй игрок при любых чистых стратегиях первого игрока.
-
14 Определение. Если в игре с матрицей А , то говорят, что эта игра имеет седловуюточку в чистых стратегиях и чистую цену игры - гиперболическиq параболоид Пример.
-
Вопросы 1.В чем заключаются особенности конфликтной ситуации? 2.Каким видом игры можно формализовать конфликтную ситуацию? 3.Что отражает матрица игры? 4.Какой уровень выигрыша гарантирует себе игрок , если он выбирает 5.стратегию, соответствующую седловой точке? 6.Как определяется седловая очка? 7.Будет ли значение выигрыша в седловой точке зависеть от выбора стратегии другого игрока? 8.Как называются стратегии игроков, соответствующие седловой точке?
-
Смешанные стратегии в матричных играх
Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с некоторой вероятностью.
-
Пример. Р=0.5 Средние потери второго игрока при стратегии Х1 первого L=0.5*3+0.5*6=4.5, при стратегииХ2 L=0.5*5+0.5*4=4.5 Следовательно, второй игрок может ограничить свой средний проигрыш величиной 4.5 независимо от стратегий, применяемых первым игроком.
-
Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x это набор чисел p = (p1, ..., pm) удовлетворяющих соотношениям pi 0 (i = 1,…,m), = 1. Аналогично для игрока 2, который имеет nчистых стратегий, смешанная стратегия q- это набор чисел q= (q1, ..., qn), = 1. qj 0 (j= 1,…,n), Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями. Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.
-
Определение. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей L(A, p, q) = = p A qT Первый игрок имеет целью за счёт изменения своих смешанных стратегий p максимально увеличить свой средний выигрыш L(А, p, q), а второй - за счёт своих смешанных стратегий стремится сделать L (А, p, q) минимальным, т.е. для решения игры необходимо найти такиеpи q, при которых достигается верхняя цена игры L(А, p, q). Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть L(А, p, q). Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы pо, qо соответственно, которые удовлетворяют равенству L(А, p, q0)L(А, pо, qо) L(А, pо, q)
-
Решение игр
Решение игры –это процесс нахождения игроков своих оптимальных стратегий, который состоит из нескольких этапов. Первый –это проверка на наличие седловой точки, т.к. в этом случае значительно упрощается процесс решения игры. Если седловая точка отсутствует, то игрокам целесообразно использовать смешанные стратегии, которые и должны быть найдены в результате решения игры. Однако прежде, чем приступать к нахождению смешанных стратегий целесообразно провести проверку доминирования стратегий, которая позволит игрокам исключить из рассмотрения заведомо невыгодные для них стратегии, что позволит сократить размерность решаемой задачи. Таким образом, вторым этапом решения игры является проверка доминирования. И, наконец, третий этап –это непосредственное решение игры. Первый этап-проверка на наличие седловой точки был рассмотрен в предыдущем разделе
-
Доминирующие и полезные стратегии
Смешанные стратегии игроков представляют собой смесь чистых стратегий, которые выбираются в соответствии с выбранным законом распределения вероятностей. Однако во многих случаях очевидно, что применение некоторых из чистых стратегий явно нецелесообразно и при определении оптимальной смешанной стратегии их просто не следует учитывать. Будем называть те из чистых стратегий, которые входят в состав оптимальной смешанной стратегии, полезными стратегиями игрока . для облегчения выделения полезных стратегий введем понятия доминирующих стратегий. Рассмотрим две стратегии l и p второго игрока. Пусть первый игрок применяет стратегию i. Потери второго игрока будутсоответственно и . Может оказаться что т.е. в матрице игры потери в столбце l не превосходят соответствующих потерь в столбце p. (4)
-
Это означает, что второму игроку ни при каких условиях невыгодно применять стратегию p, т.к. применяя ее, он заведомо несет большие потери, чем при стратегии l. Поэтому стратегия p должна быть отброшена, т.е. вычеркнута из матрицы игры. Стратегия l, удовлетворяющая условию (4) оказывается доминирующей по отношению к стратегии p. Доминирующие стратегии второго игрока имеют наглядную геометрическую иллюстрацию при переходе к эквивалентной S- игре на плоскости. В этом случае m=2 и условие (4) запишется в виде На рис.1 приведены два случая расположения точек и , соответствующих чистым стратегиям l и p второго игрока. Нетрудно видеть,(рис.1.а) что стратегия l доминирует над стратегией p. В случае , представленном рис.1.б, ни одна из стратегий не является доминирующей.
-
Для того чтобы стратегия l доминировала над стратегией p, точка должна лежать левее и ниже точки р. Аналогично определяются доминирующие стратегии первого игрока . Стратегия l доминирует над стратегией p, если выигрыш первого игрока при стратегии l больше выигрыша при стратегии p при любой стратегии второго игрока Удаление из матрицы игры тех стратегий , над которыми доминируют другие, значительно упрощает игру, а следовательно поиск оптимальной стратегии. Можно показать, что в игре с матрицей размером число полезных стратегий каждого из игроков не превышает наименьшего из чисел m и n. Теорема.Если один из игроков придерживается своей оптимальной смешанной стратегии , то выигрыш игрока остается неизменным и равным цене игры, независимо от того, какую смешанную стратегию (или чистую) стратегию применяет другой игрок, если только он не выходит за пределы своих полезных стратегий.
-
Методы решения игр
Решение игры путем сведения ее к задаче линейного программирования Предположим, что цена игры положительна ( > 0). Итак, пусть дана матричная игра с матрицей А порядка m х n. Оптимальные смешанные стратегии p = (p1, ..., pm), q = (q1, ..., qn) соответственно игроков 1 и 2 и цена игры должны удовлетворять соотношениям. Разделим все уравнения и неравенства в (1) и (2) на (это можно сделать, т.к. по предположению > 0) и введём обозначения :
-
Тогда (1) и (2) перепишется в виде :
-
Пример. Найти решение игры с матрицей, заданной таблицей
Решим задачу для первого игрока и запишем уравнения для его среднего выигрыша
-
Разделим обе части этих уравнений на и обозначим (6)
-
Запишем для смешанных стратегий второго игрока одно уравнение вида и два уравнения для полезных стратегий Вспоминая, что ко всем элементам матрицы игры прибавлялось число 5, находим цену игры
-
Графоаналитический метод решения стратегических игр
S-игра в играх 2 × 2, 2 × m и n × 2. Решению игры 2×2 можно дать простую геометрическую интерпретацию. Пусть имеется игра 2×2 с матрицей, приведенной в таб. 1.
-
Возьмем участок оси абсцисс длиной 1 (рис. 1). Средний выигрыш первого игрока
-
Несмотря на наличие пересечения стратегий, решение дает для обоих игроков чистые стратегии ( и ), а цена игры .
-
В данном случае нижняя граница выигрыш совпадает со стратегией Стратегия для противника является заведомо невыгодной.
-
Геометрическая интерпретация дает возможность представить наглядно также нижнюю и верхнюю цены игры (рис. 5). Рис. 5
-
Совершенно аналогично может быть решена любая игра 2×n, где у нас имеются всего две стратегии, а у противника – произвольное число.
-
В теории игр доказывается, что у любой конечной игры имеется решение, в котором число «полезных» стратегий той и другой стороны не превосходит наименьшего из двух чисел m и n. В частности, из этого следует, что у игры 2xn всегда имеется решение, в котором с той и другой стороны участвует не более двух «полезных» стратегий. Пользуясь геометрической интерпретацией, можно дать простой способ решения любой игры . Непосредственно по чертежу находим пару «полезных» стратегий противника и , пересекающиеся в точке (если в точке пересекается более двух стратегий, берем любые две из них). Мы знаем, что если игрок А придерживается своей оптимальной стратегии, то выигрыш не зависит от того, в какой пропорции применяет В свои «полезные» стратегии, следовательно: Из этих уравнений и условия находим и цену игры
-
Зная цену игры, можно сразу определить оптимальную стратегию игрока В. Для этого решается, например, уравнение: В случае, когда мы располагаем стратегиями, а противник – всего двумя, очевидно, задача решается совершенно аналогичным способом; достаточно заметить, что, изменяя знак выигрыша на обратный, можно превратить игрока А из «выигрывающего» в «проигрывающего». Можно решить игру и без перемены знака выигрыша; тогда задача решается непосредственно для В, ностроится не нижняя, а верхняя граница выигрыша (рис. 7).
-
S-игра при решении игр m × n
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.