Определение вероятности прихода ровно k требований к моменту времени t

Фазы работы GPSS модели

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

4. Аналитические модели в виде СМО.

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

В этих моделях элементы представимы в виде компонентов БП (буферная память) и ОА (обслуживающий аппарат).

Это элемент конвейерной системы. Модель позволяет исследовать систему во временном плане, определить узкие места.

Один ОА может обслуживать только 1 требование в единицу времени. Если есть БП, то систему называют системой с ожиданием и потерями (т.к. БП не бесконечна).

Задать систему в виде модели СМО, значит задать следующее:

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

2.1. задание закона изменения диапазона времени, требуемого для обработки требования в ОА

2.2. задание моментов времени, когда обработка допускается

2.3. задание количества одновременно обрабатываемых требований

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

Входной поток описывают, придавая ему свойства или ограничения.

5. Методы анализа синхронных моделей. Итерационные методы.

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

Математическая модель представляется в виде:

Если Ki=0, то модель называется синхронной. Она позволяет вычислить значения внутренних и выходных переменных на данном такте синхронизации.

Синхронная модель имеет следующие особенности:

1) все переменные в модели представлены в том или ином алфавите (двух-, трех- или пятизначном)

2) физическая природа системе моделирования не сообщается

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

4) для временной оценки вводят модели задержек. Существуют модели с нулевой задержкой, с единичной, со случайной задержкой, с задержкой диапазона по max или min)

Модель представляется в виде системы логических уравнений.

Методы анализа синхронной модели:

1) Метод простой итерации

Задаются начальные значения внутренних и выходных переменных. Далее с учетом начальных значений входных переменных и математической модели рассчитываются значения внутренних и выходных переменных, при этом используются их значения из предыдущей итерации . Как только , то говорят, что итерационный процесс сошелся на j-м шаге.

2) Метод Зейделя.

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

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

6. Применение при имитационном моделировании стандартных числовых атрибутов.

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

Стандартные числовые атрибуты:

- Для приборов:

1) Fj или F$<имя>

2) Fcj или FC$<имя> - счетчик числа значений

3) FRj или FR$<имя> - коэффициент использования в долях 1000

4) FTj или FT$<имя> - среднее время задержки на 1 занятие

- Для очередей:

1) Qj – текущее содержимое

2) QA – среднее содержимое очереди

3) QC – счетчик числа входов

4) QM – максимальное содержимое

5) QT – среднее время пребывания в очереди на основе QC

6) QX – среднее время пребывания без учета нулевых вхождений

7) QZ – счетчик числа нулевых вхождений

- Многоканальные устройства:

1) R – свободная емкость

2) S – текущая емкость

3) SA – среднее содержимое

4) SC – счетчик числа вхожов

5) SR – коэффициент использования в долях 1000

6) SM – максимальное содержимое

7) ST – среднее время задержки на единицу емкости

Получение информации:

Через каждые 100 единиц будет выдаваться информация.

7. Определение вероятности прихода ровно k требований к моменту времени t

Организация входного потока. Свойства простейшего входного потока

Ординарность говорит о том, что в один момент времени или за малый промежуток времени в систему может прийти только одно требование.
Стационарность говорит о том, что вероятность прихода k требований за некоторый интервал времени a, зависит только от величины интервала и не зависит от расположения интервала на оси времени.
Отсутствие последействия говорит о том, что количество требований пришедших в систему за интервал времени (a, a+t) не зависит от того, сколько требований пришло до этого интервала.

Определение вероятности прихода ровно k требований к моменту времени t

- вероятность прихода ровно k требований к моменту времени t.

Определим вероятность не-прихода (или прихода нулевого количества требований) требований к моменту времени t -

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

и Выберем интервал времени , отсюда:

, а значит

При , , а значит и

Однако , значит при ,

Если , для ; то

Разложим в ряд Тейлора: , если мало, то

Теперь можем определить вероятность прихода точно k требований

	k	k-1	k-2	...
				...	k-1	k

Если , то: , тогда

;

Имеем

