Основы имитационного моделирования

Основы имитационного моделирования

1. Суть имитационного моделирования

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

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

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

Имитационное моделирование может применяться в самых различных сферах деятельности. Ниже приведен список задач, при решении которых моделирование особенно эффективно:

проектирование и анализ производственных систем;

оценка различных систем вооружений и требований к их материально-техническому обеспечению;

определение требований к оборудованию и протоколам сетей связи;

определение требований к оборудованию и программному обеспечению различных компьютерных систем;

проектирование и анализ работы транспортных систем, например аэропортов, автомагистралей, портов и метрополитена;

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

модернизация различных процессов в деловой сфере;

определение политики в системах управления запасами;

анализ финансовых и экономических систем.

Имитационное моделирование -- один из наиболее распространенных методов, а возможно, и самый распространенный метод, исследования операций и теории управления, о чем свидетельствуют, например, Зимние конференции по вопросам имитационного моделирования (Winter Simulation Conference), ежегодно собирающие до 700 участников. Существует еще несколько конференций, организуемых поставщиками программных продуктов для моделирования, в которых ежегодно участвует свыше 100 чел.

Известно также несколько обзоров, посвященных использованию методов исследования операций. Например, Лейн, Мансор и Харпелл в своих отчетах за период с 1993 по 1998 год приходят к выводу, что моделирование постоянно входит в число трех наиболее важных методов исследования операций. К двум другим они относят математическое программирование (универсальный термин, применяемый для обозначения таких методов, как линейное программирование, нелинейное программирование и т. п.) и статистику (которая, по сути, не является методом исследования операций).

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

2. Система, модели и имитационное моделирование

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

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

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

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

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

В определенные моменты функционирования большинства систем возникает необходимость их исследования с целью получения представления о внутренних отношениях между их компонентами или вычисления их производительности в новых условиях эксплуатации. На рис. 1 изображены различные способы исследования системы. Рассмотрим их подробнее.

Рис. 1. Способы исследования системы

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

Физическая модель или математическая модель? При слове «модель» большинство из нас представляет себе кабины, установленные вне самолетов на тренировочных площадках и применяемые для обучения пилотов, либо миниатюрные супертанкеры, движущиеся в бассейне. Это все примеры физических моделей (именуемых также тоническими или образными). Они редко используются при исследовании операций или анализе систем. Но в некоторых случаях создание физических моделей может оказаться весьма эффективным при исследовании технических систем или систем управления. Примерами могут служить масштабные настольные модели погрузочно-разгрузочных систем и, по крайней мере, один случай создания полномасштабной физической модели заведения быстрого питания в большом магазине, в реализации которой были задействованы вполне реальные посетители. Однако преобладающее большинство создаваемых моделей являются математическими. Они представляют систему посредством логических и количественных отношений, которые затем подвергаются обработке и изменениям, чтобы определить, как система реагирует на изменения, точнее -- как бы она реагировала, если бы существовала на самом деле. Наверное, самым простым примером математической модели является известное соотношение d -- rt, где d -- расстояние, г -- скорость перемещения, t -- время перемещения.

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

Аналитическое решение или имитационное моделирование? Чтобы ответить на вопросы о системе, которую представляет математическая модель, следует установить, как эту модель можно построить. Когда модель достаточно проста, можно вычислить ее соотношения и параметры и получить точное аналитическое решение. Если в примере с формулой d = rt известны расстояние, на которое перемещается объект, и его скорость, то время, необходимое для перемещения, рассчитывается из соотношения t = d/r. Это простое аналитическое решение, к которому мы приходим с помощью ручки и бумаги. Однако некоторые аналитические решения могут быть чрезвычайно сложными и требовать при этом огромных компьютерных ресурсов.

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

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

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

Статическая или динамическая? Статическая имитационная модель -- это система в определенный момент времени или же система, в которой время просто не играет никакой роли. Примерами статической имитационной модели являются модели, созданные по методу Монте-Карло.

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

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

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

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

Имитационные модели, которые мы дальше рассмотрим, будут дискретными, динамическими и стохастическими.

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

