Г Л А В А 9 ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617
До сих пор рассматривались методы решения задач, в которых была известна цель (или несколько целей), достижение которой (которых) считалось желательным. Однако далеко не все ситуации таковы. Особенно ими изобилует современный этап прикладных исследований, когда приходится иметь дело со сложными системами, когда наличествует не только множество целевых функций, но далеко не все ясно с количественным выражением этих функций. В данном случае речь может идти не столько о решении тех или иных задач (хотя это присутствует и здесь), сколько об исследовании поведения сложных систем, о прогнозировании их будущих состояний в зависимости от выбираемых стратегий управления.
Итак, практике потребовался метод для исследования сложных систем, и такой метод появился - это имитационное моделирование ("simulation modeling").
Поскольку для сложных систем многие функции, параметры, характеристики носят случайный характер, то для оценки этих атрибутов, как правило, используется аппарат статистических оценок, а сам метод имитационного моделирования иногда называют методом статистических испытаний. Другими словами, это метод вероятностных оценок, а отсюда, по аналогии с игровыми ситуациями Монте-Карло, его также называют методом Монте-Карло.
Идея метода Монте-Карло чрезвычайно проста и состоит в следующем. Вместо того, чтобы описывать исследуемый процесс (как правило случайный) с помощью аналитического аппарата, производится "розыгрыш" процесса (явления) с помощью какой-либо процедуры, дающей случайный результат. Так же как и в реальности конкретное осуществление (реализация) случайного процесса складывается каждый раз по-разному, также и в результате статистического моделирования (розыгрыша) получаем каждый раз новую, отличную от других, искусственную реализацию процесса. Множество получаемых таким образом реализаций далее обрабатывается как статистический материал, и из него получаются нужные вероятностные характеристики требуемого результата.
При получении множества реализаций мы пользуемся случайностью как аппаратом исследования, заставляя случайность работать на себя.
(Вероятность и случайность рассматриваются в Приложении А).
Метод имитационного моделирования, как правило, используется для анализа функционирования сложных систем, когда возникают непреодолимые сложности при попытке построить "строгую" математическую модель изучаемого объекта, содержащего много связей между элементами, разнообразные нелинейные ограничения, огромное количество параметров и т.п. Иногда можно построить такую модель, но использовать ее из-за отсутствия математического аппарата не представляется возможным. В некоторых случаях для исследуемой системы не существует стройной теории, объясняющей все аспекты ее функционирования, а, следовательно, представляется затруднительным формулирование тех или иных правдоподобных гипотез ее поведения.
Далее, реальные системы, как правило, подвержены влиянию различных случайных факторов, учет которых аналитическим путем представляет порой непреодолимые трудности.
С другой стороны, использование математического аппарата дает возможность сопоставить модель и оригинал только в начале и после применения соответствующего аппарата, что затрудняет верификацию модели.
В основе метода имитационного моделирования лежит возможность максимального использования всей имеющейся в распоряжении исследователя информации о системе, с тем, чтобы получить возможность преодолеть аналитические трудности и найти ответы на поставленные вопросы о поведении системы.
Имитационное моделирование, как правило, используется в сугубо практических целях.
Основными этапами метода являются:
1. Формулировка основных вопросов о поведении системы и задание параметров, характеризующих состояние системы, т.е. определение вектора состояния.
2. Декомпозиция (разбиение) системы на более простые части - блоки. В один блок объединяются "родственные", т.е. преобразующиеся по близким правилам, компоненты вектора состояния и процессы, их преобразующие.
3. Формулируются правила и "правдоподобные" гипотезы относительно поведения системы в целом и ее отдельных частей. В каждом блоке может использоваться свой математический аппарат (алгебраические дифференциальные уравнения, математическое и динамическое программирование и т.п.). Именно это, т.е. блочный способ (принцип), дает возможность установить необходимые пропорции между точностью описания каждого блока, обеспеченностью его информацией и необходимостью достижения цели моделирования.
4. Вводится так называемое системное время, которое моделирует ход времени в реальной системе.
5. Формализованным образом задаются необходимые феноменологические свойства систем в целом и отдельных ее частей. (Часто эти свойства не могут быть обоснованы на современном уровне знаний, а опираются на опыт - длительное наблюдение за поведением системы). Иногда одно такое свойство оказывается эквивалентным множеству сложных математических соотношений и с успехом их заменяет, что, конечно, требует глубокого знания системы.
6. Случайным параметрам, фигурирующим в модели, сопоставляются некоторые их реализации, сохраняющиеся в течение одного или нескольких тактов системного времени. Далее отыскиваются новые реализации.
Как правило, пятый и шестой этапы наиболее просто осуществимы на ЭВМ, поэтому имитационные модели обычно реализуются с использованием специализированных программ, описывающих функционирование отдельных блоков и правила взаимодействия между ними.
Использование реализаций случайных величин требует многократного повторения экспериментов с моделью с последующим статистическим анализом полученных результатов.
Общая постановка задачи.
Под имитационным моделированием будем понимать пошаговое моделирование поведения объекта с помощью ЭВМ. Это означает, что фиксируются определенные моменты времени t1, t2, ..., tn, и состояние модели определяется (вычисляется на ЭВМ) последовательно в каждый из этих моментов времени. Для реализации этого необходимо задать правило (алгоритм) перехода модели из одного состояния в следующее, т.е. преобразование:
Yi Y i+1,
где Yi - состояние модели в i -й момент времени.
Пусть, как обычно, состояние модели определяется вектором:
Y = (y1, y2, ..., ym),
т.е. m - числами; состояние среды вектором:
Х = (х1, x2, ..., xn),
n - числами, а состояние управления вектором:
U = (u1, u2, ..., uq),
q - числами.
Тогда имитационная модель определяется оператором F, с помощью которого можно определить состояние модели в последующий момент времени, т.е. определить вектор Yi+1, зная состояние модели в предыдущий момент времени Yi и значения Хi+1 и Ui+1, т.е.
F
(Yi, Xi+1, Ui+1) Yi+1.
Таким образом, в имитационной модели состояние модели определяется рекуррентно на каждом шаге, исходя только из предыдущего шага. Этот алгоритм можно записать в виде рекуррентной формулы:
Yi+1 = F( Yi, Xi+1, Ui+1 ),
где F - оператор имитаций изменения состояния модели. Он и определяет имитационную модель объекта.
Можно рассмотреть частный случай имитационной модели под воздействием окружающей среды в виде:
Yi = F( Yi-1, Xi )
Но имитационное моделирование (или модели) тем и хорошо, что позволяет учитывать неконтролируемые факторы Е объекта, т.е. его стохастичность, в этом случае модель можно представить рекуррентным соотношением вида:
Yi+1 = F( Yi, Xi+1, Ui+1, Ei+1 ) i = 1,...,N, (9.1)
где необходимо знать, каким образом фактор Е влияет на состояние Y объекта, т.е. следует хорошо разобраться в объекте и указать точно, как входит неконтролируемый фактор Е в оператор объекта с тем, чтобы эти данные отразить в операторе F объекта. Для работы с такой моделью необходимо знать конкретные значения фактора E, который, как известно, ненаблюдаем. Возникает противоречие, которое решает, так называемый метод Монте-Карло. Собственно, как правило, он и является основным методом имитации.
Для реализации метода Монте-Карло необходимо знать некоторые статистические свойства фактора Е (например, закон его распределения). Эти свойства, вообще говоря, могут зависеть от Y, X и U. Располагая этими сведениями, можно моделировать ненаблюдаемый фактор в виде случайных рядов:
Е1j, Е2j, ... , Еnj , j = 1, 2, ..., N,
где индекс внизу соответствует дискретному времени, а верхний - номеру моделируемого ряда (всего моделируется N таких статистически эквивалентных рядов). Естественно, ни один из этих рядов не является точной реализацией действительности, но каждый имеет такие же статистические свойства, что и реальный. Именно поэтому ряды Екj позволяют исследовать статистические свойства модели (9.1).
Так поведение модели " в среднем" описывается как
_ N
Yi = 1/N å Yij , i = 1, 2, ... , N,
j=1
где Yij - j-я реализация поведения модели в i-ый момент времени:
Yij = F( Yi-1j, Xi, Ui, Eij ) , i = 1, 2, .... , N.
Дисперсия выхода модели вычисляется по формуле:
N _
D(Yi) = ( 1/(N-1)) (Yij - Yi)2 .
j=1
Таким образом, метод Монте-Карло позволяет оценить статистичесие свойства поведения объекта путем вероятностного "разыгрывания" поведения модели, причем одна реализация поведения отличается от другой различными значениями ненаблюдаемого фактора Е.
В сущности методом Монте-Карло может быть решена любая вероятностная задача, но оправданным он становится только тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.
В задачах исследования операций метод Монте-Карло применяется в трех основных ролях:
1. Моделирование сложных, комплексных объектов и операций, где присутствует много взаимодействующих случайных факторов;
2. Проверка применимости более простых, аналитических методов и выяснений условий их применимости;
3. В целях выработки поправок к аналитическим формулам "типа эмпирических формул" в технике.
Таким образом, этот метод является своеобразным ОТК математических методов. При этом статистические модели не требуют серьезных допущений и упрощений. В такую модель вписывается все, что угодно - любые законы распределения, любая сложность системы, множественность ее состояний.
Главный же недостаток таких моделей - их громоздкость и трудоемкость. Огромное число реализаций, необходимое для нахождения искомых параметров с приемлемой точностью, требует большого расхода машинного времени. Кроме этого, результаты такого моделирования труднее осмыслить, чем расчеты аналитическими методами и, соответственно, труднее оптимизировать решение (в основном, наощупь). Наиболее целесообразным является сочетание аналитических и имитационных методов. Как правило, аналитическими методами рассчитываются отдельные элементы и блоки сложной системы, а затем, как из "кирпичиков", строится большая сложная имитационная модель.
Суть метода Монте-Карло.
Основными элементами, из совокупности которых складывается статистическая модель, является одна случайная реализация моделируемого явления, например:
- один день работы цеха;
- один случай работы машины до ее отказа;
- одна эпидемия.
Реализация - это как бы один экземпляр случайного явления со всеми присущими ему случайностями. Этим реализации отличаются одна от другой. Отдельная реализация разыгрывается с помощью специально разработанной процедуры (алгоритма), в которой основную роль играет "жребий" или, как говорят, "бросание жребия". Каждый раз, когда в ход явления вмешивается случай, его влияние учитывается не расчетом, а жребием.
Понятие "жребия". Пусть в ходе процесса наступил момент, когда его дальнейшее развитие (а значит и результат) зависит от того, произошло или нет какое-то событие А. Например:
- попал ли в цель снаряд?
- исправна ли аппаратура?
- обнаружен ли объект?
- устранена ли неисправность?
Тогда нужно "бросанием жребия" решить вопрос: произошло событие или нет? Как можно осуществить этот жребий? Необходимо привести в действие какой-либо механизм случайного выбора. Например:
- бросание монеты;
- бросание игральной кости;
- вынимание жетона с цифрой из вращающегося барабана;
- выбор наугад какого-либо числа из таблицы.
Если жребий бросается для того, чтобы узнать, произошло ли событие А, его нужно организовать так, чтобы условный результат розыгрыша имел ту же вероятность, что и событие А.
Кроме случайных событий на ход и исход операции могут влиять различные случайные величины. Например:
- время до первого отказа технического устройства;
- время обслуживания заявки каналом системы массового обслуживания;
- размер детали;
- вес поезда, прибывающего на участок пути;
- координаты точки попадания снаряда.
С помощью жребия можно разыграть как значение любой случайной величины, так и совокупности значений нескольких величин.
Условимся называть "единичным жребием" любой опыт со случайным исходом, который отвечает на один из следующих вопросов:
1. Произошло или нет событие А?
2. Какое из событий А1, А2, ..., Ак произошло?
3. Какое значение приняла случайная величина Х?
4. Какую совокупность значений приняла система случайных величин Х1, Х2, ..., Хк?
Любая реализация случайного явления методом Монте-Карло строится из цепочки единичных жребиев, перемежающихся с обычными расчетами. Ими учитывается влияние исхода жребия на дальнейший ход событий (в частности на условия, в которых будет разыгран следующий жребий.
Единичный жребий может быть разыгран разными способами, но есть один стандартный механизм, с помощью которого можно осуществить любую разновидность жребия. А именно, для каждой из них достаточно уметь получать случайное число R, все значения которого от 0 до 1 равновероятны (т.е. обладают одинаковой плотностью вероятности).
Условно назовем величиной R "случайное число от 0 до 1". С помощью такого числа можно разыграть любой из четырех видов единичного жребия. Рассмотрим эти случаи.
1. Произошло или нет событие А? Для ответа на этот вопрос нужно знать вероятность р события А. Разыгрывается случайное число R от 0 до 1 и, если оно оказалось меньше р, то будем считать, что событие произошло, если больше р, то не произошло.
Если число R окажется точно равным р, вероятностью такого совпадения можно пренебречь, если же это случилось, то можно поступить как угодно: считать всякое "равно" за "больше" или "меньше" произошло или нет или попеременно за то и другое. результат же от этого не зависит.
2. Какое из нескольких событий появилось?
Пусть события А1, А2, ..., Ак несовместимы и образуют полную группу. Тогда сумма их вероятностей р1, р2, ..., рк равна 1. Делим интервал (0, 1) на к участков длиной р1, p2, ..., рк
На какой из участков попало число R, то событие, соответствующее этому рi, и появилось.
3. Какое значение приняла случайная величина Х?
Если случайная величина Х дискретна, т.е. имеет значения х1, x2, ..., хк с вероятностями р1, p2, ..., рк, то, очевидно, случай аналогичен случаю 2. Пусть случайная величина непрерывна и имеет плотность вероятности f(x). Чтобы разыграть ее значение, достаточно осуществить следующую процедуру. Перейти из плотности вероятности f(x) к функции распределения F(x) по формуле :
x
F(x) = f(x) dx,
-
затем найти для функции F(x) обратную ей функцию Y. Разыграть случайное число R от 0 до 1 и взять от него эту обратную функцию, т.е.
x = ( R ).
Можно доказать, что полученное значение х имеет как раз нужное распределение f(x).
Графически процедура розыгрыша значения х дается следующим графиком:
Разыгрывается R от 0 до 1 и для него ищется такое значение x, для которого F(x) = R. На практике приходится часто разыгрывать значение случайной величины, имеющей так называемое нормальное распределение. Для нее правило игры остается справедливым, но можно поступить проще. Известно, что при сложении достаточно большого числа независимых случайных величин с одинаковыми распределениями получается случайная величина, имеющая приближенно нормальное распределение (центральная предельная теорема теории вероятности). На практике, чтобы получить нормальное распределение, достаточно сложить шесть экземпляров случайного числа от 0 до 1:
Z = R1 + R2 + ..... + R6,
Z имеет распределение настолько близкое к нормальному, что в большинстве задач им можно заменить нормальное.
Для того, чтобы математическое ожидание и среднеквадратичное отклонение этого нормального распределения были равны заданным mx и sx, нужно подвергнуть величину Z линейному преобразованию и вычислить:
__
Х = x 2 (Z - 3) + mx..
Это и есть нужная нам нормально распределенная случайная величина.
4. Какую совокупность значений приняли случайные величины Х1, X2,..., Хк?
Если случайные величины независимы, то достаточно к раз повторить процедуру под пунктом 3. Если же они зависимы, то разыгрывать каждую последующую нужно на основе ее условного закона распределения при условии, что все предыдущие приняли те значения, которые дал розыгрыш.
Итак, все четыре возможных случайных исходов, взятые в качестве единичного жребия, могут быть получены розыгрышем (одним или многократным) случайного числа R от 0 до 1.
Как же разыгрывается само это число R? Для этого существует целый ряд разновидностей, так называемых "датчиков случайных чисел", решающих эту задачу.
Самый простой - вращающийся барабан с перемешанными перенумерованными шарами (жетонами). Например, разыгрываем число R от 0 до 1 с точностью до 0.001. Закладываем в барабан 1000 перенумерованных шаров, приводим во вращение и после остановки берем первый наугад попавший шар. Читаем его номер и делим на 1000.
Можно то же сделать и с 10 шарами, пронумерованных цифрами от 0 до 9, при этом при каждом следующем выборе шара и делении его значения на 10 будем записывать соответственно первый после десятичной точки и т.д. знаки.
Исходя из этого, можно заранее составить таблицу случайных чисел. Эти таблицы, как правило, используются при ручном счете.
При счете на ЭВМ применяются датчики случайных чисел. Это могут быть как "физические датчики", основанные на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым ЭВМ вычисляет так называемые "псевдослучайные числа" - это числа, которые, не являясь случайными, ведут себя как случайные (т.е. связь между последовательными значениями получаемых чисел практически отсутствует).
Например, берут два произвольных n-значных двоичных числа а1 и а2, перемножают их и в произведении берут n средних знаков, получают число а3. Затем перемножают а2 на а3 и снова берут n средних знаков. Полученные числа рассматривают как последовательность двоичных дробей с n знаками после запятой.
До сих пор рассматривались методы решения задач, в которых была известна цель (или несколько целей), достижение которой (которых) считалось желательным. Однако далеко не все ситуации таковы. Особенно ими изобилует современный этап прикладных исследований, когда приходится иметь дело со сложными системами, когда наличествует не только множество целевых функций, но далеко не все ясно с количественным выражением этих функций. В данном случае речь может идти не столько о решении тех или иных задач (хотя это присутствует и здесь), сколько об исследовании поведения сложных систем, о прогнозировании их будущих состояний в зависимости от выбираемых стратегий управления.
Итак, практике потребовался метод для исследования сложных систем, и такой метод появился - это имитационное моделирование ("simulation modeling").
Поскольку для сложных систем многие функции, параметры, характеристики носят случайный характер, то для оценки этих атрибутов, как правило, используется аппарат статистических оценок, а сам метод имитационного моделирования иногда называют методом статистических испытаний. Другими словами, это метод вероятностных оценок, а отсюда, по аналогии с игровыми ситуациями Монте-Карло, его также называют методом Монте-Карло.
Идея метода Монте-Карло чрезвычайно проста и состоит в следующем. Вместо того, чтобы описывать исследуемый процесс (как правило случайный) с помощью аналитического аппарата, производится "розыгрыш" процесса (явления) с помощью какой-либо процедуры, дающей случайный результат. Так же как и в реальности конкретное осуществление (реализация) случайного процесса складывается каждый раз по-разному, также и в результате статистического моделирования (розыгрыша) получаем каждый раз новую, отличную от других, искусственную реализацию процесса. Множество получаемых таким образом реализаций далее обрабатывается как статистический материал, и из него получаются нужные вероятностные характеристики требуемого результата.
При получении множества реализаций мы пользуемся случайностью как аппаратом исследования, заставляя случайность работать на себя.
(Вероятность и случайность рассматриваются в Приложении А).
Метод имитационного моделирования, как правило, используется для анализа функционирования сложных систем, когда возникают непреодолимые сложности при попытке построить "строгую" математическую модель изучаемого объекта, содержащего много связей между элементами, разнообразные нелинейные ограничения, огромное количество параметров и т.п. Иногда можно построить такую модель, но использовать ее из-за отсутствия математического аппарата не представляется возможным. В некоторых случаях для исследуемой системы не существует стройной теории, объясняющей все аспекты ее функционирования, а, следовательно, представляется затруднительным формулирование тех или иных правдоподобных гипотез ее поведения.
Далее, реальные системы, как правило, подвержены влиянию различных случайных факторов, учет которых аналитическим путем представляет порой непреодолимые трудности.
С другой стороны, использование математического аппарата дает возможность сопоставить модель и оригинал только в начале и после применения соответствующего аппарата, что затрудняет верификацию модели.
В основе метода имитационного моделирования лежит возможность максимального использования всей имеющейся в распоряжении исследователя информации о системе, с тем, чтобы получить возможность преодолеть аналитические трудности и найти ответы на поставленные вопросы о поведении системы.
Имитационное моделирование, как правило, используется в сугубо практических целях.
Основными этапами метода являются:
1. Формулировка основных вопросов о поведении системы и задание параметров, характеризующих состояние системы, т.е. определение вектора состояния.
2. Декомпозиция (разбиение) системы на более простые части - блоки. В один блок объединяются "родственные", т.е. преобразующиеся по близким правилам, компоненты вектора состояния и процессы, их преобразующие.
3. Формулируются правила и "правдоподобные" гипотезы относительно поведения системы в целом и ее отдельных частей. В каждом блоке может использоваться свой математический аппарат (алгебраические дифференциальные уравнения, математическое и динамическое программирование и т.п.). Именно это, т.е. блочный способ (принцип), дает возможность установить необходимые пропорции между точностью описания каждого блока, обеспеченностью его информацией и необходимостью достижения цели моделирования.
4. Вводится так называемое системное время, которое моделирует ход времени в реальной системе.
5. Формализованным образом задаются необходимые феноменологические свойства систем в целом и отдельных ее частей. (Часто эти свойства не могут быть обоснованы на современном уровне знаний, а опираются на опыт - длительное наблюдение за поведением системы). Иногда одно такое свойство оказывается эквивалентным множеству сложных математических соотношений и с успехом их заменяет, что, конечно, требует глубокого знания системы.
6. Случайным параметрам, фигурирующим в модели, сопоставляются некоторые их реализации, сохраняющиеся в течение одного или нескольких тактов системного времени. Далее отыскиваются новые реализации.
Как правило, пятый и шестой этапы наиболее просто осуществимы на ЭВМ, поэтому имитационные модели обычно реализуются с использованием специализированных программ, описывающих функционирование отдельных блоков и правила взаимодействия между ними.
Использование реализаций случайных величин требует многократного повторения экспериментов с моделью с последующим статистическим анализом полученных результатов.
Общая постановка задачи.
Под имитационным моделированием будем понимать пошаговое моделирование поведения объекта с помощью ЭВМ. Это означает, что фиксируются определенные моменты времени t1, t2, ..., tn, и состояние модели определяется (вычисляется на ЭВМ) последовательно в каждый из этих моментов времени. Для реализации этого необходимо задать правило (алгоритм) перехода модели из одного состояния в следующее, т.е. преобразование:
Yi Y i+1,
где Yi - состояние модели в i -й момент времени.
Пусть, как обычно, состояние модели определяется вектором:
Y = (y1, y2, ..., ym),
т.е. m - числами; состояние среды вектором:
Х = (х1, x2, ..., xn),
n - числами, а состояние управления вектором:
U = (u1, u2, ..., uq),
q - числами.
Тогда имитационная модель определяется оператором F, с помощью которого можно определить состояние модели в последующий момент времени, т.е. определить вектор Yi+1, зная состояние модели в предыдущий момент времени Yi и значения Хi+1 и Ui+1, т.е.
F
(Yi, Xi+1, Ui+1) Yi+1.
Таким образом, в имитационной модели состояние модели определяется рекуррентно на каждом шаге, исходя только из предыдущего шага. Этот алгоритм можно записать в виде рекуррентной формулы:
Yi+1 = F( Yi, Xi+1, Ui+1 ),
где F - оператор имитаций изменения состояния модели. Он и определяет имитационную модель объекта.
Можно рассмотреть частный случай имитационной модели под воздействием окружающей среды в виде:
Yi = F( Yi-1, Xi )
Но имитационное моделирование (или модели) тем и хорошо, что позволяет учитывать неконтролируемые факторы Е объекта, т.е. его стохастичность, в этом случае модель можно представить рекуррентным соотношением вида:
Yi+1 = F( Yi, Xi+1, Ui+1, Ei+1 ) i = 1,...,N, (9.1)
где необходимо знать, каким образом фактор Е влияет на состояние Y объекта, т.е. следует хорошо разобраться в объекте и указать точно, как входит неконтролируемый фактор Е в оператор объекта с тем, чтобы эти данные отразить в операторе F объекта. Для работы с такой моделью необходимо знать конкретные значения фактора E, который, как известно, ненаблюдаем. Возникает противоречие, которое решает, так называемый метод Монте-Карло. Собственно, как правило, он и является основным методом имитации.
Для реализации метода Монте-Карло необходимо знать некоторые статистические свойства фактора Е (например, закон его распределения). Эти свойства, вообще говоря, могут зависеть от Y, X и U. Располагая этими сведениями, можно моделировать ненаблюдаемый фактор в виде случайных рядов:
Е1j, Е2j, ... , Еnj , j = 1, 2, ..., N,
где индекс внизу соответствует дискретному времени, а верхний - номеру моделируемого ряда (всего моделируется N таких статистически эквивалентных рядов). Естественно, ни один из этих рядов не является точной реализацией действительности, но каждый имеет такие же статистические свойства, что и реальный. Именно поэтому ряды Екj позволяют исследовать статистические свойства модели (9.1).
Так поведение модели " в среднем" описывается как
_ N
Yi = 1/N å Yij , i = 1, 2, ... , N,
j=1
где Yij - j-я реализация поведения модели в i-ый момент времени:
Yij = F( Yi-1j, Xi, Ui, Eij ) , i = 1, 2, .... , N.
Дисперсия выхода модели вычисляется по формуле:
N _
D(Yi) = ( 1/(N-1)) (Yij - Yi)2 .
j=1
Таким образом, метод Монте-Карло позволяет оценить статистичесие свойства поведения объекта путем вероятностного "разыгрывания" поведения модели, причем одна реализация поведения отличается от другой различными значениями ненаблюдаемого фактора Е.
В сущности методом Монте-Карло может быть решена любая вероятностная задача, но оправданным он становится только тогда, когда процедура розыгрыша проще, а не сложнее аналитического расчета.
В задачах исследования операций метод Монте-Карло применяется в трех основных ролях:
1. Моделирование сложных, комплексных объектов и операций, где присутствует много взаимодействующих случайных факторов;
2. Проверка применимости более простых, аналитических методов и выяснений условий их применимости;
3. В целях выработки поправок к аналитическим формулам "типа эмпирических формул" в технике.
Таким образом, этот метод является своеобразным ОТК математических методов. При этом статистические модели не требуют серьезных допущений и упрощений. В такую модель вписывается все, что угодно - любые законы распределения, любая сложность системы, множественность ее состояний.
Главный же недостаток таких моделей - их громоздкость и трудоемкость. Огромное число реализаций, необходимое для нахождения искомых параметров с приемлемой точностью, требует большого расхода машинного времени. Кроме этого, результаты такого моделирования труднее осмыслить, чем расчеты аналитическими методами и, соответственно, труднее оптимизировать решение (в основном, наощупь). Наиболее целесообразным является сочетание аналитических и имитационных методов. Как правило, аналитическими методами рассчитываются отдельные элементы и блоки сложной системы, а затем, как из "кирпичиков", строится большая сложная имитационная модель.
Суть метода Монте-Карло.
Основными элементами, из совокупности которых складывается статистическая модель, является одна случайная реализация моделируемого явления, например:
- один день работы цеха;
- один случай работы машины до ее отказа;
- одна эпидемия.
Реализация - это как бы один экземпляр случайного явления со всеми присущими ему случайностями. Этим реализации отличаются одна от другой. Отдельная реализация разыгрывается с помощью специально разработанной процедуры (алгоритма), в которой основную роль играет "жребий" или, как говорят, "бросание жребия". Каждый раз, когда в ход явления вмешивается случай, его влияние учитывается не расчетом, а жребием.
Понятие "жребия". Пусть в ходе процесса наступил момент, когда его дальнейшее развитие (а значит и результат) зависит от того, произошло или нет какое-то событие А. Например:
- попал ли в цель снаряд?
- исправна ли аппаратура?
- обнаружен ли объект?
- устранена ли неисправность?
Тогда нужно "бросанием жребия" решить вопрос: произошло событие или нет? Как можно осуществить этот жребий? Необходимо привести в действие какой-либо механизм случайного выбора. Например:
- бросание монеты;
- бросание игральной кости;
- вынимание жетона с цифрой из вращающегося барабана;
- выбор наугад какого-либо числа из таблицы.
Если жребий бросается для того, чтобы узнать, произошло ли событие А, его нужно организовать так, чтобы условный результат розыгрыша имел ту же вероятность, что и событие А.
Кроме случайных событий на ход и исход операции могут влиять различные случайные величины. Например:
- время до первого отказа технического устройства;
- время обслуживания заявки каналом системы массового обслуживания;
- размер детали;
- вес поезда, прибывающего на участок пути;
- координаты точки попадания снаряда.
С помощью жребия можно разыграть как значение любой случайной величины, так и совокупности значений нескольких величин.
Условимся называть "единичным жребием" любой опыт со случайным исходом, который отвечает на один из следующих вопросов:
1. Произошло или нет событие А?
2. Какое из событий А1, А2, ..., Ак произошло?
3. Какое значение приняла случайная величина Х?
4. Какую совокупность значений приняла система случайных величин Х1, Х2, ..., Хк?
Любая реализация случайного явления методом Монте-Карло строится из цепочки единичных жребиев, перемежающихся с обычными расчетами. Ими учитывается влияние исхода жребия на дальнейший ход событий (в частности на условия, в которых будет разыгран следующий жребий.
Единичный жребий может быть разыгран разными способами, но есть один стандартный механизм, с помощью которого можно осуществить любую разновидность жребия. А именно, для каждой из них достаточно уметь получать случайное число R, все значения которого от 0 до 1 равновероятны (т.е. обладают одинаковой плотностью вероятности).
Условно назовем величиной R "случайное число от 0 до 1". С помощью такого числа можно разыграть любой из четырех видов единичного жребия. Рассмотрим эти случаи.
1. Произошло или нет событие А? Для ответа на этот вопрос нужно знать вероятность р события А. Разыгрывается случайное число R от 0 до 1 и, если оно оказалось меньше р, то будем считать, что событие произошло, если больше р, то не произошло.
Если число R окажется точно равным р, вероятностью такого совпадения можно пренебречь, если же это случилось, то можно поступить как угодно: считать всякое "равно" за "больше" или "меньше" произошло или нет или попеременно за то и другое. результат же от этого не зависит.
2. Какое из нескольких событий появилось?
Пусть события А1, А2, ..., Ак несовместимы и образуют полную группу. Тогда сумма их вероятностей р1, р2, ..., рк равна 1. Делим интервал (0, 1) на к участков длиной р1, p2, ..., рк
На какой из участков попало число R, то событие, соответствующее этому рi, и появилось.
3. Какое значение приняла случайная величина Х?
Если случайная величина Х дискретна, т.е. имеет значения х1, x2, ..., хк с вероятностями р1, p2, ..., рк, то, очевидно, случай аналогичен случаю 2. Пусть случайная величина непрерывна и имеет плотность вероятности f(x). Чтобы разыграть ее значение, достаточно осуществить следующую процедуру. Перейти из плотности вероятности f(x) к функции распределения F(x) по формуле :
x
F(x) = f(x) dx,
-
затем найти для функции F(x) обратную ей функцию Y. Разыграть случайное число R от 0 до 1 и взять от него эту обратную функцию, т.е.
x = ( R ).
Можно доказать, что полученное значение х имеет как раз нужное распределение f(x).
Графически процедура розыгрыша значения х дается следующим графиком:
Разыгрывается R от 0 до 1 и для него ищется такое значение x, для которого F(x) = R. На практике приходится часто разыгрывать значение случайной величины, имеющей так называемое нормальное распределение. Для нее правило игры остается справедливым, но можно поступить проще. Известно, что при сложении достаточно большого числа независимых случайных величин с одинаковыми распределениями получается случайная величина, имеющая приближенно нормальное распределение (центральная предельная теорема теории вероятности). На практике, чтобы получить нормальное распределение, достаточно сложить шесть экземпляров случайного числа от 0 до 1:
Z = R1 + R2 + ..... + R6,
Z имеет распределение настолько близкое к нормальному, что в большинстве задач им можно заменить нормальное.
Для того, чтобы математическое ожидание и среднеквадратичное отклонение этого нормального распределения были равны заданным mx и sx, нужно подвергнуть величину Z линейному преобразованию и вычислить:
__
Х = x 2 (Z - 3) + mx..
Это и есть нужная нам нормально распределенная случайная величина.
4. Какую совокупность значений приняли случайные величины Х1, X2,..., Хк?
Если случайные величины независимы, то достаточно к раз повторить процедуру под пунктом 3. Если же они зависимы, то разыгрывать каждую последующую нужно на основе ее условного закона распределения при условии, что все предыдущие приняли те значения, которые дал розыгрыш.
Итак, все четыре возможных случайных исходов, взятые в качестве единичного жребия, могут быть получены розыгрышем (одним или многократным) случайного числа R от 0 до 1.
Как же разыгрывается само это число R? Для этого существует целый ряд разновидностей, так называемых "датчиков случайных чисел", решающих эту задачу.
Самый простой - вращающийся барабан с перемешанными перенумерованными шарами (жетонами). Например, разыгрываем число R от 0 до 1 с точностью до 0.001. Закладываем в барабан 1000 перенумерованных шаров, приводим во вращение и после остановки берем первый наугад попавший шар. Читаем его номер и делим на 1000.
Можно то же сделать и с 10 шарами, пронумерованных цифрами от 0 до 9, при этом при каждом следующем выборе шара и делении его значения на 10 будем записывать соответственно первый после десятичной точки и т.д. знаки.
Исходя из этого, можно заранее составить таблицу случайных чисел. Эти таблицы, как правило, используются при ручном счете.
При счете на ЭВМ применяются датчики случайных чисел. Это могут быть как "физические датчики", основанные на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым ЭВМ вычисляет так называемые "псевдослучайные числа" - это числа, которые, не являясь случайными, ведут себя как случайные (т.е. связь между последовательными значениями получаемых чисел практически отсутствует).
Например, берут два произвольных n-значных двоичных числа а1 и а2, перемножают их и в произведении берут n средних знаков, получают число а3. Затем перемножают а2 на а3 и снова берут n средних знаков. Полученные числа рассматривают как последовательность двоичных дробей с n знаками после запятой.