МДК 02.01 Разработка, внедрение и адаптация ПО отраслевой направленности
Оценка 4.8

МДК 02.01 Разработка, внедрение и адаптация ПО отраслевой направленности

Оценка 4.8
doc
12.05.2020
МДК 02.01 Разработка, внедрение и адаптация ПО отраслевой направленности
Вероятностные модели систем.doc

Лекция 6.

 

Вероятностные модели систем

 

 

I. Вероятностные автоматы (дискретно-стохастические модели)

 

Основные соотношения. Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе на вероятностных (стохастических) автоматах Р-схемах (англ. probabijistic automat).

Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi, zs), где xi и zs – элементы входного подмножества Х и подмножества состояний Z соответственно. Если существуют две такие функции j и y, что с их помощью осуществляются отображения G®Z и G®Y, то говорят, что F = <Z, X, Y, j, y> определяет автомат детерминированного типа.

Рассмотрим более общую математическую схему. Пусть Ф – множество всевозможных пар вида (zk, yi), где уi – элемент выходного подмножества Y. Потребуем, чтобы любой элемент множества G индуцировал на множестве Ф некоторый закон распределения следующего вида:

Элементы из Ф

(z1, y2)

(z1, y2)    

. . .

(zk, yJ-1)

(zK, yJ)

(xi, zs)

b11

b12

. . .

bK(J-1)

bKJ

При этом bkj = 1, где bkj – вероятности перехода автомата в состояние zk и появления на выходе сигнала yj , если он был в состоянии zs и на его вход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P = <Z, X, Y, B> называется вероятностным автоматом (Р-автоматом).

 

 

Возможные приложения P-схемы. Пусть элементы множества G индуцируют некоторые законы распределения на подмножествах Y и Z, что можно представить соответственно в виде:

Элементы из Y

y1

y2

. . .

yJ-1

yJ

(xi, zs)

q1

q2

. . .

qJ-1

qJ

Элементы из Z

z1

z2

. . .

zK-1

zK

(xi, zs)

z1

z2

 

zK-1

zK

При этом zk = 1 и qj = 1, где zk  и qj  - вероятности  перехода Р-автомата в состояние zk и появления выходного сигнала yk при условии, что Р-автомат находился в состоянии zs и на его вход поступил входной сигнал xi.

Если для всех k и j имеет место соотношение qj zk = bkj, то такой Р-автомат называется вероятностным автоматом Мили. Это требование означает выполнение условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.

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

Элементы из Y

y1

y2

. . .

yK-1

yK

zk

s1

s2

. . .

sI-1

sI

Здесь si = 1, где si – вероятность появления выходного сигнала yi при условии, что Р-автомат находился в состоянии zk.

Если для всех k и i  имеет  место  соотношение   zk si = bki ,то такой Р-автомат называется вероятностным автоматом Мура. Понятие Р-автоматов Мили и Мура введено по аналогии с детерминированным F-автоматом. Частным случаем Р-автомата, задаваемого как P=<Z, X, Y, B>, являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминированно. Если выходной сигнал Р-автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным.

Пример 1. Пусть задан Y-детерминированный P-автомат

               

На рис. 1 показан ориентированный граф переходов этого автомата. Вершины графа сопоставляются состояниям автомата, а дуги – возможными переходами из одного состояния в другое. Дуги имеют веса, соответствующие вероятностям перехода pij, а около вершин графа пишутся значения выходных сигналов, индуцируемых этими состояниями. Требуется оценить суммарные финальные вероятности пребывания этого P-автомата в состояниях z2 и z3.

 

 

 

 

 

 

 

 

Рис. 1. Граф вероятностного автомата.

 

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

Таким образом, с2 + с3 = 13/23 = 0,5652. Другими словами, при бесконечной работе заданного в этом примере Y-детерминированного Р-автомата на его выходе формируется двоичная последовательность с вероятностью появления единицы, равной 0,5652. Вероятностные автоматы используются в формальных моделях процессов обучения, в моделях сложного поведения, когда реакция автомата неоднозначна.

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

Р (закр закр, S2) = Р (откр закр, S2) = 0;

Р (откр откр, S2) = Р (закр откр, S2) = 1;

Р (откр откр, S1) = 0,7;

Р (откр закр, S1) = 0,3;

Р (закр закр, S1) = 0,5;

Р (закр откр, S1) = 0,5.

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

 

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

 

II. Системы массового обслуживания (непрерывно-стохастические модели)

 