3. Дискретно-событийное моделирование

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

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

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

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

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

3.1 Механизмы продвижения времени

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

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

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

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

3.2 Компоненты дискретно-событийной имитационной модели и их организация

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

состояние системы -- совокупность переменных состояния, необходимых для описания системы в определенный момент времени;

часы модельного времени -- переменная, указывающая текущее значение модельного времени;

список событий -- список, содержащий время возникновения каждого последующего типа событий;

статистические счетчики -- переменные, предназначенные для хранения статистической информации о характеристике системы;

программа инициализации - подпрограмма, устанавливающая в исходное состояние имитационную модель в момент времени, равный 0;

синхронизирующая программа -- подпрограмма, которая отыскивает следующее событие в списке событий и затем переводит часы модельного времени на время возникновения этого события;

программа обработки событий -- подпрограмма, обновляющая состояние системы, когда происходит событие определенного типа (для каждого типа событий существует отдельная программа обработки событий);

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

генератор отчетов -- подпрограмма, которая считывает оценки (со статистических счетчиков) критериев оценки работы и выдает отчет по окончании моделирования;

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

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

Основная программа активизирует программу обработки событий i, при этом происходят три типа действий: первое -- обновляется состояние системы в соответствии с произошедшим событием типа г; второе -- собирается информация о критериях оценки работы системы путем обновления статистических счетчиков; третье -- генерируется время возникновения будущих событий, и информация о нем добавляется в список событий.

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

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

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

Объекты характеризуются с помощью значений, именуемых атрибутами. В дискретно-событийной имитационной модели эти атрибуты являются частью состояния системы.

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

В системе, описанной в примере 1, такими объектами являются устройство обслуживания и требования. Здесь устройство имеет атрибут «состояние устройства» (занято или свободно), а требования, ожидающие в очереди, -- атрибут «время поступления». (Число требований в очереди можно также считать атрибутом устройства.)

Рис. 2. Поток управления в механизме продвижения времени от события к событию

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

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

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

4. Моделирование системы массового обслуживания с одним устройством обслуживания

Рассмотрим систему массового обслуживания с одним устройством. В этой системе интервалы времени между поступлением требований Ait А2,... являются независимыми и одинаково распределенными случайными величинами. («Одинаково распределенные» означает, что интервалы времени между поступлением требований имеют одинаковое распределение вероятностей.) Когда требование поступает, а устройство свободно, обслуживание начинается немедленно. Время обслуживания Sb S2,... следующих требований представлено независимыми одинаково распределенными случайными величинами, на которые не влияют интервалы времени обслуживания. Если при поступлении требования устройство занято, требование становится в очередь. По завершении обслуживания требования устройство выбирает требование из очереди (если такая имеется) по принципу FIFO (First-In, First-Out -- «первым пришел -- первым обслужен»).

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

Для того чтобы определить критерии оценки работы системы, обратимся к трем параметрам их характеристики. Прежде всего найдем ожидаемую среднюю задержку в очереди для каждого из п требований, завершивших свое ожидание во время моделирования; эту величину обозначим как d(n). Слово «ожидаемая» в определении d(n) означает, что при заданном прогоне имитационной модели (или при заданном прогоне действительной системы, которую представляет имитационная модель) средняя задержка, наблюдаемая для п-то числа требований, зависит от полученных наблюдений случайных переменных, обозначающих время между поступлениями требований и время обслуживания. При следующем прогоне имитационной модели (или на второй день -- с реальной системой) требования будут прибывать в другие моменты времени, и необходимое время обслуживания также будет иным. Это приведет к получению другого среднего значения задержки для п требований. Следовательно, при прогоне имитационной модели среднее значение задержки требования в очереди также считается случайной величиной. Нам же необходимо установить ожидаемое значение случайной величины. Согласно одной интерпретации d(ri) является средним огромного (фактически бесконечного) числа средних задержек в очереди и-го числа требований. После одного прогона имитационной модели, при котором зафиксированы задержки требований в очереди di, D2, ..., Dn, очевидной оценкой d(n) является формула

