Разное по педагогике » Методика преподавания курса "Матричные игры"

Методика преподавания курса "Матричные игры"

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

В связи с развитием экономики страны я полагаю, что этот раздел математики будет интересен студентам вузов, изучающих экономику.

Этот курс рассчитан для 2-4 курсов вузов с математическим или экономическим уклоном.

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

Для достижения этой цели были сформулированы следующие задачи:

- Познакомить учеников с новыми разделами математики – теорией игр;

- Научить учеников моделировать заданные конфликтные ситуации;

- Научить учеников работать с матрицами 2×2, 2×3, 3×3;

- Научить учеников пользоваться математическим пакетом Maple.

При написании этой курсовой работы я предполагал, что ученики имеют первичные знания по теории игр и математическому пакету Maple.

Занятие №1:Основные понятия Матричных игр

Библиотека «simplex» пакета Maple.

Тип урока: урок изучения нового материала.

Вид урока: Лекция.

Продолжительность: 2 часа.

Цели:1) Повторить основные понятия Матричных игр

2) Сформулировать понятие приемлемой ситуации, ситуации равновесия, равновесия по Нэшу, седловая точка.

3) Изучить новый метод решения матричных игр.

4) Воспитать и привить интерес к предмету.

1 этап: дать краткий обзор понятий о матричных играх.

2 этап: Рассказать о программе Maple и её преимуществах

3 этап: закрепить новый материал и дать домашнее задание.

Ход занятия

На данном занятии мы познакомимся с матричными играми, и математическим пакетом Maple. Матричная игра- это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш первого игрока в виде матрицы, строка матрицы соответствует номеру применяемой стратегии игрока 1, а столбец - номеру применяемой стратегии 2-го игрока; на пересечении строки и столбца матрицы находятся выигрыш игрока 1, соответствующий применяемым стратегиям).Любая матричная игра имеет решение - доказано.

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 – свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij<0, то это значит, что игрок 1 платит второму сумму | аij|). На этом игра заканчивается.

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

А =

Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2

аij (i = )

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится

аij = = (1).

Число , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

аij

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij = = (2).

Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

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

Если в игре с матрицей А =, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

 = =.

Седловая точка– это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

где i, j– любые чистые стратегии соответственно игроков 1 и 2; (iо,jо)– стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом iо и jо называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

Пример 1:

Седловой точкой является пара (iо = 3; jо = 1), при которой  == = 2.

Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 ==, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2.

Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

В данном учебном курсе рассматривается среда программирования Maple. Интерактивная работа и программирование в ней имеют определённые преимущества: Программа Maple состоит из быстрого ядра, написанного на Си и содержащего основные математические функции и команды, а также большого количества библиотек, расширяющих ее возможности в различных областях математики. Библиотеки скомпонованы из подпрограмм, написанных на собственном языке Maple, специально предназначенном для создания программ символьных вычислений. Наиболее интересные возможности системы Maple - редактирование и изменение этих подпрограмм, а также пополнение библиотек подпрограммами, разработанными для решения конкретных задач. Они уже появились в большом количестве, а лучшие из них вошли в Share-библиотеку пользователей, распространяемую вместе с пакетом Maple.

Предлагается интерактивная программа решения матричных игр, выполненная в среде пакета Maple. Матричные игры сводятся к задаче линейного программирования, которая и реализуется командами из серии simplex. Удобство пакета в том, что имеется возможность выполнять оценки промежуточных этапов алгоритма, например, определять базисные переменные, нахождение двойственной игры, умножение матриц и т.п. В моей дипломной работе рассматриваются решения матричные игр из [5]. Для решения таких задач составлены интерактивные программы, которые реализуют решение поставленных задач в пакете Maple.

Библиотека «simplex» пакета Maple

Библиотека «simplex» - предназначена для оптимизации линейных систем с использованием симплексного алгоритма. Особенность ее в том, что имеется возможность выполнять оценки промежуточных этапов симплексного алгоритма, например, определять базисные переменные и т.п.

После подключения библиотеки командой with(simplex) пользователю становится доступны функции и опции, указанные в следующей таблице.

basis	Находит базисные переменые
cterm	Выводит список элементов вектора ресурсов
display	Представляет систему в матричной форме
dual	Преобразует данную задачу в двойственную задачу линейного програмирования
feasible	Возвращает true – если решение существует, и false – если нет
maximize	Находит максимум целевой функции
minimize	Находит минимум целевой функции
NONNEGATIVE	Опция: указание на условие не отрицательности всех переменных
setup	Приводит систему ограничений к стандартной форме
standardize	Превращает систему ограничений в пары неравенств

Занятие №2:Графоаналитический метод решения матричных игр

Тип урока: урок контроль, урок изучения нового материала.

Вид урока: Лекция.

Продолжительность: 2 часа.

Цели:1) Изучить новый метод решения матричных игр.

2) Научить пользоваться программой Maple при решении матричных игр графоаналитическим методом.

1 этап: дать краткое описание графоаналитического метода.

2 этап: показать данный метод на примерах.

3 этап: закрепить новый материал и дать домашнее задание.

