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

--PAGE_BREAK--Вид урока: Лекция.
Продолжительность: 2 часа.

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

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

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

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

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

Ход занятия.

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

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

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

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

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

Решение: Данная игра представлена матрицей А
<img width=«94» height=«40» src=«ref-1_1540933603-266.coolpic» v:shapes="_x0000_i1063">
Здесь игрок 1 и 2 имеет две чистые стратегии. Решаем игру с позиции первого игрока.

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

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

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

Найдем maxmin(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β

Найдем minmax(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= maxminаij=minmaxаij= Vв. Значит цена игры V* =0 и седловая точка равна (х*, у*) = ((1/2, 1/2), (1/2, 1/2)).

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

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

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

Задача:

Графоаналитическим методом найти цену и седловую точку матричной игры, заданную матрицей выигрыша первого игрока.
<img width=«145» height=«48» src=«ref-1_1540933869-352.coolpic» v:shapes="_x0000_i1064">
> with(simplex):

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

 

<img width=«130» height=«75» src=«ref-1_1540934221-492.coolpic» v:shapes="_x0000_i1065">
> <img width=«130» height=«25» src=«ref-1_1540934713-273.coolpic» v:shapes="_x0000_i1066">

<img width=«98» height=«37» src=«ref-1_1540934986-284.coolpic» v:shapes="_x0000_i1067">
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};


<img width=«388» height=«41» src=«ref-1_1540935270-531.coolpic» v:shapes="_x0000_i1068">
Ø     X:=maximize(f,C ,NONNEGATIVE );
<img width=«169» height=«33» src=«ref-1_1540935801-330.coolpic» v:shapes="_x0000_i1069">


> f_max:=subs(X,f);
<img width=«72» height=«33» src=«ref-1_1540936131-186.coolpic» v:shapes="_x0000_i1070">

> <img width=«102» height=«19» src=«ref-1_1540936317-203.coolpic» v:shapes="_x0000_i1071">

<img width=«46» height=«33» src=«ref-1_1540936520-146.coolpic» v:shapes="_x0000_i1072">
> XX:=X*V;
<img width=«204» height=«33» src=«ref-1_1540936666-362.coolpic» v:shapes="_x0000_i1073">

> <img width=«172» height=«16» src=«ref-1_1540937028-287.coolpic» v:shapes="_x0000_i1074">

<img width=«142» height=«16» src=«ref-1_1540937315-230.coolpic» v:shapes="_x0000_i1075">
Ø     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};



<img width=«388» height=«41» src=«ref-1_1540937545-802.coolpic» v:shapes="_x0000_i1076">
Ø     Y:=minimize(f1,C1 ,NONNEGATIVE);
<img width=«216» height=«33» src=«ref-1_1540938347-379.coolpic» v:shapes="_x0000_i1077">

> <img width=«130» height=«16» src=«ref-1_1540938726-245.coolpic» v:shapes="_x0000_i1078">

<img width=«71» height=«33» src=«ref-1_1540938971-189.coolpic» v:shapes="_x0000_i1079">

> <img width=«98» height=«19» src=«ref-1_1540939160-197.coolpic» v:shapes="_x0000_i1080">

<img width=«46» height=«33» src=«ref-1_1540936520-146.coolpic» v:shapes="_x0000_i1081">


Ø     YY:=V*Y;
<img width=«248» height=«33» src=«ref-1_1540939503-453.coolpic» v:shapes="_x0000_i1082">

> <img width=«134» height=«16» src=«ref-1_1540939956-249.coolpic» v:shapes="_x0000_i1083">

<img width=«316» height=«33» src=«ref-1_1540940205-568.coolpic» v:shapes="_x0000_i1084">

> VV:=XX*V*L;

<img width=«388» height=«74» src=«ref-1_1540940773-915.coolpic» v:shapes="_x0000_i1085">

Занятие №3 Решение систем неравенств графическим методом

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

Вид урока:Лекция, урок решения задач.

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

Цели:1) Изучить графический метод.

2) Показать применение программы Mapleпри решении систем неравенств графическим методом.

3)Развить восприятие и мышление по данной теме.

План занятия: 1 этап: изучение нового материала.

