Библиотека « 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 = j₁ стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

 

a_ij = =  (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.

⇐ Предыдущая12345Следующая ⇒

Поделиться: