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

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

Пояснительная записка
 
При решении многих практических задачприходиться анализировать ситуации, где две или более стороны, преследующиеразличные цели, причем результат каждого зависит от того, какой выбор сделаетдругая сторона. Решением таких проблем занимается – Теория игр.
В связи с развитием экономики страныя полагаю, что этот раздел математики будет интересен студентам вузов,изучающих экономику.
Этот курс рассчитан для 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 (если аij0,то это значит, что игрок 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
A[2,1]*x+A[2,2]*y+A[2,3]*z+A[2,4]*t
A[3,1]*x+A[3,2]*y+A[3,3]*z+A[3,4]*t

 
/>
Ø 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 этап:проверка изученного материала и домашнее задание.Ход занятия.
1 этап: Графический методзаключается в построении множества допустимых решений ЗЛП, и нахождении вданном множестве точки, соответствующей max/min целевой функции.
В связи с ограниченнымивозможностями наглядного графического представления данный метод применяетсятолько для систем линейных неравенств с двумя неизвестными и систем, которыемогут быть приведены к данному виду.
Для того чтобы нагляднопродемонстрировать графический метод, решим следующую задачу:
/>
/>
1.  На первом этапе надо построитьобласть допустимых решений. Для данного примера удобнее всего выбрать X2 заабсциссу, а X1 за ординату и записать неравенства в следующем виде:
/>
Так как /> и /> графики и областьдопустимых решении находятся в первой четверти. Для того чтобы найти граничныеточки решаем уравнения (1)=(2), (1)=(3) и (2)=(3).
/>

Как видно из иллюстрациимногогранник 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)=+ ∞.
/>

В нашем примере прямая f=a пересеваетобласть ABCDE в точке С(4;1). Поскольку это последняя точка пересечения,max(f)=f(C)=f(4;1)=19.
2 этап.
Задача:
Решить графически системунеравенств. Найти угловые решения.
 
x1+ 2x2
2x1+x2
x1+3x2>=3
5x1-x2>=-5
x1+6x2>=6
x1>= 0, x2>=0
 
> restart;
> />
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
>with(plots);
>with(plottools);
> />
/>
> S1:=solve( {f1x[1, 1] = X6[1, 1], f2x[1, 1] = X6[1,2]}, [x, y]);
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
> />
/>
Ответ: Все точки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) определяет на координатной плоскости /> некоторую полуплоскость(рис.2.1), а система неравенств в целом – пересечение соответствующихплоскостей. Множество точек пересечения данных полуплоскостей называется областьюдопустимых решений (ОДР). ОДР всегда представляет собой выпуклуюфигуру,т.е. обладающую следующим свойством: если две точки А и В принадлежат этойфигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может бытьпредставлена выпуклым многоугольником, неограниченной выпуклой многоугольнойобластью, отрезком, лучом, одной точкой. В случае несовместности системыограничений задачи (1.2) ОДР является пустым множеством.
Все вышесказанноеотносится и к случаю, когда система ограничений (1.2) включает равенства,поскольку любое равенство

