Методы оптимальных решений (стр. 8 )

Решая систему уравнений

найдем , , .

Таким образом, имеем полученный выше ответ игры: и .

Теперь покажем как графическим методом найти стратегии игрока В.

(69)

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

при стратегии (70)

при стратегии (71)

Очевидно, , которую называют верхней огибающей прямых III и IV.

Нетрудно видеть, что

Таким образом, нижняя точка верхней огибающей – определяет оптимальную стратегию игрока В: и цену игры .

Для рассмотренной выше гры с матрицей H найдем стратегии игрока В.

На плоскости qOz построим две прямые, описываемые уравнениями: и или (III) и (IV).

Решая систему уравнений

найдем , , .

Таким образом, имеем и .

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

или .

Для рассмотренного примера такими уравнениями будут

или

Аналогично находят оптимальную стратегию игрока А, если известна оптимальная стратегия игрока В.

и – игры.

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

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.

ОГЛАВЛЕНИЕ

Введение ……………………………………………………………………..	3
ЛЕКЦИЯ 1. Исследование операций. Экономико-математические модели. ……………………………………………………………………….	4
ЛЕКЦИЯ 2. Балансовые модели. Модель Леонтьева многоотраслевой экономики. Продуктивные модели………………………………………….	8
ЛЕКЦИЯ 3,4,5. Задачи математического и линейного программирования. Модели линейного программирования……………...	15
ЛЕКЦИЯ 6. Динамическое программирование. Принцип оптимальности и функциональности. Функциональное уравнение Беллмана…………….	40
ЛЕКЦИЯ 7. Модели потребительского выбора. Функция полезности. Линии безразличия. Оптимизация функции полезности. Функции спроса и предложения……………………………………………………….	49
ЛЕКЦИЯ 8. Элементы теории игр в задачах оптимального управления экономическими процессами……………………………………………….	58
ЛЕКЦИЯ 9. Методы решения матричных игр в смешанных стратегиях...	73
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ……………………………	84

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

,

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

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

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

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