Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 159


Доказано, что такой метод сходится: при увеличении числа «партий» средний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий — к их вероятностям в оптимальных смешанных стратегиях игроков.

Впрочем, лучше всего можно понять итерационный метод на конкретном примере. Продемонстрируем его на примере игры 3×3 предыдущего параграфа (таблица 26.5). Чтобы не иметь дела с отрицательными числами, прибавим к элементам матрицы таблицы 26.5 число 5 (см. таблицу 27.6); при этом цена игры увеличится на 5, а решение

 не изменится.

Начнем с произвольно выбранной стратегии игрока А, —

например, со стратегии А3. В таблице 27.7 приведены первые 15 шагов итерационного процесса по методу Брауна — Робинсон (читатель может самостоятельно продолжить расчеты).

Таблица 27.6

 

 

 

 

             Bj

 

Ai

 

B1

 

B2

 

B3

A1

A2

A3

7

2

9

2

9

0

9

0

11

 

В первом столбце дан номер партии (пары выборов) k, во втором — номер i выбранной в данной партии стратегии игрока А. В последующих трех столбцах — «накопленный выигрыш» за первые k партий при тех стратегиях, которые применяли игроки в предыдущих партиях и при стратегиях В1, В2, B3 игрока В

в данной партии (получается прибавлением элементов соответствующей строки к тому, что было строкой выше). Из этих накопленных

выигрышей в таблице 27.7 подчеркнут минимальный (если их несколько,  подчеркиваются все). Подчеркнутое число определяет ответный выбор игрока В в данной партии — он выбирает ту стратегию, которая соответствует подчеркнутому числу (если их несколько, берется любая). Таким образом определяется номер j оптимальной (в данной партии) стратегии В (ставится в следующем столбце). В последующих

Таблица 27.7

k

i

B1

B2

B3

j

A1

A2

A3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

3

2

2

2

1

3

1

2

2

1

3

2

2

1

3

9

11

13

15

22

31

38

40

42

49

58

60

62

69

78

0

9

18

27

29

29

31

40

49

51

51

60

69

71

71

11

11

11

11

20

31

40

40

40

49

60

60

60

69

80

2

2

3

3

3

2

2

2

3

1

2

2

3

1

2

2

4

13

22

31

33

35

37

46

53

55

57

66

73

75

9

18

18

18

18

27

36

45

45

47

56

65

65

67

76

0

0

11

2

33

33

33

33

44

53

53

53

64

73

73

0

4,5

3,67

2,75

4,00

4,84

4,43

5,00

4,45

4,90

4,64

5,00

4,61

4,93

4,74

9

9

6

5,50

6,60

5,50

5,14

5,61

5,11

5,30

5,09

5,41

5,07

5,21

5,06

4,5

6,75

4,84

4,13

5,30

5,17

4,79

5,30

4,78

5,10

4,87

5,20

4,84

5,07

4,90

<


Начало  Назад  Вперед



Книжный магазин