А. Кофман и Р. Фор. Займемся исследованием операций (стр. 23 )

Как получить частоты x1, x2, x3, x4, x5, x6 и y1, y2, дающие оптимальные стратегии? Легко констатировать, что эти частоты и общий предел g должны удовлетворять следующим соотношениям:

Соотношения для полицейских	Соотношения для воров
x1 + x2 + x3 + x4 + x5 + x6 = 1 (сумма частот равна 1) 0,51x1 + 0,64x2 + 0,19x3 + 0,58x4 + + 0,37x5 + 0,46x6 ≥ g (полицейские хотят гарантировать себе по меньшей мере g, если воры приходят только в А) 0,75x1 + 0,36x2 + 0,91x3 + 0,60x4 + + 0,85x5 + 0,76x6 ≥ g (полицейские хотят гарантировать себе по меньшей мере g, если воры приходят только в В)	y1 + y2 = 1 0,51y1+0,75y2 ≤ g – полицейские в TT 0,64y1+0,36у2 ≤ g – полицейские в АА 0,19y1+0,91y2 ≤ g – полицейские в ВВ 0,58y1+0,60y2 ≤ g – полицейские в ТА 0,37y1+0,85y2 ≤ g – полицейские в ТВ 0,46y1+0,76y2 ≤ g – полицейские в AB
Все переменные заключены между 0 и 1, включая граничные точки.

Из-за большого числа переменных уравнения и неравенства для полицейских трудно разрешимы; зато неравенства для воров, которые содержат только две переменные, легко решить графическим методом (рис. 10.2). Подставим y2=1 – y1 во все неравенства стратегии воров, рассматривая их как уравнения.

Тогда

g = 0,75 - 0,24y1 - прямая (1)

g = 0,36 + 0,28y1 - прямая (2)

g = 0,91 - 0,72y1 - прямая (3) 0 ≤ y1 ≤ 1

g = 0,60 - 0,02y1 - прямая (4)

g = 0,85 - 0,48y1 - прямая (5)

g = 0,76 - 0,30y1 - прямая (6)

Начертим эти шесть прямых в системе координат gOy1, указанной на рисунке. Каждая точка заштрихованной области определяет возможное решение, ибо она удовлетворяет теперь всем рассмотренным неравенствам для воров. Из рисунка ясно, что наименьшая величина g находится на пересечении прямых (2) и (4), ибо прямая (4) имеет отрицательный наклон.

Имеем

0,36 + 0,28y1 = 0,60 - 0,02y1;

тогда

y1 = 0,8 и y2 = 0,2,

откуда

g = 0,584.

Таким образом, выбирая стратегию y1 = 0,8 , y2 = 0,2, воры имеют минимальную вероятность быть задержанными, равную 0,584.

Рис. 10.2

Для определения оптимальной стратегии полицейских нужно принять без доказательства[51] два основных факта теории стратегических игр двух лиц:

1)  существует единственное число g, которое является одновременно верхней границей выигрыша для воров и нижней - для полицейских.

2)  каждому неравенству для одной стороны, которое в оптимальном решении оказывается строгим неравенством, соответствует для противника переменная, равная нулю [так, в нашем примере неравенство (3) для воров становится строгим неравенством, и, значит, х3 должно равняться нулю].

Здесь оптимальное решение соответствует пересечению прямых (2) и (4); неравенства (2) и (4) для этого оптимального решения превращаются в равенства, что невозможно для четырех других неравенств; отсюда заключаем, что переменные х1, x3, х5 и х6 должны быть нулями.

Итак, имеем

0,64х2 + 0,58х4 = g =0,584,

0,36х2 + 0,60х4 = g = 0,584,

откуда

.

В итоге, если оба полицейских вместе проводят 1/15 своего времени вместе в A, а 14/15 времени один проводит в T, а другой в A, то вероятность захватить вора будет всегда равной 0,584, какую бы стратегию ни выбирали воры. Последние, выбирая стратегию «красть 4 раза из 5 в A и 1 раз из 5 в B», будут уверены, что вероятность их задержания не превзойдет 0,584, какую бы стратегию ни выбирали полицейские.

Можно подумать, что полицейские поставлены в менее благоприятные условия, чем воры; для первых вероятность, соответствующая их оптимальному выбору, в точности равна 0,584, тогда как для вторых вероятность быть задержанными при их оптимальном выборе будет меньше или равна 0,584; последнее связано с природой задачи, в которой полицейские имеют 6 стратегий, а воры только 2. В действительности полицейские не находятся в менее благоприятном положении, чем воры, но, поскольку воры имеют меньший выбор, полицейские могут оценить свой выигрыш более точно.

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