2 этап: Отработка нового материала в математическом пакете Maple.

3 этап: проверка изученного материала и домашнее задание.
    продолжение
--PAGE_BREAK--Ход занятия.
1 этап: Графический метод заключается в построении множества допустимых решений ЗЛП, и нахождении в данном множестве точки, соответствующей max/min целевой функции.

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

Для того чтобы наглядно продемонстрировать графический метод, решим следующую задачу:
<img width=«125» height=«131» src=«ref-1_1540941688-1156.coolpic» v:shapes="_x0000_i1086">
<img width=«190» height=«27» src=«ref-1_1540942844-520.coolpic» v:shapes="_x0000_i1087">
1.      На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X2 за абсциссу, а X1 за ординату и записать неравенства в следующем виде:
<img width=«153» height=«120» src=«ref-1_1540943364-603.coolpic» v:shapes="_x0000_i1088">
Так как <img width=«41» height=«19» src=«ref-1_1540943967-148.coolpic» v:shapes="_x0000_i1089"> и <img width=«41» height=«19» src=«ref-1_1540944115-148.coolpic» v:shapes="_x0000_i1090"> графики и область допустимых решении находятся в первой четверти. Для того чтобы найти граничные точки решаем уравнения (1)=(2), (1)=(3) и (2)=(3).
<img width=«297» height=«192» src=«ref-1_1540944263-6437.coolpic» v:shapes="_x0000_i1091">


Как видно из иллюстрации многогранник ABCDE образует область допустимых решений.

Если область допустимых решений не является замкнутой, то либо max(f)=+ ∞, либо min(f)= -∞.

2.      Теперь можно перейти к непосредственному нахождению максимума функции f.

Поочерёдно подставляя координаты вершин многогранника в функцию f и сравнивать значения, находим что f(C)=f(4;1)=19 – максимум функции.

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

В таком случае удобнее рассмотреть линию уровня вида f=a. При монотонном увеличении числа a от -∞ до +∞ прямые f=a смещаются по вектору нормали[1]. Если при таком перемещении линии уровня существует некоторая точка X – первая общая точка области допустимых решений (многогранник ABCDE) и линии уровня, то f(X)- минимум f на множестве ABCDE. Если X- последняя точка пересечения линии уровня и множества ABCDE то f(X)- максимум на множестве допустимых решений. Если при а→-∞ прямая f=a пересекает множество допустимых решений, то min(f)= -∞. Если это происходит при а→+∞, то  max(f)=+ ∞.
<img width=«320» height=«232» src=«ref-1_1540950700-8535.coolpic» v:shapes="_x0000_i1092">


В нашем примере прямая f=a пересевает область ABCDE в точке С(4;1). Поскольку это последняя точка пересечения, max(f)=f(C)=f(4;1)=19.

2 этап.

Задача:

Решить графически систему неравенств. Найти угловые решения.
x1+ 2x2<=10

2x1+x2<=10

x1+3x2>=3

5x1-x2>=-5

x1+6x2>=6

x1>= 0, x2>=0

> restart;

> <img width=«125» height=«16» src=«ref-1_1540959235-247.coolpic» v:shapes="_x0000_i1093">

> <img width=«161» height=«17» src=«ref-1_1540959482-287.coolpic» v:shapes="_x0000_i1094">

<img width=«70» height=«23» src=«ref-1_1540959769-178.coolpic» v:shapes="_x0000_i1095">

> <img width=«161» height=«16» src=«ref-1_1540959947-270.coolpic» v:shapes="_x0000_i1096">

<img width=«70» height=«23» src=«ref-1_1540960217-177.coolpic» v:shapes="_x0000_i1097">

> <img width=«180» height=«16» src=«ref-1_1540960394-285.coolpic» v:shapes="_x0000_i1098">

<img width=«90» height=«23» src=«ref-1_1540960679-187.coolpic» v:shapes="_x0000_i1099">

> <img width=«173» height=«16» src=«ref-1_1540960866-275.coolpic» v:shapes="_x0000_i1100">

<img width=«81» height=«23» src=«ref-1_1540961141-187.coolpic» v:shapes="_x0000_i1101">

