Лекция 32.
Общие принципы построения
моделирующих алгоритмов

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

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

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

В настоящий момент известны четыре основных принципа регламентации событий.

1. Принцип Δt («дельта-тэ»).
2. Принцип особых состояний.
3. Принцип последовательной проводки заявок.
4. Принцип параллельной работы объектов (объектный принцип моделирования).

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

Принцип Δt

Принцип состоит в том, что алгоритмом моделирования имитируется движение, то есть изменение состояния системы, в фиксированные моменты времени: t, t + Δt, t + 2Δt, t + 3Δt, …

Для этого заводится счетчик времени (часы), который на каждом цикле увеличивает свое значение t на величину шага во времени Δt, начиная с нуля (начало моделирования). Таким образом, изменения системы отслеживаются такт за тактом в заданные моменты: t, t + Δt, t + 2Δt, t + 3Δt, …

Особенности реализации принципа Δt

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

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

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

Рассмотрим пример. Моделируется склад изделий с максимальной емкостью G (см. рис. 32.1).

Рис. 32.1. Схема моделируемой производственной системы (пример)

Склад принимает изделия от трех поставщиков (обозначим номера входных потоков изделий 1, 2, 3) и выдает их трем потребителям (обозначим номера выходных потоков изделий 4, 5, 6). Примем в качестве характеристики каждого входа интенсивность i-го потока изделий (λ_i). Интенсивность характеризует в среднем расстояние между двумя моментами времени приходов (уходов) изделий на склад. Обозначим через P_i размер партии изделий, уходящих или приходящих на склад. То есть этими переменными мы определили, когда и сколько приходит или уходит изделий на тот или иной вход или выход склада (блок 1 — здесь и далее см. блоки на рис. 32.2).

Обозначим переменной Z текущее количество изделий на складе. Если изделия приходят на склад (потоки 1, 2, 3), то Z увеличивается на P₁, P₂ или P₃. Если изделия изымаются со склада (потоки 4, 5, 6), то Z уменьшается на P₄, P₅ или P₆. То есть Z играет роль счетчика изделий, находящихся на складе в отдельный момент времени t. Начальное состояние склада на момент t := 0 примем Z := Z₀.

Алгоритм построим таким образом, чтобы вычислить вероятности событий возникновения дефицита P_д и переполнения P_п на складе.

Для накопления надежной статистики эксперимент повторяется KK раз. За количеством экспериментов следит счетчик экспериментов k (блоки 2, 3, 8). Каждый эксперимент длится от 0 до T_k момента времени (блоки 5, 7). Счетчик времени t отсчитывает время от 0 до T_k с дискретностью Δt (блок 11).

В каждом эксперименте подсчитывается, сколько раз на складе в результате действия входных сигналов (количество поставленных и изъятых изделий) возникает ситуация дефицита (блок 13). За этим следит счетчик D, если на складе возникает ситуация Z < 0 (блок 13), значит, возникает дефицит изделий для обработки и счетчик увеличивает свое значение на 1 (блок 16). Если дефицит не возникает Z ≥ 0, то счетчик своего значения не меняет.

Поскольку всего может быть рассмотрено N := T_k/Δt тактов, то вероятность возникновения дефицита может быть примерно оценена частостью возникновения этих событий как P_д := D/N или с учетом того, что счетчик D накапливался в течении KK экспериментов, то P_д := D/N/KK. Окончательно, подставляя N: P_д := D · Δt/T_k/KK (блоки 4, 6). Расчет вероятности переполнения склада моделируется аналогично (учитывается, что переполнение возникает, когда Z становится больше емкости склада G) (блоки 15, 19).

Заметим, что поскольку на складе в реальности не может быть изделий меньше нуля, то значение Z в момент обнаружения этого факта должно быть возвращено на ближайшую границу, то есть: Z := 0 (блок 16). Тоже самое касается ситуации переполнения (Z := G) (блок 19).

Алгоритм представляет сбой цикл по времени от 0 до T_k с шагом Δt — моделирование производится во времени. В каждом цикле (на каждом такте времени) проверяется, лежит ли сгенерированное T_i событие в интервале времени [T, T + Δt]: T ≤ T_i < T + Δt (блок 12). Если событие происходит в данный момент, то определяется, какой i-ый входной сигнал предопределил это событие (блоки 22, 10), обрабатывается ситуация (блок 17 или 18) и генерируется время следующего события (блоки 20, 21). Проверка на каждом такте происходит по всем возможным входным и выходным сигналам.

Блок-схема алгоритма показана на рис. 32.2.

