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


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


он, назло нам, выберет стратегию В3,

и мы получим какой-то жалкий выигрыш «1». Нет, выбирать стратегию А3 нельзя! Как же быть? Очевидно, исходя из принципа осторожности (а он — основной принцип теории игр), надо выбрать

Таблица 26.2

             Bj

 

Ai

 

B1

 

B2

 

B3

 

B4

 

B5

A1

A2

A3

A4

3

1

10

4

4

8

3

5

5

4

1

3

2

3

7

4

3

4

6

8

 

ту стратегию, при которой наш минимальный выигрыш максимален.

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

Перепишем таблицу 26.2 и в правом добавочном столбце запишем минимальное значение выигрыша в каждой строке, (минимум строки); обозначим его для i-й строки ?i (см. таблицу 26.3).

Таблица 26.3

 

 

 

 

            Bj

 

Ai

 

B1

 

B2

 

B3

 

B4

 

B5

 

?i

A1

A2

A3

A4

3

1

10

4

4

8

3

5

5

4

1

3

2

3

7

4

3

4

6

8

2

1

1

3

?j

10

8

5

7

8

 

Из всех значений ?i (правый столбец) выделено наибольшее (3). Ему соответствует стратегия A4. Выбрав эту стратегию, мы, во всяком случае, можем быть уверены, что (при любом поведении противника) выиграем не меньше, чем 3. Эта величина — наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем (я, может быть, получим и больше). Этот выигрыш называется нижней ценой игры (или «максимином» — максимальный из минимальных выигрышей). Будем обозначать его а. В нашем случае ? = 3.

Теперь станем на точку зрения противника и порассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию В1, мы ему ответим А3, и он отдаст 10; если выберет B2 — мы ему ответим А2, и он отдаст 8 и т. д. Припишем к таблице 26.3 добавочную нижнюю строку и в ней запишем максимумы столбцов ?j.


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



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