Получили систему дифференциальных уравнений:

эту систему можно решить методом производящих функций, решением будет - Формула Пуассона.

Мат. ожидание: ,

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

8. Алфавиты моделирования, их свойства.

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

2-значный:

a
b
a*b
a+b
Не a

Переходов в 2-значном алфавите нет.

3-значный:

a
b
a*b
a+b
Не a

Переходы в 3-значном алфавите:

1->0 по 2

0->1 по 2

1->1 по 1

0->0 по 0

5-значный:

a*b

a+b

Не a

Переходы в 5-значном алфавите:

1->0 по 3

0->1 по 4

1->1 по 1

0->0 по0

Моделирование переходов в 3-значном и 5-значном алфавитах проходит в 2 этапа:

1) Вычисляются промежуточные значения входных переменных.

2) Вычисляют промежуточные значения ветвей схемы по уравнениям логической системы.

Статический риск сбоя – переход из 0 в 0 или из 1 в 1 через 2.

Динамический риск сбоя – переход из 1 в 0 или из 0 в 1 через 2.

Выходы: 1) синхронизация 2) тщательный расчет задержек (плохой вариант).

9. Моделирование на функционально-логическом уровне детализации проекта.

Модель представляется в виде: V’=F(V,U)

V’_i -> t+k_i

U,V -> t

V’ - вектор внутренних выходных переменных для момента времени t+k_i

V - вектор внутренних выходных переменных для момента времени t

U – вектор входных переменных

Если k_i 0 то модель асинхронная, если =0 синхронная. Асинхронная модель позволяет получить значения переменных для любого момента времени, то есть построить временную диаграмму.

Синхронная модель позволяет вычислить эти значения только на данном такте синхронизации.

Особенности моделирования:

1) Все переменные в модели представлены в том или ином алфавите ({0,1},{0,1,2},{0,1,2,3,4}) (2 – признак неисправности (риск сбоя), 3 – переход 1->0, 4 – переход 0->1). N значный алфавит используется для N значной логики

2) Физическая природа переменной системе моделирования не сообщается.

3) Моделирование выполняется втечение модельного времени, которое разделяется либо на такты, либо на события. Событие – изменение сигнала хотя бы на одном из входов элемента схемы.

4) Для оценки временных соотношений вводят модели задержек: 0-ая задержка, 1-ая задержка, со случайной задержкой из диапазона, с задан. диапзон. по max-min

10. Имитационное моделирование. Основные и вспомогательные события. Способы представления событий во времени.

В имитационном моделировании известен только входной поток.

Есть 2 независимые случайные величины:

1) Интервал времени между приходами требований в систему

2) Диапазон времени обслуживания в ОА (Обслуживающий Аппарат)

Предмет исследования – определение случайных величин:

1) Кол-во требований пришедших в систему за заданный интервал времени.

2) Кол-во требований сразу поступивших на обработку

3) Кол-во требований ожидавших в очереди

4) Мах длина очереди

5) Средняя длина очереди

6) Среднее время ожидания

7) Загрузка прибора – доля времени обслуживания требований.

Происходящие события делят на:

1) Основные события – такие события, время которых можно запланировать заранее.

2) Вспомогательные события – время наступления зависит от состояния системы, заранее запланировано быть не может.

Основные события	Вспомогательные события
1) Приход требования в систему	1) Планирование прихода следующего требования 2) анализ состояния ОА: 2.1 занят (поступило требов. в очередь) 2.2 свободен (перевод ОА из «свободен» в «занят», определение времени конца обслуживания)
2) Окончание обслуживания	1) Проверка БП 1.1 есть требов. (требов. в ОА, сдвинуть очередь в БП) 1.2 нет требов. (изменить ОА из «занят» в «свободен»)

11. Организация модельного времени.

1) потактное моделирование

