Методика преподавания курса "Матричные игры" (стр. 2 из 5)
Пример 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 этап. Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. С начало в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находиться аналитически.
Данный метод решения применяется в тех задачах, в которых у одного из игроков ровно две стратегии.
В основе этого метода лежит утверждение, что maxminf(x,y) =minmaxf(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α.
Найдем 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 задачу, чтобы она решалась графоаналитическим методом.
Задача:
Графоаналитическим методом найти цену и седловую точку матричной игры, заданную матрицей выигрыша первого игрока.
> 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;
Занятие №3 Решение систем неравенств графическим методом
Тип урока: урок изучения нового материала.
Вид урока: Лекция, урок решения задач.
Продолжительность: 2 часа.
Цели:1) Изучить графический метод.
2) Показать применение программы Maple при решении систем неравенств графическим методом.
3)Развить восприятие и мышление по данной теме.
План занятия: 1 этап: изучение нового материала.
2 этап: Отработка нового материала в математическом пакете Maple.
3 этап: проверка изученного материала и домашнее задание.