Алгоритм метода потенциалов. 2 страница

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

(1.11)

Цена игры - средний выигрыш игрока 1 при использовании обо­ими игроками смешанных стратегий. Следовательно, решением матричной игры является:

1) – оптимальная смешанная стратегия игрока 1;

2) – оптимальная смешанная стратегия игрока 2;

3) g – цена игры.

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

(1.12)

Существует основная теорема математических игр.

Для матричной игры с любой матрицей А величины

и (1.13)

существуют и равны между собой: a = b = g.

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

Решить игру - означает найти цену игры и оптимальные страте­гии. Рассмотрение методов нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 2´ 2. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следует отказываться. При отсутствии седловой точки можно получить две оптимальные смешанные стратегии. Как уже отмечалось, эти смешанные стратегии записываются так:

(1.14)

Значит, имеется платежная матрица

(1.15)

При этом

a₁₁p₁ + a₂₁p₂ = g; (1.16)

a₁₂p₁ + a₂₂p₂ = g; (1.17)

p₁ + p₂ = 1.

a₁₁p₁ + a₂₁(1 – p₁) = a₁₂p₁ + a₂₂(1 – p₁); (1.19)

a₁₁p₁ + a₂₁ – a₂₁p₁ = a₁₂p₁ + a₂₂ – a₂₂p₁, (1.20)

откуда получаем оптимальные значения и :

(1.21)

(1.22)

Зная и , находим g:

(1.23)

Вычислив g, находим и :

a₁₁q₁ + a₁₂q₂ = g; q₁ + q₂ = 1; (1.24)

a₁₁q₁ + a₁₂ (1 – q₁) = g. (1.25)

при a₁₁ ¹ a₁₂. (1.26)

Задача решена, так как найдены векторы и цена игры g. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис. 2.1).

1. По оси абсцисс откладывается отрезок единичной длины.

2. По оси ординат откладываются выигрыши при стратегии А₁.

3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a₂.

4. Концы отрезков обозначаются для a₁₁-b₁₁, a₁₂-b₂₁, a₂₂-b₂₂ , a₂₁-b₁₂ и проводятся две прямые линии b₁₁b₁₂ и b₂₁b₂₂.

5. Определяется ордината точки пересечения с. Она равна g. Абсцисса точки с равна р₂ (р₁ = 1 – р₂).

Рис. 1.1. Оптимальная смешанная стратегия

Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр т´ п, состоящем в том, что в любой игре т´ п каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2´ п и т´ 2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2´ п и т´ 2 может быть сведена к игре 2´ 2. Следовательно, игры 2´ п и т´ 2 можно решить графически. Если матрица конечной игры имеет раз­мерность т´ п, где т > 2 и п > 2, то для определения оптимальных смешанных стратегий используется линейное программирование.

Мажорирование (доминирование) стратегий

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

(1.27)

Рассуждая с позиции игрока 2, можно обнаружить преимущество его третьей стратегии перед второй, поскольку при первой стратегии игрока 1 выигрыш игрока 2 равен -3 (вторая стратегия) и 1 (третья стратегия), а при второй стратегии игрока 1 выигрыш игрока 2 равен -2 (вторая стратегия) и -0, 5 (третья стратегия). Таким образом, при любой стратегии игрока 1 игроку 2 выгоднее применять свою третью стратегию по сравнению со второй; при наличии третьей стратегии игрок 2, если он стремится играть оптимально, никогда не будет использовать свою вторую стратегию, поэтому ее можно исключить из игры, т.е. в исходной платежной матрице можно вычеркнуть 2-й столбец:

(1.28)

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

Учитывая интересы игрока 2, следует оставить только его первую стратегию, поскольку, выбирая вторую стратегию, игрок 2 оказывается в проигрыше (0, 5 - выигрыш игрока 1), и матрица игры принимает простейший вид: (0), т.е. имеется седловая точка.

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

В качестве иллюстрации к сказанному рассмотрим матрицу игры:

Для первых двух чистых стратегий игрока 1 возьмем частоты их применения (вероятности) равными 0, 25 и 0, 75.

