Схемы обработки информации. СхемыОбрабИнф. Тема Схемы обработки информации
 Скачать 477.38 Kb.
|
Тема Схемы обработки информацииНепрерывно-детерминированные модели (D-схемы) В качестве математических моделей в D-схемах (от английского dynamic) используются дифференциальные уравнения. Дифференциальными уравнениями называются такие уравнения, в которых неизвестными будут функции одной или нескольких переменных, причем в уравнение входят не только функции, но и их производные различных порядков. Если неизвестные – функции многих переменных, то уравнения называются уравнениями в частных производных, в противном случае при рассмотрении функций только одной независимой переменной уравнения называются обыкновенными дифференциальными уравнениями. Обычно в таких математических моделях в качестве независимой переменной, от которой зависят неизвестные искомые функции, служит время t. Тогда математическое соотношение для детерминированных систем в общем виде будет Задачей системы является изменение выходной переменной (выходного сигнала) y(t) согласно заданному закону с определенной точностью (с допустимой ошибкой). При проектировании и эксплуатации систем автоматического управления необходимо выбрать такие параметры системы, которые обеспечили бы требуемую точность управления, а также устойчивость системы в переходном процессе. Если система устойчива, то представляет практический интерес поведение системы во времени, максимальное отклонение регулируемой переменной у (t) в переходном процессе, время переходного процесса и т. п. Выводы о свойствах систем автоматического управления различных классов можно сделать по виду дифференциальных уравнений, приближенно описывающих процессы в системах. Порядок дифференциального уравнения и значения его коэффициентов полностью определяются статическими и динамическими параметрами системы Дискретно-детерминированные модели (F- схемы) При использовании такого рода моделей система представляется в виде автомата, перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. Автомат можно представить как некоторое устройство (черный ящик), на которое подаются входные сигналы и снимаются выходные и которое может иметь некоторые внутренние состояния. Конечным автоматом называется автомат, у которого множество внутренних состояний и входных сигналов (а следовательно, и множество выходных сигналов) являются конечными множествами. Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами:
выходов Ψ(z, х). Автомат, задаваемый F-схемой, функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени. Изменение состояния автомата и выходного сигнала может произойти только в тактовые моменты. Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z (t), подается некоторый сигнал х(t), на который он реагирует переходом в (t+1)-м такте в новое состояние z (t+1) и выдачей некоторого выходного сигнала. Это можно описать следующими уравнениями: Различают два вида конечных автоматов. Приведенные выше уравнения описывают работу автомата первого рода, называемого также автоматом Мили. Задание конечного автомата Мили табличный способ с помощью графа Для F-автомата второго рода Автомат второго рода, для которого функция выходов не зависит от входной переменной х(t) называется автоматом Мура. Для него По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу х(t) определенный выходной сигнал у(t ) . Чтобы задать конечный F-автомат, необходимо описать все элементы множества F = (Z, X, Y, Φ, Ψ ), т. е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Причем среди множества состояний необходимо выделить состояние z0, в котором автомат находился в момент времени t = 0. Существуют несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный. Простейший табличный способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы — его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию z0. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение Φ(zk, xi) функции переходов, а в таблице выходов — соответствующее значение Ψ(zk, xi ) функции выходов. Для F-автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием zk автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию выходной сигнал Ψ (zk). При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi с вершиной zj, отмечается сигналом xk. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами Ψ(zi, xk ). Для автомата Мура выходные сигналы связаны только с состояниями и поэтому значениями Ψ(zk) отмечают соответствующие вершины графа. Задание конечного автомата Мура табличный способ с помощью графа Дискретно-стохастические модели (Р-схемы) В общем виде вероятностный автомат (англ. probabilistic automat) можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически. Сущность дискретизации времени при этом подходе остается аналогичной рассмотренным ранее конечным автоматам, но при этом добавляется влияние фактора стохастичности. Применение схем вероятностных автоматов (Р-схем) имеет важное значение для разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение, для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования, а также для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям. Для того, чтобы задать вероятностный автомат надо, как и для конечного автомата определить множество входных сигналов, множество выходных сигналов и множество внутренних состояний. Описание процесса функционирования автомата осуществляется путем задания ряда распределений вероятностей. Рассмотрим множество G пар и множество D пар Для задания вероятностного автомата надо определить для каждой пары из множества G вероятности перехода автомата в состояние zk и появления на выходе сигнала yh : Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество таких распределений как B. Тогда совокупность множеств Z, X, Y, B определяет вероятностный автомат. Это наиболее общий случай. Если распределения для нового состояния Р-автомата и его выходного сигнала независимы, то это вероятностный автомат Мили. Для его задания надо определить множества распределений Число таких распределений равно числу элементов множества G. Говорят, что задан вероятностный автомат Мили, если заданы два распределения вероятностей Где при этом распределения для q и p независимы. Вероятностный автомат Мура имеет место, если определение выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы, а элементы из Z определяются как у автомата Мили. Детерминированные автоматы это частный случай Р-автомата. Также частными случаями являются Y – детерминированный и Z – детерминированные автоматы. Если выходной сигнал Р - автомата определяется детерминировано, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р - автомат, у которого выбор нового состояния является детерминированным. Марковский случайный процесс Пусть имеется некоторая система, состояние которой может меняться с течением времени. Если состояние меняется случайным, непредсказуемым образом, будем говорить, что в системе протекает случайный процесс. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы: S1, S2, S3, ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система скачком (мгновенно) переходит из одного состояния в другое. Случайный процесс называется процессом с дискретным временем, если переходы из состояния в состояние возможны только в строго определенные моменты времени. В промежутках между этими моментами система сохраняет свое состояние. Случайный процесс называется процессом с непрерывным временем, если переход системы из состояния в состояние возможен в любой наперед неизвестный, случайный момент. Случайный процесс, протекающий в системе, называется марковским процессом (цепь Маркова) или процессом без последействия, если для каждого момента времени ti вероятность любого последующего состояния системы зависит только от текущего состояния и не зависит от того, когда и каким путем система пришла в это состояние (т.е. от того, как развивался процесс в прошлом). Иными словами, воздействие всей предыстории процесса на его будущее полностью сосредоточено в текущем значении процесса. Отсюда следует, что цепь Маркова должна обладать свойством отсутствия последствия. Это означает, что вероятность перехода в следующее состояние не должна зависеть от того, сколько времени процесс пребывал в текущем состоянии. При моделировании систем, в которых случайные события, приводящие к изменению состояний, могут происходить только в моменты времени, отстоящие друг от друга на величину, кратную значению тактового интервала Т (дискретно – стохастические модели), для описания интервалов времени между событиями используют регулярный просеянный поток. Его можно получить, удаляя в регулярном потоке события с вероятностью q и оставляя с вероятностью 1-q. Просеянный поток иногда называют дискретным пуассоновским, так как его свойства аналогичны для моментов времени, кратных периоду Т, свойствам простейшего потока. К просеянному регулярному потоку приводит, например регулярный поток данных, передаваемый по каналам связи с контролем наличия сбоев в передаваемом коде и исправлением путем повторной передачи. Вероятность того, что величина интервала между событиями в просеянном потоке окажется равным i тактам: Это выражение соответствует геометрическому распределению. Математическое ожидание и среднее квадратическое отклонение для интервала времени между событиями в таком потоке равны соответственно: Если число состояний системы конечно и из каждого состояния можно перейти (за то или иное число шагов) в любое другое, то существуют предельные (финальные) вероятности состояний, которые не зависят от времени и начального состояния системы. Сумма предельных вероятностей всех состояний системы равна единице: Таким образом, при t ∞ в системе устанавливается некоторый предельный стационарный режим, который состоит в том, что система случайным образом меняет свои состояния, но вероятность каждого из них уже не зависит от времени. Эта вероятность представляет собой не что иное, как относительное время пребывания системы в данном состоянии. При моделировании систем процесс их функционирования удобно представлять в виде графа, вершинами которого являются состояния Si, а направленные дуги описывают переходы между состояниями. Если процесс является марковским и известны вероятности переходов из состояния в состояние, то вероятности состояний Pi могут быть найдены исходя из того, что вероятность любого состояния Si равна сумме произведений вероятностей состояний Sj, из которых есть переход в данное состояние на вероятности этих переходов pji , т.е Рассмотрим на примере эту процедуру. Система может находиться в одном из трех состояний: S1, S2 или S3. Систему уравнений для определения вероятностей состояний: Попытка решить эту систему непосредственно неизбежно приведет к тождеству. Но решение существует и может быть получено, если воспользоваться нормировочным уравнением P1 + P2 + P3 = 1. Если подставить его вместо одной из строк системы, то можно будет получить значение вероятностей состояний. Рассмотрим пример исследования вычислительного узла с использованием аппарата Марковской дискретной цепи. Из памяти макрокоманд (МК) по синхросигналу через каждые два такта в арифметико-логическое устройство (АЛУ) считываются макрокоманды. Если АЛУ готово принять макрокоманду, она обрабатывается, иначе макрокоманда загружается в регистровую память (РП) объемом n ячеек (мест ожидания) и ожидает освобождения АЛУ. При полном заполнении РП макрокоманда блокируется в памяти макрокоманд и процесс дальнейшей выборки приостанавливается. Интервалы времени обработки макрокоманд в АЛУ случайны и имеют геометрическое распределение с параметром , т.е. с вероятностью (1- ) обработка макрокоманды в АЛУ по окончании очередного тактового интервала завершится, а с вероятностью продлится еще на один интервал. При построении и исследовании модели будем пользоваться представлением данного устройства как системы массового обслуживания (СМО). Т.к. поток обслуживаний представляет собой просеянный регулярный поток, то процесс будет марковским, и мы можем определить финальные вероятности состояний этой системы. Будем определять состояние системы трехкомпонентным вектором: jt1t2. Комбинаторная составляющая этого вектора j - количество заявок, находящихся в накопителе (длина очереди), j = 0,1,2,...n. Временная составляющая t1 – число тактов, оставшихся до появления заявки на выходе источника (t1=0, 1, 2). Значение 0 означает, что источник заблокирован. Составляющая t2 определяет состояние канала обслуживания (АЛУ) и может принимать два значения: t2 = 0 - канал свободен; t2 =1 - канал занят обслуживанием заявки. Построим граф система уравнений для стационарных (финальных) вероятностей состояний Pjt1t2. Выполнив преобразования получим, что сумма - это сумма геометрической прогрессии Используя полученное значение p (фактически, это вероятность простоя АЛУ) и рассчитав вероятности всех остальных состояний, можно найти другие интересующие нас характеристики системы. а) Cреднее время обслуживания заявки системой в целом (время пребывания заявки в системе) S. б) Интенсивность потока обработанных заявок (абсолютная пропускная способность): где (1-p) – вероятность того, что канал обрабатывал заявку, (1-) – вероятность того, что обработка закончилась. в) Средняя длина очереди Непрерывно – стохастические модели (Q – схемы) Особенностью непрерывно – стохастического подхода при моделировании систем и процессов является использование в качестве типовых математических схем систем массового обслуживания (англ. Queueing system). Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания. Системы массового обслуживания. Потоки событий Реальные системы могут быть представлены при моделировании как системы массового обслуживания (СМО), если при их функционировании можно выделить два процесса - поступление заявок на обслуживание и обслуживание заявок. Таким образом могут быть представлены различные по своей физической природе процессы – экономические, технические, производственные и т.п. Для описания работы СМО используется понятие поток событий последовательность событий, происходящих одно за другим в некоторые моменты времени. В СМО будем выделять три потока: – входной поток: множество моментов времени поступления в систему заявок; – поток обслуживаний: множество моментов времени окончания обработки системой заявок в предположении, что обслуживание осуществляется непрерывно; – выходной поток: последовательность моментов времени ухода из системы обслуженных заявок. СМО состоит из какого-то числа обслуживающих единиц, которые называются каналами обслуживания. В зависимости от количества каналов СМО могут быть одноканальными и многоканальными. СМО могут быть двух типов. 1.СМО с отказами. В таких системах заявка, поступившая в момент, когда все каналы заняты, получает отказ и покидает систему не обслуженной. 2.СМО с ожиданием. Заявка, заставшая все каналы занятыми, становится в очередь и ожидает освобождения одного из каналов. Число мест в очереди m может быть как неограниченным, так и ограниченным. В первом случае заявка может стать в очередь в любой момент, в то время как во втором она вынуждена покинуть систему, если очередь превышает заданную длину в момент прихода заявки или в процессе ожидания. Порядок выборки заявок из очереди определяется дисциплиной обслуживания. Некоторые наиболее употребляемые дисциплины: 1) FIFO (first in – first out) – в порядке поступления; 2) LIFO (last in – first out) – первой обслуживается заявка, поступившая последней; 3) SIRO (service in random order) – обслуживание в случайном порядке; 4) приоритетные системы – заявки обслуживаются в соответствии с их приоритетами. Наиболее часто на практике используются следующие правила. 1) Каналы занимаются в порядке их номеров. Канал с большим номером не может быть привлечен к обслуживанию заявки, если имеется свободный канал с меньшим номером. 2) Каналы занимаются в порядке очереди. Освободившийся канал поступает в очередь и не начинает обслуживания заявок до загрузки всех ранее освободившихся каналов. 3) Каналы занимаются в случайном порядке в соответствии с заданными вероятностями. Реальный процесс функционирования системы массового обслуживания для удобства исследования можно представлять в виде последовательности отдельных актов (фаз) обслуживания, выполняемых различными устройствами. При этом, как правило, соблюдается такой порядок, при котором следующее устройство может приступить к обслуживанию заявки лишь тогда, когда работа предыдущего с данной заявкой полностью закончена. В частном случае обслуживание может быть однофазным. Характеристики СМО существенно зависят от вида и параметров входного потока и потока обслуживаний. Поток событий называется однородным, если он характеризуется только моментами наступления событий и задается последовательностью , где Поток событий является неоднородным, если он задается последовательностью где tn – моменты наступления событий, а fn – набор признаков событий (приоритеты, принадлежность тому или иному источнику, тип канала для его обслуживания и т. д.). Поток регулярный, если события поступают через равные промежутки времени. Поток нерегулярный, если интервалы между событиями представляют собой случайные величины. Если промежутки времени между последовательными событиями представляют собой независимые, одинаково распределенные случайные величины, поток называется рекуррентным (поток Пальма, поток с ограниченным последействием). Для краткой характеристики СМО Д. Кендалл ввел символику (нотацию): Где: s - число обслуживающих приборов; m – количество мест ожидания (если не указано, то считается, что m=0, т.е. это система с отказами); при неограниченной очереди в качестве m ставят символ ; k – количество источников заявок. Если k отсутствует, то по умолчанию количество источников предполагается равным одному. A и B характеризуют соответственно: поток требований и поток обслуживания, задавая функцию распределения интервалов между заявками во входном потоке и функцию распределения времен обслуживания. А и В могут принимать значения: D – детерминированное распределение; М – показательное; Еr – распределение Эрланга порядка r; Hr - гиперпоказательное; G – распределение общего вида. При этом подразумевается, что потоки являются рекуррентными, т.е. интервалы между событиями независимы и имеют одинаковое распределение. Обязательными в этой нотации являются первые три позиции. Простейший поток Простейшим называется поток, обладающий следующими тремя свойствами: стационарность, ординарность и отсутствие последействия. Поток является стационарным, если вероятность наступления заданного числа событий в течение интервала времени фиксированной длины зависит только от продолжительности интервала и не зависит от его расположения на временной оси. Иначе говоря, вероятностные характеристики и интенсивность такого потока со временем не изменяются. Поток является ординарным, если вероятность появления двух или более событий в течение элементарного интервала времени Δt→0 есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале. Другими словами, два и более событий в таком потоке произойти одновременно не могут. Поток называется потоком без последействия, если для любых неперекрывающихся интервалов времени число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Иногда это свойство формулируют следующим образом: распределение времени до ближайшего события не зависит от времени наблюдения, т.е. от того, сколько времени прошло после последнего события. Отсутствие последействия в потоке означает, что события, образующие поток появляются в последовательные моменты времени независимо друг от друга. Для простейшего потока число событий, попадающих на любой фиксированный интервал времени подчиняется закону Пуассона, поэтому его иначе называют стационарным пуассоновским. Вероятность того, что за интервал времени в простейшем потоке произойдет ровно m событий Где λ – интенсивность, т.е. среднее число событий в единицу времени. Вероятность того, что в течении интервала времени не произойдет не одного события Вероятность того, что за это время произойдет хотя бы одно событие При построении и анализе непрерывно – стохастических моделей исследуются вероятности появления или не появления событий в течении элементарного интервала времени Δt→0. Функция распределения вероятностей и функция плотности вероятностей имеют вид: Математическое ожидание и среднее квадратическое отклонение для T: Одной из числовых характеристик для потоков является коэффициент вариации – отношение среднего квадратичного к математическому ожиданию: Для реальных потоков значение этого коэффициента лежит в пределах от 0 до 1. Коэффициент вариации характеризует степень стохастичности, непредсказуемости потока. Для регулярного потока с равными интервалами между событиями = 0. Для простейшего потока = 1, то есть этот поток является наиболее стохастичным среди всех потоков. Простейший поток обладает следующими особенностями: 1. Сумма М независимых, ординарных, стационарных потоков заявок с интенсивностями λi (i = 1, ..., М) сходится к простейшему потоку с интенсивностью, равной сумме интенсивностей исходных потоков при условии, что складываемые потоки оказывают приблизительно одинаково малое влияние на суммарный поток. Сходимость суммарного потока к простейшему осуществляется очень быстро. Практически можно считать, что сложение четырех-пяти стационарных, ординарных, независимых потоков, сравнимых по интенсивности, достаточно для того, чтобы суммарный поток был близок к простейшему. Таким образом, для выяснения всех свойств суммарного потока достаточно знать лишь интенсивности суммируемых потоков и практически не требуется знать внутреннюю структуру этих потоков. Простейший поток обладает устойчивостью, состоящей в том, что при суммировании независимых простейших потоков получается снова простейший поток, причем интенсивности складываемых потоков суммируются. 2. Поток заявок, полученный путем случайного разрежения исходного потока, когда каждая заявка с определенной вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, образует простейший поток с интенсивностью где λ — интенсивность исходного потока. В отношении исходного потока заявок делается предположение лишь об ординарности и стационарности. 3. Для простейшего потока характерно, что поступление заявок через короткие промежутки времени более вероятно, чем через длинные,— 63% промежутков времени между заявками имеют длину, меньшую среднего периода 1/λ. Следствием этого является то, что простейший поток по сравнению c другими видами потоков создает наиболее тяжелый режим работы системы. Поэтому предположение о том, что на вход системы поступает простейший поток заявок, приводит к определению предельных значений характеристик качества обслуживания. Если реальный поток отличен от простейшего, то система будет функционировать не хуже, чем это следует из полученных оценок. 4. Интервал времени между произвольным моментом времени и моментом поступления очередной заявки имеет такое же распределение с тем же средним M[] = 1/λ, что и интервал времени между двумя последовательными заявками. Эта особенность простейшего потока является следствием отсутствия последействия. Выходные потоки обычно имеют последствие, даже если входные потоки им не обладают. Пример СМО с фиксированным временем обслуживания обсл Если в момент t1 на выходе появилась обслуженная заявка, то на интервале (t1, t1+ обсл) заявка не появится. Непрерывные марковские цепи Уравнения Колмогорова Рассмотрим некоторую физическую систему с дискретными состояниями S1, S2, ..., Sn , которая переходит из состояния в состояние под влиянием каких-то случайных событий. Если все потоки, переводящие систему из состояния в состояние, пуассоновские, то процесс, протекающий в системе, будет марковским. Пуассоновский поток обладает отсутствием последействия, поэтому, при заданном состоянии системы в заданный момент, ее переходы в другие состояния в будущем обусловлены только появлением каких-то событий в пуассоновских потоках, а вероятности появления этих событий не зависят от предыстории процесса. Процессы в системах с дискретными состояниями и непрерывным временем называются непрерывными марковскими цепями. Рассмотрим систему, для которой при исследовании P – схем мы полагали входной поток детерминированным и поток обслуживания просеянным (интервалы времени обслуживания подчинялись геометрическому распределению). Будем считать, что входной поток простейший с Интенсивностью λ, а поток обслуживания – пуассоновский с интенсивностью μ. Число мест ожидания в очереди ограничено и равно n. Согласно нотации Кендалла мы можем определить вид такой системы как СМО M / M / 1 / n с блокировкой источника. Состояние системы будем определять числом заявок, находящихся в данный момент в системе. Таким образом, всего возможны n+3 состояния: 1. от 0 до n+2. Если число состояний системы конечно и из каждого состояния можно перейти (за то или иное число шагов) в любое другое, то существуют предельные (финальные) вероятности состояний, которые не зависят от времени и начального состояния системы. Обозначим Ri (t) – вероятность прихода за время Δt i заявок, а Ri'( t) – вероятность обслуживания за Δt i заявок. Тогда вероятность перехода системы из состояния s в состояние s +1 за время Δt (увеличения числа заявок в системе на 1) будет равняться Ввиду ординарности потоков слагаемыми, начиная со второго, можно пренебречь и, подставив в формулу соответствующие вероятности, получаем Вероятность подтверждения состояния 0 равна вероятности того, что за время Δt в систему не поступит ни одной новой заявки: В состоянии n+2 источник заблокирован и заявки в систему не поступают, поэтому вероятность того, что за время Δt изменения состояния не произойдет, равна вероятности не обслуживания заявки: Граф состояний для системы Построим по графу систему уравнений для вероятностей состояний. Преобразуем эту систему и получим при левая часть есть не что иное, как производная от Р0 (t) : Таким образом, наша система превратилась в систему дифференциальных уравнений, которая носит название системы уравнений Колмогорова. Если число состояний системы конечно и из каждого состояния можно перейти (за то или иное число шагов) в любое другое, то существуют предельные (финальные) вероятности состояний, которые не зависят от времени и начального состояния системы. После проведения преобразований система будет выглядеть так: Важность полученного результата заключается в том, что от системы дифференциальных уравнений мы перешли к системе алгебраических уравнений, которую можно достаточно просто решить и получить значения вероятностей состояний. Преобразуем её, начиная со второго и заканчивая предпоследним уравнением – новое уравнение получаем сложением старого с новым предыдущим и заменяя им старое значение. В результате, новое предпоследнее уравнение будет совпадать со старым последним уравнением, и все строки будут иметь вид: Введем обозначения Используем уравнение нормировки: Это сумма геометрической прогрессии. Поэтому Зная Р0, можно рассчитать значения вероятности всех остальных состояний. Определим некоторые показатели эффективности работы системы так, как это было сделано для дискретно-стохастической модели. Cреднее время пребывания заявки в системе где m – среднее время обслуживания заявки каналом, равное 1/μ , Робсл – вероятность того, что канал обслуживает заявку, равная 1-р. Отсюда Средняя длина очереди Диаграмма интенсивностей переходов Исследуя систему М/M/1/n с блокировкой, получаем искомые результаты, используя следующую последовательность действий: - построение графа Марковской цепи; - определение вероятностей переходов; - построение системы дифференциальных уравнений; - переход к системе алгебраических уравнений; - решение системы и получение вероятностей состояний. Построим вместо графа марковского процесса диаграмму интенсивностей переходов (ДИП), в которой овалами обозначим состояния, а дугами переходы между ними. Будем кодировать состояния числом заявок, находящихся в данный момент в системе. Дугам приписываются числа, соответствующие интенсивностям переходов (а не вероятностям, как это было ранее). В такой диаграмме нет петель, т.е. дуг из состояния Sкв это же состояние. Когда переходы осуществляются только в соседние состояния, говорят о процессе «размножения и гибели» и соответственно об интенсивностях, с которыми может увеличиваться или уменьшаться количество заявок в системе. Эта диаграмма содержит, по сути, ту же информацию, что и граф сети Маркова. Построим для этой диаграммы алгебраические уравнение для вероятностей состояний, исходя из закона сохранения потоков вероятностей: сумма входящих потоков вероятностей для любого состояния равна сумме исходящих из него потоков. В данном случае мы будем понимать под термином “поток вероятности” произведение вероятности состояния на интенсивность перехода из этого состояния. Для состояния с номером i ДИП имеет два входных потока вероятностей: – от состояния i -1, равный Pi-1; – от состояния i +1, равный Pi+1. Выходные потоки для этого состояния: – к состоянию i -1, равный Pi ; – к состоянию i +1, равный Pi ; Так как сумма входящих потоков вероятностей для состояния равна сумме исходящих из него потоков, получаем Для процессов «размножения и гибели» выписывание алгебраических уравнений для вероятностей состояний можно еще больше упростить, если воспользоваться следующим правилом: встречные потоки вероятностей через сечение диаграммы равны между собой. Например, для сечения между состояниями i и i+1 это выражается равенством Формула Литтла Формула Литтла используется для системы с неограниченной очередью между некоторыми характеристиками системы. Эта формула связывает для предельного (стационарного режима работы) среднее число заявок, находящихся в СМО Lc и среднее время пребывания заявки в системе Wc. Рассмотрим произвольную СМО (одноканальную, многоканальную, марковскую, немарковскую и т.д.). Если интенсивность поступления заявок, поступающих в систему будет меньше, чем интенсивность обработки этих заявок каналом, то установится стационарный (предельный) режим работы системы, когда среднее число прибывающих за единицу времени заявок равно среднему числу заявок, покидающих СМО (т.е. оба потока – входной и выходной будут иметь одну и ту же интенсивность ). Введем в рассмотрение две функции: X(t) и Y(t), значениями которых будут являться соответственно число заявок, поступивших к моменту t в систему и число заявок, покинувших систему к этому моменту Обе функции случайны, меняются скачком на 1 при приходе или окончании обслуживания очередной заявки соответственно. Число заявок, находящихся в СМО в момент t равно: Рассмотрим очень большой промежуток времени Т и вычислим для него среднее число заявок, находящихся в СМО. Это среднее значение функции Z(t) интервале T: Можем заменить этот интеграл суммой площадей и записать: Умножим и разделим это выражение на : T - это количество заявок, поступивших в систему за время Т, а ti представляет собой суммарное время пребывания всех этих заявок в системе. Следовательно, отношение ti к T является средним временем пребывания заявки в СМО, т.е. Wc. Окончательно: Аналогично выводится соотношение где Lоч – средняя длина очереди, Wоч - среднее время пребывания заявки в очереди. Эти формулы носят название формул Литтла и позволяют при анализе систем по значению L находить W и наоборот. Исследование СМО с помощью диаграмм интенсивностей переходов Задачи теории массового обслуживания — нахождение вероятностей различных состояний СМО, а также установление зависимости между заданными параметрами (числом каналов n, интенсивностью потока заявок λ, распределением времени обслуживания и т. д.) и характеристиками эффективности работы СМО. В качестве таких характеристик могут рассматриваться: – среднее число заявок А, обслуживаемое СМО в единицу времени, или абсолютная пропускная способность СМО; – вероятность обслуживания поступившей заявки Q или относительная пропускная способность СМО: – вероятность отказа Ротк т.е вероятность того, что поступившая заявка не будет обслужена, получит отказ: – среднее число заявок в СМО (обслуживаемых или ожидающих в очереди) Lc; – среднее число заявок в очереди Loч; – среднее время пребывания заявки в СМО (в очереди или под обслуживанием) Wс; – среднее время пребывания заявки в очереди Wоч; – среднее число занятых каналов k . Имитационное моделирование Условия применения имитационного моделирования Множество математических моделей можно разбить на три подмножества: аналитические, имитационные и комбинированные (аналитико-имитационные) модели. Аналитической моделью (AM) называется совокупность функциональных соотношений или логических условий, описывающих связи между параметрами, переменными и показателями эффективности системы S. Область применения AM: 1) сравнительно простые системы; 2) системы, получаемые в результате упрощения (абстрагирования) реальных систем с целью изучения некоторых свойств системы. Достоинства AM: универсальность, высокая степень общности и значимости результатов; Недостатки AM: 1) чувствительность к степени сложности системы; 2) ряд допущений, приводящих к неадекватности модели реальной системе: − замена реальных потоков событий при моделировании систем простейшими; − использование в качестве дисциплины обслуживания заявок из очереди дисциплины FIFO. 3) при моделировании сетей создание АМ становится практически невозможным при числе узлов в сети больше трех; 4) при использовании АМ невозможно исследование поведения системы при изменении со временем характера и скорости протекания процессов. Имитационной моделью (ИМ) системы называются машинные программы (или алгоритмы), позволяющие имитировать на ЭВМ поведение отдельных элементов системы и связей между ними в течение заданного времени моделирования. Эксперименты на ЭВМ с имитационной моделью называются имитационными (вычислительными) экспериментами. Отличительные особенности ИМ: - при создании ИМ законы функционирования всей системы в целом могут быть неизвестны (достаточно знания алгоритмов, описывающих поведение отдельных элементов системы и связей между ними); - в имитационной модели связи между параметрами и характеристиками системы выявляются, а значения исследуемых характеристик определяются в ходе имитационного эксперимента на ЭВМ. Применение имитационного моделирования целесообразно в следующих случаях: 1)если не существует законченной постановки задачи на исследование и идет процесс познания объекта моделирования; 2)если характер протекающих в системе процессов не позволяет описать эти процессы в аналитической форме; 3)если необходимо наблюдать за поведением системы (или отдельных ее компонентов) в течение определенного периода, в том числе с изменением скорости протекания процессов; 4)при изучении новых ситуаций в системе либо при оценке функционирования ее в новых условиях; 5)если исследуемая система является элементом более сложной системы, другие элементы которой имеют реальное воплощение; 6)когда необходимо исследовать поведение системы при введении в нее новых компонентов; 7)при подготовке специалистов и освоении новой техники (в качестве тренажеров). Область применения ИМ: широкий класс систем практически любой сложности. Достоинства ИМ: - часто единственно возможный метод исследования систем; - возможность исследования системы на различных уровнях ее детализации, определяемых целью исследования; - возможность исследования динамики взаимодействия элементов системы во времени и пространстве параметров системы; - возможность оценивания характеристик системы в определенные моменты времени. Недостатки ИМ: - дороговизна: разработка хорошей ИМ часто обходится дороже создания AM и требует больших временных затрат; - результаты имитационного моделирования обладают меньшей степенью общности по сравнению с AM и не позволяют выявить общие закономерности функционирования классов систем; - не существует надежных методов оценки адекватности ИМ. Теоретической основой метода статистического моделирования систем на ЭВМ являются предельные теоремы теории вероятностей. Множества случайных явлений (событий, величин) подчиняются определенным закономерностям, позволяющим не только прогнозировать их поведение, но и количественно оценивать некоторые средние их характеристики, проявляющие определенную устойчивость. Характерные закономерности наблюдаются также в распределениях случайных величин, которые образуются при сложении множества воздействий. Выражением этих закономерностей и устойчивости средних показателей являются так называемые предельные теоремы теории вероятностей. Теорема Бернулли Если проводится N независимых испытаний, в каждом из которых некоторое событие А осуществляется с вероятностью р, то относительная частота появления события m/N при N сходится по вероятности к р, т. е. при любом > 0 Теорема Пуассона Если проводится N независимых испытаний и вероятность осуществления события А в i -м испытании равна pi, то относительная частота появления события m/N при N сходится по вероятности к среднему из вероятностей pi, т. е. при любом > 0 Теорема Чебышева Если в N независимых испытаниях наблюдаются значения x1, x2, ..., xN случайной величины ξ, то при N среднее арифметическое значение случайной величины сходится по вероятности к ее математическому ожиданию mξ, т. е. при любом > 0 Способы моделирования случайных величин При создании имитационной модели возникает необходимость моделирования различных случайных факторов, к которым относятся случайные величины, случайные события и случайные процессы. Формирование на ЭВМ реализаций случайных объектов любой природы сводится к выработке и преобразованию случайных чисел. На практике используются три основных способа генерации случайных чисел: аппаратный (физический), файловый (табличный) и алгоритмический (программный). Аппаратный способ При этом способе генерации случайные числа вырабатываются специальной электронной приставкой — генератором (датчиком) случайных чисел, служащей в качестве одного из внешних устройств ЭВМ. Таким образом, реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику). В качестве физического эффекта, лежащего в основе таких генераторов чисел, чаще всего используются шумы в электронных и полупроводниковых приборах, явления распада радиоактивных элементов и т. д. Достоинства: - реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству; - не занимается место в памяти машины для хранения больших массивов чисел. Недостатки: - требуется периодическая проверка статистических характеристик последовательностей; - нельзя повторно воспроизводить одни и те же последовательности; - используется специальное устройство и средства его сопряжения с ЭВМ; - необходимы меры по обеспечению стабильности работы генератора. Табличный способ При использовании этого способа случайные числа, оформленные в виде таблицы, помещаются во внешнюю или оперативную память ЭВМ, предварительно сформировав из них соответствующий файл (массив чисел). Однако этот способ получения случайных чисел при моделировании систем на ЭВМ обычно рационально использовать при сравнительно небольшом объеме таблицы и соответственно файла чисел, когда для хранения можно применять оперативную память. Хранение файла во внешней памяти при частном обращении в процессе статистического моделирования не рационально, так как вызывает существенное увеличение затрат машинного времени при моделировании из-за необходимости обращения к внешнему накопителю. Достоинства: - требуется однократная проверка статистических характеристик; - можно повторно воспроизводить последовательности. Недостатки: - запас чисел ограничен; - занимает много места в оперативной памяти или необходимо время на обращение к внешней памяти; - невозможно при проведении эксперимента поменять значения статистических характеристик. Алгоритмический способ Способ получения последовательностей случайных чисел основан на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ. Достоинства: - требуется однократная проверка статистических характеристик; - можно многократно воспроизводить последовательности чисел; - занимает мало места в памяти машины; - не используются внешние устройства. Недостатки: - псевдослучайность чисел; - запас чисел последовательности ограничен ее периодом; - существенные затраты машинного времени. |