Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ВОПРОСЫ К ЭКЗАМЕНУ
ПО ДИСЦИПЛИНЕ ТЕОРИЯ СИСТЕМ И СИСТЕМНЫЙ АНАЛИЗ
22 Нахождение множества Парето
К анализу многокритериальных задач можно подойти и с других позиций: попытаться сократить множество исходных вариантов, т.е. исключить из неформального анализа те варианты решений, которые будут заведомо плохи. Один из подобных путей был предложен итальянским экономистом В. Парето в 1904 г.
Этот четвертый, полностью формализуемый способ многокритериального выбора состоит в отказе от выделения единственной «наилучшей» альтернативы и соглашения о том, что предпочтение одной альтернативе перед другой можно отдавать только если первая по всем критериям лучше второй. Если же предпочтение хотя бы по одному критерию расходится с предпочтением по другому, то эти альтернативы признаются несравнимыми. В результате попарного сравнения альтернатив все худшие по всем критериям альтернативы отбрасываются, а все оставшиеся несравнимые между собой (недоминируемые) принимаются. Далее, если все максимально достижимые значения частных критериев не относятся к одной и той же альтернативе, то принятые альтернативы образуют множество Парето и выбор на этом заканчивается. На рис. 4 выделено множество Парето для рассматриваемого примера. При необходимости же выбора единственной альтернативы следует привлекать дополнительные соображения: вводить новые, добавочные критерии и ограничения, либо бросать жребий, либо прибегать к услугам экспертов.
Возникает вопрос, как можно провести сравнение и оценку отдельных альтернатив, т.е. провести композицию альтернатив. Для иллюстрации возможных подходов воспользуемся, как всегда, удобной графической интерпретацией критериального пространства при n = 2. Точками изобразим все имеющиеся альтернативы. Наилучшей альтернативой (рис. 5) будет та, что изображена точкой выше и правее других. Исключить все улучшаемые альтернативы, а также проверить неулучшаемость альтернатив паретовского множества, можно следующим образом: из каждой точки–альтернативы провести лучи, параллельные положительному направлению обеих осей, и если в угле, образуемом этими лучами, оказываются другие точки, данная альтернативы отбрасывается. Нетрудно видеть, что если лучи проведены из точки, соответствующей неулучшаемой альтернативе, то в образованном углу других альтернатив нет (рис. 5а).
Следует иметь в виду, что этот подход годится для выпуклых множеств, однако множество Парето не всегда является выпуклым.
Примером множества Парето может служить диаграмма «грузоподъемность-дальность» для транспортных средств (рис.6).
Принцип Парето играет очень важную роль в решении различных проблем техносферы. Предположим, например, что речь идет о проектировании водохозяйственного комплекса. В результате создания этого комплекса появится возможность обеспечить водой несколько крупных промышленных и сельскохозяйственных объектов, тем самым повысив их эффективность. Но одновременно возникает ряд отрицательных явлений, в частности:
Одним словом, ситуация оказывается принципиально многокритериальной, и цели проектировщика могут быть выписаны в виде
fi(x)max, i=1,2,.......n.
Проектировщик оказывается, таким образом, перед необходимостью искать компромисс. И одним из путей отыскания этого компромисса является построение Множества Парето, изучение которого дает большую информацию. Лицо, принимающее решение видит, в частности, сколько «стоит» увеличение одного из показателей, как оно сказывается на остальных показателях, значения которых непременно ухудшаются. Искомое множество имеет, как правило, весьма сложную природу, и анализ его одними лишь интуитивными методами вряд ли возможен.
Однако, помимо критериев fi(х) в распоряжении проектировщика достаточно часто есть еще и некоторый общий критерий F(х). Иногда бывает возможно формализовать его, записать в явном виде. Например, таким критерием может быть стоимость проекта. В этом случае «исследователю операций» предоставляется возможность решить задачу до конца. Для этого достаточно определить вектор х, который дает решение задачи: F(x) max при xPG(f1,f2,...fn), где PG(f1,f2,...fn) - множество Парето для функций f1,f2,...fn на множестве G допустимых векторов х. Например, в случае водохозяйственного комплекса множество G определяется таким распределением воды по объектам хi, при котором ее количество не превосходит притока Qi .
Важно отметить, что введение «общего» критерия F(x) и максимизация его значений на множестве Парето также является некоторой гипотезой, поскольку из совокупности критериев f1, f2,....,fn , F один из критериев мы специальным образом выделяем.
Приближенное построение множества Парето относится к числу очень важных и трудных задач численного анализа. Их значение постоянно растет, однако численные методы построения точек множеств Парето начали интенсивно развиваться лишь в последние десятилетия.
23 Случай известных вероятностей. Выбор в условиях риска
Рассмотрим задачу выбора, когда решение может привести не к одному, а к нескольким результатам с разными вероятностями их осуществления. Если эти вероятности известны, то сложность задачи будет зависеть от количества показателей системы.
Рассмотрим процесс принятия решения в случае одного показателя. Поскольку нам предстоит формировать функцию полезности, определим еще раз, что мы будем понимать под термином «полезность», «функция полезности».
24 Полезность ожидаемых результатов
В процессе выбора варианта решения нам часто бывает необходимо учитывать индивидуальное отношение людей к рассматриваемым показателям, и мы оцениваем полезность ожидаемых результатов. Полезность, или показатель полезности – это число, приписываемое конкретному результату, например, рабочей характеристике или состоянию системы, и представляющее собой оценку значимости этого результата по восприятию определенного человека или группы людей. Например, важными факторами являются финансовые затраты, экономический выигрыш, вес конструкции. При наличии единственного критерия и определенной связи между вариантами решения и значением этого критерия (целевой функции, или функции полезности) мы имеем задачу линейного (или нелинейного) программирования. В реальных задачах однозначно определить вид функции полезности часто не представляется возможным. Рассмотрим это на простом примере.
Более 200 лет назад Бернулли, рассматривая вопрос о полезности богатства, пришел к выводу, что заданное приращение богатства не обязательно принесет строго определенное приращение счастья (удовлетворения). Напротив, чем бóльшим богатством обладает человек, тем меньше будет добавка полезности на определенную величину приращения богатства. Т.е. миллионер получит от подарка в 100 долларов гораздо меньшее удовлетворение, чем бедняк. Бернулли предположил, что приращение полезности обратно пропорционально богатству человека и вывел формулу
где u – полезность богатства, x – богатство, b - коэффициент пропорциональности. Интегрируя, получим u = bln x +C. Если положить b=C=1, то u =ln x, а если b = lg e, то
u =lg x.
Предположим, что приращение полезности пропорционально и приращению полезности, которого не хватает для «полного счастья», и приращению количества денег. Это значит, что если кто-то испытывает полное удовлетворение от имеющегося богатства, то приращение богатства уже не дает человеку приращение удовлетворения. Тогда мы можем записать следующую зависимость:
du = b(1-u)dx,
где u = 1 соответствует случаю полного удовлетворения. Приняв u = 0 для x = 0, в результате интегрирования получим
u = e-bx .
Эта функция также описывает более медленное изменение полезности, чем линейная.
Такие функции полезности могут использоваться для оценки предпочтительности той или иной альтернативы (варианта решения). различный вид функций полезности может отражать разные психологические установки людей, условия окружающей среды, влияющие на решение и т.п.
25 Функция полезности при наличии риска
Выше было сказано, что одним из важнейших факторов, учитываемых в процессе принятия решения, являются финансовые затраты. Выберем их в качестве показателя некоторой системы и сформулируем задачу выбора следующим образом:
необходимо определить программу действий при наличии риска в расходовании средств, который обусловлен возможностью получения нескольких результатов при осуществлении принятого решения.
Пусть возможный диапазон затрат на осуществление программы составляет 2107 - 3107 рублей. Если целью использования является выбор программы с минимальными затратами, то наиболее желательному случаю будут соответствовать затраты, составляющие 2107 рублей, а наименее желательному -3107 рублей. Здесь мы поступаем так же, как и при формировании функции полезности, или целевой функции в условиях определенности. Принимаем полезность при затратах 2107 – u2 = 1, а полезность при 3107 – u2 = 0.
Чтобы определить полезность решения для промежуточных затрат, используем следующий постулат:
если результат Ri имеет осуществления pi, то полезность решения при наличии риска определяется средним значением полезности (математическим ожиданием):
, (1)
где ui – полезность результата Ri.
Рассмотрим ситуацию, когда надо выбрать из двух событий (это может быть, например, выбор между вариантами страховки или программами развития района), каждое из которых может привести к тем или иным затратам, величина которых носит вероятностный характер:
и .
Если группа лиц с общими интересами не отдает предпочтения ни одному из двух событий, то это означает, что (u1) = (u2) , где (u1) - средняя полезность события 1, а (u2) - средняя полезность результата 2.
Из этого условия можно определить полезность каждого из возможных результатов Ri. Пусть, например, событие 1 представляет собой затраты либо в сумме 2107 руб. с вероятностью р, либо в сумме 3107 с вероятностью 1-р. Тогда
(u1) = pu2 + (1-p)u2 (2)
Так как = 1 и = 0, получим (u1) = р.
Пусть событие 2 представляет собой затраты в 2,7107 руб. с вероятностью 1, то
(u2) = 2,7107.
Условие отсутствия предпочтительности при выборе между событиями 1 и 2 записывается как (u1) = (u2), тогда получим, что u8,5 = р.
Из этого следует, что если можно найти такое значение р, при котором группа с общими интересами не отдает предпочтения ни одному из событий 1 или 2, то можно сказать, что полезность затрат в 2,7107 равна р.
Рис.2. Кривые полезности, характеризующие различное отношение к5 риску консервативного руководителя (1) и руководителя, склонного к риску (2).
Рис.1. Зависимость полезности от расходов для групп лиц, не склонных к риску (А), и для группы лиц, безразличной к риску (В).
Однако соответствующая шкала фактической стоимости реализации программы не обязательно будет прямо пропорциональна расходам.
Предположим, например, что принятое решение с одинаковой 50-%-й вероятностью может потребовать затрат в 2107 руб. и в 3107 руб. Если средние значения полезностей двух решений равны и, следовательно, эти решения эквивалентны, то при линейной зависимости между полезностью и затратами приемлемое решение было бы связано с определенной суммой затрат равной 2,5107 руб., которая реализуется с вероятностью, равной 1. Однако, чтобы избежать максимальных затрат в сумме 3107 руб., вероятность которых составляет 50%, некоторая группа лиц с общими интересами, скорее согласится на строго установленные затраты в 2,7107 руб. Это характерно для лиц, не желающих рисковать и готовых уплатить несколько больше, чем приемлемо для всей группы, чтобы избежать более нежелательного исхода. При этом полезность u2,7 оценивалась бы как 0,5, поскольку
(u) =0,5u2 +0,5u3 = 0,5 (1) + 0,5 (0) = 0,5 = u2,8.
На рис.1 показаны кривые полезностей, отражающие разное отношение людей к риску. (Знак минус перед числами означает, что рассматриваются затраты, а не прибыль). Промежуточные точки кривой А можно рассчитать тем же методом, который использовался для оценки u2,7, т.е. путем приравнивания средних значений (u) для случая известных значений полезностей и случая известного результата при неизвестном значении полезности. Лицо, которое избегает риска, потребовало бы «разницу» возможных полезностей в свою пользу, и поэтому рискованной ситуации предпочитает вполне определенную (кривая А). Кривая В отражает линейную зависимость полезности от затрат, характерную для группы лиц, которые к риску относятся с безразличием.
На рис.2 показаны кривые полезностей для двух предпринимателей, один из которых склонен к риску (2), а другой – осторожный и консервативный (1).
26 Дерево решений
Рис.3. Дерево решений
Процесс выбора при наличии риска может быть представлен в виде графа – так называемого дерева решений. Дерево решений показывает решения, которые могут быть приняты, возможные результаты и вероятности получения этих результатов при осуществлении каждого из этих решений.
Пример. Предположим, что предприниматель рассматривает вопрос о разработке и выпуске новой продукции. Если продукция будет принята покупателем, предприниматель получит прибыль, но если продукция не будет пользоваться спросом, он не оправдывает своих затрат. Предприниматель исходит из того, что его новая продукция будет распродана с вероятностью 50%. Ему поступило предложение поручить другой фирме обследование рыночного спроса с соответствующей оплатой этой работы. Анализируя предшествующие отчеты, предприниматель может быть уверен на 90%, что если эта фирма даст рекомендацию на освоение новой продукции, то она будет принята покупателем. Следовательно он имеет следующие варианты выбора решения:
Дерево решения, соответствующее этой задаче, представлено на рис. 3. Здесь на концах ветвей проставлены значения возможной прибыли при каждом из трех решений при условии, что в случае изучения рыночного спроса фирме, проводящей такое исследование надо заплатить 2106 руб.
Если сопоставить каждой из ветвей (решению), соответствующей определенному результату некоторую вероятность, то можно рассчитать полезность каждого решения.
27 Энтропия системы. Принцип максимизации энтропии
В рассмотренном примере существовала возможность дать рекомендации для выбора решения, поскольку были известны вероятности случайных событий. Однако часто возникают ситуации, когда эти вероятности неизвестны.
Ранее в курсе рассматривались 3 вида неопределенностей в системах: а) из-за недостаточного знания; б) расплывчатость; в) случайная неопределенность.
Для неопределенности случайного объекта существует количественная мера (неопределенности), называется энтропией.
Рассмотрим простейший вариант – случайное событие. Пусть некоторое событие может произойти с вероятностью Р1 = 0,99 и не произойти с вероятностью Р2 = 0,01, а другое событие имеет вероятности Р1 = Р2 = 0,5. Очевидно, что в 1-м случае результатом опыта «почти наверняка» является наступление события, во втором случае неопределенность исхода так велика, что от прогноза лучше воздержаться.
Если мы имеем дело со случайной числовой величиной, то для характеристики различности распределений используется дисперсия или доверительный интервал.
Дх = для дискретной величины и
Дх =
Однако эти величины имеют смысл лишь для случайных числовых величин и не могут применяться к случайным объектам, состояния которых различаются качественно (например, выбор тех или иных команд или спортсменов при жеребьевке и т.п.).
Следовательно, мера неопределенности, связанной с распределением случайного события должна быть некоторой его числовой характеристикой, функционалом от распределения, но никак не связанным с тем, в какой шкале измеряются реализации случайного объекта.
Такой мерой неопределенности случайного объекта А с конечным множеством возможных состояний А1 …Аn с соответствующими вероятностями р1…рn величину,
Н = -
которая называется энтропией случайного объекта А (или распределения рi).
Действительно, любая большая система может рассматриваться как система, которая принимает некоторое множество состояний S1, S2, …Sn с вероятностями Р1, Р2, ….Pn соответственно. Энтропия системы, будучи, как видно из формулы, математическим ожиданием логарифма вероятности пребывания системы в некотором состоянии S, рассматривается в качестве меры разнообразия для множества возможных состояний S.
Эта функция соответствует выделенной К.Шенноном в теории информации «мере неопределенности». Если выбор любого состояния равновероятен, то неопределенность выбора максимальна и определяется общим числом возможных вариантов:
Н = - .
Величина Н(n) эквивалентна понятию энтропии в статистической физике H = klnW, где W (Е) – статистический вес системы, или количество возможных квантовых состояний физической системы, внутренняя энергия которой не превосходит Е.
В связи со всем сказанным выше можно записать и еще одно утверждение в отношении энтропии:
Энтропия Н рассматриваемой системы является мерой ее неупорядоченности.
Пример с голосованием: если n кандидатов имеют одинаковую вероятность получения голоса любого заданного избирателя, то, очевидно, что Pi = - вероятность того, что избиратель выберет i-го кандидата. Если все избиратели голосуют за какого-то определенного кандидата, то можно с определенностью сказать, за какого избирателя подает голос любой произвольно выбранный избиратель. Такое распределение будет полностью упорядоченным ( Н = Нmin).
Рассмотрим следующую задачу.
Рассчитать энтропию системы, состоящей из избирателей и 5 кандидатов на государственный пост для следующих вариантов:
2-го 500
3-го 50
4-го 40
5-го всего 10 опрошенных
в пользу 2-го 250
3-го 30
4-го 15
5-го 5
Пример:
n = 5 неупорядоченная более упорядоченная система
система
Pi = lnPi = -1,609 P1 = 0,4 lnp1 = - 0,916
P2 = 0,5 lnp2 = - 0,693
P3 = 0,05 lnp3 = - 2,996
P4 = 0,04 lnp4 = - 3,219
P5 = 0,01 lnp5 = - 4,605
Полностью упорядоченная система
Р1 = 1
Р2…Р5 = 0.
Принцип максимизации энтропии заключается в том, что в ситуациях, когда распределение вероятностей или значения вероятностей нам неизвестны, мы задаем их, исходя из следующего утверждения:
Система находится в равновесии, когда энтропия максимальна, что соответствует полному беспорядку. В рассмотренном примере это соответствует ситуации, когда нам ничего неизвестно о распределении пристрастий избирателей, и мы принимаем вероятность избрания любого кандидата равной Pi = , что будет соответствовать максимуму энтропии. Это также соответствует равновесному и наиболее вероятному состоянию системы.
Энтропия системы, таким образом, является весьма полезной величиной при моделировании систем в условиях случайной неопределенности.
28,32( одинаковые) Примеры решения задач при парной игре с нулевой суммой
Задача 1.1.
Найти решение игры, заданной матрицей А
А=.
Решение. Прежде всего проверим наличие седловой точки в данной матрице.
Для этого найдем нижнюю и верхнюю цену игры.
Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (3 и 6) тогда верхняя цена игры = min (3; 6) = 3. Отсюда видно, что = =3 и мы имеем седловую точку .= 3, т.е. задача имеет решение в чистых стратегиях.
Оптимальные чистые стратегии для первого и второго игроков равны соответственно U* = (0; 1), Z* = (1; 0), а цена игры = 3.
Задача 1.2.
Найти решение игры, заданной матрицей А
А=.
Решение. Прежде всего проверим наличие седловой точки в данной матрице.
Для этого найдем нижнюю и верхнюю цену игры.
Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (4 и 6) тогда верхняя цена игры = min (4; 6) = 4. Отсюда видно, что и мы имеем игру, которая имеет решение в смешанных стратегиях, а цена игры .
Предположим, что для первого игрока смешанная стратегия задается вектором U = (u1; u2). Первый игрок, если придерживается своей оптимальной стратегии, независимо от стратегии второго игрока получает цену игры , т.е.
4u1* + 3u2* = (1)
2u1* + 6u2* = .
Кроме этого относительные частоты связаны условием:
u1* + u2* = 1.
Решаем полученную систему трех линейных уравнений с тремя неизвестными. Получим оптимальную стратегию первого игрока и цену игры:
U* = ( u1* ; u2*) = (3/5; 2/5), = 18/5.
Составим уравнения для нахождения оптимальной стратегии второго игрока, если при любой чистой стратегии первого, второй проигрывает цену игры:
4z1* + 2z2* = = 18/5 (2)
3z1* + 6z2* = = 18/5.
Решаем полученную систему двух линейных уравнений с двумя неизвестными. Получим оптимальную стратегию второго игрока:
Z* = ( z1* ; z2*) = (4/5; 1/5).
Рассмотрим геометрическую интерпретацию этой задачи в смешанных стратегиях. Для этого в плоскости введем систему координат и на горизонтальной оси Ou отложим вероятность применения первым игроком его двух стратегий, сумма этих вероятностей равна 1, поэтому весь график расположится на отрезке единичной длины. В точках 0 стратегия (1; 0), а в 1 стратегия (0; 1).
Рисунок 1.
По оси ординат в точке 0 отложим выигрыши первого игрока по первой его стратегии при обеих стратегиях второго, а в точке 1 при второй стратегии первого игрока. Соединим эти платежи по столбцам, тогда пересечение прямых дадут решение системы уравнений (1), а ордината этой точки цену игры .
Аналогично можно построить график для нахождения оптимальной стратегии второго игрока.
Мы рассмотрели только самый простой вариант парной матричной игры с нулевой суммой, но она достаточно наглядно показывает, что иногда можно количественно оценить и выбрать оптимальный вариант поведения в конфликтной ситуации.
29. Понятие об игре с «природой»
Неопределенность в ситуации принятия решения далеко не всегда связана с сознательным противодействием партнера. Часто бывает, что мы не распологаем точной информацией о поведение партнера и это вызывает неопределенность в игре с ним. В таких случаях данная матричная игра будет называтся игрой с природой .
В этих условиях игроку (лицу принимающему решение) казалось бы легче найти решение, но даже в условиях отсутствия активного противодействия, его выбор должен быть обоснован.
В матричной игре с «природой» ставится задача поиска оптимальной стратегии в условиях риска. Введем четкое математическое определение риска в матричной игре с «природой».
Риском rij игрока при выборе стратегии Аi в условиях Hj называется разность
rij = bj - ai ,
где bj - максимальный элемент в j - м столбце.
Другими словами риск при выборе стратегии Аi это проигрыш по сравнению с тем случаем, когда игрок знал бы условие при котором он может получить выигрыш bj .
Пример:
Найдем матрицу риска R для следующей матрицы игры А.
A= ; R=
Рассмотрим наиболее распространенные критерии выбора стратегии при условии неопределенности в матричной игре с «природой».
1. Критерий максимального математического ожидания выигрыша.
Предположим, что неопределенность состояний природы (доброкачест-венная ), то есть вероятности состояний Pj известны, вычислим математическое ожидание выигрыша первого игрока, то есть выбрать стратегию удовлетворяющую условию
ai = Pj aij max.
Следует отметить, что точно та же стратегия соответствует минимальному математическому ожиданию риска
ri = Pj rij min.
Пример:
Пусть распределение вероятности состояний природы в последней задаче равны:
P(H1)=2/5; P(H2)=1/5; P(H3)=1/5; P(H4)=1/5;
Тогда
a1 = 13/5; a2 = 69/5; a3 = 13; a = max (13/5, 69/5, 13) = 69/5 = 13,8.
Следовательно оптимальной по этому критерию является стратегия А3.
Далее расмотрим критерий минимального математического ожидания риска
r1 = 78/5; r2 = 22/5; r3 = 26/5; r = min (78/5, 22/5, 26/5) = 22/5 = 4,4.
2. Критерий Вальда (максиминный).
Критерий Вальда совпадает с крайне осторожной максиминной стратегией
.
3. Критерий минимального риска Севиджа.
Критерий рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной сетуации
Игрок, применяющий критерий Севиджа, также придерживается позиции пессимизма, ориентирующийся на минимально возможный риск
4. Критерий Гурвица.
Критерий Гурвица соответствует всем промежуточным стратегиям между пессимизмом и крайним оптимизмом. Выигрыш рассчитывается по формуле:
, 0 1,
где - коэффициент пессимизма ; чем больше игрок хочет подстраховаться тем большее значение он выбирает. При = 1 критерий Гурвица соответствует критерию крайнего пессимизма, критерию Вальда.
30 Постановка задачи выбора в условиях неопределенности
Ранее мы познакомились с задачами выбора решения, когда каждой альтернативе (варианту выбора) соответствовал определенный исход. Это был, таким образом, выбор в условиях определенности.
В реальных задачах часто приходится иметь дело с ситуацией, когда альтернатива неоднозначно определяет последствия сделанного выбора. Другими словами, имеется набор возможных исходов y Y, из которых один окажется совмещенным с выбранной альтернативой, но с какой именно – в момент выбора неизвестно, но станет ясно только тогда, когда выбор уже сделан, и ничего изменить нельзя. Хотя с разной альтернативой x X связано одно и то же множество исходов Y, для разных альтернатив разные исходы имеют неодинаковое значение.
1.1 Задание неопределенности с помощью матрицы
В случае дискретного набора альтернатив и исходов описанную выше стиуацию можно представить в виде матрицы
|
X, Y |
y1 |
y2 |
y3 |
yj |
… |
ym |
|
x1 |
a11 |
a12 |
a13 |
a1i |
… |
a1m |
|
x2 |
a21 |
a22 |
a23 |
a2i |
… |
a2m |
|
xi |
ai1 |
ai2 |
ai3 |
aii |
… |
aim |
|
… |
… |
… |
… |
… |
… |
… |
|
xn |
an1 |
an2 |
an3 |
ani |
… |
anm |
Вектор y = (y1,….ym) – это все возможные исходы. Числа aii выражают оценку ситуации, когда сделан выбор альтернативы хi и реализовался исход yi. В разных случаях числа aii могут иметь различный смысл (“выигрыш”, “потери”, “платеж”).
Возможны два варианта:
В случае непрерывных множеств X и Y ситуация описывается аналогично с помощью задаваемых на этих множествах функциях a (x,y), x X, y Y.
Мы несколько определились с ситуацией, однако всего этого пока недостаточно для формальной постановки задачи выбора. Реальные задачи могут быть самыми разными и требуют, соответственно, самых разных методов решения.
31.Основные определения и теоремы теории игр
Теория игр относится к разделу прикладной математики исследующей математические модели принятия решений в условиях конфликта, противоречий и неопределенности. Задачей теории игр является нахождение оптимальной стратегии поведения в условиях конфликта, неопределенности или противодействия какой то стороны в этой ситуации независимо от того сознательно или неосознанно это происходит. Игровые математические модели позволяют не только найти оптимальную стратегию, которая не всегда однозначна, но и оценить каждый вариант решения с различных иногда противоречивых точек зрения, а так же глубже разобраться во всех сложностях и неопределенностях реальной ситуации для принятия до конца продуманного решения.
Началом теории игр как последовательной математической теории поведения можно считать выход в свет 50 лет назад монографии Дж. фон Неймана и О. Моргенштерна. Французский математик Э. Мулен так характеризует значение теории игр для социально-экономических наук: «По нашему мнению, теория игр представляет собой набор инструментов для построения моделей в экономических и политических теориях. Единственным, но вполне достаточным оправданием существования теории игр служит её растущее применение в этих дисциплинах. Она является поистине неиссякаемым источником гибких концепций, каждая из которых проливает свет на определенные стороны социальных взаимоотношений.».
Вначале введем несколько фундаментальных понятия теории игр, после этого дадим определение этому разделу прикладной математики.
Конфликт - это противоречие, вызванное противоположными интересами сторон.
Конфликтная ситуация - ситуация в которой участвуют стороны интересы которых полностью или частично противоположны.
Игра - это действительный или формальный конфликт, в котором имеется по крайней мере два участника, каждый из которых стремится к достижению собственных целей
Правилами игры называют допустимые действия каждого из игроков, направленные на достижение некоторой цели.
Платежом называется количественная оценка результатов игры.
Парная игра - игра в которой участвуют только две стороны (два игрока).
Игра с нулевой суммой - парная игра при которой сумма платежа равна нулю, т. е. если проигрыш одного игрока, равен выигрышу другого.
Стратегия игрока - это однозначный выбор игрока в каждой из возможных ситуаций, когда этот игрок должен сделать личный ход.
Оптимальная стратегия - это такая стратегия игрока, которая при многократном повторении игры обеспечивает ему максимально возможный средний выигрыш или минимально возможный средний проигрыш.
Пусть мы имеем парную игру с нулевой суммой, один игрок может выбрать при данном ходе i -ю стратегию из m своих возможных (i=1..m), а второй, не зная выбора первого j -ю стратегию из n своих возможных стратегий (j=1..n). В результате первый игрок выигрывает величину , а второй проигрывает эту величину. Из этих величин составим матрицу A.
A
Платежная матрица - так назовем матрицу A или еще по другому матрицей игры.
Конечной игрой размерности (m n) называется игра определенная матрицей А имеющей m строк и n столбцов.
Максимином или нижней ценой игры назавем число ,
а соответствующая ему стратегия (строка) максиминной.
Минимаксом или верхней ценой игры назавем число
,
а соответствующая ему стратегия (столбец) минимаксной.
Теорема 1.1. Нижняя цена игры всегда не превосходит верхнюю цену игры.
Игрой с седловой точкой называется игра для которой .
Ценой игры называется величина , если .
В случае игры с седловой точкой , игрокам выгодно придерживатся максиминной и минимаксной стратегий и не выгодно отклонятся от них . В таких случаях про игру говорят, что в ней имеет место равновесие в чистых стратегиях.
Возможна игра и с несколькими седловыми точками. Тогда игра имеет несколько оптимальных решений, но с одинаковой ценой игры.
Чаще встречаются матричные игры без седловой точки, когда и тогда для нахождения её решения используются смешанные стратегии.
Смешанной стратегией игрока называется вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии.
Теорема 1.2. Основная теорема теории матричных игр. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Теорема 1.3. Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры в не зависимости от того, с какими частотами будет применять второй игрок свои стратегии (в том числе и чистые стратегии).
32. Примеры решения задач при парной игре с нулевой суммой
Задача 1.1.
Найти решение игры, заданной матрицей А
А=.
Решение. Прежде всего проверим наличие седловой точки в данной матрице.
Для этого найдем нижнюю и верхнюю цену игры.
Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (3 и 6) тогда верхняя цена игры = min (3; 6) = 3. Отсюда видно, что = =3 и мы имеем седловую точку .= 3, т.е. задача имеет решение в чистых стратегиях.
Оптимальные чистые стратегии для первого и второго игроков равны соответственно U* = (0; 1), Z* = (1; 0), а цена игры = 3.
Задача 1.2.
Найти решение игры, заданной матрицей А
А=.
Решение. Прежде всего проверим наличие седловой точки в данной матрице.
Для этого найдем нижнюю и верхнюю цену игры.
Минимальные элементы по строкам равны (2 и 3) тогда нижняя цена игры = max (2; 3) = 3. Максимальные элементы по столбцам равны (4 и 6) тогда верхняя цена игры = min (4; 6) = 4. Отсюда видно, что и мы имеем игру, которая имеет решение в смешанных стратегиях, а цена игры .
Предположим, что для первого игрока смешанная стратегия задается вектором U = (u1; u2). Первый игрок, если придерживается своей оптимальной стратегии, независимо от стратегии второго игрока получает цену игры , т.е.
4u1* + 3u2* = (1)
2u1* + 6u2* = .
Кроме этого относительные частоты связаны условием:
u1* + u2* = 1.
Решаем полученную систему трех линейных уравнений с тремя неизвестными. Получим оптимальную стратегию первого игрока и цену игры:
U* = ( u1* ; u2*) = (3/5; 2/5), = 18/5.
Составим уравнения для нахождения оптимальной стратегии второго игрока, если при любой чистой стратегии первого, второй проигрывает цену игры:
4z1* + 2z2* = = 18/5 (2)
3z1* + 6z2* = = 18/5.
Решаем полученную систему двух линейных уравнений с двумя неизвестными. Получим оптимальную стратегию второго игрока:
Z* = ( z1* ; z2*) = (4/5; 1/5).
Рассмотрим геометрическую интерпретацию этой задачи в смешанных стратегиях. Для этого в плоскости введем систему координат и на горизонтальной оси Ou отложим вероятность применения первым игроком его двух стратегий, сумма этих вероятностей равна 1, поэтому весь график расположится на отрезке единичной длины. В точках 0 стратегия (1; 0), а в 1 стратегия (0; 1).
Рисунок 1.
По оси ординат в точке 0 отложим выигрыши первого игрока по первой его стратегии при обеих стратегиях второго, а в точке 1 при второй стратегии первого игрока. Соединим эти платежи по столбцам, тогда пересечение прямых дадут решение системы уравнений (1), а ордината этой точки цену игры .
Анологично можно построить график для нахождения оптимальной стратегии второго игрока.
Мы рассмотрели только самый простой вариант парной матричной игры с нулевой суммой, но она достаточно наглядно показывает, что иногда можно количественно оценить и выбрать оптимальный вариант поведения в конфликтной ситуации.