Методические_рекомендации_Методы_оптимизации

31

Варианты работы

(нечетные варианты – задача максимизации / четные варианты – задача минимизации)

Требования к отчету

Отчет должен содержать: титульный лист; цель работы; постановку задачи; решение задачи БП методом Балаша с разъяснением правил выбора вариантов; сравнение полу-

ченного решения с решением по методу полного перебора и/или жадным алгоритмом.

Контрольные вопросы

1.Формулировка задачи БП.

2.Комбинаторная сложность задачи БП.

3.Идея «жадного» алгоритма.

4.Схема метода Балаша.

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

32

5 Лабораторная работа № 5

Матричные игры с нулевой суммой. Смешанные стратегии

Цель работы

Изучить постановку антагонистической игры двух лиц в нормальной форме; найти решение игры за обоих игроков в смешанных стратегиях (стратегическую седловую точку).

Постановка задачи и методические указания

Формулировка матричной игры. В общем случае игра двух игроков, A и B, с нулевой суммой записывается в виде матрицы стратегий:

Здесь cij – выигрыш первого игрока (проигрыш второго игрока) при реализации

ими своих стратегий ai (i 1,..., m), bj ( j 1,..., n) соответственно.

Минимальный гарантированный выигрыш игрока A называется нижней ценой

игры. Он равен max min cij . При плохой игре игрока В выигрыш может быть и боль-

i j

шим. Минимально возможный проигрыш игрока B равен min max cij и называется верх-

j i

ней ценой игры.

Теорема о минимаксе. Пусть (cij ) – произвольная матрица m n , тогда

Если нижняя и верхняя цены игры равны, их значение называется ценой игры.

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

33

Теорема о седловой точке. Пусть (cij ) – произвольная матрица m n , тогда

Стратегии обоих противников в задачах с седловой точкой называются опти-

мальными и не зависят от дополнительно полученной информации.

Смешанные стратегии. Если игровая задача не имеет седловой точки, то на практике конкурирующие игроки используют смешанные стратегии, т.е. попеременно используют две или более стратегий.

По определению,

x * – оптимальная частота выбора стратегии для игрока A, y * – оптимальная частота выбора стратегии для игрока B,

если

E x, y * E x*, y * E x*, y ,

где E обозначает математическое ожидание выигрыша.

Рассмотрим произвольную игру с матрицей стратегий

i 1

Sm – множество всех смешанных стратегий игрока A.

Аналогично определяется смешанная стратегия игрока B: y j ( j 1,..., n ):

n

y j 1.

j 1

Sn – множество всех смешанных стратегий игрока B.

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

34

Стратегия игрока A, когда

x1 x2 ... xi 1 xi 1 xi 2 ... xm 0 ,

а

xi 1 ,

называется i-й чистой стратегией. Аналогично определяется j-я чистая стратегия иг-

рока B.

Если смешанная стратегия игрока A

X (x1,..., xm ) ,

а смешанная стратегия игрока B

Y ( y1,..., ym ) ,

то математическое ожидание выигрыша игрока A равно

ловая точка.

Основная теорема прямоугольных игр (теорема Неймана или теорема о минимаксе).

Пусть задана матрица стратегий (5.1) и выбраны стратегии X (x1,..., xm ) Sm , Y ( y1,..., ym) Sn ; математическое ожидание выигрыша игрока A имеет вид

где ( X *,Y*) – стратегическая седловая точка.

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

35

Сведение матричной игры к задаче ЛП. Рассмотрим прямоугольную игру с нулевой суммой и матрицей стратегий (5.1). Пусть

Задача игрока A заключается в том, чтобы g( X ) max ,

т.е.

Для игрока B поступаем аналогично. Пусть

max E( X ,Y ) h(Y ) ,

X Sm

тогда для любых X Sm , Y Sn

E( X ,Y ) h(Y ) .

В частности, для любой чистой стратегии X i и любых Y Sn имеем

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

36

