9.5. Задачи теории графов и игр

Граф – универсальное средство наглядного представления достаточно разнообразных задач экономических, технических и организационных систем. Разнообразие сочетания различных ребер и вершин представляют многообразие возможных графов и их применение.

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

Типичным представителем графического метода решения управленческих задач являются рассмотренные ранее сетевые методы проектирования, планирования и оптимизации (главы 10, 11, ч. 4).

Другим известным представителем графического подхода к решению задач является блок-схема.

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

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

Весьма близкой по смысловой нагрузке является теория графов сигналов.

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

Современное применение этих графов основано на пионерских работах Мэзона /30 /. Граф сигналов есть топологический способ записи системы уравнений. Основой построения сигнального графа являются узлы переменных, которые строят первыми, а затем изображают передачи согласно следующим правилам:

• сигнал течет по ветви в направлении стрелки;

• сигнал, протекающий по ветви, умножается на передачу ветви;

• значение переменной в узле равно сумме всех сигналов, входящих в узел;

• значение переменной в узле поступает в каждую ветвь, выходящую из узла;

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

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

С помощью теории графов решают различные задачи. С некоторыми мы уже познакомились в части четвертой, когда рассматривали решения задач с помощью «дерева целей». Другие можно решать на базе марковских процессов, сущность которых заключается в последовательности состояний или событий, в которой исход зависит только от текущего состояния, но не от предшествующей истории процесса. Этим способом можно решать некоторые задачи антикризисного управления, проблемы развития инновационных процессов, а также производить выбор эффективного варианта принятия решения на базе затрат и вероятности благоприятного исхода /30/.

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

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

Теорию игр можно определить как теорию математических моделей принятия решений в условиях конфликта.

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

• анализ конфликтных ситуаций в военных и экономических областях (простым экономическим примером конфликтной ситуации, для описания которой применяется теория игр, является конкурентная борьба торговых фирм или промышленных предприятий);

• конкурентная борьба торговых фирм или промышленных предприятий);

• обменные и торговые операции;

• анализ и проектирование иерархических структур управления и экономических механизмов (например, анализ различных моделей стимулирования);

• анализ целесообразности права первого хода, взаимной информированности, возможности блефовать;

• анализ коалиционного поведения;

• ряд других задач.

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

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

Система условий, регламентирующая возможные варианты действий сторон, объем информации каждой стороны о поведении другой, а также результат, к которому приводит данная совокуп­ность действий, составляют правила игры. Здесь уместно обратить внимание на то, что крайний экстремизм: «Нарушать любое правило» становится правилом.

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

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

Так как цели противоположны, а результат мероприятия каждой из сторон зависит от действий конкурента, то эти действия называют конфликтными ситуациями.

В конфликтной ситуации сталкиваются противоположные интересы двух участников. Формализованная (схематизированная) модель конфликтной ситуации называется игрой. Результат игры – победа (успех) или поражение (неудача), которые не всегда имеют количественное выражение, можно выразить условно числами (например, в шахматах: 1,0, 1/2).

Игра называется игрой с нулевой суммой, если один из игроков выигрывает ровно столько, сколько проигрывает другой.

Развитие игры во времени представляется как ряд последовательных «ходов». Ходы могут быть сознательные и случайные. Случайный ход – это результат, получаемый не решением игрока, а каким-либо механизмом случайного выбора (покупательским спросом, задержкой с поставкой материалов и т.п.). Сознательный ход - выбор игроком одного из возможных вариантов действия (стратегии) и принятие решения о его осуществлении /30/.

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

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

Здесь первая сторона принимает решение, а вторая сторона – «природа» – не оказывает первой сознательного агрессивного противодействия, но ее реальное поведение неизвестно.

Риск r_ij при пользовании стратегией С_i и состоянии «природы» П_j оценивается разностью между максимально возможным выигрышем при данном состоянии природы В_i^max и выигрышем B_ij при выбранной стратегии С_i:

. (6.26)

Исходя из этого определения, можно оценивать максимальный риск каждого решения:

. (6.27)

Решения могут приниматься по результатам анализа ряда критериев.

1. Критерий, основанный на известных вероятностных состояниях «природы» (например, спроса, по данным анализа за прошлые годы):

• если известны вероятности состояний «природы» P_i = P(П_i), тогда в качестве показателя эффективности (рациональности, обоснованности) стратегии C_i берется среднее (математическое ожидание) – выигрыш применения этой стратегии:

, (6.28)

а оптимально считают стратегию, для которой этот показатель эффективности имеет максимальное значение, т.е.

. (6.29)

• если каждому решению С_i соответствует множество возможных результатов B_ij с вероятностями P_ij, а среднее значение выигрыша определится по (21), то в этом случае можно использовать стратегию минимального риска для каждого i-го состояния «природы»

. (6.30)

2. Максимальный критерий Вальда. Здесь выбирается решение (в нашем случае торгового предприятия), при котором гарантируется максимальный выигрыш в наихудших условиях внешней среды (состояния «природы»):

. (6.31)

3. Критерий пессимизма Гурвича (Гурвица). Здесь выбирается некий компромиссный вариант между двумя крайностями с учетом как наихудшего, так и наилудшего поведения «природы». При этом для каждого решения будет линейная комбинация минимального и максимального выигрышей и выбирается тот, для которого эта величина окажется наибольшей:

, (6.32)

где x – показатель «пессимизма – оптимизма» (чаще всего принимается равным 0,5).

4. Критерий максимального риска Сэвиджа. Здесь предлагается применять минимаксный критерий не к исходной платежной матрице, а к новой матрице, которую многие (но не сам Сэвидж) называют матрицей "сожаления". Элементы матрицы "сожаления" получаются из элементов платежной матрицы максимального элемента того же столбца. В этом случае выбирают ту стратегию, при которой величина риска имеет минимальное значение в самой неблагоприятной ситуации

(6.33)

чтобы избежать слишком большого риска при выборе решения.

Итак, нами рассмотрены четыре подхода с выбором соответствующих критериев, результаты решения по которым, естественно будут различными. Справедливо возникает вопрос: какая альтернатива действительно лучшая? Должны ли мы поступить демократически и принять компромиссное ранжирование альтернатив?

Из этой проблемы есть два выхода. Первый – разработка критериев, или требований, для выбора критерия решения. Второй – использование любых возможных обрывков информации о вероятностях появления различных состояний природы или проведение экспериментов для получения оценок этих возможностей. Однако вывод крупнейших специалистов в этой области неутешителен: «Не существует критерия решения, не использующего вероятностных оценок для состояния природы и вместе с тем удовлетворяющего определенным «разумным» требованиям к «хорошему критерию» /30/. Поэтому использование знаний индивида о вероятностях состояния «природы» или получение новых знаний посредством эксперимента является лучшим выходом.

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

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