Ход занятия.

1 этап. Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. С начало в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находиться аналитически.

Данный метод решения применяется в тех задачах, в которых у одного из игроков ровно две стратегии.

В основе этого метода лежит утверждение, что max min f (x,y) = min max f (x,y) = Vв.

2 этап. Рассмотрим данный метод на задаче под названием «орлянка»

Пример 6.1: Два игрока независимо друг от друга называют числа, если оба числа имеют одинаковую четность, то один получает рубль, если разные, то рубль получает второй.

Решение: Данная игра представлена матрицей А

Здесь игрок 1 и 2 имеет две чистые стратегии. Решаем игру с позиции первого игрока.

Пусть его стратегия х = (α, 1-α), 0 ≤α≤1.

Вычислим хА=(α, 1-α)(1 -1)= (α- (1-α), -α+1-α)=(2α-1, 1-2α). (-1 1)

Обозначим f2(α)=2α-1 и f2(α)=1-2α.

Найдем max min (f1 (α), f2 (α))= max( min(2α-1, 1-2α)).

Для нахождения максимина приведем графическую иллюстрацию (1)

Вначале для каждого α € [0,1] найдем min(2α-1, 1-2α). На рисунке (1) такие минимумы для каждого α € [0,1] образуют ломанную – нижнюю огибающую MPQ. Затем на огибающей находим наибольшее значение, которое будет в точке P. Эта точка достигает при α € [0,1], которое является решением уравнения f1 = f2 , т.е. 2α-1= 1-2α. Здесь α=1/2. Вторая координата точки P будет 2*1/2-1=0. итак P(1/2, 0). В смешанном расширении данной игры max( min(2α-1, 1-2α))=0.

Максиминная стратегия первого игрока хн = (α, 1-α)=(1/2, 1/2). По аналогичной схеме найдем минимаксную стратегию второго игрока. Его стратегию обозначим y=(β, 1-β), 0≤β≤1.

Вычислим Аy=( 2β-1, 1-2β).

Обозначим f1(β)= 2β-1, f2(β)= 1-2β

Найдем min max (f1(β), f2(β))= min (max (2β-1, 1-2β)).

Проведем геометрическую иллюстрацию на рисунке 2.

Для каждого β€[0,1] найдем min(2β-1, 1-2β).

На рисунке (2) такие минимумы для каждого β € [0,1] образуют ломанную – верхнюю огибающую RST. Затем на огибающей находим наименьшее значение, которое будет в точке S. Координаты точки S(1/2,0).

В смешанном расширении данной игры min (max (2β-1, 1-2β))=0.

YВ=( β, 1-β)=(1/2, 1/2) и выполняется условие, что

VH = max min аij = min max аij = Vв. Значит цена игры V* =0 и седловая точка равна (х*, у*) = ((1/2, 1/2), (1/2, 1/2)).

Ответ: (х*, у*)=((1/2, 1/2), (1/2, 1/2)), V* =0.

3 этап. Учитель повторяет последовательность решения данной задачи графоаналитическим методом. Дает домашнее задание.

Домашнее задание: придумать каждому ученику 1 задачу, чтобы она решалась графоаналитическим методом.

Задача:

Графоаналитическим методом найти цену и седловую точку матричной игры, заданную матрицей выигрыша первого игрока.

> with(simplex):

> A := Matrix(4,4, [[4, 2,3,-1],[-4,0,-2,2],[-5,-1,-3,-2],[-5,-1,-3,-2]]);

C:={ A[1,1]*x+A[1,2]*y+A[1,3]*z+A[1,4]*t <=1,

A[2,1]*x+A[2,2]*y+A[2,3]*z+A[2,4]*t <=1,

A[3,1]*x+A[3,2]*y+A[3,3]*z+A[3,4]*t

<=1,A[4,1]*x+A[4,2]*y+A[4,3]*z+A[4,4]*t <=1};

X:=maximize(f,C ,NONNEGATIVE );

> f_max:=subs(X,f);

> XX:=X*V;

C1:={ A[1,1]*p1+A[2,1]*p2+A[3,1]*p3+A[4,1]*p4 >=1,

A[1,2]*p1+A[2,2]*p2+A[3,2]*p3+A[4,2]*p4 >=1,

A[1,3]*p1+A[2,3]*p2+A[3,3]*p3+A[4,3]*p4

>=1,A[1,4]*p1+A[2,4]*p2+A[3,4]*p3+A[4,4]*p4 >=1};

Y:=minimize(f1,C1 ,NONNEGATIVE);

YY:=V*Y;

> VV:=XX*V*L;

Это интересно

Особенности интересов детей – воспитанников детского дома в сфере проведения досуга в каникулярное время
Исследование проводилось на базе Моу «Детский дом №2 г. Петрозаводска в октябре – ноябре 2009 г. В нём приняли участие 15 человек детей младшего школьного возраста – воспитанников детского дома; 4 педагога, работающих в детском доме. На первом этапе опытно – экспериментальной работы также приняли у ...

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

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

Методика преподавания курса "Матричные игры"

Навигация по сайту