Методика преподавания курса «Матричные игры»
Пояснительная записка
При решении многих практических задач приходиться анализировать ситуации, где две или более стороны, преследующие различные цели, причем результат каждого зависит от того, какой выбор сделает другая сторона. Решением таких проблем занимается – Теория игр.
В связи с развитием экономики страны я полагаю, что этот раздел математики будет интересен студентам вузов, изучающих экономику.
Этот курс рассчитан для 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 этап. Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. С начало в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находиться аналитически.
Данный метод решения применяется в тех задачах, в которых у одного из игроков ровно две стратегии.
В основе этого метода лежит утверждение, что 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 этап: проверка изученного материала и домашнее задание.
Ход занятия.
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=a пересевает область ABCDE в точке С(4;1). Поскольку это последняя точка пересечения, max(f)=f(C)=f(4;1)=19.
2 этап.
Задача:
Решить графически систему неравенств. Найти угловые решения.
x
1
+ 2
x
2
<=10
2
x
1
+
x
2
<=10
x
1
+3
x
2
>=3
5
x
1
-
x
2
>=-5
x
1
+6
x
2
>=6
x
1
>= 0,
x
2
>=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-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
IV. Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
V. Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны
.
VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении
вектора , при поиске минимума ЦФ – против направления
вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов
сверху (при поиске максимума) или снизу (при поиске минимум).
VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .
Решить задачу линейного программирования
1.
f
(
x
)=2
x
1
+
x
2
->
extr
x
1
+
x
2
<=3
x
1
+3
x
2
<=5
5
x
1
-
x
2
<=5
x
1
+
x
2
>=0
x
1
>= 0,
x
2
>=0
> plots[inequal]({a+b<=3,a+3*b<=5,5*a-b<=5,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 <=3, x+3*y <=5, 5*x-y <=5,x+y >=0};
> dp:=setup({ x+y <=3, x+3*y <=5, 5*x-y <=5,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);
ОТВЕТ: При x
1
=5/4 x
2
=5/4 f_max=15/4; При x
1
=0 x
2
=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
<=1
2x1
+x3
<=1
3x1
<=1
x1
>= 0, x2
>=0, x3
>=0
> with(simplex):
> C:={ 0*x+3*y+2*z <=1, 2*x+0*y+1*z <=1, 3*x+0*y+0*z <=1};
-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.
[1]
Вектор нормали имеет координаты (С1;С2), где C1 и C2 коэффициенты при неизвестных в целевой функции f=C1◦X1+C2◦X2+C0.