представляющая среднее время Д и-го числа задержек, которое наблюдалось при моделировании (поэтому d(n)1 может быть также обозначено как D (п)). Следует отметить, что говоря о времени задержки, мы не исключаем возможности того, что оно будет равно 0 в случае поступления требования в момент, когда система находится в состоянии незанятости (в этой модели нам точно известно, что di = 0).

Время задержки, равное 0, учитывается в среднем, поскольку большое количество таких случаев, когда время задержки равно 0, указывает на то, что система предоставляет надлежащее обслуживание, и наши выходные оценки критериев работы должны это отражать. Одна из причин того, что мы берем среднее значение задержек Ц, а не рассматриваем каждую из них по отдельности, состоит в том, что их распределение не будет одинаковым, и среднее является единым показателем времени задержки всех требований в очереди. В данном контексте речь не идет об обычном «среднем» базовой статистики, так как отдельные слагаемые не являются независимыми случайными наблюдениями одного и того же распределения. Также обратим внимание на то, что d(n) -- это оценка, основанная на выборке размера «1», поскольку мы выполняем только один полный прогон имитационной модели. Из элементарной статистики нам известно, что выборка размера 1 не имеет большой статистической ценности.

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

Таким образом, нам нужно определить среднее по времени число требований в очереди. С этой целью число требований в момент времени t (для любого вещественного числа t >0) мы обозначим как (20п. а время, необходимое для наблюдения п-то числа задержек в очереди, как Т(п). Тогда для любого времени t между 0 и Т(п) значение 20п будет неотрицательным целым числом. Далее, пусть Pi - ожидаемая часть (имеющая значение от 0 до 1) времени, когда (20п равно г, тогда приемлемым определением q(n) будет

Таким образом, q(n) является взвешенным средним возможных значений z для очереди длиной Q(t), при этом весовые коэффициенты являются ожидаемой частью времени, которое расходуется на каждую из своих возможных длин очереди. Чтобы определить q(ri), заменяем значения р их оценками и получаем

где pi является частью времени, измеряемой (а не ожидаемой) в процессе моделирования, когда число требований в очереди равнялось г. Однако для вычисления q (и) удобнее переписать формулу, используя некоторые геометрические методы. Пусть Т{ будет суммарным временем в течение моделирования очереди длиной i, тогда Т(п) = Т1 + ti + T2 + ... и pi = Tt/T(n). В результате приведенное выше уравнение (1.1) мы можем переписать как

На рис. 3 показано возможное течение времени или реализация Q(t) в системе при условии, что п = б (на данном этапе не следует учитывать штриховку прямоугольников). Требования прибывают в моменты времени, равные 0,4; 1,6; 2,1; 3,8; 4,0; 5,6; 5,8 и 7,2. Уход требований (завершение обслуживания) происходит в моменты времени, равные 2,4; 3,1; 3,3; 4,9 и 8,6. В момент времени, когда Г(6) = = 8,6, моделирование завершается.

Обращаясь к рис. 3, имейте в виду, что Q(t) не учитывает требование, находящееся на обслуживании (если таковое есть), и в период времени между 0,4 и 1,6 очередь будет отсутствовать (Q(t)= 0), хотя при этом одно требование находится на обслуживании. То же самое касается периодов времени с 3,1 по 3,3, с 3,8 по 4,0 и с 4,9 по 5,6. Но в период времени с 3,1 по 3,3 требования отсутствуют вообще, и система находится в состоянии незанятости, как и в период времени с 0 по 0,4.

Рис. 3. Q(f), время поступления и время ухода в реализации системы массового обслуживания с одним устройством обслуживания

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

Таким образом, коэффициент й(«) можно выразить как часть времени, когда В(Ј) = 1. На рис. 4 изображен график функции B(t) для реализации процесса моделирования, использованного на рис. 3.

Результат указывает на то, что в ходе моделирования 90 % времени устройство занято. Но числитель в формуле может также рассматриваться как площадь под функцией B(t), так как высотаВ(Ј) всегда равна либо 0, либо 1.

Рис. 4. B(t), время поступления и время ухода в реализации системы массового обслуживания с одним устройством обслуживания

Итак, три критерия оценки работы системы включают: среднюю задержку в очереди d(n); среднее по времени число требований в очереди q(n); часть времени, когда устройство обслуживания находится в состоянии занятости й(п). Средняя задержка требования в очереди является статистикой дискретного времени, поскольку она определяется относительно ряда случайных переменных {D,}, которые имеют индекс дискретного времени i = 1, 2,.... Среднее по времени число требований в очереди и часть времени, когда устройство обслуживания находится в состоянии занятости, -- это примеры статистики непрерывного времени, поскольку они определяются относительно совокупности случайных переменных {Ј>(Ј)} и {5(0} соответственно, каждая из которых индексируется по параметру непрерывного времени t & [0, <х>). (Символ е означает «содержащийся». Таким образом, в этом случае t может быть любым не отрицательным вещественным числом.) Как статистика дискретного времени, так и статистика непрерывного времени часто используются в моделировании, при этом они позволяют получить не только средние показатели. Например, нам могут понадобиться значения либо максимальной наблюдаемой задержки в очереди (статистика дискретного времени), либо части времени в ходе моделирования, когда в очереди насчитывалось, как минимум, пять требований (статистика непрерывного времени).

События в этой системе: поступление требования и его уход (после завершения обслуживания). Переменными состояния, необходимыми для оценки d(n), q(n) и и(п), являются состояние устройства обслуживания (0 -- состояние незанятости, 1 -- состояние занятости); число требований в очереди; время поступления каждого требования, находящегося на данный момент в очереди (представлено в виде списка); время последнего события. Время последнего события, определенное как ем, если е^ <t<e{ (где t -- текущее время при моделировании), требуется для вычисления ширины прямоугольников при суммировании площадей в оценках q(n) и и(п).

4.1 Интуитивное объяснение

Для объяснения процесса моделирования системы массового обслуживания с одним устройством обслуживания рассмотрим вначале, как имитационная модель будет представлена в компьютере в моменты времени е0 = 0 и е2, ..., е13, когда происходит 13 последовательных событий, необходимых для наблюдения заданного числа задержек требований в очереди п = 6. Для удобства примем, что время между поступлениями и время обслуживания требований равны:

ai = 0,4;Л2 =1,2; Л3 =0,5; Л4 =1,7; А5 =0,2; А6 =1,6;Л7 =0,2; Л8 =1,4; А, =1,9 ...;

5t =2,0;52=0,7; 53=0,2;54=1,1;55=3,7;56=ОД ...

Так, между моментом времени 0 и моментом поступления первого требования проходит 0,4 единицы времени, между поступлением первого и второго требований -- 1,2 единицы времени и т. д. Время, необходимое для обслуживания первого требования, равно 2 единицам времени и т. д. Нет необходимости задавать сами единицы времени (минуты, часы и т. п.), необходимо только, чтобы все значения времени выражались в одних и тех же единицах. В реальном моделировании значения Аі и Si генерируются из соответствующих им распределений вероятностей (по мере необходимости) в процессе моделирования. Приведенные числовые значения Ai и Sі выбраны так, чтобы можно было сгенерировать реализацию моделируемой системы, изображенную на рис. 3 и 4, демонстрирующих процессы Q(t) и В(Ј).

Литература

1. Петров П.К. - Моделирование - М. «Протон» - 2002 г.

2. Карков И.С. - Физика элементарных частиц. - М. - 1999 г.

3. Синджанов И.К. Электродинамика - М. 1998 г.

4. Электротехнические материалы. Справочник / В.Б. Березин, Н.С. Прохоров, А.М. Хайкин. - М.: Энергоатомиздат, 1993. - 504с.

5. Рычина Т.А., Зеленский А.В. Устройства функциональной электроники и электрорадиоэлементы . - М.: Радио и связь, 1999. - 352с.

6. Имитационное моделирование - под ред. Ткаченоков С.В. - М. 2006 г.

7. Моделирование процессов - Шабов И.К. - 2000 г.