Изменение модельного времени (МВ) происходит через определённые промежутки времени, то есть за всё время моделирования МВ принимает ряд фиксированных значений 1∆t,2∆t,3∆t…n∆t. Времени наступления события присваивают значение того интервала на который приходится событие (очевидно, что 2 события попадающие в 1 интервал в модели наступают одновременно). Из этого следует, что если ∆t мало, то выполняется множество лишних вычислений, которые увеличивают время обработки модели. Однако, даже при очень малом ∆t время наступления событий в системе не совпадает с временем наступления событий в модели.

2) событийное моделирование

* - Вычисление тех величин, которые были написаны как зависящие величины.

12. Моделирование неисправностей.

Основной метод выявления неисправности – тестирование. Для получения теста необходимо уметь моделировать неисправность.

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

Среди моделей неисправностей различают частные и общие. К общим относятся константные неисправности (фиксация сигнальных линий в 0 или 1) и перемычки (и/или). Пример обозначения константной неисправности: a/1.

Определения:

Пусть - выходная функция исправной системы, - выходная функция схемы с i-ой неисправностью.

Введем функцию , где - исключающее или.

Функция принимает значение 1, если и различны.

Если F=1, то набор X называют тестом для i-ой неисправности.

Тестовое множество – все тесты для неисправностей

Если , то X – входной набор, который различает i-ую и j-ую константную неисправности, называется динамическим.

Для анализа входных наборов на предмет тестируемости схемы составляют таблицу неисправностей.

13. Методика составления уравнений Чепмана-Колмогорова. (два подхода – в приращениях и в графах)

В приращениях:

– вероятность того, что за время произошло одно событие, так как

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

В силу ординарности входного потока и потока обслуживания получаем:

– вероятность того, что за время прибытий не произошло;

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

Первое уравнение:

Принимается: ,

Уравнения образуют систему Чепмана-Колмогорова. Ее можно решить численными методами. В установившемся режиме левые части равенств обращаются в 0 и переменные не зависят от t. СЛАУ для установившегося режима:

Методом подстановок доказывается, что , для

используя нормировочное равенство получаем

В графах:

Составим уравнения Чепмена-Колмогорова по сокращенному графу состояний. В СГС дуги взвешены интенсивностями переходов между состояниями.

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

S₀ – все каналы свободны

S₁ – занят один канал, остальные свободны

---

S_m₊₁ – заняты все m каналов, одно требование в очереди

---

S_m₊_k – заняты все m каналов, k требований в очереди

Уравнения составляют по формальным правилам:

В левой части каждого уравнения стоит производная вероятности состояния, а в правой части содержится столько членов, сколько стрелок связано с этим состоянием.
Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.
Каждый член равен произведению плотности вероятности перехода (интенсивность), соответствующий данной стрелке, и вероятности того состояния, из которого выходит стрелка.

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

методом математической индукции доказывается, что , где

вероятность потерь:

относительная пропускная способность:

среднее число требований в буфере:

14. Применение конкурентного моделирования

Моделирование неисправностей в логических схемах.

Среди моделей неисправностей различают частные и общие. К общим относятся константные неисправности (фиксация в 0 или 1) и перемычки (и/или). Пример обозначения константной неисправности: a/1.

Конкурентное моделирование.

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

Входы	Выходы элементов	Список пр-х неисправостей	Список выявляемых н.	Список транспортируемых н.
a=0 b=0	c=1			-
d=1 c=1	l=0
f=1 g=0	h=0			-
l=0 h=0	z=0

Список неисправностей, выявляемых на z:

15. Простейший входной поток В СМО. Его свойства.

Входной поток в СМО представлен в виде закона распределения прихода требований в систему (определяет диапазон времени между приходами требований).

Часто представлен в виде диаграммы:

t1 t2 t3 t4

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

Свойства:

1) Одинарности – свойство говорит о том, что в один момент времени, или малый отрезок времени в систему может прийти не более одного требования.

2) Стационарности – говорит о том, что вероятность прихода точно К требований за определённый интервал зависит только от величины интервала и не зависит от его местоположения на оси времени.

3) Отсутствия последствия – кол-во требований, пришедших в систему за некоторый интервал (t,t+∆t) не зависит от числа требований, пришедших до момента t.

Вероятность прихода ровно К требований к моменту времени t: V_k(t).

