Игра 2х2

Наиболее простым случаем конечной игры является игра 2x2, где у каждого игрока две стратегии. Рассмотрим игру с матрицей:

Здесь могут встретиться два случая:

1) игра имеет седловую точку;

2) игра не имеет седловой точки.

В первом случае решение очевидно: это — пара стратегий, пересекающихся в седловой точке. Нетрудно доказать, что если игра 2x2 имеет седловую точку, то в этой игре всегда какая-нибудь из стратегий может быть отброшена как заведомо невыгодная или дублирующая. Не будем этого доказывать. Предоставим читателю доказать это положение или убедиться в его справедливости на ряде произвольно выбранных примеров.

Рассмотрим второй случай: предположим, что в матрице 2x2 седловой точки нет. При этом нижняя цена игры не равна верхней:. Решение должно быть в смешанных стратегиях. Найдем это решение, т. е. пару оптимальных смешанных стратегий:

Сначала определим оптимальную смешанную стратегию.

Согласно теореме об активных стратегиях (см. § 5), если мы будем придерживаться этой стретегии, то, независимо от образа действий противника (если он только не выходит за пределы своих активных стратегий), выигрыш будет оставаться равным цене игры v. В игре 2x2 обе стратегии противника являются активными (иначе игра имела бы седловую точку). Значит, если мы придерживаемся своей оптимальной стратегии, то противник может, не меняя выигрыша, применять любую из своих чистых стратегий. Отсюда имеем два уравнения:

из которых, принимая во внимание условие получим:

Цену игры v найдем, подставляя значения в любое из уравнений (7.1):

Аналогично находится оптимальная стратегия противника:

из уравнений

