Примеры. Пример 1. Выбор стратегии

Пример 1. Выбор стратегии. Матрица некоторой игры имеет вид

Найдите оптимальные стратегии игроков.

Решение. В этой игре игрок 1 имеет три возможные страте­гии: а ₁, а ₂, а ₃ из, а игрок 2 — четыре возможные стратегии: b ₁, b ₂, b ₃, b ₄.

Рассмотрим процесс принятия игроками решения (предпола­гается, что они действуют рационально). Взглянув на таблицу, можно заметить, что если игрок 1 не знает, как поступит его про­тивник, то, действуя наиболее целесообразно и считая, что про­тивник будет действовать подобным же образом, он выберет стра­тегию а ₂, которая гарантирует ему наибольший из трех возмож­ных наименьших выигрышей: 9, 13, 8. Другими словами, игрок 1 руководствуется принципом максиминного выигрыша. Этот выигрыш a = а_ij есть нижняя цена игры. Для нашего примера a = 13.

Игрок 2 рассуждает аналогично: если он выберет стратегию b ₁,,то потеряет самое большее 23, если стратегию b ₂, то — 40, и т.д. В результате он выберет стратегию b ₃, которая гарантирует ему наименьший из четырех возможных проигрышей: 23, 40, 13, 25. Принято говорить, что игрок 2 руководствуется принципом мини­максного проигрыша. Этот проигрыш b = а_ij есть верхняя цена игры. Для нашей матрицы b = 13.

Ситуация (a ₂, b ₃) есть седловая точка, и a = b = 13 есть цена игры.

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

Пример 2. Где строить?

Две конкурирующие крупные торговые фирмы Ф₁ и Ф₂ пла­нируют построить в одном из четырех небольших городов Г ₁, Г ₂, Г ₃ и Г ₄, лежащих вдоль автомагистрали, по одному универсаму. Взаимное расположение городов, расстояние между ними и чис­ленность населения показаны на рис. 1.

Рис. 1

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

Например, если универсам фирмы Ф ₁ расположен к городу Г ₁ближе универсама фирмы Ф ₂, то прибыль от покупок, сделанных жителями данного города, распределится следующим образом: 75% получит Ф ₁, остальное — Ф ₂.

Представьте описанную ситуацию как игру двух лиц.

В каких городах фирмам целесообразно построить свои уни­версамы?

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

Платежная матрица имеет вид

Рассмотрим примеры расчета значений элементов (Г ₁, Г ₂) и (Г ₃, Г ₄) матрицы.

Ситуация (Г ₁, Г ₂) означает, что фирма Ф ₁, строит универсам в городе Г ₁, а фирма Ф₂ — в городе Г ₂. Число покупателей фирмы Ф ₁ складывается из покупателей четырех городов. Для ситуации (Г ₁, Г ₂) число покупателей из Г ₁: 0,75×30, из Г ₂: 0,45×50, из Г ₃0,45×40, из Г ₄: 0,45×30, т.е. в сумме 76,5 тыс. руб. Для ситуации (Г ₃, Г ₄) число покупателей из Г₁: 0,75×30, из Г ₂: 0,75×50, из Г ₃: 0,75×40, из Г ₄: 0,45×30, т.е. в сумме 103,5 тыс. руб. Элементы мат­рицы выигрышей фирмы Ф ₂ — дополнения до числа 150 (общее число жителей в четырех городах). Таким образом, имеет место игра двух лиц с ненулевой постоянной суммой, оптимальные стратегии которой те же, что и для соответствующей игры с ну­левой суммой.

Полученная платежная матрица имеет седловую точку (Г ₂, Г ₂). Соответствующий элемент матрицы равен 90.

Таким образом, обеим фирмам следует строить свои универ­самы в одном и том же городе Г ₂, при этом прибыль фирмы Ф ₁составит 90 тыс., а фирмы Ф ₂ — 60 тыс. руб.

.

3. Метод Монте-Карло (метод статистических испытаний Имитационное моделирование случайных факторов) состоит из четырех этапов:

1. Построение математической модели системы, описывающей зависимость моделируемых характеристик от значений стохастических переменных.

2. Установление распределения вероятностей для стохастичес­ких переменных.

3. Установление интервала случайных чисел для каждой сто­хастической переменной и генерация случайных чисел.

4. Имитация поведения системы путем проведения многих ис­пытаний и получение оценки моделируемой характеристики си­стемы при фиксированных значениях параметров управления. Оценка точности результата.