К счастью для воров и к несчастью для честных людей, обстоятельства не всегда достаточно благоприятствуют задержанию жуликов. Впрочем, существует неоспоримый закон, что чем крупнее кража, тем меньше шансов на то, что ее автор действительно попадет в тюрьму. Эти замечания объясняют то, что число воров и мошенников не слишком быстро стремится к нулю - как в Мехико, так и в Париже.

Один из наших друзей, которому мы показали эту задачу, утверждал (вот злое остроумие!), что если выведенные на сцену воры и полицейские были умны, то директор общества «Пронто» был не столь умен. Действительно, он обратил наше внимание на то, что это лицо вовсе не было заинтересовано в рентабельности службы наблюдения в своем магазине.

Таблица 10.3

	А	B
АА	0,64	0,36	х1
BB	0,19	0,91	х2
AВ	0,46	0,76	х3

Предположим, сказал он нам, что телевизионной камерой как средством исследования пренебрегают. Игровая таблица сократится тогда до таблицы 10.3.

Отсюда легко найти, что решение игры теперь дается пересечением прямых (2) и (6), и в этом случае

y1 = 0,69, y2 = 0,31, х1 = 0,53, х6 = 0,47 и g = 0,55.

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

На это мы ответили:

1)  что стремление проводить больше половины своего служебного времени сидя ничуть не противоречит характеру работы частного полицейского;

2)  что наличие телевизионной камеры могло бы оказать мощное психологическое воздействие на учеников воров, которые крепко призадумались бы, прежде чем решительно встать на избранный ими путь,

и что, следовательно,

a)  ничуть не удивительно, что наблюдатели не сочли нужным обратить внимание директора на слабую отдачу телевизионной установки и

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

Введение в теорию игр

Общая теория игр n лиц весьма сложна. Зато теория игр двух лиц или двух групп лиц, как в изложенном выше примере, вполне доступна. Мы попытаемся дать ее краткое изложение.

Таблица, в которую сведены правила игры, называется матрицей игры; она содержит выигрыши игрока A, называемого максимизирующим игроком (или проигрыши игрока B, называемого минимизирующим), если рассматриваемая игра является игрой с нулевой суммой, т. е. если выигрыши одного равны проигрышам другого[52] (табл. 10.4).

Таблица 10.4

	Игрок B
Игрок A		I	II	III
1	2	-1	1
2	-2	1	-1
3	-2	1	-2
4	2	-2	3

Допуская, что в каждой партии игры игрок A и игрок B должны одновременно выбрать чистую стратегию каждый, т. е. А — строку и B — столбец, имеем:

если A выбрал строку 2, а B выбрал столбец II, то A получит одну единицу;

если A выбрал строку 3, а B выбрал столбец III, то A получит - 2 единицы или вернет B 2 единицы и т. д.

Если бы речь шла только об одной партии этой игры, рассуждения[53] игроков A и B, согласно элементарному принципу фон Неймана, могли бы быть следующими.

Мой минимальный выигрыш для каждой чистой стратегии 1, 2, 3, 4 будет составлять соответственно

-1; -2; -2; -2;

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

Мой максимальный проигрыш для каждой из чистых стратегий I, II и III будет соответственно 2; 1; 3; я выбираю минимум среди своих максимальных проигрышей и, таким образом, принимаю чистую стратегию II, которая независимо от чистой стратегии моего противника гарантирует мне по крайней мере минимакс, равный 1. Иначе говоря, она дает мне возможность выиграть, не допуская проигрыша, большего чем 1.

Действительно, согласно этому рассуждению, в игре, состоящей из одной партии, игрок A потерял бы 1, а игрок B выиграл бы 1 в пределах риска, который они себе зафиксировали. Таким было бы поведение разумных и осторожных игроков. В самом деле, предположим, что игроки были бы только разумными. Игрок A мог бы сказать себе: B выберет столбец II; при этих условиях я буду выбирать стратегию 2 или 3, обе из которых гарантируют мне выигрыш 1. Но B мог бы тогда подумать: А будет наверняка играть стратегию 2 или 3; я выберу тогда стратегию 1, чтобы обеспечить себе выигрыш 2. И так далее... .

Очевидно, что выбор стратегий, отличных от стратегий, определяемых принципом фон Неймана, только увеличит риск каждого из игроков.