16. Моделирование с учетом задержек.

Используют следующие модели задержек:

1) модели задержек распространения сигналов

1.1) нулевые задержки 0

1.2) единичные задержки 1

1.3) случайные задержки (неопределенные задержки). Случайные величины из диапазона (min - max)

1.4) распределенные задержки. Распределение общей задержки по элементам

1.5) максиминная (минимаксная) задержка. Эта модель задержки предъявляет наивысшие требования к схеме. При слиянии от последнего блока без слияния и дальше распространяется одна неопределенность, и надо вводить тактирование. Слияние – признак динамического риска сбоя. При использовании этой модели min задержка рассчитывается от минимального значения, max – от максимального. Поэтому зона неопределенности растет при прохождении элементов схемы, до того момента, когда в схеме происходит распространение лишь зоны неопределенности, это говорит о возможности динамического риска сбоя.

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

Сначала проводится моделирование без задержек, затем с максиминной задержкой.

17. Аналитические модели. Конкурентное моделирование.

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

Аналитические модели могут быть исследованы тремя способами:

1. Аналитическим. Получение в общем виде зависимости выходных характеристик от исходных.

2. Численным. Нельзя решить сложные уравнения в общем виде. Результаты получают для конкретных начальных данных.

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

Моделирование неисправностей в логических схемах.

Конкурентное моделирование.

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

Входы	Выходы элементов	Список пр-х неисправостей	Список выявляемых н.	Список транспортируемых н.
a=0 b=0	c=1			-
d=1 c=1	l=0
f=1 g=0	h=0			-
l=0 h=0	z=0

Список неисправностей, выявляемых на z:

18. Анализ в установившемся режиме r-канальной однофазной СМО.

Закон входного потока простейший.

Время обслуживания подчинено экспоненциальному закону с параметром .

Поступающие требования идут в любой свободный аппарат. Если все они заняты, то требование теряется.

Дисциплины выборки нет, т.к. нет памяти.

– интенсивность входного потока требований

– интенсивность обслуживания требований (среднее число обслуживаний в единицу времени)

– параметр обслуживания

k– число требований, r – число обслуживающих устройств

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

Тогда – вероятность того, что в системе в момент времени тоже имеется требований.

– вероятность того, что за время произошло одно событие, так как

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

В силу ординарности входного потока и потока обслуживания получаем:

– вероятность того, что за время прибытий не произошло;

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

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

1. В момент времени 0 требований, а за время нет новых прибытий

2. В момент времени 1 требование, за время нет новых прибытий, и завершилось 1 обслуживание

(1)

Рассмотрим возможные случаи появления события .

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

а при

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

Тогда при получаем

а при такой вариант не рассматривается

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

Тогда при получаем

Вероятность равна сумме вероятностей рассмотренных выше случаев.

Для случая

(2)

Для случая

(3)

Уравнения (1)-(3) образуют систему дифференциальных уравнений (СДУ) Чепмена-Колмогорова. Ее можно решить численными методами. В установившемся режиме левые части равенств обращаются в 0 и переменные не зависят от t. СЛАУ для установившегося режима:

Методом подстановок доказывается, что , для

используя нормировочное равенство получаем

Зная все вероятности состояний p₀, …, p_r _,можно найти характеристики СМО:

вероятность потерь – вероятность того, что все r каналов заняты

относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию

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

19. Однофазная одноканальная СМО с буфером на m сообщений. Методика составления уравнений Колмогорова по графу состояний.

Уравнения составляют по формальным правилам:

В левой части каждого уравнения стоит производная вероятности состояния, а в правой части содержится столько членов, сколько стрелок связано с этим состоянием.
Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.
Каждый член равен произведению плотности вероятности перехода (интенсивность), соответствующий данной стрелке, и вероятности того состояния, из которого выходит стрелка.

Система алгебраических уравнений для установившегося режима.

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

вероятность потерь:

относительная пропускная способность:

среднее число требований в б

Определение вероятности прихода ровно k требований к моменту времени t

Поиск по сайту