Оглавление
Л 29   Л 30   Л 31   Л 32   Л 33   Л 34   Л 35

Лекция 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. Схема моделируемой производственной системы (пример) ]
Рис. 32.1. Схема моделируемой производственной системы (пример)

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

Обозначим переменной Z текущее количество изделий на складе. Если изделия приходят на склад (потоки 1, 2, 3), то Z увеличивается на P1, P2 или P3. Если изделия изымаются со склада (потоки 4, 5, 6), то Z уменьшается на P4, P5 или P6. То есть Z играет роль счетчика изделий, находящихся на складе в отдельный момент времени t. Начальное состояние склада на момент t := 0 примем Z := Z0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[ Рис. 32.4. Схема системы массового обслуживания с двумя каналами и ограниченной очередью ]
Рис. 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) с временами освобождения T1 канала 1, канала 2 — T2, места в очереди 1 — T3, места в очереди 2 — T4. Как только обнаруживается факт того, что место в системе свободно (см. рис. 30.5): Tс > T1, или Tс > T2, или Tс > T3, или Tс > T4, так немедленно переводим заявку на свободное место и имитируем обработку ее на этом месте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// если счетчик x равен 0, то это момент появления заявки
// tau — обеспечивает генерацию времени между заявками в момент появления заявки
tau := –1/λ · ln(rnd) · delta(x) + tau · not(delta(x))

// y — фиксирует факт появления заявки
y:= delta(x)

// счетчик моделирует заявочный процесс во времени, отсчитывая время между заявками
// если счетчик x равен 0, то это момент появления заявки
// если x больше нуля, то новая заявка пока не появилась
x := x + ed(~tau – x) · dt – x · ed(x – ~tau )

// счетчик заявок
Nx := Nx + delta(~x)

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

// канал свободен, если не обрабатывает заявку
своб := not(обраб)

// своб — флаг-признак, если канал свободен, то «своб» равен 1.
// обраб — флаг-признак, если канал занят, то «обраб» равен 1.
// Если канал был свободен, и пришла заявка, то канал начинает ее обрабатывать.
обраб := ed(~своб · вх + not(delta(y))

// вх — сигнал о подаче заявки на обслуживание в канале
// tau — обеспечивает генерацию необходимого времени обслуживания заявки в момент ее появления
// Новая генерация происходит только в том случае, если канал свободен и пришла заявка
// Если в канале обслуживается заявка, то новое tau не генерируется
// mu — интенсивность потока обслуживания (задается константой)
tau := –1/mu · ln(rnd) · ~своб · ~вх + tau · not(delta(~y))

своб: = not(~обраб)

// счетчик «y» моделирует заявочный процесс во времени, отсчитывая время обслуживания
// если «y» выдал 1, то значит канал выдал обслуженную заявку
y := y + ed(~tau – ~y) · dt – ~y · ed(~y – ~tau)

// счетчик обслуженных заявок
Ny := Ny + delta(~y)

// флаг «обработка» будет погашен, если закончится время обслуживания
обраб := not(delta(~y))
// канал будет свободен, если канал не обрабатывает заявки
своб := not(~обраб)

// счетчик накапливает статистику — общее время простоя канала
ОВП := ОВП + ~своб · dt

// счетчик накапливает статистику — общее время работы канала
ОВР := ОВР + ~обраб · dt

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

// «отказ» — счетчик фиксирует отказ, если все места в очереди заняты (Z > Zm)
// и приходит очередная заявка (вх = 1)
// Zm — максимальное количество мест в очереди
// Z — текущее количество занятых мест
отказ := ~отказ + delta(~вх – 1) · ed(~Z – Zm + 1)

// счетчик количества занятых мест в очереди увеличивается, если приходит
// заявка и есть незанятые места в очереди
Z := Z + delta(~вх – 1) · ed(Zm – Z)

// передаем заявку из очереди в канал
// флаг, фиксирующий освобождение места в очереди в момент
// освобождения канала, если очередь есть
// ch_free — флаг (свободен (1) или занят канал обслуживания (0))
вых := delta(~ch_free – 1) · ed(~Z)

// счетчик уменьшает количество занятых мест в очереди,
// после взятия заявки в канал обслуживания
Z := Z – ~вых

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

Tэкс := Tэкс + 1 · dt
проп_сп := Nоб/Tэкс
Pоб := Nоб/Nобщ
Pотк := Nотк/Nобщ
Tпрост1 := Tпрост1 + ~своб1 · dt
Tпрост12 := Tпрост12 + ~своб1 · ~своб2 · dt
Tпрост123 := Tпрост123 + ~своб1 · ~своб2 · ~своб3 · dt
ср_кол_пр_КО := Tпрост1 + Tпрост12 · 2 + Tпрост123 · 3
ср_кол_зан_КО := всего_КО – ср_кол_пр_КО
S := S + ~тек_дл_очер · dt
ср_дл_очер := ~S/Tэкс

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


[ ] Лекция 31. Исследование функционирования СМО… Лекция 33. Моделирование марковских случайных… [ ]
Л 29   Л 30   Л 31   Л 32   Л 33   Л 34   Л 35