/>
можно представить в видесистемы двух неравенств (см. рис.2.1)
/>
ЦФ /> при фиксированном значении/> определяет на плоскостипрямую линию />. Изменяязначения L, мы получим семейство параллельныхпрямых, называемых линиями уровня.
Это связано с тем, чтоизменение значения L повлечетизменение лишь длины отрезка, отсекаемого линией уровня на оси /> (начальная ордината), аугловой коэффициент прямой /> останетсяпостоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну излиний уровня, произвольно выбрав значение L.
Вектор /> с координатами из коэффициентовЦФ при /> и /> перпендикулярен к каждойиз линий уровня (см. рис.2.1). Направление вектора /> совпадаетс направлениемвозрастания ЦФ, что является важныммоментом для решения задач. Направлениеубывания ЦФпротивоположно направлению вектора/>.
Суть графического методазаключается в следующем. По направлению (против направления) вектора /> в ОДР производится поископтимальной точки />. Оптимальнойсчитается точка, через которую проходит линия уровня />, соответствующаянаибольшему (наименьшему) значению функции />.Оптимальное решение всегда находится на границе ОДР, например, в последнейвершине многоугольника ОДР, через которую пройдет целевая прямая, или на всейего стороне.
При поиске оптимальногорешения задач линейного программирования возможны следующие ситуации:существует единственное решение задачи; существует бесконечное множестворешений (альтернативный оптиум); ЦФ не ограничена; область допустимыхрешений – единственная точка; задача не имеет решений.
/>
Рисунок 2.1Геометрическая интерпретация ограничений и ЦФ задачи. Методика решения задач ЛП графическим методом
 I. В ограниченияхзадачи (1.2) заменить знаки неравенств знаками точных равенств и построитьсоответствующие прямые.
 II. Найти изаштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи(1.2). Для этого нужно подставить в конкретное неравенство координатыкакой-либо точки [например, (0;0)], и проверить истинность полученногонеравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость,содержащую данную точку;
иначе (неравенство ложное) надозаштриховать полуплоскость, не содержащую данную точку.
Поскольку /> и /> должны бытьнеотрицательными, то их допустимые значения всегда будут находиться выше оси /> и правее оси />, т.е. в I-м квадранте.
Ограничения-равенстваразрешают только те точки, которые лежат на соответствующей прямой. Поэтомунеобходимо выделить на графике такие прямые.
 III. Определить ОДРкак часть плоскости, принадлежащую одновременно всем разрешенным областям, ивыделить ее. При отсутствии ОДР задача не имеет решений.
 IV. Если ОДР –не пустое множество, то нужно построить целевую прямую, т.е. любую из линийуровня /> (где L – произвольноечисло, например, кратное /> и />, т.е. удобное дляпроведения расчетов). Способ построения аналогичен построению прямыхограничений.
 V. Построить вектор />, который начинается вточке (0;0) и заканчивается в точке />. Еслицелевая прямая и вектор /> построеныверно, то они будут перпендикулярны.
 VI. При поискемаксимума ЦФ необходимо передвигать целевую прямую в направлении вектора/>, при поиске минимумаЦФ – против направления вектора />.Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ.Если такой точки (точек) не существует, то можно сделать вывод о неограниченностиЦФ на множестве планов сверху (при поиске максимума) или снизу (при поискеминимум).
 VII. Определитькоординаты точки max (min) ЦФ /> ивычислить значение ЦФ />. Для вычислениякоординат оптимальной точки /> необходиморешить систему уравнений прямых, на пересечении которых находится />.
Решить задачу линейногопрограммирования
1.f(x)=2x1+x2->extr

x1+ x2
x1+3x2
5x1-x2
x1+x2>=0
x1>= 0, x2>=0
>plots[inequal]({a+b=0,a>=0,b>=0},a=-2..5, b=-2..5, optionsfeasible=(color=red),
optionsopen=(color=blue, thickness=2),
optionsclosed=(color=green, thickness=3),
optionsexcluded=(color=yellow));
 
/>
> with(simplex):
> C:={ x+y =0};
/>
> dp:=setup({ x+y =0});
>n:=basis(dp);

/>
/>
Ødisplay(C,[x,y]);
/>
> f :=2*x+y:
> L:=cterm(C);
/>
> feasible(C, NONNEGATIVE, 'NewC', 'Transform');
ØX:=dual(f,C,p);
/>
Ø R:=maximize(f,C ,NONNEGATIVE );
/>
Ø f_max:=subs(R,f);
/>
Ø R1:=minimize(f,C ,NONNEGATIVE );
/>

f_min:=subs(R1,f);
/>
ОТВЕТ: При x1=5/4 x2=5/4 f_max=15/4; При x1=0 x2=0 f_min=0;
 
