close

Вход

Забыли?

вход по аккаунту

?

Курсовая работа по ИО

код для вставкиСкачать
Формулировка задания:
Один игрок имеет 5 фишек, другой – 3 фишки. Каждый игрок независимо от другого
распределяет свои фишки по l позициям. Выигрыш игрока складывается из выигрышей,
полученных им на каждой позиции. Если на позиции количество размещённых игроками
фишек оказалось одинаковым, то выигрыш каждого игрока равен нулю. Игрок,
разместивший на позиции большее количество фишек, выигрывает эту позицию и все
фишки противника, расположенные на ней. Стоимость позиции и стоимость 1 фишки – 1
единица.
Для параметра l = 2k, k=1,2… построить матрицу антагонистической игры и найти
её решение, т.е. определить тройку (ΓА, х*, у*), где X*={x*} - множество всех
оптимальных стратегий первого игрока, а Y*={y*} - множество всех оптимальных
стратегий второго игрока.
Решение:
Рассмотрим общий случай l позиций.
В нашем случае игроки не равноправны (у одного 5 фишек у другого 3 фишки),
поэтому пронумеруем игроков: пусть у первого игрока будет 5 фишек, у второго - 3.
Матрица игры А будет большой размерности, поэтому для решения игры ΓА,
воспользуемся теоремой 7 (Методические указания по курсу «Теория игр и исследование
операций»), которая связывает решения игр ΓА и ΓВ. Для применения теоремы 7
необходимо правильно сгруппировать стратегии игроков в матрице А, так, чтобы они
образовывали группы, удовлетворяющие разбиению матрицы А на блоки, описанные
условиями теоремы 7.
Для этого рассмотрим все способы распределения 5 и 3 фишек по l позициям:
Игрок 1
Игрок 2
i=1 5+0
j=1 3+0
i=2 4+1+0
j=2 2+1+0
i=3 3+2+0
j=3 1+1+1+0
i=4 3+1+1+0
i=5 2+2+1+0
i=6 2+1+1+1+0
i=7 1+1+1+1+1+0
Элементами матрицы В будут средние выигрыши первого игрока при применении им
стратегии i, а вторым игроком стратегии j.
bij=ξP(Ak)P(Bt), где событие Аk={на позиции окажется nk фишек первого игрока},
Вk={на позиции окажется nt фишек второго игрока},
ξ - выигрыш игрока 1 при применении им стратегии i, а
вторым игроком стратегии j.
P(Аk)=lk/l
P(Bt)=lt/l
Чтобы найти решения игры ΓА достаточно найти решения игры ΓВ. Следовательно
задача сводится к нахождению решения игры ΓВ. Выпишем найденную матрицу В
(вычисления приводятся в Приложении 1 к настоящей работе).
В=1/l2
4
2+l
-3+l
-4+2l
-8+2l
-9+3l
-10+4l
5-l
3
7
1+l
2+l
-4+2l
-10+3l
6-2l
6-l
12-l
6
12
6+l
2l
Рассмотрим случай l=2
Матрица В при l=2 получается из общей матрицы В (для случая l позиций) путем
вычеркивания последнего столбца и четырех последних строчек (т.к. такие комбинации
при l=2 там встретиться не могут)
В=1/4
4
4
-1
3
3
7
Используя теоремы 4 и 5 (Методические указания по курсу «Теория игр и
исследование операций») о доминировании строк и столбцов получаем матрицу меньшей
размерности (первая строчка доминируется второй).
4
В`=1/4 4
-1
3
3
7
Найдем оптимальные стратегии графическим методом:
х`=(ξ,1-ξ)
у`=(ξ,1-ξ)
Н(ξ,1)=5ξ-1
Н(1,ξ)=ξ+3
Н(ξ,2)=-4ξ+7
Н(2,ξ)=-8ξ+7
ξ=8/9
ξ=4/9
х`*=(0;8/9;1/9)
у`*=(4/9;5/9)
ν=31/36
Найдем множество всех оптимальных стратегий первого игрока по оптимальной
стратегии второго игрока и цене матричной игры:
Ищем несущественные стратегии первого игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(i,y*)<υ,
то i - несущественная стратегия первого игрока, значит x*i=0 для всех оптимальных
стратегий.
В данном случае несущественных стратегий нет (т.к. Н(i,y*)=31/36 при j=1,2)
По теореме о равновесии все оптимальные стратегии первого игрока
уравновешиваются существенными стратегиями второго игрока, т.е. хb1=ν и хb2=ν
¼(4x1+4x2-x3)=31/36
¼(3x1+3x2+7x3)=31/36
X*= x1+x2+x3=1
x1≥0
x2≥0
x3≥0
Преобразовывая и решая систему уравнений и неравенств, получаем:
x1є[0,8/9]
X*= x2=8/9-x1
x3=1/9
Множество оптимальных стратегий Х* первого игрока будет выглядеть как
множество, представленное в виде линейных комбинации двух векторов:
Х*={α1(0,8/9,1/9)+α2(8/9,0,1/9)} где α1+α2=1, α1,α2≥0
Найдем множество всех оптимальных стратегий второго игрока по оптимальной
стратегии первого игрока и цене матричной игры:
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае несущественных стратегий нет (т.к. Н(х*, j)=31/36 при j=1,2)
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b2y=ν и b2y=ν
¼(4у1+3у2)=31/36
Y*= ¼(-у1+7у2)=31/36
у1+у2=1
Решая данную систему, получаем, что:
y1=4/9, а y2=5/9
Следовательно, множество всех оптимальных стратегий Y* второго игрока состоит
из одной стратегии у*=(4/9,5/9)
Y*={y*}={(4/9,5/9)}
Таким образом мы нашли решение игры с матрицей В при l=2:
Х*={α1(0,8/9,1/9)+α2(8/9,0,1/9)} где α1+α2=1, α1,α2≥0
Y*={(4/9,5/9)}
ν=31/36
Рассмотрим случай l=4
Матрица В при l=4 получается из общей матрицы В (для случая l позиций) путем
вычеркивания последней строки (т.к. такая комбинация при l=4 встретиться не может)
4
1
-2
6
3
2
В=1/16 1
7
8
4
5
6
0
6
12
3
4
10
Используя теоремы 4 и 5 (Методические указания по курсу «Теория игр и
исследование операций») о доминировании строк и столбцов получаем матрицу меньшей
размерности (b1<b2).
4
1
-2
6
3
2
В=1/16 1
7
8
4
5
6
0
6
12
3
4
10
Проверим, что х*=(0,1/4,0,3/4,0,0) и у*=(1/2,1/2,0) являются оптимальными
стратегиями первого и второго игроков соответственно, а цена игры ν=9/32. Проверка
приводится в Приложении 2 к настоящей работе.
Найдем множество всех оптимальных стратегий первого игрока по оптимальной
стратегии второго игрока и цене матричной игры:
Ищем несущественные стратегии первого игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(i,y*)<υ,
то i - несущественная стратегия первого игрока, значит x*i=0 для всех оптимальных
стратегий.
В данном случае H(i,y*)< 9/32 при i=1,3,5,6. Значит первая, третья, пятая и шестая
стратегии первого игрока несущественны, т.е. x1*=x3*=x4*=x6*=0 для всех оптимальных
стратегий первого игрока.
По теореме о равновесии все оптимальные стратегии первого игрока
уравновешиваются существенными стратегиями второго игрока, т.е. хb1=ν и хb2=ν
x1=0
х3=0
x5=0
X*= x6=0
1/16(6x2+4x4)=9/32
1/16(3x2+5x4)=9/32
x2+x4=1
Решая данную систему, получаем, что:
x2=1/4
x4=3/4
Следовательно, множество всех оптимальных стратегий X* первого игрока состоит
из одной стратегии х*=(0,1/4,0,3/4,0,0)
X*={(0,1/4,0,3/4,0,0)}
Найдем множество всех оптимальных стратегий второго игрока по оптимальной
стратегии первого игрока и цене матричной игры:
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае Н(х*, j)>9/32 при j=3. Значит третья стратегия второго игрока
несущественна, т.е. у3*=0 для всех оптимальных стратегий второго игрока.
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b2y=ν и b4y=ν
у3=0
Y*= 1/16(6у1+3у2)=9/32
1/16(4у1+5у2)=9/32
у1+у2=1
Решая данную систему, получаем, что:
y1=1/2, а y2=1/2
Следовательно, множество всех оптимальных стратегий Y* второго игрока состоит
из одной стратегии у*=(1/2,1/2,0)
Y*={(1/2,1/2,0)}
Таким образом мы нашли решение игры с матрицей В при l=4:
X*={(0,1/4,0,3/4,0,0)}
Y*={(1/2,1/2,0)}
ν=9/32
Рассмотрим случай l=6
4
-1
8
3
3
7
В=1/36 8
7
4
8
9
8
14
8
-6
0
6
6
12
12
12
В этой таблице элементы b62 и b72 являются максимальными в своих столбцах и при
этом минимальными в своих строках. Это означает, что здесь есть чистые оптимальные
стратегии x*=(0,0,0,0,0,0,1), x*=(0,0,0,0,0,1,0), y*=(0,1,0), а цена игры будет равняться
ν=8/36.
Найдем множество всех оптимальных стратегий первого игрока по оптимальной
стратегии второго игрока и цене матричной игры:
Ищем несущественные стратегии первого игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(i,y*)<υ,
то i - несущественная стратегия первого игрока, значит x*i=0 для всех оптимальных
стратегий.
В данном случае H(i,y*)< 8/36 при i=1,2,3,4. Значит первая, вторая, третья и
четвертая стратегии первого игрока несущественны, т.е. x1*=x2*=x3*=x4*=0 для всех
оптимальных стратегий первого игрока.
По теореме о равновесии все оптимальные стратегии первого игрока
уравновешиваются существенными стратегиями второго игрока, т.е. хb2=ν
x1=0
x2=0
x3=0
x4=0
1/36(8x5+8x6+8x7)=8/36
X*= x5+x6+x7=1
1/36(4x4+9x6+14x7)≥8/36
1/36(12x5+12x6+12x7)≥8/36
x5≥0
x6≥0
x7≥0
Решая эту систему уравнений и неравенств (решение приводится в Приложении 3 к
настоящей работе) мы получаем, что множество всех оптимальных стратегий будет
выглядеть как множество представленное в виде линейных комбинаций четырех векторов:
X*={α1(0,0,0,0,0,0,1)+α2(0,0,0,0,0,1,0)+α3(0,0,0,0,1/5,4/5,0)+α4(0,0,0,0,3/5,0,2/5)}
Где ∑αi=1 и αi≥0 i=1,2,3,4.
Найдем множество всех оптимальных стратегий второго игрока по оптимальной
стратегии первого игрока и цене матричной игры:
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае Н(х*, j)>8/36 при j=1,3. Значит первая и третья стратегии второго
игрока несущественны, т.е. y1*=у3*=0 для всех оптимальных стратегий второго игрока.
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b7y=ν
у1=0
Y*= у3=0
у2=1
Следовательно, множество всех оптимальных стратегий Y* второго игрока состоит
из одной стратегии у*=(0,1,0)
Y*={(0,1,0)}
Таким образом мы нашли решение игры с матрицей В при l=6:
X*={α1(0,0,0,0,0,0,1)+α2(0,0,0,0,0,1,0)+α3(0,0,0,0,1/5,4/5,0)+α4(0,0,0,0,3/5,0,2/5)}
Где ∑αi=1 и αi≥0 i=1,2,3,4.
Y*={(0,1,0)}
ν=8/36
Рассмотрим случай l=8
4
-3
-10
10
3
-2
5
7
4
В=1/64 12
9
6
8
10
12
15
12
14
22
14
16
В этой таблице элемент b72 является максимальным в своем столбце и при этом
минимальным в своей строке. Это означает, что x*=(0,0,0,0,0,0,1), y*=(0,1,0) – чистые
оптимальные стратегии, а цена игры будет равняться ν=14/64.
Найдем множество всех оптимальных стратегий первого игрока по оптимальной
стратегии второго игрока и цене матричной игры:
Ищем несущественные стратегии первого игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(i,y*)<υ,
то i - несущественная стратегия первого игрока, значит x*i=0 для всех оптимальных
стратегий.
В данном случае H(i,y*)< 14/64 при i=1,2,3,4,5,6. Значит первая, вторая, третья,
четвертая, пятая и шестая стратегии первого игрока несущественны, т.е.
x1*=x2*=x3*=x4*=х5*=х6*=0 для всех оптимальных стратегий первого игрока.
Сумма xi=1, следовательно, множество всех оптимальных стратегий X* первого
игрока состоит из одной стратегии X*={(0,0,0,0,0,0,1)}
Множество Х* остается неизменным при l≥8.
Найдем множество всех оптимальных стратегий второго игрока по оптимальной
стратегии первого игрока и цене матричной игры:
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае Н(х*, j)>14/64 при j=1,3. Значит первая и третья стратегии второго
игрока несущественны, т.е. y1*=у3*=0 для всех оптимальных стратегий второго игрока.
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b7y=ν
у1=0
Y*= у3=0
у2=1
Следовательно, множество всех оптимальных стратегий Y* второго игрока состоит
из одной стратегии Y*={(0,1,0)}
Таким образом мы нашли решение игры с матрицей В при l=8:
X*={(0,0,0,0,0,0,1)} при l≥8
Y*={(0,1,0)}
ν=14/64
Рассмотрим случай l=10
4
-5
12
3
7
7
В=1/1000 16
11
12
12
21
16
30
20
-14
-4
2
6
12
16
20
В этой таблице элементы b72 и b73 являются максимальными в своих столбцах и при
этом минимальными в своих строках. Это означает, что здесь есть чистые оптимальные
стратегии x*=(0,0,0,0,0,0,1), y*=(0,1,0), y*=(0,0,1), а цена игры будет равняться ν=20/100.
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае Н(х*, j)>14/64 при j=1. Значит первая стратегия второго игрока
несущественна, т.е. y1*=0 для всех оптимальных стратегий второго игрока.
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b7y=ν
y1=0
20y2+20y3=20
y2+y3=1
-5y2-14y3≥20
3y2-4y3≥20
7y2+2y3≥20
11y2+6y3≥20
12y2+12y3≥20
16y2+16y3≥20
Решив эту систему уравнений и неравенств легко получаем, что множество всех
оптимальных стратегий будет выглядеть как множество представленное в виде линейных
комбинаций четырех векторов:
Y*={α1(0,0,1)+α2(0,1,0)} Где ∑αi=1 и αi≥0 i=1,2
Рассмотрим случай l=12
4
5-l
6-2l
2+l
3
6-l
-3+l
7
12-l
2
В=1/l
-4+2l
1+l
6
-8+2l
2+l
12
-9+3l
-4+2l
6+l
-10+4l
-10+3l
2l
В этой таблице элемент b73 является максимальным в своем столбце и при этом
минимальным в своей строке. Это означает, что здесь есть чистые оптимальные стратегии
x*=(0,0,0,0,0,0,1), y*=(0,0,1) а цена игры будет равняться ν=2l/l2.
Ищем несущественные стратегии второго игрока по следствию из теоремы 2
(Методические указания по курсу «Теория игр и исследование операций»). Если Н(x*,j)>υ,
то j - несущественная стратегия второго игрока, значит y*j=0 для всех оптимальных
стратегий.
В данном случае Н(х*, j)>2l/l2 при j=1,2. Значит первая и вторая стратегии второго
игрока несущественны, т.е. y1*=у2*=0 для всех оптимальных стратегий второго игрока.
По теореме о равновесии все оптимальные стратегии второго игрока
уравновешиваются существенными стратегиями первого игрока, т.е. b7y=ν
у1=0
Y*= у2=0
у3=1
Следовательно, множество всех оптимальных стратегий Y* второго игрока состоит
из одной стратегии Y*={(0,0,1)}
Таким образом мы нашли решение игры с матрицей В при l≥12:
Y*={(0,0,1)}
ν=2l/l2
Документ
Категория
Математика
Просмотров
12
Размер файла
97 Кб
Теги
курсовая_работа_по_ио
1/--страниц
Пожаловаться на содержимое документа