Механики
 Скачать 4.29 Mb.
|
|
моделью системы. Модель обычно включает в себя те аспекты системы, которые представляют интерес или нуждаются в исследовании. Поскольку целью построения любой модели является исследование характеристик моделируемой системы, в имитационную модель должны быть включены средства сбора и обработки статистической информации по всем интересующим характеристикам, основанные на методах матема- тической статистики. 6.1.2. Принципы организации имитационного моделирования «Даже маленькая практика стоит большой теории» (Закон Буккера) Рассмотрим принципы имитационного моделирования на примере простейшей базовой модели в виде одноканальной системы массового обслуживания с однородным потоком заявок (рис.6.1), в которую поступает случайный поток заявок с интервалами между соседними заявками, распределёнными по закону ) ( τ A , а длительность обслуживания заявок в приборе распределена по закону ) ( τ B Процесс функционирования такой системы может быть представлен в виде временных диаграмм , на основе которых могут быть измерены и рассчи - таны характеристики обслуживания заявок Поскольку процессы поступле - ния и обслуживания заявок в системе носят случайный характер , то для построения диаграмм необходимо иметь генераторы случайных чисел Положим , что в нашем распоряжении имеются генераторы случай - 242 Раздел 6. Имитационное моделирование ных чисел , формирующие значения соответствующих случайных величин с заданными законами распределений ) ( τ A и ) ( τ B Тогда можно построить временные диаграммы , отображающие процесс функционирования рассма - триваемой системы На рис .6.2 представлены четыре диаграммы , отображающие : 1) « процесс поступления заявок » в виде моментов i t поступления заявок в систему , формируемых по правилу : i a i i t t τ + = − 1 ( 0 0 = t ), где i a τ ( , 2 , 1 = i ) – интервалы между поступающими в систему заявками , значения которых вырабатываются с помощью генератора случайных величин ) ( τ A ; 2) « процесс обслуживания в приборе », представленный в виде длительностей обслуживания bi τ , которых вырабатываются с помощью генератора случайных величин ) ( τ B , и моментов завершения обслуживания ' i t заявок в приборе , определяемых по следующему правилу : i b i i t t τ + = ' , если на момент поступления i - й заявки обслуживающий прибор был свободен ; i b i i t t τ + = − ' 1 ' , если на момент поступления i- й заявки обслуживающий прибор был занят обслуживанием предыдущей заявки ( , 2 , 1 = i ; 0 ' 0 = t ); 3) « модельное или реальное время », показывающее дискретное ( скачкообразное ) изменение времени в реальной системе , каждый момент которого соответствует одному из следующих событий : поступление заявки в систему или завершение обслуживания заявки в приборе ; отметим , что в эти моменты времени происходит изменение состояния системы , описываемое числом заявок , находящихся в системе ; 4) « число заявок в системе », описывающее состояние дискретной системы и изменяющееся по правилу : увеличение на 1 в момент поступления заявки в систему и уменьшение на 1 в момент завершения обслуживания При соблюдении выбранного временного масштаба представленные диаграммы позволяют путем измерения определить значения вероятностно - временных характеристик функционирования моделируемой системы , в частности , как показано на второй диаграмме , время нахождения ( пребывания ) каждой заявки в системе : ...) , 2 , 1 ( = i i u τ Очевидно , что время пребывания заявок в системе – величина случайная В простейшем случае , применяя методы математической статистики , можно рассчитать два первых момента распределения времени пребывания : • математическое ожидание : ∑ = = N i u i N u 1 1 τ ; Раздел 6. Имитационное моделирование 243 • второй начальный момент: ∑ = − = N i u i N u 1 2 ) 2 ( 1 1 τ , где N - количество значений времени пребывания заявок, полученных на диаграмме, то есть количество заявок, отображенных на диаграмме как прошедшие через систему и покинувшие её. Отсюда легко могут быть получены значения дисперсии, среднеквадратического отклонения и коэффициента вариации времени пребывания заявок в системе. На основе полученных с помощью временных диаграмм значений времени пребывания заявок в системе можно построить гистограмму функции или плотности распределения времени пребывания. Точность полученных числовых моментов распределения и качество гистограмм существенно зависит от количества значений N времени пре- бывания заявок, на основе которых они рассчитываются: чем больше N , тем точнее результаты расчета. Значение N может составлять от несколь- ких тысяч до десятков миллионов. Конкретное значение N зависит от многих факторов, влияющих на скорость сходимости результатов к истин- ному значению, основными среди которых при моделировании систем и сетей массового обслуживания являются законы распределений интерва- лов между поступающими заявками и длительностей обслуживания, загрузка системы, сложность модели, количество классов заявок и т.д. Ясно, что построение вручную таких временных диаграмм с тысячами и более проходящими через систему заявками, нереально. В то же время, использование ЭВМ для реализации временных диаграмм «Процесс поступления заявок» «Процесс обслуживания в приборе» «Модельное (реальное) время» «Число заявок в системе» 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 t ' 1 t ' 2 t ' 3 t ' 4 t ' 5 t ' 6 t ' 7 t 0 1 2 3 1 u τ 2 u τ 3 u τ 4 u τ 5 u τ 6 u τ 1 b τ 2 b τ 3 b τ 4 b τ 5 b τ 6 b τ 7 b τ 4 a τ 7 a τ 3 a τ 6 a τ 1 a τ 8 a τ Рис.6.2. Диаграммы функционирования одноканальной СМО t t t t 244 Раздел 6. Имитационное моделирование позволяет существенно ускорить процессы моделирования и получения конечного результата. Поэтому, как сказано выше, имитационное моделирование можно рассматривать как процесс реализации диаграммы функционирования исследуемой системы. Таким образом, имитационная модель представляет собой алгоритм реализации временной диаграммы функционирования исследуемой системы. Наличие встроенных в большинство алгоритмических языков генераторов случайных чисел значительно упрощает процесс реализации имитационной модели на ЭВМ. Однако при этом остаётся ряд проблем, требующих своего решения. Одна из них заключается в принципе реализации временной диаграммы и, связанной с ней, проблемой организации службы времени в имитационной модели. В простейшем случае временная диаграмма может быть реализована следующим образом: сначала формируются моменты поступления всех заявок в систему, а затем для каждой заявки определяются длительности обслуживания в приборе и формируются моменты завершения обслуживания (выхода заявок из системы). Очевидно, что такой подход неприемлем, поскольку даже для нашей очень простой системы придётся хранить в памяти ЭВМ одновременно миллионы значений моментов поступления и завершения обслуживания заявок, а также других переменных, причём с увеличением количества классов заявок и количества обслуживающих приборов это число увеличится многократно. Второй подход, который может быть предложен для реализации временной диаграммы, – пошаговое построение диаграммы. Для этого следует сформировать переменную для модельного времени и выбрать шаг t ∆ его изменения. В каждый такой момент времени необходимо проверять, какое событие (поступление в систему или завершение обслуживания заявки) произошло в системе за предыдущий интервал t ∆ Этот подход значительно сокращает потребность в памяти, поскольку в этом случае в каждый момент времени необходимо хранить в памяти ЭВМ значения параметров (моментов поступления и завершения обслуживания) только тех заявок, которые находятся в системе на данный момент времени. Недостатки такого подхода очевидны. Во-первых, проблематичным является выбор длины интервала t ∆ . С одной стороны, интервал t ∆ должен быть как можно меньше для уменьшения методической погрешности моделирования, с другой стороны, интервал t ∆ должен быть как можно больше для уменьшения времени моделирования. Наиболее эффективным подходом признан подход с переменным шагом продвижения модельного времени, который реализуется в соответ- ствии с принципом «до ближайшего события». Принцип «продвижения модельного времени до ближайшего события» заключается в следую- щем. По всем процессам, параллельно протекающим в исследуемой систе- ме, в каждый момент времени формируются моменты наступления «бли- Раздел 6. Имитационное моделирование 245 жайшего события в будущем». Затем модельное время продвигается до момента наступления ближайшего из всех возможных событий. В зависи- мости от того, какое событие оказалось ближайшим, выполняются те или иные действия. Если ближайшим событием является поступление заявки в систему, то выполняются действия, связанные с занятием прибора при условии, что он свободен, и занесение заявки в очередь, если прибор занят. Если же ближайшим событием является завершение обслуживания заявки в приборе, то выполняются действия, связанные с освобождение прибора и выбором на обслуживание новой заявки из очереди, если последняя не пуста. Затем формируется новый момент наступления этого же события. На третьей диаграмме «Модельное (реальное) время» (рис.6.2) продвиже- ние времени в соответствии с этим принципом показано в виде стрелок. Для того чтобы обеспечить правильную временную последователь- ность событий в имитационной модели, используются системные часы, хранящие значение текущего модельного времени. Изменение значения модельного времени осуществляется в соответствии с принципом «пере- счёта времени до ближайшего события». Например, если текущее значение модельного времени равно 25, а очередные события должны наступить в моменты времени 31, 44 и 56, то значение модельного времени увели- чивается сразу на 6 единиц и «продвигается» до значения 31. Отметим, что единицы времени в модели не обязательно должны быть конкретными единицами времени, такими как секунда или час. Основной единицей вре- мени в модели можно выбрать любую единицу, которая позволит получить необходимую точность моделирования. Важно помнить, единицы времени выбираются исходя из требований пользователя к точности моделирова- ния. Какая бы единица ни была выбрана, например миллисекунда или одна десятая часа, она должна неизменно использоваться во всей модели. Кроме рассмотренной службы времени в имитационной модели необходимо реализовать процедуры, связанные с формированием потоков заявок и имитацией обслуживания, с организацией очередей заявок, с орга- низацией сбора и статистической обработки результатов моделирования. Таким образом, имитационное моделирование дискретных систем со стохастическим характером функционирования, таких как системы и сети массового обслуживания, предполагает использование ряда типовых процедур, обеспечивающих реализацию соответствующих имитационных моделей. К таким процедурам, в первую очередь, относятся следующие процедуры: 1) выработка (генерирование) случайных величин: равномерно распределенных; с заданным законом распределения; 2) формирование потоков заявок и имитация обслуживания; 3) организация очередей заявок; 4) организация службы времени; 5) сбор и статистическая обработка результатов моделирования. 246 Раздел 6. Имитационное моделирование 6.2. Методы формирования случайных чисел «То, что ищешь, найдешь только обыскав все» (Закон Буба) Функционирование элементов системы, подверженных случайным воздействиям, задается генераторами (датчиками) случайных чисел: аппаратными или программными. Генераторы случайных чисел в ЭВМ обычно реализуются программными методами, вырабатывающими псевдо- случайные последовательности. Псевдослучайными последовательностями называются вполне детерминированные числа, обладающие: • статистическими свойствами случайных чисел, определяемых путем их проверки специальными тестами, • периодичностью, то есть повторяемостью через определенные промежутки времени. Количество случайных величин, вырабатываемых между двумя одинаковыми значениями, называется длиной периода генератора случайных величин. При моделировании используются интервалы последовательностей псевдослучайных чисел, в которых нет ни одного числа, встречающегося более одного раза. Для формирования случайных чисел с заданными законами распре- делений в качестве исходных используют случайные числа, выработанные программными генераторами равномерно распределенных случайных чисел в интервале (0,1), встроенные практически во все языки программи- рования. Специализированные программные средства, предназначенные для вероятностного моделирования, обычно имеют специальные встроен- ные процедуры генерирования случайных величин с разными законами распределений. 6.2.1. Формирование равномерно распределённых случайных величин Для формирования равномерно распределённых случайных чисел в интервале (0; 1) могут использоваться следующие методы: • метод квадратов; • метод произведений; • мультипликативный конгруэнтный метод; • методы, представляющие модификации перечисленных методов. Метод квадратов является одним из простейших методов и служит хорошей иллюстрацией принципа алгоритмического формирования равномерно распределённых случайных величин. Алгоритм формирования равномерно распределённых случайных величин по методу квадратов заключается в выполнении следующих этапов: Раздел 6. Имитационное моделирование 247 1) выбирается некоторое исходное n -разрядное целое число, которое должно удовлетворять определённым условиям для получения качественного генератора случайных величин с максимально возможной длиной периода; 2) выбранное n -разрядное число возводится в квадрат, в результате чего получается целое число с вдвое большей разрядностью; 3) из полученного 2 n -разрядного числа выделяются n средних разрядов, которые рассматриваются как дробная часть случайного числа, равномерно распределённого в интервале (0; 1); 4) выделенные на предыдущем этапе n средних разрядов рассматриваются как новое исходное n -разрядное целое число; 5) повторяются этапы 2 – 4. Проиллюстрируем метод квадратов на следующем примере. Пример 1. Для простоты будем оперировать десятичными числами, а не двоичными, как это реализуется в программных генераторах. Пусть выбрано некоторое исходное четырехразрядное целое число, равное 7153. Результаты применения описанного алгоритма представлены в виде следующей таблицы: Исх.число Квадрат Случайное число 7153 51 1654 09 0,1654 1654 02 7357 16 0,7357 7357 54 1254 49 0,1254 1254 01 5725 16 0,5725 5725 32 7756 25 0,7756 7756 60 1555 36 0,1555 Очевидно, что максимальная длина периода генератора, то есть максимальное количество неповторяющихся случайных чисел определя- ется количеством разрядов в дробной части. В нашем примере максималь- но возможная длина периода равна 9999 (от 0,0001 до 0,9999). Однако в действительности длина периода меньше максимально возможной и зави- сит от исходного целого числа. Неудачно выбранное значение исходного числа может привести к двум неприятностям: маленькой длине периода или даже к вырождению генератора, когда значения случайной величины начинают повторяться, как это показано в примере 2. Пример 2. Исходное четырехразрядное целое число = 1357 Исх.число Квадрат Случайное число 1357 01 8414 49 0,8414 8414 70 7953 96 0,7953 7953 63 2502 09 0,2502 2502 06 2600 04 0,2600 2600 06 7600 00 0,7600 7600 57 |