Вероятностные методы оптимизации

Рассмотренные выше постановки предполагали детерминированный характер исследуемых процессов. Они описывают первую степень неопределенности СЭС (см. параграф 5.2). В связи с этим заслуживает особого интереса вероятностная постановка задач принятия решений, которая реализуется, например, с помощью:

• • технологии минимизации риска;
• • формализмов теории игр.

Пусть имеется двумерная матрица стоимости (табл. 5.9) использования j-го управляющего воздействия на объект i-го типа.

В табл. 5.9 число aij указывает величину выигрыша от управления объекта типа xi воздействием уi.

Таблица 5.9

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

(5.49).

т.е. с некоторой вероятностью объект может принадлежать каждому из выделенных типов объектов. Здесь? i — вероятности принадлежности данного объекта типу xi. Постановка задачи соответствует второй степени сложности исследуемого СЭС. Если сложность СЭС еще выше (нет априорной информации о законе распределения или статистических данных для его расчета), то схема принятия решения (5.49) отражает субъективную вероятность и (или) функцию принадлежности нечеткого множества.

Если перемножить вектор-строку (?1, ?2, …, ?n) и вектор-столбец (a1, a2, …, an) по правилам перемножения векторов, то получим.

(5.50).

Это суммарная стоимость выигрыша от использования7-го управляющего воздействия. Сравнение между собой позволяет выбрать наиболее предпочтительное решение.

Задача 5.16. Имеется возможность купить четыре типа ценных бумаг (валют): у1, у2, у3, у4. Экономическая ситуация в регионе классифицируется следующим образом: x1 — благоприятное развитие экономики региона, х2 — инерционное, х3 — пессимистическое. Матрица стоимостей R, отражающая выигрыши ценных бумаг yi, в каждой из выделенных ситуаций представлена в табл. 5.10.

Таблица 5.10

Матрица стоимостей вариантов управления (выбора ценных бумаг)

Рассмотрим описанную процедуру выбора вида ценных бумаг для двух ситуаций: А1 = (0,2; 0,5; 0,3), где 0,2; 0,5; 0,3 — соответственно вероятности принадлежности экономической ситуации А1 к сценариям развития «благоприятному», «инерционному» и «пессимистическому», и А2= (0,6; 0,3; 0,1). Согласно вышеописанному.

B = R•A. (5.51).

Откуда для А = А1, и А = А2 легко найти B1 = (0,16; 0,39; 0,36; 0,9) и В2= (0,12; 0,29; 0,44; 0,15). Очевидно (из сравнения Вj), что наибольший выигрыш (т.е. минимальный риск) достигается при покупке второго типа ценных бумаг в ситуации А1 и бумаг третьего типа в ситуации А2.

Рассмотрим далее вероятностные методы принятия решений на примере моделей теории игр (ТИ).

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

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

Рассмотрим характерные примеры теории игр.

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

Описать данный «конфликт» между государством и предприятием можно с помощью понятий ТИ, определив возможные стратегии поведения дотирующей и дотационной сторон.

Отрасль может рассматривать следующие варианты решений: A1 — дотация предприятия в объеме средств, обеспечивающих эффективное выполнение производственных функций; А2 — дотация в объеме, обеспечивающем выживание в определенном периоде времени; А3 — закрытие предприятия.

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

Таблица 5.11

Платежная матрица игровой стратегии принятия решений

Таблица задает каждой паре ходов указанных сторон платежную матрицу {сij}. В общем случае таких матриц должно быть две: одна — для отрасли, другая — для предприятия. Коэффициенты сij могут отражать «выигрыш» или «проигрыш» соответствующей стороны в ситуации, когда предприятие принимает i-е решение, а отрасль — j-e. Эффективность использования дотаций и характер развития дотационной фирмы зависят от условий, заложенных в этой матрице. Так, предприятие должно учитывать упущенную выгоду и получаемые дотации в варианте 1. А в варианте 2 учитываются недополученные инвестиции и доход от рыночной деятельности.

Пример 5.2. В условиях ограниченного ресурса (финансового, кадрового, временно? го и др.) развития организации интересы различных субъектов организационно-экономических отношений могут нс совпадать. Это относится к различным подразделениям внутри организации (службы организации, отвечающие соответственно за техническое состояние и технологический процесс); различным уровням управления; разнородным сферам деятельности (профсоюз и администрация). Характер этих отношений может варьировать от конструктивного сотрудничества (коалиции интересов) до непримиримо враждебных. Исключение субъективизма на основе формализованного описания — важнейшая задача эффективного управления организацией.

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