Урок № 5.Решение матричных игр,используя методы линейного программирования и симплекс метод
 
Тип урока: урок контроль+ урок изучения нового материала. Видурока: Лекция.
Продолжительность: 2 часа.
Цели:1)Проверить и закрепить знания попрошедшему материалу на прошлых уроках.
2) Изучить новый методрешения матричных игр.
3) развить память,математическое мышление и внимание.
1 этап: проверить домашнее задание в видесамостоятельной работы.
2 этап: дать краткое описание метода зигзага
3 этап: закрепить новый материал и датьдомашнее задание.
Ход занятия.
Методылинейного программирования — численные методы решения оптимизационных задач,cводящихся к формальным моделям линейного программирования.
/>Как известно, любая задача линейного программирования можетбыть приведена к канонической модели минимизации линейной целевой функции слинейными ограничениями типа равенств. Поскольку число переменных в задачелинейного программирования больше числа ограничений (n > m), томожно получить решение, приравняв нулю (n - m) переменных, называемыхсвободными. Оставшиеся m переменных, называемых базисными,можно легко определить из системы ограничений-равенств обычными методамилинейной алгебры. Если решение существует, то оно называется базисным.Если базисное решение допустимо, то оно называется базисным допустимым.Геометрически, базисные допустимые решения соответствуют вершинам (крайнимточкам) выпуклого многогранника, который ограничивает множество допустимыхрешений. Если задача линейного программирования имеет оптимальные решения, топо крайней мере одно из них является базисным.
Приведенныесоображения означают, что при поиске оптимального решения задачи линейногопрограммирования достаточно ограничиться перебором базисных допустимых решений.Число базисных решений равно числу сочетаний из n переменных по m:
С = m n! / n m! * (n — m)!
и может бытьдостаточно велико для их перечисления прямым перебором за реальное время. То,что не все базисные решения являются допустимыми, существо проблемы не меняет,так как чтобы оценить допустимость базисного решения, его необходимо получить.
Проблемарационального перебора базисных решений задачи линейного программирования былавпервые решена Дж. Данцигом. Предложенный им симплекс-метод до настоящеговремени является наиболее распространенным общим методом линейногопрограммирования. Симплекс-метод реализует направленный перебор допустимыхбазисных решений по соответствующим им крайним точкам выпуклого многогранникадопустимых решений в виде итеративного процесса, где на каждом шаге значенияцелевой функции строго убывают. Переход между крайними точками осуществляетсяпо ребрам выпуклого многогранника допустимых решений в соответствии с простымилинейно-алгебраическими преобразованиями системы ограничений. Поскольку числокрайних точек конечно, а целевая функция линейна, то перебирая крайние точки внаправлении убывания целевой функции, симплекс-метод за конечное число шаговсходится к глобальному минимуму.
Практикапоказала, что для большинства прикладных задач линейного программирования симплекс-методпозволяет отыскать оптимальное решение за относительно небольшое число шагов посравнению с общим числом крайних точек допустимого многогранника. В тоже времяизвестно, что для некоторых задач линейного программирования со специальноподобранной формой допустимой области, применение симплекс-метода приводит кполному перебору крайних точек. Этот факт в известной мере стимулировал поискновых эффективных методов решения задачи линейного программирования,построенных на иных, нежели симплекс-метод, идеях, позволяющих решать любуюзадачу линейного программирования за конечное число шагов, cущественно меньшеечисла крайних точек.
/>Cреди полиномиальных методов линейного программирования,инвариантных к конфигурации области допустимых значений, наиболеераспростаненным является метод Л.Г. Хачияна. Однако, хотя этот метод и имеетполиномиальную оценку сложности в зависимости от размерности задачи, тем неменее он оказывается неконкурентноспособным по сравнению с симплекс-методом.Причина этого в том, что зависимость числа итераций симплекс-метода отразмерности задачи выражается полиномом 3-го порядка для большинствапрактических задач, в то время как в методе Хачияна, эта зависимость всегдаимеет порядок, не ниже четвертого. Указанный факт имеет решающее значение дляпрактики, где сложные для симплекс-метода прикладные задачи встречаются крайнередко.
Cледует такжеотметить, что для важных в практическом смысле прикладных задач линейногопрограммирования разработаны специальные методы, учитывающие конкретныйхарактер ограничений задачи. B частности, для однородной транспортной задачиприменяются специальные алгоритмы выбора начального базиса, наиболее известнымииз которых являются метод северо-западного угла и приближенный метод Фогеля, асама алгоритмическая реализация симплекс-метода приближена к специфике задачи.Для решения задачи линейного назначении (задачи выбора) вместо симплекс-методаобычно применяется либо венгерский алгоритм, основанный на интерпретации задачив терминах теории графов как задачи поиска максимального по весу совершенногопаросочетания в двудольном графе, либо метод Мака.
2 этап.
Решить матричную игруразмера 3х3
 
