33.Принцип Дельта t построения моделирующих алгоритмов.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Рассмотрим пример. Моделируется склад изделий с максимальной емкостью
(см.
рис.
32.1).
Рис.
32.1. Схема моделируемой производственной системы (пример)
Склад принимает изделия от трех поставщиков (обозначим но
мера входных потоков
изделий 1, 2, 3) и выдает их трем потребителям (обозначим номера выходных потоков
изделий 4, 5, 6). Примем в качестве характеристики каждого входа интенсивность
потока изделий (
). Интенсивность характеризует в среднем расстояние между двумя
моментами времени приходов (уходов) изделий на склад. Обозначим через
размер
партии изделий, уходящих или приходящих на склад. То есть этими переменными мы
определили, когда и сколько прихо
дит или уходит изделий на тот или иной вход или
выход склада (
блок 1
здесь и далее см. блоки на рис.
32.2).
Обозначим переменной
текущее количество изделий на складе. Если изделия приходят
на склад (потоки 1, 2, 3), то
увеличивается на
или
. Если изделия изымаются со
склада (потоки 4, 5, 6), то
уменьшается на
или
. То есть
играет роль счетчика
изделий, находящихся на складе в отдельный момент времени
. Начальное состояние
склада на момент
0 примем
Алгоритм постро
им таким образом, чтобы вычислить вероятности событий
возникновения дефицита
и переполнения
на складе.
Для накопления надежной статистики эксперимент повторяется
раз. За количеством
экспериментов следит счетчик экспериментов
блоки 2, 3, 8
). Каждый эксперимент
длится от 0 до
момента времени (
блоки 5, 7
). Счетчик времени
отсчитывает время от
0 до
с дискретностью Δ
блок 11
).
В каждом эксперименте подсчитывается, сколько раз на складе в результате действия
входных сигналов
(количество поставленных и изъятых изделий) возникает ситуация
дефицита (
блок 13
). За этим следит счетчик
, если на складе возникает ситуация
блок 13
), значит, возникает дефицит изделий для обработки и счетчик увеличивает свое
значение на 1 (
блок 1
). Если дефицит не возникает
0, то счетчик своего значения не
меняет.
Поскольку всего может быть рассмотрено
тактов, то вероятность
возникновения дефицита может быть примерно оценена частостью возникновения этих
событий как
или с учетом того, что счетчик
накапливался в течении
экспериментов, то
. Окончательно, подставляя
блоки
). Расчет вероятности переполнения склада моделируется аналогично (учитывается,
что переполнение возникает
, когда
становится больше емкости склада
блоки 15, 19
).
Заметим, что поскольку на складе в реальности не может быть изделий меньше нуля, то
значение
в момент обнаружения этого факта должно быть возвращено на ближайшую
границу, то есть:
блок 16
). Тоже самое касается ситуации переполнения (
блок 19
).
Алгоритм представляет сбой цикл по времени от 0 до
с шагом Δ
моделирование
производится во времени. В каждом цикле (на каждом такте времени) проверяется, лежит
ли сгенерированно
событие в интервале времени [
]:
блок 12
).
Если событие происходит в данный момент, то определяется, какой
ый входной сигнал
предопределил это событие (
блоки 22, 10
), обрабатывается ситуация (
блок 17 или 18
) и
генерируется в
ремя следующего события (
блоки 20, 21
). Проверка на каждом такте
происходит по всем возможным входным и выходным сигналам.
Блок
схема алгоритма показана на рис.
Рис.
32.2. Блок
схема алгоритма, реализованного по принципу Δt.
Пример
моделирование производственного склада
Принцип особых состояний
Назовем состояние, в котором обычно находится система, обычным состоянием. Такие
состояния интереса не представляют, хотя занимают большую часть времени.
Особые состояния
это такие состояния в изолированные моменты времени, в которых
характеристики системы изменяются скачкообразно. Для изменения состояния системы
нужна определенная причина, например, приход очередного входного сигнала. Ясно, что с
точки з
рения моделирования интерес представляет именно изменение характеристик
системы, то есть принцип требует от нас отслеживать моменты перехода системы из
одного особого состояния в другое.
По сравнению с предыдущим случаем, мы не будем проверять изменение с
остояния
системы в каждый момент времени. Выберем среди будущих моментов только те, в
которые происходит поступление или уход изделий со склада, ближайший к текущему
моменту времени (
блок 7
здесь и далее см. блоки на рис.
32.3). Определив такой
момент, с
разу перейдем в него скачком, изменив значение счетчика времени на величину
Ln(
блок 18
). В остальном, алгоритм похож на предыдущий. Заметим только, что
цикл опроса входных сигналов ликвидирован, поскольку
блок 7
четко отвечает на вопрос,
какой из
ых сигналов имел место.
Все это существенно экономит время моделирования.
Блок
схема алгоритма показана на рис.
Рис.
32.3. Блок
схема алгоритма, реализованного по принципу особых состояний.
Пример
модел
ирование производственного склада
Принцип последовательной проводки заявок
Принцип состоит в том, что каждая заявка отслеживается от момента поступления ее в
систему до момента ее выхода из системы. И только потом рассматривается следующая
заявка.
Рассмотрим работу алгоритма на примере двухканальной системы массового
обслуживания заявок с двумя местами в общей очереди с дисциплиной FIFO и отказами
при переполнении очереди (см. рис.
32.4), см. также
лекцию 30
Рис.
32.4. Схема системы массового обслуживания
с двумя каналами и ограниченной очередью
Обозначим:
интенсивность прихода заявки;
интенсивность обслуживания
заявки.
Построим алгоритм, определяющий вероятности обслуживания заявок и отказа заявок, а
также пропускную способность системы.
Чтобы понять работу алгоритма, представьте себе для наглядности параллельные линейки
оси времени для каждого из мест, в которых може
т оказаться заявка в процессе
обслуживания
так, как мы это делали ранее (см.
лекцию 30
).
Генерируем заявку (
блоки 3, 4
здесь и далее см. блоки на рис.
32.6). Случайный
момент времени, когда заявка пришла в систему, равен
. Время между двумя
случайными заявками имитируется формулой
Ln(
), которое прибавляется к
предыдущей заявки
Ln(
). У
чтем этот факт в счетчике пришедших заявок
блок 4
).
Последовательно сравниваем
в порядке приоритетов (
блоки 5, 6, 7, 8
) с временами
освобождения
канала 1, канала 2
, места в очереди 1
, места в очереди 2
. Как только обнаруживается факт того, что место в системе свободно (см. рис.
30.5):
, или
, или
, или
, так немедленно переводим заявку на
свободное место и имитируем обработку ее на этом месте.
Рис.
32.5. Механизм
определения освобождения канала
(иллюстрация)
Допустим, что освободилось место в первом канале. Обработка состоит в том, что
вычисляется время простоя этого канала до прихода заявки (например,
), и это
время прибавляется в счетчик времен простоя (
блок 15
). Вычисляется следующее время
изменения состояния канала
модифицируется переменная
, которая укажет нам в
дальнейшем, когда снова освободится канал. Величина
изменяется на величину
Ln(
время обслуживания, отсчитываемую от на
чала обслуживания
. Счетчик
обслуженных заявок
об
увеличивается на единицу.
Аналогично обработка происходит и во втором канале, если заявка попадет именно туда
блок 14
).
Особенность обработки заявки в очереди состоит в том, что первое место в очереди
освобождается, когда освобождается место в одном из каналов, конечно, заявка уходит
туда, где место освобождается раньше (
блоки 5, 6
). Второе место в очереди
освобождается одновременно с первым, так как заявка в очереди передвигается на первое
освободивше
еся место (
блок 12
).
Далее алгоритм генерирует в цикле следующую заявку (
блоки 3, 16
). Остановка
моделирования происходит тогда, когда каждая линейка будет заполнена до момента
блок 16
). После этого происходит обработка статистических результатов, нак
опленных в
счетчиках (
блок 17
). Вероятность оценивается частостью появления события, которая
вычисляется как отношение количества появившихся событий к количеству возможных
таких появлений.
Блок
схема алгоритма показана на рис.
Рис.
Блок
схема алгоритма, реализованного по принципу последовательной
проводки заявок. Пример
моделирование системы массового обслуживания
И, конечно, надо помнить, что чем больше время моделирования, тем точнее будет
вычисленный результат.
Имеет смысл нап
омнить еще раз, что необходимо наблюдать за поведением
статистической характеристики, какой, например, является
об
. Ранее (см.
лекцию 21
лекцию 34
) мы отмечали, что статистическая величина меняется в зависимости от
времени наблюдения. Как только статистическая величина перестает меняться в пределах
объявленной точности, то есть кривая входит в коридор, отведенный ей т
очностью, то это
сигнализирует о достаточности количества экспериментов.
Необходимо внимательно следить, чтобы все искомые переменные вошли в интервал
объявленной точности, только тогда можно прекратить моделирование и быть уверенным
в результате.
Для по
вышения эффективности алгоритма (уменьшения времени его работы) можно
отбросить нехарактерную часть реализации
обычно это начальный участок работы
системы, «выход ее на режим».
Заметим также, что не важно, имеем ли мы дело с одной длинной реализацией ил
и с
большим количеством коротких реализаций (у которых, конечно, вырезан участок «выход
на режим»), в сумме дающих реализацию такой же длины
статистический результат
будет тем же. Это рассуждение устанавливает равенство усреднений по ансамблю
реализаций
усреднениям по времени.
Примечание
. На практике обычно применяют комбинации всех трех методов.
Объектный принцип моделирования
Как правило, алгоритмы, спроектированные по первым трем принципам, плохо
модернизируются. А производственная ситуация часто меняется и требует
соответствующих моделей для нахождения рациональных решений в процессе
управления.
Таким образом, возникла необх
одимость в приемах моделирования, обеспечивающих
независимость составления моделей элементов сложной системы от изменения задачи или
структуры производства. Такой подход моделирования отдельных объектов независимо
друг от друга
позволяет собирать сколь уго
дно сложные системы без изменения их
составляющих
. Принцип объектного моделирования обеспечивает модернизацию
сложных систем, удлиняя жизненный цикл АСУ.
Пример. СМО состоит из следующих элементов, существующих самих по себе: источник
заявок, очередь, кан
ал (см. рис.
36.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
// передаем заявку из очереди в канал
// флаг, фиксирующий освобождение места в очереди в момент
// освобождения канала, если очередь есть
// 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экс
Данные модели могут собираться в любые конфигурации без изменения их содержания.

Приложенные файлы

  • pdf 15893017
    Размер файла: 210 kB Загрузок: 0

Добавить комментарий