Описание этапов:

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

где F, R — вектор-функции;

I _i, U _i, S _i — векторы соответственно входных, выходных пере­менных и переменных состояния системы в так­товый момент моделирования i.

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

Существует два подхода в имитационном моделировании ди­намических процессов.

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

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

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

Третий этап. Моделирование случайных величин при компью­терных имитационных экспериментах производится с помощью датчика псевдослучайных чисел, предусмотренного в любом со­временном языке программирования. Обычно это датчик случай­ных чисел с равномерным распределением на интервале [0, 1]. Если известны вероятности наступления событий, то, используя такой датчик, можно отвечать на вопросы: «Какое из N возмож­ных событий произошло?» или «Какое значение приняла случай­ная величина?»

Предположим, что в ИМ используется случайная величина X, принимающая дискретные значения х ₁, х ₂ ,..., х_N с вероятностями соответственно p ₁, p ₂ ,..., p_N (). Получение некоторой реализации этой переменной в модели производится следующим образом.

Строится функция распределения случайной величины X. Ука­занная функция определяется посредством равенства F(X) = å p_k, в котором суммирование распространяется на все индексы, для которых х_k < X. С помощью датчика случайных чисел получают случайное число и из отрезка [0, 1].

Из равномерности распределения получаемых случайных чи­сел следует, что вероятность получения случайного числа из про­извольного интервала, включенного в [0, 1], равна длине этого интервала. Поэтому вероятность реализации Х = х_k равна веро­ятности попадания полученного от датчика случайного числа и в произвольный интервал длиной p_k на отрезке [0, 1]. Можно, та­ким образом, утверждать, что если очередное число и датчика удовлетворяет неравенствам 0 < и £ р ₁, то имеет место реализа­ция Х = х ₁, в случае p ₁ < и £ p ₁ + р ₂ — реализация Х = х ₂ и т.д. В общем случае для k = 2,..., N: если < и £ , то Х = х_k.

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

Удобнее, однако, иметь дело не с дробными значениями гра­ниц интервалов, в которые попадает случайное число и, а с их целочисленными значениями, тем более, что с помощью датчи­ков случайных чисел можно генерировать числа из любого диа­пазона. Чтобы получить целые значения границ интервалов, до­статочно умножить все p_k на 10 ^d, где d — целое, минимальное зна­чение которого равно максимальной точности (максимальному числу знаков после десятичной точки) чисел p_k, k = 1,..., N. На­пример, если { р_k } = {0,3; 0,153; 0,5; 0,047}, то минимальное зна­чение d равно 3 (все р_k нужно умножить на 1000). Таким образом, 10 ^d определяет длину интервала значений рассматриваемой слу­чайной величины в ИМ.

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

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

Другой метод заключается в реализации т независимых про­гонов модели, т.е. в m -кратном повторении одного и того же цикла имитирования. При этом, если мы хотим получить в сумме Т наблюдений, в течение каждого прогона можно делать по Т/т (допустим, что это число целое) наблюдений. Оба метода дают примерно одинаковый результат.

Пусть значения у_t (t = 1,..., Т) представляют собой результа­ты Т последовательных измерений значений случайной величи­ны y во время одного и того же сеанса имитации. Среднее по вре­мени значение у определяется выражением

Обозначим через  математическое ожидание случайной вели­чины у. Тогда для достаточно большого T получаем

Оценка дисперсии (если временной ряд не является авто­коррелированным) имеет вид

где D (у) — дисперсия случайной величины у.

Для оценки качества результатов, полученных методом Мон­те-Карло при неизвестной дисперсии наблюдаемой случайной величины, предположим, что Z — характеристика, которая долж­на быть определена (вероятность события, математическое ожи­дание, дисперсия и т.п.), a x — ее значение, уточняемое по мере накопления данных, остающееся случайным вследствие ограни­ченности числа T проведенных наблюдений. В этих условиях мож­но говорить о вероятности p (| Z – x| < ) по отношению к инте­ресующей нас характеристике. Величина | Z – | представляет со­бой погрешность в оценке Z, a  — некоторый допустимый ее предел.

Из неравенства Чебышёва следует

Из этого неравенства следует

откуда при заданных р и  и при известной зависимости D _ (Т)можно найти предельно необходимое Т.

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

где d не зависит от Т.

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

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

Предельное число наблюдений Т ₀ определяется формулой T₀ = d/[(1 – p)²].

При любом числе наблюдений больше Т ₀ обеспечивается тре­буемая точность.