Основные соотношения. Особенности непрерывно-стохастического подхода рассмотрим на примере типовых математических Q-схем – систем массового обслуживания (англ. queueing system).

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

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью {tn} = {0 £ t1 £ t2 ... £ tn £ }, где tn момент наступления п-го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между п-м и (n – 1)-м событиями {tn}, которая однозначно связана с последовательностью вызывающих моментов {tn}, где tn = tn tn-1, п ³ 1, t0 = 0, т.е. t1 = t1.

Потоком неоднородных событий называется последовательность {tn, fn}, где tn вызывающие моменты; fnнабор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого i-го прибора обслуживания Пi (рис. 2), состоящего из накопителя заявок Hi, в котором может одновременно находиться ji =  заявок, где LiH емкость i-гo накопителя, и канала обслуживания заявок (или просто канала) Ki. На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi, на канал Ki поток обслуживаний иi .

 

 

 

 

 


Рис. 2. Прибор обслуживания заявок

 

Заявки, обслуженные каналом Ki, и заявки, покинувшие прибор Пi по различным причинам необслуженными (например, из-за переполнения накопителя Hi), образуют выходной поток yi Î Y, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Обычно, поток заявок wiÎW, т.е. интервалы времени между моментами появления заявок на входе Ki, образует подмножество неуправляемых переменных, а поток обслуживания uiÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.

 

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

Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементов во времени zi(t). Переход в новое состояние для Пi означает изменение количества заявок, которые в нем находятся (в канале Ki и в накопителе Hi). Таким образом, вектор состояний для Пi имеет вид: , где ziH – состояние накопителя Hi (ziH = 0 – накопитель пуст, ziH = 1 – в накопителе имеется одна заявка, ..., ziH = LiH накопитель полностью заполнен); LiH емкость накопителя Нi, измеряемая числом заявок, которые в нем могут поместиться; zikсостояние канала Ki (zik = 0канал свободен, zik = 1 – канал занят).

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

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

Собственными (внутренними) параметрами Q-схемы будут являться количество фаз Lф, количество каналов в каждой фазе Lkj, j = , количество накопителей каждой фазы LHk, k = , емкость i-го накопителя LiH. Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию для систем массового обслуживания: системы с потерями (LiH = 0, т.е. накопитель в приборе Пi отсутствует, а имеется только канал обслуживания Кi), системы с ожиданием (LiH®¥, т.е. накопитель Нi имеет бесконечную емкость и очередь заявок не ограничивается) и системы смешанного типа (с ограниченной емкостью накопителя Нi). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.

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

В зависимости от динамики приоритетов в Q-схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя Нi на обслуживание каналом Кi, можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi, ожидает окончания обслуживания предшествующей заявки каналом Ki и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Hi, прерывает обслуживание каналом Кi заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из Кi заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Hi).

При рассмотрении алгоритмов функционирования приборов обслуживания Пi (каналов Кi и накопителей Нi) необходимо также задать набор правил, по которым заявки покидают Нi и Кi: для Нi – либо правила переполнения, по которым заявки в зависимости от заполнения Нi покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Нi, для Кi – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале Кi или не допускаются до обслуживания каналом Кi, т.е. правила блокировок канала. При этом различают блокировки Ki по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок A.

Таким образом, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задается в виде Q = <W, U, Н, Z, Y, R, A>.

Возможности оценки характеристик с использованием аналитических моделей теории массового обслуживания являются весьма ограниченными. Несравненно большими возможностями обладают имитационные модели, позволяющие исследовать Q-схему, задаваемую Q = <W, U, Н, Z, Y, R, A> без ограничений. На работу с Q-схемами при машинной реализации моделей ориентированы многие языки имитационного моделирования, например SIMULA, SIMSCRIPT, GPSS и др.

 


Скачано с www.znanio.ru

Лекция 6. Вероятностные модели систем

Лекция 6. Вероятностные модели систем

Возможные приложения P -схемы

Возможные приложения P -схемы

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

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

Таким образом, с 2 + с 3 = 13/23 = 0,5652

Таким образом, с 2 + с 3 = 13/23 = 0,5652

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

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

Потоком неоднородных событий называется последовательность { t n , f n } , где t n – вызывающие моменты; f n – набор признаков события

Потоком неоднородных событий называется последовательность { t n , f n } , где t n – вызывающие моменты; f n – набор признаков события

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

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

L Hk , k = , емкость i -го накопителя

L Hk , k = , емкость i -го накопителя

Н i , для К i – правила выбора маршрутов или направлений ухода

Н i , для К i – правила выбора маршрутов или направлений ухода
Скачать файл