Третья стратегия игрока 1 мажорируется линейной выпуклой комбинацией первой и второй чистых стратегий, взятых с частотами 0, 25 и 0, 75 соответственно, т.е. смешанной стратегией:

24 × 0, 25 + 0 × 0, 75 = 6 > 4; (1.30)

0 × 0, 25 + 8 × 0, 75 = 6 > 5. (1.31)

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

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

(1.32)

третья стратегия игрока 2 мажорируется смешанной стратегией из первой и второй его чистых стратегий, взятых с частотами 0, 5 и 0, 5:

10 × 0, 5 + 0× 0, 5 = 5 < 6; (1.33)

0 × 0, 5 + 10 × 0, 5 = 5 < 7. (1.34)

Таким образом, исходная матрица игры эквивалентна матрице следующего вида:

(1.35)

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

Тема 10

Теория статистических решений (Игры с природой)

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

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

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

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ИГР С ПРИРОДОЙ

Постановка задачи

Рассмотрим игры с природой на примере следующей задачи. Необходимо закупить уголь для обогрева дома. Количество хранимого угля ограничено и в течение холодного периода должно быть полностью израсходовано. Предполагается, что неизрасходованный зимой уголь в лето пропадает. Покупать уголь можно в любое время, однако летом он дешевле, чем зимой. Неопределенность состоит в том, что не известно, какой будет зима: суровой, тогда придется докупать уголь, или мягкой, тогда часть угля может остаться неиспользованной. Очевидно, что у природы нет злого умысла и она ничего против человека «не имеет». С другой стороны, долгосрочные прогнозы, составляемые метеорологическими службами, неточны и поэтому могут использоваться в практической деятельности только как ориентировочные при принятии решений.

Имеются следующие данные о количестве и ценах угля, необходимого зимой для отопления дома (табл. 3.1). Вероятности зим: мягкой - 0, 35; обычной - 0, 5; холодной - 0, 15.

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

Сколько угля летом покупать на зиму?

Решение задач игр с природой

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

Вычислим, например, показатель для холодной зимы. Игрок 1 приобрел уголь для обычной зимы 5 т по цене 6 грн. за 1 т. Для обогрева он должен закупить еще 1 тонну по цене 8 грн за 1т.

Следовательно, расчет платы за уголь будет 5 × 6 – при заготовке, и зимой 8 × 1. Аналогично производятся расчеты при других сочетаниях.

В итоге получим следующую платежную матрицу в игре с природой платежную матрицу (табл. 3.2).

Таблица.

Произведем расчет ожидаемой средней платы за уголь

Таблица

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

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

Формулы теории вероятности:

Дисперсия случайной величины ξ равна

Среднеквадратичное отклонение составит

где D и М - соответственно символы дисперсии и математического ожидания.

Проводя соответственно вычисления для всех случаев по такому принципу:

Мягкая зима:

М(ξ ²) = - (24² × 0, 35 + 31, 5² × 0, 5 + 40² × 0, 15) = - 937, 725

(Мξ)² = -(30, 15²) = - 909, 0225

Dξ =937, 725- 909, 0225 = 28, 7025

sx = 5, 357

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

• для мягкой зимы sx = 5, 357;

• для обычной зимы sx = 2, 856;

• для холодной зимы sx = 0.

Минимальный риск, естественно, будет для холодной зимы, однако при этом ожидаемая средняя плата за уголь оказывается максимальной - 36 ф. ст.

Вывод. Мы склоняемся к варианту покупки угля для обычной зимы, так как ожидаемая средняя плата за уголь по сравнению с вариантом для мягкой зимы возрастает на 3, 5%, а степень риска при этом оказывается почти в 2 раза меньшей (sx = 2, 856 против 5, 357).

Отношение среднеквадратичного отклонения к математическому ожиданию, вариабельность (средний риск на затрачиваемый 1 ф. ст.) для обычной зимы составляет 2, 856/31, 2 = 0, 0915 против аналогичного показателя для мягкой зимы, равного 5, 357/30, 15 = 0, 1777, т.е. вновь различие почти в 2 раза.

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

