и – игры.

Решают такие игры графическим способом, описанным выше. Отличие от – игр заключается в следующем.

4) Нижняя (верхняя) огибающая семейства прямых

содержит большее число отрезков.

5) Пусть в игре в верхней точке нижней огибающей пересекаются прямые и . Тогда при нахождении оптимальной смешанной стратегии игрока В полагают, что , , , , где q – решение уравнения

или

6) Пусть в игре в нижней точке верхней огибающей пересекаются прямые и . Тогда при нахождении оптимальной смешанной стратегии игрока А полагают, что , , , , где p – решение уравнения

или .

Игры.

При решении таких игр рекомендуется предварительно уменьшить размеры платежной матрицы или упростить ее в некотором смысле. С этой целью применяют следующие правила.

Правило доминировнаия.

Из платежной матрицы исключают чистые стратегии заведомо невыгодные по сравнению с другими:

а) для игрока А такими стратегиями являются те, которым соответствуют строки с элементами не большими по сравнению с элементами других строк;

б) для игрока В такими стратегиями являются те, которым соответствуют столбцы с элементами не меньшими по сравнению с элементами других столбцов.

Например, рассмотрим игру с матрицей

Сравнивая строки, убеждаемся, что элементы 2-ой строки не больше соответствующих элементов 1-ой строки, а 3-ья строка совпадает с 4-ой. Следовательно, стратегии и невыгодные и могут быть отброшены. Матрица игры преобразуется к матрице

Сравнивая столбцы полученной матрицы, убеждаемся, что элементы 2-го столбца не меньше соответствующих элементов 1-го столбца, а элементы 3-го столбца не меньше соответствующих элементов 4-го столбца, т.е. стратегии и также могут быть отброшены. Окончательно усеченная матрица игры имеет вид

.

Таким образом, оптимальными стратегиями игроков А и В игры с матрицей Н будут и , где и – оптимальные стратегии игры с матрицей .

Аффинное правило.

Пусть и – оптимальные смешанные стратегии игроков А и В в игре с платежной матрицей и ценой . Тогда и будут оптимальными стратегиями и в игре с матрицей и ценой .

Например, игру с матрицей можно заменить игрой с матрицей , т.к. элементы этих матриц связаны соотношениями : ; ; ; ; ; . При этом оптимальные стратегии игр совпадают, а цены игр связаны соотношением .

В общем случае решение игр размера в смешанных стратегиях сводят к решению двух возможно двойственных ЗЛП.

Редукция матричных игр к ЗЛП.

Пусть игра задана платежной матрицей . Через и обозначим соответственно оптимальные стратегии игроков А и В. Пусть – цена игры. Не умаляя общности, полагаем . В противном случае с помощью аффинного правила добьемся того, что все .

Оптимальная стратегия стратегия игрока А обеспечивает ему средний выигрыш, не меньший , при любой стратегии игрока В. Поэтому все средние выигрыши игрока А можно выписать в виде системы неравенств:

(72)

Введем новые переменные:

(73)

Тогда после деления каждого неравенства из (71) на получим новую систему неравенств

(73)

Из равенства

нетрудно получить соотношение для :

.

Игрок А стремится максимизировать свой гарантированный выигрыш . Максимизация равносильна минимизации . Следовательно, получили следующую задачу для нахождения оптимальной стратегии игрока А:

(74)

при условиях (73) и

(75)

Сформулированная задача (74) – (76) является ЗЛП.

Повторим с естественными изменениями предыдущие рассуждения для определения оптимальной стратегии игрока В.

Игрок В стремиться минимизировать гарантированный проигрыш . Все средние проигрыши игрока В запишем в виде системы неравенст:

, (76)

которые следуют из того, что средний проигрыш игрока В не превосходит цены игры при любой стратегии игрока А.

В обозначениях

система неравенств (76) примет вид

(77)

Применение удовлетворяют соотношению

.

Минимизация равносильна максимизации .

Получили следующую задачу для нахождения оптимальной стратегии игрока В:

(78)

при условиях (77) и

(79)

Задача (77) – (79) также является ЗЛП.

Таким образом, игра свелась к двум ЗЛП, которые запишем в матричном виде

, , ,

Очевидно, задачи I и II являются двойственными ЗЛП.

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010.

2. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010.

3. Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Питер, 2000.

4. М. Интрилигатор. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.

5. Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.

ОГЛАВЛЕНИЕ

Учебное издание

Г. Н. Камышова,

Н. Н. Терехова

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Краткий курс лекций

Издается в авторской редакции

Корректура авторов