(откуда

Пример 1. Найти решение игры «поиск» (см. пример 1 § 2). Решение. Игра 2 X 2 с матрицей не имеет седловой точки:

Ищем решение в смешанных стратегиях. По формулам (7.2), (7.3), (7.5) получаем:

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

Пример 2. Игра «Два бомбардировщика и истребитель».

Сторона А посылает в район расположения противника В два бомбардировщика I и II; I летит спереди, II — сзади. Один из бомбардировщиков (заранее неизвестно, какой) должен нести бомбу, другой выполняет только функцию сопровождения. В районе противника бомбардировщики подвергаются нападению истребителя стороны В (рис. 9.2). Оба бомбардировщика вооружены пушками. Если истребитель атакует задний бомбардировщик, то по нему ведут огонь пушки только этого бомбардировщика, поражающие истребитель с вероятностью 0,3. Если же истребитель атакует передний бомбардировщик, по нему ведут огонь пушки как переднего, так и заднего бомбардировщика; совместно они поражают его с вероятностью

Если истребитель не сбит ответным огнем бомбардировщиков, то он поражает выбранную им цель с вероятностью 0,8.

Задача бомбардировщиков — донести бомбу до цели; задача истребителя — воспрепятствовать этому.

Требуется найти оптимальные стратегии сторон:

— Для стороны А — какой бомбардировщик сделать носителем?

— Для стороны В — какой бомбардировщик атаковать?

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

1. — носитель l, атакуется 1.

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

2. — носитель II, атакуется I;

3. — носитель 1, атакуется II;

4. — носитель II, атакуется II;

Матрица игры с добавочным столбцом и строкой:

Нижняя — цена игры верхняя Игра не имеет седловой точки; решение достигается в смешанных стратегиях. По формулам (7.2), (7.3), (7.5) находим (с точностью до третьего знака после запятой):

(В данном случае, в силу того)

Рис. 9.2

Итак, оптимальные стратегии сторон и цена игры найдены:

т. е. наша оптимальная стратегия состоит в том, чтобы в 58,8% всех случаев (с вероятностью 0,588) делать носителем l, а в 41,2% случаев — II. Аналогично противник должен с вероятностью 0,588 атаковать первый бомбардировщик, а с вероятностью 0,412 — второй. При этом сторона А будет выполнять свою задачу — доносить бомбы до цели — с вероятностью 0,768, что больше нижней цены игры 0,608 и меньше верхней цены игры 1.

Решению игры 2X2 можно дать удобную геометрическую интер претацию Пусть имеется игра с матрицей:

Возьмем участок оси абсцисс длиной единица (рис. 9.3). Левый конец участка (точка с абсциссой будет изображать стратегию правый конец участка — стратегию все промежуточные точки участка будут изображать смешанные стратегии игрока А, причем вероятность стратегии будет равна расстоянию от точки до правого конца участка, а вероятность стратегии — расстоянию до левого конца. Проведем через точки два перпендикуляра к оси абсцисс: ось l — I и ось II — II. На оси l — I будем откладывать выигрыш при стратегии а на оси II — II — выигрыши при стратегии

Рис. 9.3

Рис. 9.4

Рис. 9.5

Пусть противник применяет стратегию она дает на осях I—I и II — II соответственно точки с ординатами Проведем через эти точки прямую BXBV Очевидно, при любой смешанной стратегии наш выигрыш выразится точкой М на прямой соответствующей точке на оси абсцисс, делящей отрезок в отношении Прямую условно будем называть «стратегией

Очевидно, точно таким же способом может быть построена и стратегия (рис. 9.4).

Нам нужно найти оптимальную стратегию т. е. такую, при которой наш минимальный выигрыш (при наихудшем для нас поведении В) обращался бы в максимум.

Для этого построим нижнюю границу выигрыша при стратегиях т. е. ломаную, отмеченную на рис. 9.4 жирной линией. На этой границе будет лежать минимальный выигрыш игрока А при любой его смешанной стратегии; точка в которой этот выигрыш достигает максимума, и определяет решение и цену игры. Нетрудно убедиться, что ордината точки есть не что иное, как цена игры v, ее абсцисса равна а расстояние до правого конца отрезка равно, т. е. расстояния от точки ДО концов отрезка равны вероятностям, стратегий и А в оптимальной смешанной стратегии игрока А.

В нашем случае решение игры определялось точкой пересечения стратегий это не всегда будет так. На рис. 9.5 показан случай, когда оптимальной стратегией игрока А является чистая стратегия хотя это и не соответствует точке пересечения стратегий.

Рис. 9.6

Рис. 9.7

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

Геометрическая интерпретация дает возможность наглядно изобразить также нижнюю цену игры а и верхнюю (рис. 9.7). На том же графике можно дать и геометрическую интерпретацию оптимальных стратегий противника В. Действительно, нетрудно убедиться, что доля стратегии в оптимальной смешанной стратегии

равна отношению длины отрезка к сумме длин отрезков и КВХ на оси l — I:

или, что то же,

на оси II — II.

Оптимальную стратегию можно найти и другим, непосредственным способом, если поменять местами игроков А и В, а ьместо максимума нижней границы выигрыша рассмотреть минимум верхней границы (рис. 9.8).

Рис. 9.8

Рис. 9.9

На рис. 9.9 дана геометрическая интерпретация решения игры «два бомбардировщика и истребитель» (пример 2).

МЕТОД СЕТЕВОГО ПЛАНИРОВАНИЯ

ЗАДАЧА ПЛАНИРОВАНИЯ КОМПЛЕКСА РАБОТ

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

Примерами таких работ могут быть:

— строительство большого промышленного объекта,

— перевооружение армии или отдельных видов вооруженных сил,

— развертывание системы медицинских или профилактических мероприятий,

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

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

Планирование любого такого комплекса работ должно производиться с учетом следующих существенных элементов:

— времени, потребного на выполнение всего комплекса работ и его отдельных звеньев;

— стоимости всего комплекса работ и его отдельных звеньев;

— сырьевых, энергетических и людских ресурсов.

Рациональное планирование комплекса работ требует, в частности, ответа на следующие вопросы:

— Как распределить имеющиеся материальные средства и трудовые ресурсы между звеньями комплекса?

— В какие моменты начинать и когда заканчивать отдельные звенья?

— Какие могут возникнуть препятствия к своевременному завершению комплекса работ и как их устранять? и т. д.

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

Одним из математических методов, широко применяемых при решении такого рода задач, является метод сетевого планирования или, как его часто называют, СПУ (сетевое планирование управления).

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

Обратные задачи, как правило, гораздо сложнее прямых. Чтобы решать обратные задачи, нужно прежде всего научиться решать прямые. Естественно, с такого рода задач мы и начнем.

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

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

Таблица 1.1

Таблица 1.2

Таблица 1.3

Пример структурной таблицы комплекса работ дан в табл. 1.1.

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

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

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

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

Для примера произведем упорядочение работ, помещенных в табл. 1.1 (см. табл. 1.2). В двух первых столбцах табл. 1.2 приведены: номер и обозначения работы в прежней нумерации, в двух последних — ранг работы и ее новое обозначение в упорядоченной структурной таблице.

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

Нетрудно видеть, что в новой, упорядоченной структурной табл. 1.3 каждая из работ опирается только на работы с меньшими порядковыми номерами.

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