> <img width=«180» height=«16» src=«ref-1_1540961328-290.coolpic» v:shapes="_x0000_i1102">

<img width=«90» height=«23» src=«ref-1_1540961618-190.coolpic» v:shapes="_x0000_i1103">

> <img width=«226» height=«16» src=«ref-1_1540961808-353.coolpic» v:shapes="_x0000_i1104">

<img width=«144» height=«23» src=«ref-1_1540962161-264.coolpic» v:shapes="_x0000_i1105">

> <img width=«176» height=«16» src=«ref-1_1540962425-285.coolpic» v:shapes="_x0000_i1106">

<img width=«57» height=«45» src=«ref-1_1540962710-221.coolpic» v:shapes="_x0000_i1107">

> <img width=«82» height=«16» src=«ref-1_1540962931-166.coolpic» v:shapes="_x0000_i1108">

<img width=«94» height=«23» src=«ref-1_1540963097-199.coolpic» v:shapes="_x0000_i1109">

> <img width=«82» height=«16» src=«ref-1_1540963296-168.coolpic» v:shapes="_x0000_i1110">

<img width=«94» height=«23» src=«ref-1_1540963464-208.coolpic» v:shapes="_x0000_i1111">

> <img width=«82» height=«16» src=«ref-1_1540963672-171.coolpic» v:shapes="_x0000_i1112">

<img width=«105» height=«23» src=«ref-1_1540963843-205.coolpic» v:shapes="_x0000_i1113">

> <img width=«82» height=«16» src=«ref-1_1540964048-167.coolpic» v:shapes="_x0000_i1114">

<img width=«105» height=«23» src=«ref-1_1540964215-211.coolpic» v:shapes="_x0000_i1115">

> <img width=«82» height=«16» src=«ref-1_1540964426-167.coolpic» v:shapes="_x0000_i1116">

<img width=«105» height=«26» src=«ref-1_1540964593-228.coolpic» v:shapes="_x0000_i1117">

> with(plots);

> with(plottools);

> <img width=«388» height=«121» src=«ref-1_1540964821-2234.coolpic» v:shapes="_x0000_i1118">
<img width=«454» height=«363» src=«ref-1_1540967055-16826.coolpic» v:shapes="_x0000_i1119">

> S1:=solve( {f1x[1, 1] = X6[1, 1], f2x[1, 1] = X6[1, 2]}, [x, y]);

<img width=«145» height=«33» src=«ref-1_1540983881-342.coolpic» v:shapes="_x0000_i1120">

> <img width=«366» height=«17» src=«ref-1_1540984223-515.coolpic» v:shapes="_x0000_i1121">

<img width=«130» height=«16» src=«ref-1_1540984738-210.coolpic» v:shapes="_x0000_i1122">

> <img width=«362» height=«17» src=«ref-1_1540984948-515.coolpic» v:shapes="_x0000_i1123">

<img width=«114» height=«16» src=«ref-1_1540985463-204.coolpic» v:shapes="_x0000_i1124">

> <img width=«362» height=«17» src=«ref-1_1540985667-505.coolpic» v:shapes="_x0000_i1125">

<img width=«130» height=«16» src=«ref-1_1540986172-201.coolpic» v:shapes="_x0000_i1126">

> <img width=«372» height=«17» src=«ref-1_1540986373-539.coolpic» v:shapes="_x0000_i1127">

<img width=«149» height=«33» src=«ref-1_1540986912-313.coolpic» v:shapes="_x0000_i1128">

> <img width=«362» height=«17» src=«ref-1_1540987225-516.coolpic» v:shapes="_x0000_i1129">

<img width=«138» height=«33» src=«ref-1_1540987741-322.coolpic» v:shapes="_x0000_i1130">

> <img width=«362» height=«17» src=«ref-1_1540988063-512.coolpic» v:shapes="_x0000_i1131">

<img width=«145» height=«33» src=«ref-1_1540988575-345.coolpic» v:shapes="_x0000_i1132">

> <img width=«366» height=«16» src=«ref-1_1540988920-504.coolpic» v:shapes="_x0000_i1133">

<img width=«142» height=«33» src=«ref-1_1540989424-326.coolpic» v:shapes="_x0000_i1134">