Задачи (5.2) и (5.3) – прямая и двойственная задачи ЛП: minW (U ) W (U*) max Z(V ) Z(V*).

Оптимальные стратегии определяются как

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

Верно и обратное: если X *,Y * – оптимальные стратегии A и B, то

оптимальные решения прямой и двойственной задач ЛП (5.2) и (5.3).

Пример выполнения работы

Пусть матрица стратегий имеет вид

Найдем смешанные стратегии для игрока А. Для этого составим систему уравне-

ний:

x1 + 2x2 + 7x3 ≥ g, 3x1 + 6x2 + 2x3 ≥ g, 9x1 + 2x2 +6x3 ≥ g, 6x1 + 3x2 + 5x3 ≥ g, x1 + x2 + x3 = 1.

где g – минимальный выигрыш.

Разделим систему на функцию g:

u1 + 2u2 + 7u3 ≥ 1, 3u1 + 6u2 + 2u3 ≥ 1, 9u1 + 2u2 +6u3 ≥ 1, 6u1 + 3u2 + 5u3 ≥ 1, u1 + u2 + u3 = 1/g.

Сформулируем задачу для решения симплекс-методом:

W = u1 + u2 + u3  min; u1 + 2u2 + 7u3 ≥ 1,

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

38

3u1 + 6u2 + 2u3 ≥ 1, 9u1 + 2u2 +6u3 ≥ 1, 6u1 + 3u2 + 5u3 ≥ 1, ui ≥ 0, i =1,2,3.

Находим оптимальное решение:

u1 = 1/57, u2 = 7/57, u3 = 2/19, W = 14/57,

g = 1/W = 57/14.

Оптимальные стратегии:

x1 = u1g = 1/57·57/14=1/14, x2 = u2g = 7/57·57/14=1/2, x3 = u3g = 2/19·57/14=3/7.

Таким образом, оптимальная смешанная стратегия игрока A равна

(1/14, 1/2, 3/7).

Для нахождения смешанной стратегии игрока B составим систему y1 + 3y2 + 9y3 + 6y4 ≤ h,

2y1 + 6y2 + 2y3 + 3y4 ≤ h, 7y1 + 2y2 + 6y3 + 5y4 ≤ h, y1 + y2 + y3 + y4 = 1.

где h – максимальный проигрыш игрока B.

Разделим систему на h:

v1 + 3v2 + 9v3 + 6v4 ≤ 1, 2v1 + 6v2 + 2v3 + 3v4 ≤ 1, 7v1 + 2v2 + 6v3 + 5v4 ≤ 1, v1 + v2 + v3 + v4 = 1/h.

Сформулируем задачу для решения симплекс-методом: v1 + v2 + v3 + v4  max;

v1 + 3v2 + 9v3 + 6v4 ≤ 1, 2v1 + 6v2 + 2v3 + 3v4 ≤ 1, 7v1 + 2v2 + 6v3 + 5v4 ≤ 1, vi ≥ 0, i = 1,2,3,4.

Решение имеет вид

v1 = 2/57, v2 = 17/171, v3 = 0, v4 = 1/9,

Z = 14/57,

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

39

H = 1/Z = 57/14.

Частоты выбора стратегий:

y1 = v1h = 2/57·57/14 = 1/7, y2 = v2h = 17/171·57/14 = 17/42,

y3 = v3h = 0,

y4 = v4h = 1/9·57/14 = 19/42.

Таким образом, оптимальная смешанная стратегия игрока В равна

(1/7, 17/42, 0, 19/42).

Варианты работы

В нижеприведенных вариантах строки соответствуют стратегиям игрока A, столбцы – стратегиям игрока B.

1

[[1 11 12 11] [7 5 7 7] [16 6 13 2] [9 9 16 13] [17 18 15 7]]

2

[[4 1 17 18] [4 14 6 16] [0 14 14 13] [6 13 4 15] [12 11 3 16]]

3

[[1 3 4 16] [11 3 7 18] [6 15 16 7] [15 10 0 7] [10 7 10 5]]

4