Рис. 32.2. Блок-схема алгоритма, реализованного по принципу Δt. Пример — моделирование производственного склада

Принцип особых состояний

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

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

По сравнению с предыдущим случаем, мы не будем проверять изменение состояния системы в каждый момент времени. Выберем среди будущих моментов только те, в которые происходит поступление или уход изделий со склада, ближайший к текущему моменту времени (блок 7 — здесь и далее см. блоки на рис. 32.3). Определив такой момент, сразу перейдем в него скачком, изменив значение счетчика времени на величину (–Ln(r)/λ_i) (блок 18). В остальном, алгоритм похож на предыдущий. Заметим только, что цикл опроса входных сигналов ликвидирован, поскольку блок 7 четко отвечает на вопрос, какой из i-ых сигналов имел место.

Все это существенно экономит время моделирования.

Блок-схема алгоритма показана на рис. 32.3.

Рис. 32.3. Блок-схема алгоритма, реализованного по принципу особых состояний. Пример — моделирование производственного склада

Принцип последовательной проводки заявок

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

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

Рис. 32.4. Схема системы массового обслуживания с двумя каналами и ограниченной очередью

Обозначим: λ — интенсивность прихода заявки; μ_i — интенсивность обслуживания заявки.

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

Чтобы понять работу алгоритма, представьте себе для наглядности параллельные линейки — оси времени для каждого из мест, в которых может оказаться заявка в процессе обслуживания — так, как мы это делали ранее (см. лекцию 30).

Генерируем заявку (блоки 3, 4 — здесь и далее см. блоки на рис. 32.6). Случайный момент времени, когда заявка пришла в систему, равен T_с. Время между двумя случайными заявками имитируется формулой τ := –1/λ · Ln(r), которое прибавляется к T_с предыдущей заявки T_с := T_с – 1/λ · Ln(r). Учтем этот факт в счетчике пришедших заявок N (блок 4).

Последовательно сравниваем T_с в порядке приоритетов (блоки 5, 6, 7, 8) с временами освобождения T₁ канала 1, канала 2 — T₂, места в очереди 1 — T₃, места в очереди 2 — T₄. Как только обнаруживается факт того, что место в системе свободно (см. рис. 30.5): T_с > T₁, или T_с > T₂, или T_с > T₃, или T_с > T₄, так немедленно переводим заявку на свободное место и имитируем обработку ее на этом месте.

Рис. 32.5. Механизм определения освобождения канала (иллюстрация)

Допустим, что освободилось место в первом канале. Обработка состоит в том, что вычисляется время простоя этого канала до прихода заявки (например, T_с – T₁), и это время прибавляется в счетчик времен простоя (блок 15). Вычисляется следующее время изменения состояния канала — модифицируется переменная T₁, которая укажет нам в дальнейшем, когда снова освободится канал. Величина T₁ изменяется на величину τ := –1/μ₁ · Ln(r) — время обслуживания, отсчитываемую от начала обслуживания T_с. Счетчик обслуженных заявок N_об увеличивается на единицу.

Аналогично обработка происходит и во втором канале, если заявка попадет именно туда (блок 14).

Особенность обработки заявки в очереди состоит в том, что первое место в очереди освобождается, когда освобождается место в одном из каналов, конечно, заявка уходит туда, где место освобождается раньше (блоки 5, 6). Второе место в очереди освобождается одновременно с первым, так как заявка в очереди передвигается на первое освободившееся место (блок 12).

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

Блок-схема алгоритма показана на рис. 30.6.

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

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

Имеет смысл напомнить еще раз, что необходимо наблюдать за поведением статистической характеристики, какой, например, является P_об. Ранее (см. лекцию 21, лекцию 34) мы отмечали, что статистическая величина меняется в зависимости от времени наблюдения. Как только статистическая величина перестает меняться в пределах объявленной точности, то есть кривая входит в коридор, отведенный ей точностью, то это сигнализирует о достаточности количества экспериментов.

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

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

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

Примечание. На практике обычно применяют комбинации всех трех методов.

Объектный принцип моделирования

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

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

Пример. СМО состоит из следующих элементов, существующих самих по себе: источник заявок, очередь, канал (см. рис. 36.7). Смоделируем их по отдельности.

Рис. 32.7. Схема реализации объектно-ориентированного моделирования (на примере СМО)

1. Источник заявок (Sourcer) генерирует последовательность случайных событий.

2. Канал обслуживания (Channel).

3. Очередь (Queue).

4. Статистика (Stats).

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