Библиотека « simplex » пакета Maple

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Библиотека «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)

Обозначим f₂(α )=2α -1 и f₂(α )=1-2α.

Найдем max min (f₁(α ), f₂(α ))= max( min(2α -1, 1-2α )).

Для нахождения максимина приведем графическую иллюстрацию (1)

Вначале для каждого α ? [0, 1] найдем min(2α -1, 1-2α ). На рисунке (1) такие минимумы для каждого α ? [0, 1] образуют ломанную – нижнюю огибающую MPQ. Затем на огибающей находим наибольшее значение, которое будет в точке P. Эта точка достигает при α ? [0, 1], которое является решением уравнения f₁= f₂, т.е. 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β ).

Обозначим f₁(β )= 2β -1, f₂(β )= 1-2β

Найдем min max (f₁(β ), f₂(β ))= 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) и выполняется условие, что

V_H = 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 задачу, чтобы она решалась графоаналитическим методом.

Задача:

Графоаналитическим методом найти цену и седловую точку матричной игры, заданную матрицей выигрыша первого игрока.