- •1. Элементы теории игр
- •1.1. Основные понятия
- •1.2. Матричные игры
- •1.3. Принцип минимакса. Седловые точки
- •1.4. Смешанные стратегии
- •1.5. Пример полного решения матричной игры
- •1.6. Задания для самостоятельной работы}
- •2.Задача о назначениях
- •2.1. Содержательная постановка
- •2.2. Математическая модель
- •2.3. Венгерский метод
- •2.4. Алгоритм венгерского метода
- •2.5. Пример
- •2.6. Задания для самостоятельной работы
- •3.Задача коммивояжера
- •Постановка задачи
- •Метод ветвей и границ
- •Метод ветвей и границ для решения задачи коммивояжера.
- •3.4 Пример
- •3.5. Задания для самостоятельной работы
- •4.Динамическое программирование
- •4.1. Постановка задачи
- •4.2. Построение модели дп
- •4.3. Построение вычислительной схемы дп
- •4.4. Несколько замечаний к методу дп
- •4.5. Задачи распределения ресурсов
- •5.6. Пример решения задачи распределения ресурсов
- •4.7. Задачи о замене оборудования.
- •4.8. Пример решения задачи о замене оборудования
- •5.9. Задания для самостоятельной работы
1.2. Матричные игры
Матричной игрой называется конечная игра двух лиц с нулевой суммой.
Так как число стратегий каждого игрока в матричной игре конечно, то их можно пронумеровать. Будем считать, что игрок имеет стратегии =1, …, m, а игрок - стратегии =1, …, n. В дальнейшем будем называть ихчистыми стратегиями (ч.с.)
Функции выигрыша игроков в матричной игре могут быть заданы в виде платежной матрицы =() размера, где- выигрыш игрока (и, соответственно, проигрыш игрока ) в ситуации (,).
Пример 1.2. Игра "Два числа".
Играют двое. Каждый из игроков втайне от другого записывает одно из двух чисел: 1 или 2. Затем числа предъявляются и подводится итог. Если оба записали 1, то выигрывает 1 очко, а если оба записали 2, то выигрывает 2 очка. Если записал меньшее число, то выигрывает 1 очко; в противном случае выигрывает 2 очка. В любой ситуации выигрыш игрока равен проигрышу соперника.
Здесь у каждого из игроков имеется по две ч.с.: записать 1 или записать 2. Платежная матрица игры изображена на рис. 2, строки соответствуют стратегиям игрока , столбцы - стратегиям игрока .
|
1 |
2 |
|
|
|
О |
Р |
1 |
-1 |
1 |
|
|
О |
-1 |
1 |
2 |
-2 |
2 |
|
|
Р |
1 |
-1 |
Рис. 3
Рис. 2
Пример 1.3. Игра в орлянку.
Игрок кладет монету, игрок , не видя, пытается угадать, какой стороной положил монету игрок - "орлом" (О) или "решкой" (Р). Угадал - выиграл 1 очко (а в этом случае проиграл 1 очко), не угадал - проиграл 1 очко (а выиграл 1 очко).
В этой игре у каждого из игроков имеется по две ч.с. : у игрока - положить монету "орлом" или "решкой", у игрока - назвать "орел" или "решку". Платежная матрица игры изображена на рис. 3.
1.3. Принцип минимакса. Седловые точки
Будем предполагать, что игроки ведут себя разумно и каждый из них стремится максимизировать свой выигрыш. Попытаемся выяснить, как следовало бы действовать игрокам в матричной игре, чтобы добиться поставленной цели.
Предположим, что игроки и участвуют в матричной игре с платежной матрицей =() размера. Выбирая чистую стратегию, игрок выбирает строку , а игрок - столбец . Выигрыш или, что то же, проигрыш в этой ситуации равен . Ясно, что игрок будет стараться увеличить , в то время как будет пытаться его уменьшить.
Если игрок выбрал ч.с. , то должен ответить такой стратегией , чтобы выигрышбыл наименьшим среди чисел, обозначим его:
.
Величина есть наименьший, то естьгарантированный выигрыш игрока при выборе им ч.с. . Значит, игроку выгодно выбрать ту стратегию, которая даст наибольшее значение :
.
Стратегия , для которой,максиминной стратегией игрока .
Аналогично рассуждая, получаем, что величина
есть наибольший, то есть гарантированный проигрыш игрока при выборе им ч.с. . Игроку из всех стратегий выгодно выбрать минимаксную ч.с., при которой его гарантированный проигрыш минимален:
.
Величины иназываются соответственнонижней и верхней ценой игры в ч.с.
Еще раз подчеркнем, что выбрав максиминную ч.с., игрок гарантированно получит выигрыш, не меньший , а игрок , выбрав минимаксную ч.с., не проиграет больше .
Описанные рассуждения носят название принципа минимакса (или принципа гарантированного результата). Кратко этот принцип может быть сформулирован следующим образом: каждый игрок должен стремиться максимально увеличить свой гарантированный выигрыш.
Легко показать, что в любой матричной игре . Например, в игре "Два числа" (пример 1.2), а в игре в орлянку (пример 1.3).
Хорошо известно [2], что равенство имеет место тогда и только тогда, когда платежная матрица имеет седловую точку, то есть существует такая пара номеров , что
для любых ,.
Седловая точка платежной матрицы дает ситуацию равновесия
в матричной игре, когда игроку невыгодно отступать от своей максиминной ч.с. , а игроку - от минимаксной ч.с. , поскольку отклоняясь от этих стратегий, игроки могут разве что уменьшить свой выигрыш. Если- седловая точка, то стратегииназываютсяоптимальными ч.с. Пара оптимальных ч.с. называетсярешением игры в ч.с., а сама матричная игра - разрешимой в ч.с. Величина называется в этом случаеценой игры в ч.с.
Если же , то матрица не имеет седловой точки. В такой игре ситуации равновесия нет, и она не разрешима в ч.с.
Между играми с седловой точкой и без нее существует огромная разница, которая проявляется особенно ярко при многократном повторении игры. Поясним эту разницу на примерах 1.2 и 1.3.
Рассмотрим игру "Два числа" (пример 1.2) и подумаем, как поведут себя разумные игроки в этой игре. Если выберет ч.с. 1, то есть запишет 1, он может выиграть 1 очко (если запишет 2), но может и проиграть 1 очко (если запишет 1). Если же выберет ч.с. 2, то он может выиграть 2 очка (если запишет 2), но может и проиграть 2 очка (если запишет 1). А поскольку игрок разумен, то он наверняка выберет ч.с. 1 (при этом он вообще не проигрывает). И тогда игроку ничего другого не остается, как выбрать меньшее из зол и записать число 1.
Итак, в этой игре есть ситуация равновесия (1,1), когда игрокам невыгодно отступать от своих оптимальных ч.с. =1,=1, сколько бы ни продолжалась игра. Правда, при этом каждый раз будет проигрывать 1 очко, но, выбирая число 2, он проиграет еще больше. Игроку тем более невыгодно отступать от избранной стратегии, так как записав число 2, он вместо выигрыша проиграет 1 очко. Оба даже могут заранее объявить о своих намерениях, секретность в играх с седловой точкой не имеет никакого значения.
Иное дело в игре в орлянку (пример 1.3). В этой игре седловой точки нет, и игрокам имеет смысл скрывать свои намерения от соперника. Если при многократном повторении игры один из игроков будет все время придерживаться какой-либо одной ч.с. или даже выбирать свои ч.с. по некоторой заранее определенной схеме, то его разумный соперник может понять это и принять контрмеры. Единственный разумный выход видится в следующем: в такой игре игроки должны выбирать свои ч.с. случайно, но сама схема рандомизации должна выбираться разумно. В этом и состоит идея использования смешанных стратегий.