> <img width=«362» height=«16» src=«ref-1_1540989750-487.coolpic» v:shapes="_x0000_i1135">

<img width=«114» height=«16» src=«ref-1_1540990237-201.coolpic» v:shapes="_x0000_i1136">

> <img width=«369» height=«16» src=«ref-1_1540990438-507.coolpic» v:shapes="_x0000_i1137">

<img width=«162» height=«33» src=«ref-1_1540990945-353.coolpic» v:shapes="_x0000_i1138">
Ответ: Все точки Si где i=1..10 для которых x и y положительна.

Область, ограниченная данными точками: (54/11,2/11) (5/7,60/7) (0,5) (10/3, 10/3)

3 этап. Каждому ученику даётся один из 20 вариантов, в котором ученику предлагается самостоятельно решить неравенство графическим методом, а остальные примеры в качестве домашнего задания.


Занятие №4 Графическое решение задачи линейного программирования
Тип урока: урок изучения нового материала.

Вид урока:Лекция + урок решения задач.

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

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

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

2) Развить восприятие, мышление.

План занятия: 1 этап: изучение нового материала.

2 этап: Отработка нового материала в математическом пакете Maple.

3 этап: проверка изученного материала и домашнее задание.

Ход занятия.

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости <img width=«55» height=«23» src=«ref-1_1540991298-158.coolpic» v:shapes="_x0000_i1139"> некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство


<img width=«111» height=«24» src=«ref-1_1540991456-221.coolpic» v:shapes="_x0000_i1140">
можно представить в виде системы двух неравенств (см. рис.2.1)
<img width=«120» height=«51» src=«ref-1_1540991677-439.coolpic» v:shapes="_x0000_i1141">
ЦФ <img width=«119» height=«23» src=«ref-1_1540992116-229.coolpic» v:shapes="_x0000_i1142"> при фиксированном значении <img width=«61» height=«21» src=«ref-1_1540992345-152.coolpic» v:shapes="_x0000_i1143"> определяет на плоскости прямую линию <img width=«101» height=«23» src=«ref-1_1540992497-199.coolpic» v:shapes="_x0000_i1144">. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения Lповлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси <img width=«28» height=«23» src=«ref-1_1540992696-117.coolpic» v:shapes="_x0000_i1145"> (начальная ордината), а угловой коэффициент прямой <img width=«73» height=«47» src=«ref-1_1540992813-214.coolpic» v:shapes="_x0000_i1146"> останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор <img width=«79» height=«24» src=«ref-1_1540993027-182.coolpic» v:shapes="_x0000_i1147"> с координатами из коэффициентов ЦФ при <img width=«16» height=«23» src=«ref-1_1540993209-93.coolpic» v:shapes="_x0000_i1148"> и <img width=«19» height=«23» src=«ref-1_1540993302-95.coolpic» v:shapes="_x0000_i1149"> перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора <img width=«17» height=«21» src=«ref-1_1540993397-96.coolpic» v:shapes="_x0000_i1150"> совпадает с направлениемвозрастания ЦФ, что является важным моментом для решения задач. Направлениеубывания ЦФ противоположно направлению вектора<img width=«17» height=«21» src=«ref-1_1540993397-96.coolpic» v:shapes="_x0000_i1151">.

Суть графического метода заключается в следующем. По направлению (против направления) вектора <img width=«17» height=«21» src=«ref-1_1540993397-96.coolpic» v:shapes="_x0000_i1152"> в ОДР производится поиск оптимальной точки <img width=«97» height=«23» src=«ref-1_1540993685-205.coolpic» v:shapes="_x0000_i1153">. Оптимальной считается точка, через которую проходит линия уровня <img width=«71» height=«24» src=«ref-1_1540993890-176.coolpic» v:shapes="_x0000_i1154">, соответствующая наибольшему (наименьшему) значению функции <img width=«35» height=«21» src=«ref-1_1540994066-123.coolpic» v:shapes="_x0000_i1155">. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
<img width=«537» height=«372» src=«ref-1_1540994189-26272.coolpic» v:shapes="_x0000_i1156">

Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.
    продолжение
--PAGE_BREAK--