Теория игр - рефераты, скачать рефераты, бесплатно рефераты

Рефераты. Теория игр

/i>

По формулам (1) - (3) находим оптимальные стратегии и цену игры:

x1 = 7/8, x4 = 1/8; y1 = 3/8, y2 = 5/8; v =27/8.

Ответ. Оптимальные смешанные стратегии игроков (7/8, 0, 0, 1/8) и (3/8, 5/8), цена игры составляет v =27/8.

Данный ответ означает следующее:

если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.

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

Если платежная матрица не имеет седловой точки, т.е. < и , то решение игры представлено в смешанных стратегиях (x1, x2,..., xm) и (y1, y2,..., yn). Применение первым игроком оптимальной стратегии опт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры.

, .

Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения

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

Преобразуем систему ограничений, разделив все члены неравенств на v.

(1)

где

, . (2)

По условию x1 + x2 + … +xm = 1.

Разделим обе части этого равенства на v.

Оптимальная стратегия (x1, x2,..., xm) игрока А должна максимизировать величину v, следовательно, функция

(3)

должна принимать минимальное значение.

Таким образом, получена задача линейного программирования: найти минимум целевой функции (3) при ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения , и величину 1/v, затем отыскиваются значения xi = vti.

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

, .

Рассмотрим задачу отыскания оптимальной стратегии игрока B, для которой имеют место ограничения

Преобразуем систему ограничений, разделив все члены неравенств на v.

(4) где , . (5)

По условию y1 + y2 + … +yn = 1. Разделим обе части этого равенства на v.

Оптимальная стратегия (y1, y2,..., yn) игрока В должна минимизировать величину v, следовательно, функция

(6)

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

Пример. Найти решение игры, заданной матрицей

= max (2, 3,1) = 3, = min (4, 5, 6,5) = 4, , .

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

Для определения оптимальной стратегии игрока А имеем следующую задачу линейного программирования:

, .

Для нахождения оптимальной стратегии игрока В имеем следующую задачу линейного программирования:

, .

Оптимальные решения пары двойственных задач имеют вид

, , .

Учитывая соотношения между xi и ti, yj и sj, а также равенство

можно найти оптимальные стратегии игроков и цену игры:

(1/2, 1/2, 0), (3/4, 0, 0, 1/4), v=7/2.

1.6 Игры с природой
В рассмотренных выше матричных играх предполагалось, что в них принимают участие два игрока, интересы которых противоположны. Поэтому действия каждого игрока направлены на увеличение выигрыша (уменьшение проигрыша). Однако в некоторых задачах, приводящихся к игровым, имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности. Такие игры называются играми с природой. Человек в играх с природой старается действовать осмотрительно, второй игрок (природа, покупательский спрос) действует случайно.

Условия игры задаются матрицей

Пусть игрок А имеет стратегии А1, А2, …, Аm, а природа - состояния В1, В2, …, Вn. Наиболее простой является ситуация, когда известна вероятность pj каждого состояния природы Вj. При этом, если учтены все возможные состояния, p1 + p2 + … + pj + … + pn = 1.

Если игрок А выбирает чистую стратегию Аi, то математическое ожидание выигрыша составит p1 ai1 + p2 ai2 + … + pn ain. Наиболее выгодной будет та стратегия, при которой достигается

1 ai1 + p2 ai2 + … + pn ain).

Если информация о состояниях с приро

дой мала, то можно применить принцип недостаточного основания Лапласа, согласно которому можно считать, что все состояния природы равновероятностны:

т.е. стратегию, для которой среднее арифметическое элементов соответствующей строки максимальное.

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

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия

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

2. Критерий максимума. Он выбирается из условия

Критерий является оптимистическим, считается, что природа будет наиболее благоприятна для человека.

3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

где - степень оптимизма и изменяется в диапазоне [0, 1].

Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При = 1 критерий превращается в критерий Вальда, при = 0 - в критерий максимума. На оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем больше последствия ошибочных решений, больше желания застраховаться, тем ближе к единице.

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

Элементы матрицы рисков находятся по формуле

где - максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия определяется выражением

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

Пример. Возможно строительство четырех типов электростанций: А1 (тепловых), А2 (приплотинных), А3 (бесшлюзовых), А4 (шлюзовых). Состояния природы обозначим через Р1, Р2, Р3, Р4. Экономическая эффективность строительства отдельных типов электростанций изменяется в зависимости от состояния природы и задана матрицей

1) Согласно критерию Вальда

следует строить бесшлюзовую электростанцию

2) Воспользуемся критерием Сэвиджа. Построим матрицу рисков:

Согласно критерию Сэвиджа определяем

В соответствии с этим критерием также предлагается строить бесшлюзовую электростанцию.

3) Воспользуемся критерием Гурвица. Положим =1/2.

т.е. следует принять решение о строительстве приплотинной электростанции.

4) Если принять известным распределение вероятностей для различных состояний природы, например считать эти состояния равновероятностными (р1=р2=р3=р4=1/4), то для принятия решения следует найти математические ожидания выигрыша:

Так как максимальное значение имеет М3, то следует строить бесшлюзовую электростанцию. [16, 18, 21, 25, 27, 49]

Выводы по I главе
Таким образом, в первой главе были рассмотрены основные теоретические положения и определения теории игр. Было сформулировано и дано определение теории игр, а также были затронуты такие понятия как: игра, правила игры, стратегия, оптимальная стратегия, партия, ход.

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

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

Исходя из того, что игра зависит от многих параметров, были представлены различные виды игр и способы их решения:

Решение матричной игры в чистых стратегиях.

Решение матричной игры в смешанных стратегиях.

Решение игр графическим методом.

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

Игры с природой.

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

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

Глава II Разработка элективного курса “Элементы теории игр в начальной школе”

2.1 Место компьютера в начальной школе
Почему маленьким детям на уроке не всегда интересно? То устанут, то скука одолеет. Почему жизнь школы порой непохожа на цветной, яркий мир, который сопровождает ребенка в его общении с друзьями и книгами? Школа и школьная жизнь должна увлекать ребенка, вводя его в удивительный мир познания.

Вот тут-то на помощь и приходит компьютер со своим занимательным и познавательным миром. Диапазон использования компьютера в учебно-воспитательном процессе возрастает все больше: от тестирования учащихся, учета их личностных особенностей до игры. Компьютер может быть как объектом изучения, так и средством обучения, т.е. возможны два вида направления компьютеризации обучения: изучение информатики и также его использование при изучении различных предметов. При этом компьютер является мощным средством повышения эффективности обучения. [23]

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

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

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

Страницы: 1, 2, 3, 4