Пример 5.3. Для выполнения ответственного задания принимается сотрудник. Он проходит за счет фирмы обучение, получает высокую зарплату и в результате может оправдать или не оправдать ожидания, может просто уволиться. Руководство в последнем случае теряет средства и время. Как регламентировать отношения работника и администрации фирмы? Что должно быть прописано в контракте, чтобы поведение обеих сторон было прогнозируемым и взаимно удовлетворительным?

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

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

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

Рассмотренная в каждом случае ситуация взаимодействия сторон называется игрой. Стороны, участвующие в игре, называются игроками, а возможные варианты решений игроков — стратегиями.

Рассмотрим и проанализируем задачу.

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

Положим, что экспертов два: представитель отдела информатизации (И) и работник отдела маркетинга (М), обеспечивающий продвижение продукции организации. Возможных рассматриваемых решений тоже два: А1 — осуществить обновление системы информационного обеспечения предприятия, A2 — потратить имеющиеся средства на совершенствование маркетинговой стратегии организации. Очевидно, что «выигрыши» заинтересованных сторон в рассматриваемом случае не одинаковы. Представим выигрыши участников в виде табл. 5.12 и 5.13.

Таблица 5.12

Соотношение размеров выигрыша представителя И в зависимости от принимаемых экспертами решений

Таблица 5.13

Соотношение размеров выигрыша представителя М в зависимости от принимаемых экспертами решений

Прокомментируем содержание таблиц. Если оба эксперта выскажутся в пользу информатизации станции, то выигрыш отдела информатизации, согласно табл. 5.12, составляет 10 условных единиц (у.е.), а выигрыш технологов равен 5 у.е. (см. табл. 5.13). Если эксперты одновременно поддержат проект A2, то выигрыш специалистов по информатизации равен лишь 2 у.е. (см. табл. 5.12), а выигрыш технологов — 8 у.е. (см. табл. 5.13). Если эксперты не придут к согласованным решениям, то ни одно из усовершенствований не проходит и выигрыши равны нулю.

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

В данной задаче множества допустимых стратегий игроков совпали. Это набор решений (A1, A2). В общем случае игроки имеют различные множества стратегий, как по сущности принимаемых решений, так и по их количеству. Так, в игре «руководителя» и «подчиненного» стратегиями первого могут быть: повышение работника в должности, материальное поощрение, штраф, меры морального стимулирования; второй игрок, например, может выполнить или не выполнить поручение.

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

Множество всех ситуаций является декартовым произведением:

Каждому игроку присваивается для всех возможных значений X соответствующий выигрыш: Н (Х).

В теории существует множество классификаций игр. Рассмотрим некоторые из них.

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

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

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

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

Рассмотрим подробнее формализованный процесс матричной игры с нулевой суммой.

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

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

• 1. Формулирование и формализация условий игры: определение участников, выбор классификационных признаков, обоснование стратегий поведения сторон. Решение этой задачи обеспечивается руководством, технологами, экономистами, математиками.
• 2. Расчет функции выигрыша H (Х). Данная процедура реализуется одним из способов:
  • • на основе установленных нормативных данных о потерях и выигрышах сторон при тех или иных комбинациях ситуаций (детерминированный подход);
  • • статистически, на основе анализа предшествующего опыта работы (применим в стационарных условиях функционирования);
  • • на базе экспертных процедур: статистики нет, но у экспертов достаточно опыта и интуиции для адекватного моделирования ситуаций;
  • • на основе обучающих процедур. Функция выигрыша Н (Х) корректируется в этом случае в процессе работы системы принятия решений. Коррекция может осуществляться по любому из вышеназванных планов;
  • • комбинированным способом.
• 3. Разработка алгоритмов расчета оптимального поведения игроков.
• 4. Внедрение методологи теории игр в практику исследования и управления СЭС.

В теоретическом и практическом плане наиболее хорошо разработаны (и одновременно понятны) прямоугольные игры. В их основе лежит прямоугольная матрица чисел, отражающая платежи одного из игроков. Рассуждения далее будем вести относительно матрицы платежей первого игрока. Игроки одновременно и независимо друг от друга выбирают номер своего хода. Для первого игрока он соответствует номеру строки, для второго — номеру столбца. Практически любую задачу выбора из множества альтернатив можно представить моделью ТИ. Однако некоторые из них тривиальны и не требуют развития специального математического аппарата. Пример такой игры приведен ниже (табл. 5.14).