[[16 0 10 2] [3 6 3 3] [14 17 4 9] [4 0 16 11] [8 12 2 19]]

5

[[8 12 4 17] [1 6 19 19] [17 11 11 6] [8 10 15 17] [1 16 2 16]]

6

[[6 18 6 15] [17 8 13 14] [16 16 18 2] [18 8 4 18] [15 8 3 19]]

7

[[19 16 11 4] [6 18 1 5] [17 13 5 15] [9 13 3 19] [18 12 12 4]]

8

[[12 5 4 9] [16 0 12 0] [5 13 6 7] [10 10 3 16] [1 11 19 1]]

9

[[19 7 3 19] [6 9 18 10] [8 2 11 6] [2 0 9 19] [7 12 10 4]]

10

[[12 0 16 19] [6 5 19 12] [3 16 12 7] [17 0 18 2] [9 15 11 13]]

11

[[11 2 5 2] [11 11 3 10] [14 12 16 12] [16 10 19 17] [11 5 5 3]]

12

[[13 3 14 7] [15 5 0 9] [7 19 13 0] [0 5 19 13] [17 5 0 9]]

13

[[10 9 3 0] [11 7 0 15] [16 6 19 13] [15 17 15 10] [2 1 4 6]]

14

[[14 4 2 0] [5 6 5 6] [9 10 13 14] [1 18 11 1] [17 4 0 16]]

15

[[12 9 11 7] [15 4 18 12] [16 3 17 17] [1 15 0 19] [2 3 14 0]]

16

[[16 0 13 11] [17 3 19 15] [8 19 7 2] [15 8 15 16] [17 2 9 2]]

17

[[18 7 15 2] [0 13 16 3] [1 17 9 19] [3 15 17 9] [5 2 11 4]]

18

[[7 9 15 5] [15 8 6 4] [12 0 11 7] [7 11 10 12] [12 2 0 13]]

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности

40

19

[[4 18 5 3] [1 10 5 15] [8 6 15 15] [15 10 8 12] [19 12 1 0]]

20

[[5 1 13 9] [18 10 9 1] [9 0 14 14] [17 0 10 19] [11 3 11 14]]

21

[[15 9 3 15] [19 5 1 8] [9 14 5 18] [4 9 9 0] [12 9 14 0]]

22

[[13 2 4 0] [7 6 10 14] [8 14 6 3] [3 18 18 0] [8 7 11 14]]

23

[[7 7 15 5] [19 18 3 12] [1 5 16 19] [19 2 19 14] [8 6 4 18]]

24

[[5 11 12 17] [15 5 16 9] [11 8 0 19] [8 0 16 0] [13 9 7 16]]

25

[[15 4 16 12] [12 10 13 1] [7 18 19 1] [2 4 3 19] [3 15 19 12]]

26

[[14 2 19 17] [6 18 7 8] [6 17 14 6] [15 19 15 5] [11 8 12 4]]

27

[[12 7 18 5] [19 0 7 12] [10 1 3 6] [12 2 8 7] [4 12 14 17]]

28

[[12 7 16 0] [12 16 11 12] [17 11 1 1] [9 19 0 8] [3 3 12 13]]

29

[[6 3 18 15] [2 9 19 1] [2 7 13 3] [13 3 7 10] [3 8 0 8]]

30

[[12 8 13 13] [13 14 16 6] [7 5 11 18] [13 5 5 12] [10 16 14 4]]

Требования к отчету

Отчет должен содержать: титульный лист; цель работы; постановку задачи; решение матричной игры в смешанных стратегиях симплекс-методом за обоих игроков (прямая и двойственная задачи ЛП).

Контрольные вопросы

1.Определение матричной игры с нулевой суммой.

2.Верхняя и нижняя цена игры. Теорема о минимаксе.

3.Цена игры. Теорема о седловой точке.

4.Основная теорема прямоугольных игр.

5.Смешанные стратегии.

Басараб М.А., Вельц С.В. Методы оптимизации и исследование операций в информационной безопасности