f(x)=x1+x2+x3
3x2+2x3
2x1+x3
3x1
x1>= 0, x2>=0, x3>=0
> with(simplex):
> C:={ 0*x+3*y+2*z
/>
Ø display(C,[x, y,z]);
/>
> f :=x+y+z:
> feasible(C, NONNEGATIVE, 'NewC', 'Transform');
>S:=dual(f,C,p);
/>

Ø R:=maximize(f,C ,NONNEGATIVE );
/>
Ø f_max:=subs(R,f);
/>
ØR1:=minimize(S,NONNEGATIVE);
/>
 
>G:=p1+p2+p3;
/>
 
> f_min:=subs(R1,G);
/>
Найдёмцену игры
>V:=1/f_max;
/>
Найдёмоптимальную стратегию первого игрока > X:=V*R1;
/>

Найдём оптимальнуюстратегию второго игрока
>Y:=V*R;
/>
 
ОТВЕТ: При X=(3/7, 3/7,1/7) V=9/7; При Y=(3/7,1/7,3/7) V=9/7;
3 этап.
Каждому ученику даётся один из 20 вариантов, в котором ученику предлагается самостоятельно решить матричную игру 2x2,а остальные примеры в качестве домашнего задания.

Заключение
 
В наше время науканеумолимо быстро развивается, и для ее развития требуются все более сложныерешения тех или иных вопросов. Поэтому для роста научно технического прогресса иусложнения экономических процессов требуются новые привлечения математическихпроцессов. Для того чтобы наука двигалась вверх нужно, чтобы наше подрастающеепоколение заинтересовалась в решении той или иной экономической проблеме, а дляэтого они должны знать, как их можно решить.
В своей работе япредставил основные факты «Теории игр», определения и основные методы решенияматричных игр. Я попытался как можно легче и точно дать представление этогораздела математики и экономики.
Для написания свойкурсовой работы я пользовался очень хорошей и интересной литературой, которуюнепременно порекомендую своим ученикам.
Для написаниятеоретического материала я воспользовался такими книга как «Основные теорииигр. Бескоалиционные игры», автор Вороьев Н.Н; «Теория игр», авторы ПетросянЛ.А., Зенкевич Н.А., Семина Е.А; «Теория игр для экономистов», авторы ПечерскийС.Л. и Беляев А.А.
Для написанияпрактического материала и интересные задачи я воспользовался несколькимизадачниками практикумами по линейной и высшей алгебре, и книгой Матвеева В.А.«Конечные бескоалиционные игры и равновесия».
Апробация проводилась вВольном институте среди студентов второго курса. Данный спец-курс был проведёнМатвеевым Владимиром Александровичем для студентов вольного института на 3курсе в группах юристов и экономистов, я был ассистентом. Курс был успешноусвоен, и студенты без особого труда освоили теорию Матричных игр иматематический пакет Maple.