- •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.4. Смешанные стратегии
Смешанной стратегией (с.с.) игрока в матричной игре называется вероятностное распределение на множестве его ч.с. Таким образом, если - чистые стратегии игрока , а - чистые стратегии игрока , то с.с. игрока - это вероятностный вектор , где- вероятность выбора игроком чистой стратегии ,. Очевидно, вектордолжен удовлетворять условиям:
. (1)
Аналогично, с.с. игрока - это вероятностный вектор , удовлетворяющий условиям
. (2)
Обозначим множество всех с.с. игрока через , а игрока - через . Если выбрал с.с. , а - , товыигрышем игрока (соответственно проигрышем игрока в ситуации естественно считать математическое ожидание
. (3)
В соответствии с принципом минимакса гарантированный, то есть наименьший выигрыш игрока при выборе им с.с. будет равен
. (4)
Поэтому игроку выгодно выбрать так, чтобы максимально увеличить:
. 5)
Аналогично, гарантированный, то есть наибольший проигрыш игрока при выборе им с.с. равен
. (6)
и игроку выгодно минимизировать :
. (7)
Числа ,называются соответственнонижней и верхней ценой игры в смешанных стратегиях.
Замечание. Строго говоря, следовало бы доказать, что все минимумы и максимумы в (4)-(7) существуют. Однако, это очевидно, так как в силу (1), (2) множества , компактны, а функции (3), (4) и (6) непрерывны.
Следующая лемма дает более простые, чем (4), (6) выражения величин ,.
Лемма 1.1[2] (о гарантированных выигрышах).
для всякой с.с. ;
для всякой с.с. .
Матричная игра называется разрешимой в с.с., если , а стратегии*,*, для которых, называютсяоптимальными с.с. Пара (*,*) оптимальных с.с. образуетситуацию равновесия в с.с., а величина -цена игры в с.с. - равна ожидаемому среднему выигрышу игрока (и, соответственно, ожидаемому среднему проигрышу игрока ).
Как и в случае чистых стратегий, несложно показать, что всегда . Однако, замечательно, что в случае смешанных стратегий строгое неравенствоневозможно. Это вытекает из следующей основной теоремы матричных игр, доказанной Дж. фон Нейманом в 1928 г.
Теорема 1.2[2] (о минимаксе). Для любой матричной игры имеет место равенство Другими словами, любая матричная игра разрешима в с.с.
Оптимальные с.с. игроков, а также цена игры в с.с. могут быть найдены как решения пары двойственных задач линейного программирования:
, (8)
Здесь - элементы платежной матрицы , переменные ,- компоненты смешанных стратегий игроков , соответственно, - гарантированный выигрыш игрока , - гарантированный проигрыш игрока в с.с.
1.5. Пример полного решения матричной игры
Задача. Решить игру с платежной матрицей
.
Решение. 1. Выясним, имеет ли игра решение в ч.с. Для этого вычислим нижнюю и верхнюю цены игры в ч.с.:
; .
, следовательно, матрица не имеет седловой точки, и игра не разрешима в ч.с.
2. Будем искать решение игры в с.с. Смешанная стратегия игрока - это вероятностный вектор:
, где ;.
Аналогично, смешанная стратегия игрока - это вероятностный вектор:
, где ;.
3. Заметим, что каждый элемент строки 1 не меньше соответствующего элемента строки 3, то есть выигрыш игрока при выборе им ч.с. 1 не меньше его выигрыша при выборе им ч.с. 3. Ясно, что разумный игрок предпочтет стратегию 1 стратегии 3. В этом случае говорят, что ч.с. 1 игрока доминирует над его ч.с. 3. Аналогично, каждый элемент столбца 2 не больше соответствующего элемента столбца 3, и ч.с. 2 игрока доминирует над его ч.с. 3. Легко понять, что в оптимальные с.с. доминируемые ч.с. войдут с нулевыми вероятностями ,. Поэтому в дальнейшем мы можем рассматривать сокращенную матрицу игры, полученную из исходной вычеркиванием третьей строки и третьего столбца:
.
4. "Сдвиг" матрицы. Вместо матрицы рассмотрим матрицу
,
полученную из матрицы добавлением одного и того же числа ко всем ее элементам. Число это (в данном случае 2) выбирается так, чтобы все элементы матрицыстали неотрицательными. Несложно показать, что такой сдвиг платежной матрицы не приводит к изменению оптимальных смешанных стратегий игроков. Изменяется только значение цены игры, в данном случае оно увеличивается на 2.
Смысл такого сдвига в следующем. В игре с платежной матрицей выигрыш игрока в любой ситуации неотрицателен, а значит не отрицательны и все его гарантированные выигрыши, а также цена игры в с.с. Это дает нам право, составляя пару двойственных задач ЛП, считать переменные неотрицательными.
5. Составляем пару двойственных задач ЛП для игры с платежной матрицей :
(9)
Прежде чем решать их, удобно сделать замену переменных ,,=1,2. Тогда задачи принимают вид:
(10)
6. Приводим вторую задачу к канонической форме (вводя дополнительные переменные ), и решаем ее симплекс-методом [1]:
|
t0 |
t1 |
t2 |
t3 |
t4 |
f |
0 |
-1 |
-1 |
0 |
0 |
t3 |
1 |
3 |
1 |
1 |
0 |
t4 |
1 |
0 |
4 |
0 |
1 |
|
t0 |
t1 |
t2 |
t3 |
t4 |
f |
1/3 |
0 |
-2/3 |
1/3 |
0 |
t3 |
1/3 |
1 |
1/3 |
1/3 |
0 |
t4 |
1 |
0 |
4 |
0 |
1 |
|
t0 |
t1 |
t2 |
t3 |
t4 |
f |
1/2 |
0 |
1 |
1/3 |
1/6 |
t3 |
1/4 |
1 |
0 |
1/3 |
-1/12 |
t4 |
1/4 |
0 |
1 |
0 |
1/4 |
Оптимальное решение , .Используя вторую теорему двойственности, находим оптимальное решение двойственной задачи:,. Возвращаясь к исходным переменным и вспоминая, что,, получаем оптимальные с.с. игроков:,. Цена игры в с.с. равна 0 (с учетом сдвига матрицы).
Комментарий. Оптимальные с.с. игроков диктуют им следующие действия при многократном повторении игры: игроку следует выбирать свою первую ч.с. с вероятностью 2/3, а вторую - с вероятностью 1/3. Игроку - выбирать как первую, так и вторую ч.с. с вероятностью 1/2. При этом ожидаемый средний выигрыш игрока (и проигрыш игрока ) будет равен нулю - ничья.