Тема 11

Теория массового обслуживания

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

Одноканальная система массового обслуживания с ограниченной длиной очереди. Одноканальная система массового обслуживания с неограниченной очередью. Многоканальная система массового обслуживания с ограниченной очередью. Многоканальная система массового обслуживания с неограниченной очередью. Многоканальная система массового обслужива-ния с ограниченной очередью и ограниченным временем ожидания в очереди

В своем изначальном состоянии рассматриваемая СМО представляет собой один из классических случаев, а конкретно M/M/2/5 по принятому обозначению Кэндалла. После исследования системы были сделаны выводы о неэффективности ее работы. Были предложены методы оптимизации работы СМО, но с этими изменениями система перестает быть классической. Основная проблема при исследовании систем массового обслуживания заключается в том, что в реальности они могут быть исследованы с использованием классической теории массового обслуживания только в редких случаях. Потоки входящих и исходящих заявок могут оказаться не простейшими, следовательно, нахождение предельных вероятностей состояний с использованием системы дифференциальных уравнений Колмогорова невозможно, в системе могут присутствовать приоритетные классы, тогда расчет основных показателей СМО также невозможен.

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S₁, S₂, …, S_n, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t₁, t₂, t₃, называемые шагами.

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

Случайный процесс называется марковским, если вероятность перехода из любого состояния S_i в любое состояние S_j не зависит от того, как и когда система S попала в состояние S_i (т.е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова.

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

Рисунок – Пример размеченного графа состояний

Вершины графа S₁, S₂, S₃ обозначают возможные состояния системы. Стрелка, направленная из вершины S_i в вершину S_j обозначает переход ; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i-той вершине графа, обозначает, что система остается в состоянии S_i с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу NxN, элементами которой являются вероятности переходов p_ij между вершинами графа. Например, граф на рис. 1 описывается матрицей P:

называемой матрицей вероятностей переходов. Элементы матрицы p_ij удовлетворяют условиям:

Элементы матрицы p_ij – дают вероятности переходов в системе за один шаг. Переход

S_i – S_j за два шага можно рассматривать как происходящий на первом шаге из S_i в некоторое промежуточное состояние S_k и на втором шаге из S_k в S_i. Таким образом, для элементов матрицы вероятностей переходов из S_i в S_j за два шага получим:

В общем случае перехода за m шагов для элементов матрицы вероятностей переходов справедлива формула:

Получим два эквивалентных выражения для :

Пусть система S описывается матрицей вероятностей переходов Р:

Если обозначить через Р(m) матрицу, элементами которой являются рi вероятности переходов из S_i в S_j за m шагов, то справедлива формула

,

где матрица Р_m получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы Q(q_i) (называемым также стохастическим вектором).

где q_j - вероятность того, что исходным состоянием системы является S_j состояние. Аналогично (1) и (2) справедливы соотношения

Обозначим через

вектор состояния системы после m шагов, где q_j – вероятность того, что после m шагов система находится в S_i состоянии. Тогда справедлива формула

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

Если система S может переходить в другое состояние случайным образом в произвольный момент времени, то говорят о случайном процессе с непрерывным временем. В отсутствии последействия такой процесс называется непрерывной марковской цепью. При этом вероятности переходов для любых i и j в любой момент времени равны нулю (в силу непрерывности времени). По этой причине вместо вероятности перехода вводится величина - плотность вероятности перехода из состояния в состояние , определяемая как предел:

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

Зная интенсивности переходов можно найти величины p₁(t), p₂(t), …, p_n(t) – вероятности нахождения системы S в состояниях S₁, S₂, …, S_n соответственно. При этом выполняется условие:

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

Состояния S_i и Sj называются сообщающимися, если возможны переходы .

Состояние S_i называется существенным, если всякое S_j, достижимое из S_i, является сообщающимся с S_i. Состояние S_i называется несущественным, если оно не является существенным.

Если существуют предельные вероятности состояний системы:

,

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

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

Теорема 1. Если S_i – несущественное состояние, то т.е. при система выходит из любого несущественного состояния.

Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой.