Методика преподавания курса "Матричные игры" (стр. 5 из 5)
Практика показала, что для большинства прикладных задач линейного программирования симплекс-метод позволяет отыскать оптимальное решение за относительно небольшое число шагов по сравнению с общим числом крайних точек допустимого многогранника. В тоже время известно, что для некоторых задач линейного программирования со специально подобранной формой допустимой области, применение симплекс-метода приводит к полному перебору крайних точек. Этот факт в известной мере стимулировал поиск новых эффективных методов решения задачи линейного программирования, построенных на иных, нежели симплекс-метод, идеях, позволяющих решать любую задачу линейного программирования за конечное число шагов, 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.