Таблица 5.14

Матрица платежей первого игрока

Из данных таблицы можно заключить, что первый игрок имеет только два варианта ходов (стратегий), второй — три. При выборе первым игроком первой стратегии, а вторым — второй первый игрок от второго получает выигрыш, равный 2 ед. При выборе соответственно второй и третьей стратегий «выигрыш» первого составит -5 ед., т. е. в действительности он проигрывает оппоненту 5 единиц.

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

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

Таблица 5.15

Матрица платежей первого игрока

В этом случае ситуация не столь однозначна, как в первоначальном случае.

Рассмотрим игру, заданную соотношением (5.52). Для удобства здесь и далее указана только платежная матрица.

(5.52).

Очевидно, что в данном случае свойство, наблюдаемое в первой игре, отсутствует. Будем считать, что разумность поведения игроков заключается в следующем.

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

(5.53).

Ему выгодно, чтобы выражение (5.53) было как можно больше, т. е. он выбирает такой ход iопт, который обеспечивает максимум (5.53). Иначе.

(5.54).

В нашем примере при выборе первым игроком первого хода (5.54) имеет значение, равное 10, а при выборе второй стратегии он получает выигрыш по (5.54), равный 2. Максимальное из этих чисел 10, а соответствующий ему iопт = 1.

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

При выборе им произвольного i-го столбца, он получает «выигрыш» не менее чем.

(5.55).

Его желание — «получить» .

(5.56).

То есть он выбирает столбец.

(5.57).

Это означает, что он может допустить вознаграждение первого в размере не более чем.

(5.58).

Итак, первый игрок, обеспечивая себе величину.

(5.59).

и при правильной игре второго не получит более чем (5.58).

Если вдруг окажется, что (5.58) равно (5.59), то исход игры понятен: игроки, не рассчитывая на явные ошибки противников, должны выбирать соответственно (5.54) и (5.57).

В нашем примере (матрица (5.52)) легко найти, что, действительно,

То есть и первый, и второй игроки выбирают свои первые ходы.

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

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

Очевидно, что прямоугольная игра с матрицей.

(5.60).

таким свойством не обладает. В этом можно убедиться проверкой элементов матрицы.

Если первый игрок изберет первую стратегию, то при выборе вторым также первой стратегии выигрыш первого составит лишь 1 ед., т. е. минимум возможного, тогда как при иной стратегии второго игрока выигрыш будет равен 3 ед., что не так уж плохо. Если первый игрок выберет вторую стратегию, то он может получить или 4, или 2 ед. выигрыша, выигрывая в первом, но проигрывая во втором случае. Очевидно, что в данном примере первому игроку бессмысленно выбирать фиксированную стратегию, так как у второго всегда есть «противоядие», сводящее на «нет» желание игрока увеличить свою прибыль.

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

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

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

В данной игре можно говорить о среднем выигрыше первого игрока, равном.

(5.61).

так как выигрыш, равный 1 ед., появляется с вероятностью ху, а выигрыш в 3 ед. — с вероятностью x(1 — у) и т. д. Выражение (5.61) легко представить в виде.

(5.62).

из чего следует, что первый игрок при независимо от поведения второго обеспечивает себе средний выигрыш, равный . В то же время второй игрок, избирая , не допускает выигрыш первого больше, чем . Заметьте, он больше, чем 1 или 2, хотя и меньше, чем 3 или 4. То есть смешанные стратегии игроков и представляют собой некоторый компромисс заданной игры. Если один из них будет знать очередную чистую стратегию противника, то он может достичь результата лучшего (для себя), чем это дает рассчитанная смешанная стратегия. Обобщим полученные результаты для прямоугольной игры игроков Р1 и Р2 размерности т? п, заданной матрицей.

(5.63).

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

(5.64).

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

Аналогично, смешанной стратегией для игрока Р2, будет набор чисел yj, j = 1, п, для которого.

(5.65).

Математическое ожидание выигрыша игрока Р1 определяется формулой.

(5.66).

Оптимальными смешанными стратегиями называются вектора и при которых

(5.67).