Представим себе теперь, что два игрока решили играть матч, т. е. серию последовательных партий. В некоторых случаях, как, например, в случае матрицы, изображенной в таблице 10.5, поиски максимина приводят игрока A к выбору чистой стратегии 2, откуда минимальный гарантированный выигрыш равен 1; поиски минимакса приводят игрока B к выбору чистой стратегии I, откуда минимальный гарантированный проигрыш равен 1. Здесь максимин и минимакс совпадают: они имеют в качестве своего значения один и тот же элемент матрицы, который называется седловой точкой и который обладает тем свойством, что является наименьшим элементом в своей строке и наибольшим элементом в своем столбце. Тогда, каким бы ни было число партий, выбираемые оптимальные стратегии останутся одними и теми же: А будет выбирать неизменно строку 2, а B - столбец I; в каждой партии A будет выигрывать единицу, а B - терять единицу. Речь здесь не идет об игре справедливой, ибо в каждой партии значение игры g = l соответствует выигрышу для A и проигрышу для В.

Таблица 10.5

		В
		I	II
А	1	-1	1
2	1	2
3	0	-1

Напротив, возвращаясь к таблице 10.4, мы констатируем, что седловой точки в ней не существует и рассуждения игроков в матче могли бы быть следующими.

Игрок А. Если мой противник выбирает столбцы I, II, III с частотами y1, y2, y3 и если я сам выбираю строки 1, 2, 3, 4 с частотами х1, х2, х3, х4, то математическое ожидание моего выигрыша будет

(2х1 – 2х2 – 2х3 +2х4) у1 + (-х1 + х2 + х3 – 2х4) у2 + (х1 - х2 - 2х3 + 3х4) у3.

Я желаю максимизировать эту величину.

Игрок В. В противоположность моему противнику я желаю минимизировать выражение, которое представляет математическое ожидание моего проигрыша:

(2y1 – y2 + y3) x1 + (-2y1 + y2 - y3) x2 + (-2y1 + y2 -2y3) x3 + (2y1 - 2y2 + 3y3) x4.

Предположим, что существует единое значение игры g (а это действительно так, как мы увидим из двойственности в линейном программировании). Тогда ясно, что, поскольку математическое ожидание для каждого из игроков должно быть оптимизировано независимо от принятой противником стратегии (в частности, если последний выбрал какую-нибудь чистую стратегию), мы придем к двум системам неравенств и уравнений:

I II

Мы приходим к задачам линейного программирования[54] - прямой слева и двойственной справа (или наоборот). К счастью, внимательное исследование позволит нам легко решить их.

Действительно, прежде всего складывая (а') и (b'), мы усматриваем, что значение игры не может быть меньше нуля.

Тогда, складывая (а) и удвоенное (b), получаем

и так как x4 ≥ 0, необходимо принять x4 = 0. Следовательно, неравенства (b) и (с) принимают вид

Отсюда после сложения получаем – x3 ≥ 0, что вместе с неравенством x3 ≥ 0 дает x3 = 0.

Окончательно имеем

откуда и g = 0.

Тогда смешанной оптимальной стратегией первого игрока будет

и при этом g = 0. Система II сводится тогда к системе

решения которой следующие:

Для двух крайних значений λ мы имеем соответственно

.

Это еще один случай, когда выбор кажется более легким для игрока B, но это только видимость; математическое ожидание его выигрыша имеет вид

.

Оно обращается в нуль, как только х3 и x4 не будут использоваться игроком A; таким образом,

.

Для фактической реализации смешанных оптимальных стратегий каждый игрок должен будет использовать таблицу случайных чисел, позволяющую ему учитывать вычисленные частоты, оставляя своего противника в неведении относительно последовательности своих ходов, или же, с тем же результатом, он должен будет положиться на рулетку[55].

Замечание 1. Система II сводится к двум эквивалентным уравнениям (а') и (b') и двум строгим неравенствам (c') и (d'); это соответствует сформулированному выше правилу, согласно которому x3 = x4 = 0.

Система I сокращается до трех уравнений, и мы видим, что у1, у2 и y3 отличны от нуля.

Замечание 2. Существование смешанной оптимальной стратегии - это содержание теоремы фон Неймана. Здесь мы находим понятие равновесия (единое значение игры), устойчивости и безопасности (невозможность для каждого из игроков отклониться от своих оптимальных стратегий без дальнейшего риска).

Глава 11. Один да один - один! Назидательная пьеса в двух актах, делающая хорошие сборы (Применение булевой алгебры)

Действие I

Сцена I

(Действие происходит на улице, где только что повстречались Пьер и Жан.)

Пьер. У меня есть потрясающая идея для нашей ярмарки!

Жан. Что за идея?

Пьер. Будем мастерить карманные радиоприемники и продавать их в нашем павильоне. Почти все парни увлекаются радио. Мы организуем маленькую мастерскую; в ней не будет рабочих, которым нужно платить, — достаточно будет только покупать отдельные детали и монтировать их.

