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


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


Это делается подобно тому, как мы когда-то отбрасывали заведомо невыгодные решения в § 6. Введем понятие «доминирования». Стратегия Ai игрока А

называется доминирующей над стратегией Аk, если в строке Ai стоят выигрыши не меньшие, чем в соответствующих клетках строки Ak, и из них по крайней мере один действительно больше, чем в соответствующей клетке строки Аk. Если все выигрыши строки Ai, равны соответствующим выигрышам строки Ak, то стратегия Аi называется дублирующей стратегию Ak. Аналогично определяются доминирование и дублирование для стратегий игрока В:

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

Поясним сказанное примером. Пусть игра 5×5 задана матрицей таблицы 27.1.

Таблица 27.1

 

 

 

             Bj

 

Ai

 

B1

 

B2

 

B3

 

B4

 

B5

A1

A2

A3

A4

A5

4

3

4

3

3

7

5

4

6

5

2

6

2

1

6

3

8

2

2

8

4

9

8

4

9

Прежде всего заметим, что в ней стратегия A5 дублирует стратегию А2, поэтому любую из них можно отбросить. Отбрасывая A5, замечаем, что в строке А1 все выигрыши больше (или равны) соответствующим выигрышам строки А4

значит А1 доминирует над A4. Отбросим A4 и получим матрицу 3×5 (таблица 27.2).

Но это еще не все! Приглядевшись к таблице 27.2, замечаем, что в ней некоторые стратегии игрока В доминируют над другими: например, B3 над B4, и В5,

a B1 — над стратегией В2 (не забудьте, что В стремится отдать поменьше!).

Таблица 27.2

             Bj

 

Ai

 

B1

 

B2

 

B3

 

B4

 

B5

A1

A2

A3

4

3

4

7

5

4

2

6

2

3

8

2

4

9

8

<


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



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