ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.04.2024
Просмотров: 25
Скачиваний: 0
СОДЕРЖАНИЕ
Раздел 2 Линейное программирование
2 Составьте опорный план транспортной задачи методом Фогеля и оцените его стоимость.
Раздел 3 Динамическое программирование
1 Антагонистические матричные игры
1.1 Определите нижнюю и верхнюю цены, проверьте, имеет ли игра решение в чистых стратегиях.
1.4 Решите матричную игру методом Брауна-Робинсон и методом обратной матрицы.
1.4 Решите матричную игру методом Брауна-Робинсон и методом обратной матрицы.
Решение:
Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры. В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков. Пусть на первом этапе выбрана стратегия №1 Итерация №1. Минимальный элемент для нее равен -1 и находится под номером j=3. Следовательно, игрок II выбирает стратегию №3 Максимальный элемент равен 4 и находится под номером j=3. Следовательно, игрок I выбирает стратегию №3 Итерация №2. Минимальный элемент для нее равен 2 и находится под номером j=2. Следовательно, игрок II выбирает стратегию №2 Максимальный элемент равен 6 и находится под номером j=3. Следовательно, игрок I выбирает стратегию №3 Остальное решение сведем в таблицу.
|
k |
i |
B1 |
B2 |
B3 |
j |
A1 |
A2 |
A3 |
Vmin |
Vmax |
Vср |
|
1 |
1 |
5 |
0 |
-1 |
3 |
-1 |
2 |
4 |
-1 |
4 |
3/2 |
|
2 |
3 |
6 |
2 |
3 |
2 |
-1 |
0 |
6 |
1 |
3 |
2 |
|
3 |
3 |
7 |
4 |
7 |
2 |
-1 |
-2 |
8 |
4/3 |
8/3 |
2 |
|
4 |
3 |
8 |
6 |
11 |
2 |
-1 |
-4 |
10 |
3/2 |
5/2 |
2 |
|
5 |
3 |
9 |
8 |
15 |
2 |
-1 |
-6 |
12 |
8/5 |
12/5 |
2 |
|
6 |
3 |
10 |
10 |
19 |
1 |
4 |
-5 |
13 |
5/3 |
13/6 |
23/12 |
|
7 |
3 |
11 |
12 |
23 |
1 |
9 |
-4 |
14 |
11/7 |
2 |
25/14 |
|
8 |
3 |
12 |
14 |
27 |
1 |
14 |
-3 |
15 |
3/2 |
15/8 |
27/16 |
|
9 |
3 |
13 |
16 |
31 |
1 |
19 |
-2 |
16 |
13/9 |
19/9 |
16/9 |
|
10 |
1 |
18 |
16 |
30 |
2 |
19 |
-4 |
18 |
8/5 |
19/10 |
7/4 |
здесь: k - номер партии. i - номер стратегии, выбираемой игроком A. j - номер стратегии, выбираемой игроком В. Bi - накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bi. Аj - накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аj. Vmin - нижняя оценка игры = min (накопленный выигрыш)/k. Vmax - верхняя оценка игры = max (накопленный проигрыш)/k.
Доказано, что: W=(Vmin+Vmax)/2, при k → ∞ и pi = Ni/k qj = Nj/k Ni - сколько раз выбирается Аi стратегия. Nj - сколько раз выбирается Bj стратегия. NA1 = 2 P(A1) = 2/10 = 1/5 NA2 = 0 P(A2) = 0/10 = 0 NA3 = 8 P(A3) = 8/10 = 4/5 NB1 = 4 Q(B1) = 4/10 = 2/5 NB2 = 5 Q(B2) = 5/10 = 1/2 NB3 = 1 Q(B3) = 1/10 = 1/10 Цена игры, W = 7/4 Стратегия игрока I: p = (1/5, 0, 4/5) Стратегия игрока II: q = (2/5, 1/2, 1/10)
Метод обратной матрицы
|
5 |
0 |
-1 |
|
1 |
-2 |
2 |
|
1 |
2 |
4 |
Главный определитель:
∆=5*((-2)*4 - 2*2) - 1*(0*4 - 2*(-1)) + 1*(0*2 - (-2)*(-1)) = -64
Найдём миноры и алгебраическое дополнение:
M11=
|
-2 |
2 |
|
2 |
4 |
= -12
A11 = (-1)1+1 * M1= 1 * (-12) = -12
M12 = 2; A12 = -2
M13 = 4; A13 = 4
M21 = -2; A21 = -2
M22 = 21; A22 = 21
M23 = 10; A23 = -10
M31 = -2; A31 = -2
M32 = 11; A32 = -11
M33 = -10; A33 = -10
Выпишем союзную матрицу (матрицу алгебраических дополнений):
C*=
|
-12 |
-2 |
4 |
|
-2 |
21 |
-10 |
|
-2 |
-11 |
-10 |
Транспонированная союзная матрица (поменяем местами строки со столбцами):
C*T=
|
-12 |
-2 |
-2 |
|
-2 |
21 |
-10 |
|
4 |
-11 |
-10 |
Найдем обратную матрицу:
2 Биматричные игры.
Решите биматричную игру графическим методом
Решение:
В каждом столбце матрицы A найдем максимальный элемент. Эти элементы подчеркнуты в матрице A. Их положение соответствует приемлемым ситуациям 1-го игрока, когда второй игрок выбрал стратегию j соответственно. Затем в каждой строке матрицы B выберем наибольший элемент. Эти элементы подчеркнуты в матрице B. Их положение будет определять приемлемые ситуации 2-го игрока, когда первый игрок выбрал стратегию i соответственно. Платежная матрица игрока А:
|
3 |
2 |
|
5 |
1 |
Позиции максимумов в столбцах матрицы А: (2,1), (1,2) Платежная матрица игрока B:
|
4 |
2 |
|
0 |
1 |
Позиции максимумов в строках матрицы В: (1,1), (2,2) Если биматричная игра не имеет равновесных ситуаций в чистых стратегиях, то она неразрешима в чистых стратегиях. И тогда можно искать решение в смешанных стратегиях. Итак, чтобы в биматричной игре: А=(a), В = (b) пара (p,q); определяемая равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств: (p–1)(Cq-α) ≥ 0, p(Cq-α) ≥ 0; 0 ≤ p ≤ 1 (q-1)(Dp-β) ≥ 0, q(Dp-β) ≥ 0; 0 ≤ q ≤ 1 где C = a11 - a12 - a21 + a22 α = a22- a12 D = b11-b12-b21+b22 β = b22-b21 Проводя необходимые вычисления: C = 3 - 2 - 5 + 1 = -3 α = 1 - 2 = -1 D = 4 - 2 - 0 + 1 = 3 β = 1 - 0 = 1 и рассуждения (p–1)(-3q+1) ≥ 0 p(-3q+1) ≥ 0 (q-1)(3p-1) ≥ 0 q(3p-1) ≥ 0 получаем, что: 1) p=1,q ≤ 1/3 p=0, q ≥ 1/3 0 ≤ p ≤ 1, q=1/3 2) q=1,p ≥ 1/3 q=0, p ≤ 1/3 0 ≤ q ≤ 1, p=1/3
Рассматриваемая игра имеет единственную ситуацию равновесия (P*,Q*), где оптимальными стратегиями по Нэшу являются: P* = (1/3;2/3); Q* = (1/3;2/3).
Она может быть реализована при многократном повторении игры (то есть при многократном воспроизведении описанной ситуации) следующим образом: игрок I должен использовать чистые стратегии 1 и 2 с частотами 1/3 и 2/3, а игрок II – чистые стратегии 1 и 2 с частотами 1/3 и 2/3. Любой из игроков, отклонившись от указанной смешанной стратегии, уменьшает свой ожидаемый выигрыш. Цена игры Цена игры для первого игрока: Ha(1/3;1/3) = 7/3 Цена игры для второго игрока: Hb(1/3;1/3) = 4/3
Ответ: Смешанная стратегия для первого игрока P* = (1/3;2/3); Смешанная стратегия для второго игрока Q* = (1/3;2/3). Выигрыш игроков в равновесной ситуации: f(P*,Q*) = (7/3;4/3).