Условие (5.67) гарантирует игроку Р1 при выборе х0 выигрыш, не меньший независимо от того, как будет играть Р2. Аналогично, смешанная стратегия у0 гарантирует Р2 возможность не дать Р1 выигрыш, больший

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

Пусть игра задана матрицей.

(5.68).

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

Введем систему координат x0z, где частотах удовлетворяется условию 0 < х < 1, а г обозначает величину выигрыша (рис. 5.9).

Рис. 5.9. Графическое решение игры 2?3, заданной матрицей (5.68).

Если второй игрок примет чистую стратегию 1, то выигрыш первого будет составлять.

На графике ему соответствует прямая 1. При выборе вторым игроком чистой стратегии 2 выигрыш первого составит.

(прямая 2). И наконец, при третьей чистой стратегии второго первый имеет.

(прямая 3).

При каждом выборе игроком Р{ стратегии х он может быть уверенным в получении минимальной ординаты z (из трех заданных). Поэтому первому игроку целесообразно рассматривать части построенных прямых, выделенных жирной линией. Наибольший выигрыш, как это следует из рисунка, соответствует ординате точки А. Оптимальная стратегия определяется абсциссой этой точки. Координату точки А найдем как пересечение прямых 2 и 3, т. е. из решения системы.

Откуда следует: х = 0,25, z = 2,75. Таким образом, оптимальная стратегия первого игрока (0,25; 0,75) гарантирует ему средний выигрыш 2,75 ед.

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

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

Задача 5.18. Предполагается реструктуризация двух предприятий, осуществляющих однотипную работу и допускающих перераспределение нагрузки между собой. Суммарная производственная мощность фиксирована и определяется потребностями заданного региона. Обозначим ее за 1, обозначим также производственную мощность первого предприятия через у (доля от суммарной мощности), тогда второе предприятие будет характеризоваться величиной (1 — у). Если окажется, что выделенные производственные нагрузки на первом предприятии x и соответственно (1 — x) на втором, то напряженность их работы будет для первого х/у и соответственно для второго . Цель распределения производственных мощностей может быть принята следующей: минимизировать максимальное из выражений х/у и . В формальном виде.

(5.69).

Таким образом, поставленная задача является игрой с «природой», которая задает значение х. Второй игрок — представитель отрасли, устанавливающий и реализующий на предприятиях мощность у (соответственно на второй: (1 — у)).

Если бы ход «природы», т. е. значение х было известно заранее, то задача была бы тривиальной. Достаточно взять у = х, и тогда на обоих предприятиях min Н (х, у) = 1. Что означает, с одной стороны, полную загрузку предприятия и с другой — отсутствие перегрузки. Очевидно, что «природа» будет случайным образом распределять х с течением времени. Предположим, что эксперты могут оценить нижнюю а и верхнюю b границы этого диапазона. То есть.

(5.70).

Нет сомнения в том, что в этих условиях и у должен изменяться в промежутке [a; b]. Действительно: задавая у < a, мы заведомо занижаем мощность предприятия. В этом случае у него всегда будут проблемы с недостатком мощностей. При у > b на этом предприятии будет излишек мощности. Недогрузка предприятия вызовет проблемы нехватки мощности на втором предприятии. Таким образом, наша игра осуществляется на квадрате [a, b]? [a, b]. Переменные х и у при этом могут меняться непрерывно. Разность (b — a) характеризует, с одной стороны, степень неопределенности информации о работе исследуемого комплекса и стабильность его работы — с другой. В первом случае можно рекомендовать приобретение информации и сужение сегмента [а, b]. Это ограничивает возможности противника — «природы» .

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

(5.71).

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

(5.72).

В выражении (5.72) мы воспользовались очевидными равенствами и

Оптимальной стратегией второго игрока (администратора) будет та, которая обеспечивает на множестве у? [a; b] минимум выражения (5.72). То есть.

(5.73).

Построим на множестве [a; b] переменной у графики зависимостей и (рис. 5.10).

Рис. 5.10. Графическая иллюстрация выбора оптимальной стратегии.

Анализ рис. 5.10 позволяет сделать вывод, что достигается при z1= z2, т. е. при . Отсюда следует.

(5.74).

Пусть менеджеру известно, что потребность в мощностях на нервом предприятии может колебаться от 30 до 50% суммарной, т. е. а = 0,3 и b = 0,5. В этом случае согласно выражению (5.74) имеем уопт = 5/12. То есть на первом предприятии следует поместить примерно 41,67% производственной мощности.