Жан. Идея мне кажется хорошей, но есть ли у тебя схемы приемников?

Пьер. Как же, я тебе их завтра покажу.

Сцена II

(На следующий день у Жана.)

Пьер. Вот три типа схем. Я знаю цены транзисторов, деталей и корпусов. Все схемы реализуемы, но при некоторых условиях.

1°. Как ты видишь, для каждого приемника можно применить одну из трех серий транзисторов: T1, Т2 или Т3; эти серии различаются между собой, и в одном приемнике следует применять транзисторы только одной серии.

2°. Можно сделать деревянный корпус Е или купить готовый корпус Р из пластика; но если применить корпус Р, то его размеры не позволят применить серию транзисторов Т2, и так как для трансформатора F не остается места, можно применить только специальное питание А.

3°. Если выбрать серию T1, обязательно следует применить трансформатор F.

4°. Серии Т2 и Т3 требуют специального питания А.

Тебя интересуют цены транзисторов и отдельных деталей?

Вот они:

Серия транзисторов	Т1 28 франков	Специальное питание A 23 франка
>> >>	Т2 30 франков	Деревянный корпус E 9 франков
>> >>	Т3 31 франк	Корпус из пластика P 6 франков
Трансформатор	F 25 франков

Остальные детали (сопротивления, катушки, конденсаторы, крепеж, переключатели, потенциометры, шкалы настройки и т. п.), расчет по которым я тоже составил, будут одними и теми же для всех серий транзисторов. Правда, для серии T1 их нужно на 27 франков, при серии T2 — на 28 франков и при серии T3 — на 25 франков.

Мы сможем продавать наши приемники на 30% дешевле, чем в магазинах — я уже справлялся о ценах. Нам нужно будет установить цену приемника в деревянном корпусе в 110 франков, а в пластиковом — в 105 франков.

Мне сдается, что выбор решения о том, какую именно модель нам нужно производить, столь же сложен, как и схема монтажа. Что ты об этом думаешь? Можно было бы выбрать серию Т2, но в каком футляре — деревянном или пластиковом? А может быть, предпочтительнее будет серия T3?

Жан. Я предлагаю выбрать те транзисторы и футляры, которые принесут наибольшую прибыль.

Пьер. Совершенно с тобой согласен. Пойду займусь расчетами.

Действие II

Сцена I

(Еще через день у Пьера.)

Пьер. Я попытался вычислить себестоимость, как мы условились, но, увы, запутался во всех противоречивых условиях, о которых я тебе говорил.

Жан. Пойдем посоветуемся с моим братом Луи. Это великий математикус, он справится с любой задачей.

Сцена II

(Десять минут спустя у Жана.)

Луи. Друзья мои, ваша задача любопытна. Слышали вы о Джордже Буле?

Пьер и Жан. Кто это?

Луи. У него была очень интересная жизнь. Этот английский математик жил более ста лет тому назад. Ему пришла в голову идея выражать логические предложения в алгебраической форме. При этих условиях исследование справедливости или ложности некоторого множества предложений сводится благодаря алгебре Буля к ряду операций, впрочем, очень простых. Это страшно занятно, вы увидите!

Пьер и Жан. Мы тебя слушаем.

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

Луи. Пусть а и b — два элемента предложения, связанные соединительным союзом «и»; мы будем записывать это в виде а∙b. Предположим теперь, что два элемента связаны таким образом, что союз означает в действительности: «один или другой или оба вместе» (это латинское vel, которое можно было бы перевести как «и/или»). Мы запишем это как а+b; остерегайтесь смешивать это «и», означающее «и/или», с «или» исключительным («кошелек или жизнь»!).

Рассмотрим теперь предложение: «чтобы писать, нужна ручка или карандаш и лист бумаги».

Я применяю следующие обозначения:

иметь ручку	a	не иметь ручки
иметь карандаш	b	не иметь карандаша
иметь лист бумаги	c	не иметь листа бумаги
быть в состоянии писать	1	не быть в состоянии писать	0

Названную выше фразу можно представить как (а+b)∙с=1. Просто, не правда ли? Посудите сами: это даже точнее, чем наш язык! В русском[56] языке «или» исключительное и «или» не исключительное не различаются, и это очень досадно. Изменим слегка наше начальное предложение: «чтобы писать, нужно иметь в руке ручку или карандаш и лист бумаги перед собой». Здесь союз «или» уже будет исключительным (попробуйте писать пером и карандашом сразу!), и предложение будет записано в виде