«Т.И. Алиев ОСНОВЫ МОДЕЛИРОВАНИЯ ДИСКРЕТНЫХ СИСТЕМ Учебное пособие Санкт-Петербург 2009 2 Алиев Т.И. Основы моделирования дискретных систем. – СПб: СПбГУ ИТМО, 2009. – 363 с. В пособии излагаются математические модели и ...»

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

Производящие функции используются для дискретных, а преобразования Лапласа – для непрерывных случайных величин.

2.4.1. Производящая функция Производящей функцией распределения p k = P( X = k ) дискретной случайной величины X, принимающей неотрицательные целочисленные значения k = 0, 1, 2, K, называется ряд Распределение вероятностей однозначно определяется своей производящей функцией:

На основе производящей функции (2.4) могут быть вычислены начальные и центральные моменты случайной величины, в частности математическое ожидание и дисперсия определяются как независимых случайных величин равна произведению производящих функций слагаемых:

2.4.2. Преобразование Лапласа Преобразованием Лапласа плотности распределения f (x ) неотрицательной непрерывной случайной величины X называется функция Плотность распределения однозначно определяется своим преобразованием Лапласа.

Дифференцируя преобразование Лапласа по s в точке s=0, можно определить начальные моменты случайной величины:

Преобразование Лапласа F * ( s ) суммы независимых случайных величин равно произведению преобразований Лапласа слагаемых:

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

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

• распределение Пуассона;

• геометрическое распределение.

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

• равномерный;

• экспоненциальный;

• Эрланга нормированный;

• гиперэкспоненциальный;

• гиперэрланговский.

2.5.1. Распределение Пуассона Дискретная случайная величина X распределена по закону Пуассона, если вероятность P(X=k) того, что она примет определенное значение xk = k выражается формулой:

где a – некоторая положительная величина, называемая параметром распределения Пуассона.

На рис.2.4 показаны многоугольники распределения Пуассона для трех значений параметра распределения: a=0,5; a=1; a=2.

Производящая функция распределения Пуассона:

2.5.2. Геометрическое распределение Распределение дискретной случайной величины X=k вида где - параметр распределения (0 < < 1), называется геометрическим.

Распределение (2.9) может быть записано в несколько ином виде, если параметр заменить параметром =1-:

На рис.2.5 показаны многоугольники геометрического распределения для трех значений параметра распределения: = 0,2 ; = 0,5 ; = 0,8.

Производящая функция геометрического распределения:

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

1. Определить математическое ожидание, второй начальный момент, дисперсию, коэффициент вариации для пуассоновского и геометрического распределений.

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

Вероятность 2.5.3. Равномерный закон распределения Непрерывная случайная величина Х распределена равномерно в интервале (a; b), где a b;

распределения.

Рис.2.6. Функция и плотность равномерного распределения Задание на самостоятельную работу:

1. Определить математическое ожидание, второй начальный момент, дисперсию, коэффициент вариации и построить график функции и плотности равномерного распределения.

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

1) в интервале (0; b) при условии, что b>0;

2) в интервале (а; 0) при условии, что a Напомним, что представленные числовые характеристики связаны между собой достаточно простыми соотношениями:

2.6. Аппроксимация неэкспоненциальных распределений Как было отмечено в п.2.5.4, экспоненциальное распределение обладает замечательным свойством – свойством отсутствия последействия, благодаря которому оно широко используется при описании случайных процессов, протекающих в моделях массового обслуживания. Свойство отсутствия последействия заключается в следующем (рис.2.12). Если некоторый временной интервал = t1 t 0 представляет собой случайную величину, распределенную по экспоненциальному закону, то интервал = t1 t *, начинающийся от случайного момента времени t1 до завершения данного временного интервала, распределен по тому же экспоненциальному закону с тем же параметром (средним значением = 1 / ). Другими словами, продолжительность интервала не зависит от предыстории, то есть от того, сколько времени уже прошло до момента t *.

Рис.2.12. Свойство отсутствия последействия Это замечательное свойство экспоненциального распределения используется при построении моделей марковских процессов, представляющих собой особый класс случайных процессов, развитие которых не зависит от предыстории процесса (см. п.5.1.2). Благодаря этому для многих моделей массового обслуживания удается достаточно просто получить конечные результаты, в том числе, в виде аналитических зависимостей в явном виде для расчета характеристик исследуемой системы. Поэтому часто при исследовании систем, в которых временные процессы отличаются от экспоненциальных, стремятся свести эти процессы к экспоненциальному представлению.

Напомним, что для экспоненциального закона распределения случайных величин, определённых в области положительных значений 0, коэффициент вариации, описывающий разброс значений случайной величины, равен единице. Если реальные временные интервалы имеют значения коэффициента вариации значительно отличающиеся от единицы, использование экспоненциального распределения может привести к большим погрешностям конечных результатов. В этих случаях в качестве аппроксимирующих функций законов распределений могут использоватьРаздел 2. Элементы теории вероятностей ся вероятностные законы, представляющие собой композицию экспоненциальных распределений, а именно:

• распределение Эрланга и гипоэкспоненциальное распределение, когда коэффициент вариации временного интервала меньше единицы:

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

• математическому ожиданию;

• коэффициенту вариации.

2.6.1. Аппроксимация распределения с коэффициентом вариации 0 > bk +1, так как количество прерываний заявками более высокого приоритета и, следовательно, время ожидания в прерванном состоянии прямо пропорционально зависит от длительности обслуживания заявок данного класса. Вследствие этого, полное время ожидания заявок высокоприоритетного класса, складывающееся из времени ожидания начала обслуживания и времени ожидания в прерванном состоянии, может оказаться больше, чем у заявок класса с низким приоритетом:

wk >> wk +1. Очевидно, что w1 < w2 < K < wH, если длительности

АП АП АП АП АП

обслуживания заявок разных классов связаны соотношением 5. Введение АП по сравнению с ОП приводит к уменьшению среднего времени ожидания самых высокоприоритетных заявок первого класса и к его увеличению для заявок класса H: w1 < w1 и wH > wH.

АП ОП АП ОП

Два последних результата иллюстрируются рис.4.10,а. Для ДО АП пунктиром показан случай, когда w3 >> w4, из чего следует, что b3 >> b4.

Зависимость полного времени ожидания от суммарной нагрузки Y системы при использовании ДО АП аналогична зависимости для ДО ОП (см. рис.4.10,б) с тем лишь отличием, что при ДО АП высокоприоритетные заявки лучше защищены от перегрузок.

Рис.4.10. Зависимости среднего времени ожидания от номера класса (а) и 4.3.4. Законы сохранения Изменение ДО позволяет уменьшить время ожидания высокоприоритетных заявок за счет увеличения времени ожидания низкоприоритетных заявок. Очевидно, что за счет изменения ДО нельзя добиться того, чтобы уменьшилось или увеличилось время ожидания заявок всех классов.

Этот факт сформулирован в виде закона сохранения времени ожидания.

Формулировка закона сохранения времени ожидания. Для любой дисциплины обслуживания (ДО) то есть сумма произведений загрузок i на среднее время ожидания wi (i = 1, H ) заявок всех классов инвариантна относительно ДО.

Закон сохранения времени ожидания выполняется при следующих условиях:

• система без потерь – все заявки на обслуживание удовлетворяются;

• система простаивает лишь в том случае, когда в ней нет заявок;

прерванных заявок распределена по экспоненциальному закону;

• все поступающие потоки заявок – простейшие, и длительности обслуживания не зависят от интенсивностей потоков заявок.

Значение константы в законе сохранения можно определить следующим образом. Поскольку закон сохранения справедлив для любых ДО, удовлетворяющих перечисленным условиям, то он справедлив и для ДО БП, для которой wk = w БП для всех (k = 1, …, H). Отсюда находим значение константы:

Подставив полученное значение константы и формулу (4.9) для расчёта w БП в закон сохранения, окончательно получим:

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

Модификация закона сохранения. Закон сохранения может быть модифицирован применительно ко времени пребывания заявок в системе с учетом того, что wi = ui bi. Подставив это выражение в закон сохранения времени ожидания (4.14) после некоторых преобразований, получим закон сохранения времени пребывания:

Заметим, что изменение ДО приводит только к изменению времени ожидания и времени пребывания, а остальные величины, входящие в выражения (4.14) и (4.15), не изменяются.

Рассмотрим случай, когда средние длительности обслуживания заявок разных классов одинаковы: bi = b = const для всех i = 1, H. Тогда выражение (4.14) может быть преобразовано следующим образом:

откуда получим новую формулировку закона сохранения в виде закона сохранения суммарной длины очереди заявок:

Таким образом, если средние длительности обслуживания заявок разных классов одинаковы, то изменение ДО не приводит к изменению суммарной длины L очередей заявок всех классов, которая остается постоянной. В то же время длины очередей li (i = 1, H ) заявок каждого класса меняются с изменением ДО.

4.4. Разомкнутые экспоненциальные СеМО с однородным потоком заявок 4.4.1. Описание разомкнутых СеМО Рассмотрим разомкнутую экспоненциальную сеть массового обслуживания (СеМО) с однородным потоком заявок при следующих предположениях:

1) разомкнутая СеМО (РСеМО) произвольной топологии содержит n узлов;

2) после завершения обслуживания в каком-либо узле передача заявки в другой узел происходит мгновенно;

3) в качестве узлов могут быть как одноканальные, так и многоканальные СМО;

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

5) заявка, поступившая в многоканальный узел, когда все или несколько приборов свободны, направляется случайным образом в любой свободный прибор;

6) в каждом узле РСеМО имеется накопитель заявок неограниченной ёмкости, что означает отсутствие отказов поступающим заявкам при их постановке в очередь, то есть любая поступающая в узел заявка всегда найдет в накопителе место для ожидания независимо от того, сколько заявок уже находится в очереди;

7) заявки поступают в РСеМО из внешнего независимого источника и образуют простейший поток заявок;

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

9) обслуживающий прибор любого узла не простаивает, если в его накопителе имеется хотя бы одна заявка, причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка;

10) в каждом узле сети заявки из накопителя выбираются в соответствии с бесприоритетной дисциплиной обслуживания в порядке поступления (ОПП) по правилу «первым пришел – первым обслужен»

(FIFO – First In First Out).

Для описания линейных разомкнутых однородных экспоненциальных СеМО необходимо задать следующую совокупность параметров:

• число узлов в сети: n;

• число обслуживающих приборов в узлах сети: K1,..., K n ;

• матрицу вероятностей передач: P = [ pij i, j = 0, 1,K, n], где вероятности передач pij должны удовлетворять условию (3.23):

сумма элементов каждой строки должна быть равна 1;

• интенсивность 0 источника заявок, поступающих в РСеМО;

• средние длительности обслуживания заявок в узлах сети:

На основе перечисленных параметров могут быть рассчитаны узловые и сетевые характеристики, описывающие эффективность функционирования соответственно узлов и РСеМО в целом.

Расчет характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО базируется на эквивалентном преобразовании сети и проводится в четыре этапа:

• расчет коэффициентов передач j и интенсивностей потоков • проверка условия отсутствия перегрузок в СеМО;

• расчет узловых характеристик;

• расчет сетевых характеристик.

4.4.2. Расчет коэффициентов передач и интенсивностей потоков заявок в узлах Покажем, что интенсивности 0,K, n потоков заявок, поступающих в узлы 0,..., n сети, однозначно определяются вероятностями передач pij (i, j = 1,K, n), задающими маршруты заявок в СеМО.

Будем рассматривать только установившийся режим.

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

Интенсивность потока заявок, входящих в любой узел j сети, равна сумме интенсивностей потоков заявок, поступающих в него из других узлов i = 0, n (рис.4.11). Поскольку заявки из узла i поступают в узел j с вероятностью pij, то интенсивность потока заявок, поступающих из i в j, равна pij i, где i - интенсивность выходящего и, следовательно, входящего потока заявок узла i. С учетом этого, на входе узла j имеется поток с интенсивностью Рис.4.11. К расчёту интенсивностей потоков заявок в узлах РСеМО Выражение (4.16) представляет собой систему линейных алгебраических уравнений (n + 1) -го порядка, из которой могут быть найдены интенсивности потоков заявок в виде соотношения j = j 0 ( j = 1, n).

Коэффициент j называется коэффициентом передачи и определяет среднее число попаданий заявки в узел j за время ее нахождения в сети, причем 0 = 1.

Для разомкнутой СеМО известна интенсивность источника заявок 0. Можно показать, что система уравнений для расчета интенсивностей имеет единственное решение вида j = j 0, где 0 – заданная величина.

4.4.3. Проверка условия отсутствия перегрузок в В п.3.4.2 показано, что в разомкнутой СеМО отсутствуют перегрузки, если выполняется условие (3.25):

Если указанное условие не выполняется, то, как следует из него, стационарный режим в разомкнутой СеМО может быть реализован одним из следующих способов:

• уменьшением интенсивности 0 внешнего источника заявок до значения, при котором это условие будет выполняться;

• увеличением количества обслуживающих приборов K j в перегруженных узлах;

• уменьшением длительностей b j обслуживания заявок в перегруженных узлах;

• уменьшением коэффициентов передач j в перегруженных 4.4.4. Расчет узловых характеристик РСеМО Один и тот же объект, рассматриваемый на разных уровнях детализации, можно представить различными моделями массового обслуживания, характеристики которых одинаковы или отличаются на величину, не превосходящую заданной погрешности. При выполнении определенных условий такие модели легко преобразуются друг в друга.

Для сетевых моделей в виде разомкнутых и замкнутых СеМО могут использоваться два вида преобразований:

• эквивалентное преобразование;

• толерантное преобразование.

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

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

Использование свойств эквивалентных и толерантных моделей позволяет упростить расчет характеристик моделей путем замены сложных сетевых моделей более простыми. Эквивалентными могут быть сетевые модели одного типа (например, две замкнутые сети), толерантными — модели как одного, так и разных типов [11].

Расчет характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО базируется на эквивалентном преобразовании сети, заключающемся в представлении разомкнутой СеМО с n узлами в виде n независимых экспоненциальных СМО типа M/M/N (простейший поток заявок, длительность обслуживания распределена по экспоненциальному закону, N обслуживающих приборов).

При этом интенсивность входящего потока заявок в СМО, отображающую узел j ( j = 1, n) сети, определяется из системы алгебраических уравнений (4.16) через интенсивность входящего в сеть потока и коэффициент передачи узла: j = j 0, а средняя длительность обслуживания заявок в СМО равна длительности обслуживания b j заявок в соответствующем узле СеМО.

Характеристики всех n СМО (время ожидания заявок в очереди и пребывания в системе, длина очереди и число заявок в системе, среднее число занятых приборов и т.д.) представляют собой узловые характеристики СеМО.

Среднее время ожидания заявок в очереди может быть рассчитано с использованием выражения (4.8) для многоканальных СМО типа M/M/N или выражения (4.1) для одноканальных СМО типа M/M/1, остальные характеристики узла j ( j = 1, n) – с использованием фундаментальных соотношений, представленных в п.3.4.3, а именно:

• нагрузка в узле j, показывающая среднее число занятых приборов:

обслуживающих приборов в узле j;

• время пребывания заявок в узле: u j = w j + b j ;

• число заявок в узле (в очереди и на обслуживании в приборе):

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

4.4.5. Расчет сетевых характеристик РСеМО Сетевые характеристики, описывающие эффективность функционирования СеМО в целом, рассчитываются на основе полученных значений узловых характеристик.

В состав сетевых характеристик входят:

• среднее число заявок, ожидающих обслуживания в сети, и среднее число заявок, находящихся в сети:

где l j – средняя длина очереди и m j – среднее число заявок в узле j;

• среднее время ожидания и среднее время пребывания заявок в где w j и u j – соответственно среднее время ожидания и среднее время пребывания заявок в узле j; j – коэффициент передачи для узла j, показывающий среднее число попаданий заявки в узел j за время ее нахождения в сети.

Пример 4.2. Проиллюстрируем изложенный метод расчета характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО на примере СеМО с четырьмя узлами ( n = 4 ), граф которой представлен на рис.4.12. Связи между узлами СеМО описываются следующей матрицей вероятностей передач:

В РСеМО поступает простейший поток заявок с интенсивностью 0 = 0,1 с 1 Положим, что все узлы СеМО – одноканальные, а средние длительности обслуживания заявок в узлах соответственно равны:

b1 = 0,8 с; b2 = 2 с; b3 = 0,4 с; b4 = 0,3 с.

Система линейных алгебраических уравнений для расчёта интенсивностей потоков заявок в узлах СеМО, согласно (4.16), имеет вид:

Решая эту систему уравнений, получим следующие значения интенсивностей: 1 = 1 с 1, 2 = 0,2 с 1, 3 = 0,7 с 1, 4 = 0,9 с 1. Тогда коэффициенты передач будут равны: 1 = 1 / 0 = 10 ; 2 = 2 / 0 = 2 ;

Определим предельную интенсивность поступления заявок в разомкнутую СеМО, при которой в сети отсутствуют перегрузки. Для этого воспользуемся выражением (3.25), определяющим условие отсутствия перегрузок в РСеМО:

РСеМО работает без перегрузок, поскольку данное условие выполняется.

В соответствии с эквивалентным преобразованием представим рассматриваемую экспоненциальную разомкнутую СеМО в виде 4-х независимых СМО типа M/M/1, в которые поступают простейшие потоки заявок соответственно с интенсивностями: 1 = 1 с 1, 2 = 0,2 с 1, 3 = 0,7 с 1, 4 = 0,9 с 1, а средние длительности обслуживания заявок в СМО совпадают с длительностями обслуживания в соответствующих узлах СеМО: b1 = 0,8 с; b2 = 2 с; b3 = 0,4 с; b4 = 0,3 с.

Значения узловых характеристик СеМО, рассчитанные с использованием выражения (4.1) для среднего времени ожидания заявок в очереди СМО типа M/M/1 и фундаментальных соотношений, представленных в п.3.4.3, приведены в табл.4.1.

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

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

На рис. 4.13 показана зависимость основной сетевой характеристики РСеМО – среднего времени пребывания U заявок в сети от интенсивности 0 поступления заявок в сеть. Зависимость U ' = f ' (0 ) аналогична зависимости среднего времени пребывания заявок в СМО от загрузки системы, изменение которой может быть обусловлено, в частности, изменением интенсивности поступления заявок в СМО. Как и в СМО, имеется некоторое предельное значение интенсивности '0, при котором среднее время пребывания заявок в сети становится бесконечно большим, что свидетельствует о перегрузке в СеМО. Выше (см.п.3.4.2) показано, что в РСеМО отсутствуют перегрузки, если они отсут- U ствуют во всех узлах сети, то есть перегрузка в разомкнутой СеМО настуU ' = f ' (0 ) пает в том случае, когда загрузка одного из узлов сети становится равной характеризуется тем, что очередь заявок перед ним Рис.4.13. Время пребывания заявок в РСеМО со временем растёт до бесконечности и, как следствие, становится бесконечным число заявок в разомкнутой СеМО.

Для того чтобы избавиться в РСеМО от перегрузки, необходимо разгрузить «узкое место». Это может быть достигнуто следующими способами:

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

Любой из этих способов позволяет увеличить производительность СеМО в целом и, как следствие, улучшить характеристики сети. Зависимость среднего времени пребывания U заявок в сети от интенсивности 0 поступления заявок в сеть принимает вид U " = f " (0 ), то есть время пребывания заявок при одной и той же интенсивности 0 становится меньше (поскольку сеть имеет большую производительность), а предельное значение интенсивности ", при котором наступает перегрузка место в СеМО, и дальнейшее улучшение сети может быть достигнуто путём разгрузки нового узкого места. Очевидно, что если СеМО является моделью реальной технической системы, разгрузка узкого места за счёт увеличения скорости работы обслуживающего прибора или числа приборов в узле означает увеличение стоимости реальной системы.

Существует ещё один способ разгрузки узкого места СеМО, заключающийся в уменьшении вероятности передачи заявок к узлу, являющемуся узким местом. Этот способ часто используется в реальных системах и обычно не связан с увеличением стоимости системы.

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

Характер зависимостей других сетевых характеристик (времени ожидания, числа заявок в сети и в состоянии ожидания) разомкнутой СеМО от интенсивности поступления заявок аналогичен показанному на рис. 4.13.

Пример 4.3. Проиллюстрируем способы разгрузки узкого места и получаемый от этого эффект для четырёхузловой разомкнутой СеМО, рассмотренной в примере 4.2. Там же было показано, что интенсивность поступления заявок в разомкнутую СеМО, при которой в сети отсутствуют перегрузки, должна удовлетворять условию: 0 < 0,125 с 1.

1. Рассчитаем сначала характеристики РСеМО, работающей в области загрузок, близких к 1, для чего положим, что интенсивность потока поступающих в сеть заявок равна 0 = 0,12 с Тогда интенсивности потоков заявок в узлы РСеМО соответственно 4 = 4 0 = 1,08 с 1, а средние длительности обслуживания заявок, как и ранее, будут равны: b1 = 0,8 с; b2 = 2 с; b3 = 0,4 с; b4 = 0,3 с.

Рассчитанные значения узловых и сетевых характеристик СеМО приведены в табл.4.3.

Анализ представленных результатов показывает, что увеличение интенсивности поступления заявок в РСеМО всего лишь на 20% до значения 0 = 0,12 с 1, привело к резкому росту значений сетевых характеристик. В частности, среднее время пребывания заявок в сети выросло в 4 раза, а число заявок, находящихся в очередях – почти в 6,5 раз.

Это говорит о том, что СеМО работает в области больших загрузок, где незначительное увеличение нагрузки приводит к существенному изменению характеристик обслуживания заявок. Наиболее загруженным узлом СеМО, то есть узким местом, является узел 1, загрузка которого много больше загрузок других узлов и составляет 1 = 0,96. Именно в этом узле характеристики обслуживания заявок выросли наиболее существенно: среднее время пребывания заявок в 5 раз (с 4 до 20 секунд), а средняя длина очереди – более чем в 7 раз (с 3,2 до 23 заявок).

2. Для улучшения характеристик обслуживания заявок в РСеМО необходимо разгрузить узкое место сети, которым является узел 1. Для этого увеличим скорость работы обслуживающего прибора в 2 раза, что, в конечном счете, приведёт к уменьшению длительности обслуживания заявок в 2 раза, которая станет равной b1 = 0,4 с.

Рассчитанные значения узловых и сетевых характеристик СеМО после разгрузки узкого места приведены в табл.4.4.

Анализ представленных результатов показывает, что разгрузка узкого места позволила существенно уменьшить значения сетевых характеристик: среднее время пребывания заявок в сети уменьшилось более чем в раз, а число заявок, находящихся в очередях – почти в 20 раз. Отметим, что изменение длительности обслуживания заявок в узле 1 привело к изменению узловых характеристик только этого узла; узловые характеристики остальных узлов не изменились. Это является следствием независимого функционирования узлов экспоненциальной разомкнутой СеМО, что фактически и позволяет использовать метод расчёта характеристик сети, основанный на декомпозиции, то есть представлении сети в виде совокупности независимых СМО.

3. Для сравнения выполним разгрузку узкого места другим способом, а именно: увеличим число обслуживающих приборов в узле 1 с одного до двух: K1 = 2, сохранив прежнее значение длительности обслуживания одним прибором: b1 = 0,8 с.

Рассчитанные значения узловых и сетевых характеристик СеМО после разгрузки узкого места приведены в табл.4.5.

Время пребывания 1,088 3,846 0,602 0,444 26, Сравним полученные значения сетевых характеристик со значениями, представленными в табл. 4.4 для первого способа разгрузки узкого места за счёт уменьшения длительности обслуживания заявок. При втором способе разгрузки узкого места за счёт увеличения числа обслуживающих приборов ( K1 = 2 ; b1 = 0,8 с) среднее время ожидания заявок в сети несколько уменьшилось по сравнению с первым способом ( K1 = 1 ;

b1 = 0,4 с). В то же время, среднее время пребывания заявок в РСеМО увеличились более чем на 10%, что обусловлено большей длительностью обслуживания заявок ( b1 = 0,8 с) в каждом из приборов двухканального узла 1 по сравнению с одноканальным узлом при первом способе ( b1 = 0, с). Как и в предыдущем случае, изменение числа обслуживающих приборов в узле 1 привело к изменению узловых характеристик только этого узла.

4.5. Замкнутые экспоненциальные СеМО с однородным потоком заявок те, которые взяты из технических справочников) должны рассматриваться как переменные» (Универсальные законы …) 4.5.1. Описание замкнутых СеМО Рассмотрим замкнутую экспоненциальную сеть массового обслуживания с однородным потоком заявок при следующих предположениях:

1) замкнутая СеМО (ЗСеМО) произвольной топологии содержит n узлов;

2) после завершения обслуживания в каком-либо узле передача заявки в другой узел происходит мгновенно;

3) все узлы замкнутой СеМО одноканальные;

4) в СеМО циркулирует постоянное число заявок;

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

6) ёмкость накопителя в каждом узле СеМО достаточна для хранения всех заявок, циркулирующих в сети, что означает отсутствие отказов поступающим заявкам при их постановке в очередь любого узла (в частности, можно считать, что ёмкость накопителя в каждом узле равна числу заявок, циркулирующих в сети);

7) обслуживающий прибор любого узла не простаивает, если в его накопителе имеется хотя бы одна заявка, причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка;

8) в каждом узле сети заявки из накопителя выбираются в соответствии с бесприоритетной дисциплиной обслуживания в порядке поступления (ОПП) по правилу «первым пришел – первым обслужен»

(FIFO – First In First Out).

Для описания линейных замкнутых однородных экспоненциальных СеМО необходимо задать такую же совокупность параметров, как и для разомкнутых СеМО, с единственным отличием, заключающимся в том, что вместо интенсивности источника заявок следует задать число заявок, циркулирующих в ЗСеМО. Таким образом, совокупность параметров для замкнутых СеМО будет иметь следующий вид:

• число узлов в сети: n;

• число обслуживающих приборов в узлах сети: K1,..., K n ;

• матрица вероятностей передач: P = [ pij i, j = 0, 1,K, n], где pij – вероятность передачи заявки из узла i в узел j;

• число заявок M, циркулирующих в ЗСеМО;

• средние длительности обслуживания заявок в узлах сети: b1,K,bn.

На основе перечисленных параметров могут быть рассчитаны узловые и сетевые характеристики, описывающие эффективность функционирования соответственно узлов и ЗСеМО в целом.

Расчёт характеристик функционирования линейных замкнутых однородных экспоненциальных СеМО с одноканальными узлами базируется на так называемой «теореме о прибытии» и проводится с использованием метода средних значений в два этапа:

• расчет коэффициентов передач в узлах замкнутой СеМО;

• расчет характеристик ЗСеМО.

4.5.2. Расчет коэффициентов передач в узлах Для замкнутой СеМО на первом этапе рассчитываются только коэффициенты передач. Интенсивности потоков заявок в узлах ЗСеМО не могут быть рассчитаны, как в РСеМО, поскольку для ЗСеМО изначально не известна интенсивность 0, которая является не параметром, задаваемым в составе исходных данных, а характеристикой, представляющей собой производительность ЗСеМО и определяемой в процессе анализа эффективности функционирования ЗСеМО.

Для расчёта коэффициентов передач 1,K, n после некоторых преобразований можно воспользоваться той же системой линейных алгебраических уравнений (4.16). Для этого в левой и правой части выражения (4.16) представим интенсивности в виде j = j 0. Разделив левую и правую часть выражения (4.16) на 0, окончательно получим систему линейных алгебраических уравнений относительно 1, K, n :

Полагая 0 = 1, можно найти корни системы уравнений, численно определяющие значения. 1,K, n 4.5.3. Расчет характеристик ЗСеМО Характеристики ЗСеМО могут быть рассчитаны с использованием марковских процессов, поскольку количество состояний марковского процесса, в отличие от РСеМО, не бесконечно и равно числу сочетаний C M + n 1, где n – число узлов в ЗСеМО и M – число заявок, циркулирующих в ЗСеМО. При этом основная трудность заключается в определении вероРаздел 3. Аналитическое моделирование ятностей состояний сети P( M 1,K, M n ) в случае большой ее размерности (n > 5; M > 5), когда число состояний оказывается значительным. При выполнении расчетов на ЭВМ это, во многих случаях, приводит к потере значимости в процессе промежуточных вычислений и, следовательно, к невозможности получения конечных результатов.

От указанного недостатка свободен метод средних значений, позволяющий вычислять средние характеристики функционирования экспоненциальных СеМО на основе сравнительно простых рекуррентных соотношений.

Положим, что замкнутая однородная СеМО содержит n одноканальных узлов, длительности обслуживания заявок в которых распределены по экспоненциальному закону со средними значениями b1,K, bn соответственно. Пусть для каждого узла i сети известно среднее число попаданий заявки в данный узел за время ее нахождения в сети, то есть коэффициент передачи i, который, если конфигурация сети задана матрицей вероятностей передач P = [ pij i, j = 0,1,K, n], определяется в результате решения системы линейных алгебраических уравнений (4.17).

Обозначим: ui - среднее время пребывания заявки в узле i за время пребывания в сети; mi – среднее число заявок в узле i (i = 1, K, n) ; 0 – производительность замкнутой сети. Очевидно, что эти величины зависят от числа заявок M, циркулирующих в замкнутой сети, то есть ui = ui (M ) ;

Можно показать, что имеют место следующие соотношения:

где U (M ) – среднее время пребывания заявок в сети при условии нахождения в ней M заявок; mi (0) = 0.

Выражение (4.18) получено на основе так называемой теоремы о прибытии [1], утверждающей, что в замкнутой экспоненциальной сети с одноканальными узлами, в которой циркулируют M заявок, стационарная вероятность состояния любого узла в момент поступления в него новой заявки совпадает со стационарной вероятностью того же состояния рассматриваемого узла в сети, в которой циркулирует на одну заявку меньше, то есть ( M 1) заявок. Это означает, что в сети с M заявками среднее число заявок mi (M ), находящихся в узле i в момент поступления в этот узел новой заявки, равно mi ( M 1). Тогда среднее время пребывания в узле i поступившей заявки будет складываться из среднего времени обслуживания всех mi ( M 1) ранее поступивших и находящихся в узле i заявок и средней длительности обслуживания рассматриваемой заявки:

В этом выражении учтено, что среднее время дообслуживания заявки, находящейся в приборе на момент поступления рассматриваемой заявки, равно средней длительности обслуживания bi в силу свойства отсутствия последействия, присущего экспоненциальному закону. Среднее время пребывания заявки в узле i за время ее нахождения в сети, учитывающее число попаданий i заявки в данный узел, равно Выражения (4.19) и (4.20) представляют собой формулы Литтла для сети, а выражение (4.21) – для узла i, где i ( M ) = i 0 ( M ) – интенсивность потока заявок в узел i (i = 1,K, n).

На основе рекуррентных соотношений (4.18) – (4.21) последовательно для M = 1, 2,K, M *, где M * – заданное число заявок в замкнутой сети, могут быть рассчитаны средние значения характеристик замкнутой экспоненциальной СеМО.

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

Пример 4.4. Рассчитаем характеристики замкнутой однородной экспоненциальной СеМО, полученной путём преобразования разомкнутой СеМО (рис. 4.12), рассмотренной в Примере 4.2, в замкнутую. Положим, что «нулевая точка», отображающая завершение обслуживания заявок в сети и мгновенное формирование новой заявки, выбрана на дуге, выходящей из узла 1 и входящей снова в этот же узел (рис.4.14).

Напомним, что в ЗСеМО относительно «нулевой точки» рассчитываются временные сетевые характеристики: время нахождения в состоянии ожидания и время пребывания заявок в сети, а также производительность ЗСеМО.

ЗСеМО содержит n = 4 одноканальных узла, связи между которыми описываются той же матрицей вероятностей передач:

Следовательно, коэффициенты передач для всех узлов, рассчитываемые путём решения системы линейных алгебраических уравнений (4.17), будут иметь те же самые значения: 1 = 10 ; 2 = 2 ; 3 = 7 ; 4 = 9.

В ЗСеМО циркулирует М заявок, средние длительности обслуживания которых в узлах равны: b1 = 0,8 с; b2 = 2 с; b3 = 0,4 с; b4 = 0,3 с.

Ниже в табл.4.6 представлены значения времени пребывания ui (M ) и числа заявок mi (M ) в узлах сети, а также среднего времени пребывания U (M ) заявок в сети и производительности 0 ( M ), рассчитанные на основе выражений (4.18) – (4.21), для числа циркулирующих в сети заявок M = 1, 2,K, 6. Корректность выполненных расчетов подтверждается тем, что для всех M = 1, 2, K, 6 выполняется проверочное условие:

На рис.4.15 представлены зависимости производительности рассматриваемой замкнутой СеМО и среднего времени пребывания заявок в сети от количества M = 1, 10 циркулирующих заявок. Анализ полученных результатов показывает, что все характеристики, включая производительность 0, растут с увеличением M.

Производительность Рис.4.15. Производительность и время пребывания заявок в ЗСеМО Производительность сети асимптотически приближается к максимально возможной производительности (пропускной способности ЗСеМО), совпадающей с предельно допустимой интенсивностью поступления заявок в аналогичной разомкнутой СеМО (см. Пример 4.1), при которой в сети отсутствуют перегрузки, и равна 0 = 0,125 с 1.

Среднее время пребывания заявок в ЗСеМО растёт неограниченно с увеличением количества заявок с сети.

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

4.5.4. Анализ свойств замкнутых СеМО Для замкнутых СеМО, как и для разомкнутых, наибольший интерес представляют свойства сети в целом, в частности, влияние циркулирующих в ЗСеМО числа заявок, на такие сетевые характеристики как производительность 0 замкнутой СеМО и среднее время пребывания U заявок в сети.

Анализ представленных на рис.4.16, зависимостей позволяет сформулировать следующие выводы.

1. Зависимость 0 = f ( M ) производительности ЗСеМО 0 от числа M циркулирующих заявок вначале растёт с увеличением M до некоторого значения M 0, после которого рост производительности замедляется, а с дальнейшим увеличением M производительность сети асимптотически стремится к некоторому предельному значению 0, представляющему собой пропускную способность ЗСеМО. Для объяснения этой завиU симости вспомним, что производительность замкнутой сети измеряет- ся как интенсивность потока заявок, проходящих через некоторую условную точку, обозначаемую как «0» и расположенную на одной из мгновенное формирование новой заявки, поступающей в сеть. Выше Рис.4.16. Характеристики ЗСеМО (см. пример 4.4) было показано, что увеличение числа заявок в замкнутой СеМО приводит к увеличению значений всех сетевых характеристик, включая производительность 0. В свою очередь, увеличение производительности приводит к увеличению загрузок узлов СеМО, связанных с интенсивностью 0 зависимостью:

где j, b j и K j – соответственно коэффициент передачи, средняя длительность обслуживания и количество приборов в узле j = 1, n.

Когда число заявок в ЗСеМО достигает некоторого значения M 0, загрузка одного из узлов становится близкой к 1, при этом практически прекращается рост производительности, которая при M достигает своего предельного значения – пропускной способности 0. Такой узел представляет собой «узкое место» сети, и значение пропускной способности 0 определяется пропускной способностью узкого места из условия, что загрузка у этого узла равна 1:

Отсюда пропускная способность замкнутой СеМО:

где у, b у и K у – соответственно коэффициент передачи, средняя длительность обслуживания и количество обслуживающих приборов в узле, являющимся узким местом.

Правая часть последнего выражения представляет собой пропускную способность узла, являющегося узким местом сети: µ у =.

Действительно, у b у представляет собой полное время обслуживания одной заявки в данном узле с учётом того, что заявка за время нахождения в сети в среднем у раз побывает в данном узле. Тогда величина, обратная у b у, представляет собой интенсивность обслуживания заявок одним прибором в данном узле: µ1 = 1 / у b у, а µ у = K у µ1 – интенсивность обслуживания заявок узлом, то есть всеми приборами.

Этот же результат можно получить следующими рассуждениями.

Если загрузка некоторого узла, являющегося узким местом СеМО, становится равной 1, то это означает, что все приборы данного узла постоянно обслуживают заявки, то есть не простаивают. Тогда интенсивность выходящего из этого узла потока заявок будет равна интенсивности обслуживания: у = µ у = K у µ1. Напомним, что интенсивность потока заявок в узле у связана с производительностью ЗСеМО зависимостью у = у 0. Отсюда вытекает, что производительность 2. Среднее время пребывания заявок (рис.4.16) в замкнутой СеМО, как и производительность, растёт с увеличением числа M циркулирующих в сети заявок, причём вначале наблюдается незначительный рост, а затем, после значения M = M 0, наблюдается линейный рост времени пребывания.

Действительно, если в сети циркулирует только одна заявка, то в такой сети не может быть очередей, и время пребывания заявок в СеМО складывается только из времён обслуживания заявок в узлах с учётом коэффициентов передач:

С увеличением числа заявок M в узлах ЗСеМО появляются очереди, причём очевидно, что чем больше заявок в сети, тем более длинные очереди образуются в узлах и тем больше время ожидания, а, следовательно, и время пребывания заявок в ЗСеМО.

Сопоставляя зависимости производительности и среднего времени пребывания заявок от их числа в ЗСеМО, можно сделать следующий вывод: увеличение числа заявок в сети, с одной стороны, приводит к увеличению производительности, что может рассматриваться как положительный фактор, а, с другой стороны, – к увеличению времени пребывания заявок в сети, что является нежелательным фактором.

Точка M = M 0 характеризует некоторое граничное значение числа заявок в ЗСеМО. Дальнейшее увеличение числа заявок в сети оказывается нецелесообразным, поскольку приводит к резкому увеличению времени пребывания заявок в ЗСеМО при незначительном увеличении производительности сети.

3. Когда загрузка узкого места становится равной единице, дальнейший рост производительности за счёт увеличения числа заявок в ЗСеМО невозможен. Для увеличения производительности ЗСеМО, как и в РСеМО, необходимо разгрузить узкое место, то есть уменьшить загрузку:

у = у 0 у = 1, что при одной и той же производительности может быть достигнуто:

• уменьшением длительности обслуживания заявок b у, например за обслуживающего прибора;

• увеличением числа обслуживающих приборов K у в узле;

• уменьшением коэффициента передачи у или, что то же самое, вероятности передачи заявок к узлу, являющемуся узким местом.

Если до разгрузки узкого места зависимость производительности ЗСеМО от числа заявок в сети имела вид '0 = f ( M ) (рис.4.17), а пропускная способность была рав- 0 " ', то после разгрузки – зависимость производительности от числа заявок будет иметь вид "0 = f ( M ), а пропускная способность станет равной 0 > 0. При этом граничM ное значение числа заявок в ЗСеМО увеличится: M 0 > M Следует отметить, что к рассматриваемой зависимости производительности ЗСеМО 0 от числа M циркулирующих в сети заявок может быть применена линейная аппроксимация 0 = f ( M ), показанная на рис.4.17 в виде пунктирных линий и представляющая собой верхнюю границу производительности ЗСеМО. Последнее означает, что производительность ЗСеМО будет не больше, чем рассчитанное верхнее значение.

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

Отметим, что в некоторых случаях разгрузка узкого места не приводит к улучшению характеристик СеМО, в частности, к увеличению производительности. Обычно это связано с тем, что в СеМО может существовать несколько узлов, являющихся «узкими местами». Условием откуда окончательно получим:

улучшения характеристик ЗСеМО необходимо одновременно разгрузить все «узкие места».

Последовательно разгружая узкие места СеМО, мы можем прийти к некоторой «идеальной» сети, в которой загрузки всех узлов одинаковы.

СеМО, в которой загрузки всех узлов равны, называется сбалансированной. Сбалансированная СеМО обладает наилучшими характеристиками по сравнению с несбалансированной.

При построении реальных систем, моделями которых служат СеМО, необходимо, по-возможности, строить сбалансированные системы, хотя на практике по многим причинам достичь этого не удаётся.

4.6. Резюме 1. Одноканальная экспоненциальная СМО M/M/1 является наиболее простой с точки зрения аналитического расчета. Средние времена ожидания и пребывания заявок в СМО M/M/1 рассчитываются по сравнительно простым формулам:

где = b < 1 – загрузка системы; – интенсивность поступления заявок в систему; b – средняя длительность обслуживания заявок в приборе.

Для СМО M/G/1 среднее время ожидания заявок определяется по формуле Поллачека-Хинчина:

где b – коэффициент вариации длительности обслуживания.

Для общего случая одноканальных СМО типа G/G/1 с однородным потоком применяются приближённые аналитические методы расчёта.

Свойства одноканальной СМО с однородным потоком заявок:

• среднее время ожидания заявок в очереди минимально при детерминированной длительности обслуживания заявок с коэффициентом вариации b = 0 и увеличивается нелинейно с ростом коэффициента вариации (дисперсии) длительности • среднее время ожидания заявок существенно зависит от нагрузки неограниченно: w, т.е. заявки могут ожидать обслуживания • для дисциплин обслуживания в обратном порядке и обслуживания в случайном порядке средние времена ожидания заявок будут такими же, как и при обслуживании в порядке поступления, но дисперсии времени ожидания будут больше.

2. В случае многоканальных СМО с однородным потоком заявок точный метод расчета среднего времени ожидания заявок разработан только для СМО типа M/M/K:

где = – загрузка системы; P – вероятность того, что все K приборов заняты обслуживанием заявок:

где P0 – вероятность простоя многоканальной СМО, то есть вероятность того, что в системе нет заявок:

Свойства многоканальной СМО с однородным потоком заявок:

• с увеличением числа обслуживающих приборов времена ожидания и пребывания заявок уменьшаются, при этом в пределе при K время ожидания стремится к нулю, а время пребывания становится равным длительности обслуживания заявок;

• при увеличении числа обслуживающих приборов K и сохранении их суммарной производительности (скорости работы) время ожидания заявок уменьшается, однако время пребывания заявок в системе увеличивается и в пределе (при K ) асимптотически стремится к длительности обслуживания заявок, то есть с точки зрения задержек (времени пребывания заявок) более эффективной является одноканальная система, чем многоканальная, при равенстве суммарной производительности; достоинством многоканальной системы является более высокая надежность;

• среднее время ожидания заявок, как и для одноканальных систем, зависит от нагрузки y (загрузки ) системы и при y K ( 1) время ожидания заявок возрастает неограниченно: w, то есть заявки могут ожидать обслуживания сколь угодно долго.

3. Для одноканальных СМО с неоднородным потоком заявок и бесприоритетной ДО средние времена ожидания одинаковы для всех классов заявок и определяются по следующей формуле:

где R = i = i bi – суммарная загрузка системы ( R < 1 ).

Свойства одноканальной СМО с бесприоритетной ДО:

• среднее время ожидания заявок разных классов при использовании ДО БП одинаково;

• среднее время ожидания заявок в очереди минимально при детерминированной длительности обслуживания заявок каждого класса и увеличивается нелинейно с ростом коэффициента вариации (дисперсии) длительности обслуживания;

• среднее время ожидания заявок зависит от суммарной нагрузки Y (загрузки R) системы и при Y 1 ( R 1) время ожидания заявок всех классов возрастает неограниченно: w БП, однако средние времена пребывания в системе и средние длины очередей заявок разных классов, в общем случае, различны, поскольку различны длительности обслуживания и интенсивности поступления заявок • для бесприоритетной дисциплины обслуживания в обратном порядке средние времена ожидания заявок будут такими же, как и при обслуживании в порядке поступления, но дисперсия времени ожидания будет больше;

• для дисциплины обслуживания в циклическом порядке средние времена ожидания заявок разных классов в общем случае не 4. Для ДО ОП средние времена ожидания заявок k–го класса определяются по следующей формуле:

где Rk 1 и Rk – суммарные загрузки системы со стороны заявок, которые имеют приоритет не ниже (k 1) и k соответственно.

Свойства ДО ОП:

• введение относительных приоритетов по сравнению с ДО БП приводит к уменьшению времени ожидания высокоприоритетных заявок и к увеличению времени ожидания низкоприоритетных • средние времена ожидания заявок при использовании ДО ОП монотонно увеличиваются с уменьшением приоритета:

ОП ОП ОП

• ДО ОП обладает свойством защиты от перегрузок, заключающемся в том, что высокоприоритетные заявки даже при возникновении перегрузки ( Y 1 ) имеют конечное время ожидания за счёт отказа в обслуживании низкоприоритетным заявкам, время ожидания которых при этом резко возрастает и стремится к бесконечности.

5. Для ДО АП средние времена ожидания заявок k–го класса определяются по следующей формуле:

где Rk 1 и Rk – суммарные загрузки системы со стороны заявок, которые имеют приоритет не ниже (k 1) и k соответственно.

Свойства ДО АП:

• среднее время ожидания заявок складывается из двух составляющих: среднего времени ожидания начала обслуживания и среднего времени ожидания в прерванном состоянии;

• время ожидания заявок класса k зависит только от значений параметров классов заявок, имеющих более высокий или такой же приоритет, и не зависит от параметров классов заявок, имеющих более низкий приоритет;

• для заявок с самым высоким абсолютным приоритетом обеспечивается минимально возможное время ожидания по сравнению со всеми другими ДО;

• полное время ожидания у заявок высокоприоритетного класса k может оказаться больше, чем у заявок класса (k + 1) с более низким приоритетом, если длительности обслуживания заявок этих классов связаны соотношением bk >> bk +1 ;

• введение АП по сравнению с ОП приводит к уменьшению среднего времени ожидания самых высокоприоритетных заявок и к его увеличению для заявок класса самого низкого приоритета;

• при ДО АП высокоприоритетные заявки лучше защищены от 6. В соответствии с законом сохранения времени ожидания изменение ДО позволяет уменьшить время ожидания высокоприоритетных заявок за счет увеличения времени ожидания низкоприоритетных заявок:

Закон сохранения выполняется при следующих условиях:

• система без потерь;

• система простаивает лишь при отсутствии в системе заявок;

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

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

7. В качестве параметров линейных разомкнутых однородных экспоненциальных СеМО необходимо задать:

• число узлов в сети: n;

• число обслуживающих приборов в узлах сети: K1,..., K n ;

• матрицу вероятностей передач: P = [ pij i, j = 0, 1,K, n], где pij – вероятность передачи заявки из узла i в узел j;

• интенсивность 0 источника заявок, поступающих в РСеМО;

• средние длительности обслуживания заявок в узлах сети:

Условие отсутствия перегрузок в разомкнутой СеМО:

Расчет характеристик функционирования линейных разомкнутых однородных экспоненциальных СеМО базируется на эквивалентном преобразовании сети и проводится в три этапа:

• расчет интенсивностей потоков заявок j в узлах j = 1, n РСеМО путём решения системы линейных алгебраических уравнений:

• расчет узловых характеристик:

нагрузка в узле j, показывающая среднее число занятых число заявок в узле (в очереди и на обслуживании в приборе):

• расчет сетевых характеристик:

среднее число заявок, ожидающих обслуживания в сети, и среднее число заявок, находящихся в сети:

где l j - средняя длина очереди и m j - среднее число заявок в узле j;

среднее время ожидания и среднее время пребывания заявок в где w j и u j - соответственно среднее время ожидания и среднее время пребывания заявок в узле j; j = j / 0 ( j = 1, n) - коэффициент передачи для узла j, показывающий среднее число попаданий заявки в узел j за время ее нахождения в сети.

Свойства разомкнутых СеМО:

• свойства отдельных узлов СеМО аналогичны свойствам соответствующих одноканальных и многоканальных СМО;

• с увеличением интенсивности 0 поступления заявок в сеть сетевые характеристики увеличиваются, причём имеется предельное значение интенсивности '0, при котором, в частности, среднее время пребывания заявок в сети становится бесконечно большим, что свидетельствует о перегрузке в СеМО;

• узел сети, загрузка которого с увеличением 0 стремится к единице, называется «узким местом» и характеризуется бесконечным ростом очереди заявок перед ним и, как следствие, бесконечным ростом числа заявок в СеМО;

• способы разгрузки «узкого места»:

обслуживающего прибора;

увеличение числа обслуживающих приборов в узле;

уменьшение вероятности передачи заявок к узлу, являющемуся 8. В качестве параметров линейных замкнутых однородных экспоненциальных СеМО необходимо задать:

• число узлов в сети: n;

• число обслуживающих приборов в узлах сети: K1,..., K n ;

• матрица вероятностей передач: P = [ pij i, j = 0, 1,K, n], где pij – вероятность передачи заявки из узла i в узел j;

• число заявок M *, циркулирующих в ЗСеМО;

• средние длительности обслуживания заявок в узлах сети:

В замкнутых СеМО всегда существует установившийся режим.

Расчет характеристик функционирования линейных замкнутых однородных экспоненциальных СеМО с одноканальными узлами проводится с использованием метода средних значений в два этапа:

• расчет коэффициентов передач в узлах замкнутой СеМО путём решения системы линейных алгебраических уравнений относительно 1,K, n с учётом того, что ( 0 = 1) :

• расчет характеристик ЗСеМО с использованием следующих рекуррентных соотношений для значений M = 1, 2,K, M * :

где M * - заданное число заявок в замкнутой сети; mi (0) = 0.

Свойства замкнутых СеМО:

• зависимость производительности ЗСеМО 0 от числа M циркулирующих заявок растёт с увеличением M и стремится к некоторому предельному значению 0, представляющему собой пропускную способность ЗСеМО;

• среднее время пребывания заявок в замкнутой СеМО, как и производительность, растет с увеличением числа циркулирующих в сети заявок, причём рост времени пребывания вначале незначителен, а затем принимает линейный характер;

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

• для каждой замкнутой СеМО существует некоторое граничное значение числа заявок в сети, после которого резко увеличивается время пребывания заявок в ЗСеМО при незначительном увеличении производительности сети;

• когда загрузка узкого места становится равной единице, дальнейший рост производительности за счёт увеличения числа заявок в ЗСеМО невозможен; для увеличения производительности ЗСеМО необходимо разгрузить узкое место одним из следующих (увеличением скорости работы обслуживающего прибора);

увеличением числа обслуживающих приборов в узле;

уменьшением коэффициента передачи.

• если в СеМО существует несколько узлов, одновременно являющихся «узким местом», для улучшения характеристик функционирования ЗСеМО необходимо одновременно разгрузить • при построении реальных систем, моделями которых служат СеМО, следует, по-возможности, строить сбалансированные системы, в которых загрузки всех узлов одинаковы.

4.7. Практикум: решение задач Задача 1. В одноканальную систему обслуживания поступают заявки двух классов с интенсивностями 0,3 и 1 заявок в секунду. Интенсивности их обслуживания соответственно равны 0,5 и 5 заявок в секунду.

а) Сформулировать условия, при которых время пребывания заявок 1-го класса будет равно 2 секунды?

б) Чему будет равно время пребывания заявок 1-го класса, если при тех же условиях интенсивность их поступления увеличится в два раза?

в) Чему будет равно время пребывания заявок 1-го класса, если при тех же условиях интенсивность их обслуживания увеличится в два раза?

Дано: Одноканальная СМО:

количество классов заявок:

интенсивности потоков:

Требуется: а) сформулировать условия, при которых u1 = 2 c ;

а) Время пребывания заявок класса 1: u1 = w1 + b1, где w1 – время ожидания; b1 = 1 / µ1 = 2 с – длительность обслуживания. Очевидно, что u1 = 2 c, если w1 = 0, то есть заявки 1-го класса не должны образовывать очередь. Для этого необходимо, чтобы:

• заявки 1-го класса имели абсолютный приоритет по отношению к заявкам 2-го класса; это означает, что заявки 2-го класса не смогут влиять на характеристики обслуживания заявок 1-го класса, однако это не исключает образования очереди заявок 1-го • для того чтобы заявки 1-го класса не образовывали очередь, процессы поступления и обслуживания заявок 1-го класса должны быть детерминированными, то есть интервалы между поступающими в систему заявками 1-го класса и длительности их обслуживания должны быть детерминированными (не случайными) величинами;

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

Проверим выполнение последнего условия: y1 = 1 / µ1 = 0,6 – система работает без перегрузок. Таким образом, для того чтобы u1 = 2 c, необходимо выполнение двух первых условий.

б) Определим u1 = ? при 1 = 21. Если интенсивность поступления заявок 1-го класса увеличится в 2 раза, то загрузка, то создаваемая заявками нагрузка тоже увеличится в 2 раза и станет равной y 1 = 21 / µ1 = 1,2, что означает перегрузку системы, следовательно, время ожидания и время пребывания заявок 1-го класса вырастут до бесконечности: u1 =.

Заметим, что если бы нагрузка не превысила значение 1, то время пребывания заявок 1-го класса осталось бы прежним: u1 = 2 c.

в) Определим u1 = ? при µ1 = 2µ1. Увеличение интенсивности обслуживания заявок 1-го класса приведёт к уменьшению нагрузки в раза: y " = 1 /(2 µ1 ) = 0,3, то есть система будет работать без перегрузки. С другой стороны, длительность обслуживания заявок тоже уменьшится в раза: b1 = 1 /( 2 µ1 ) = 1 с, следовательно, время пребывания станет равным Задача 2. Интенсивность поступления заявок в разомкнутую трехузловую СеМО равна 2 заявки в секунду. Среднее число заявок в узлах СеМО соответственно равно: 2, 4 и 6. Определить среднее время пребывания заявок в сети.

Требуется: определить U.

Среднее время пребывания заявок в СеМО определяется по формуле:

Здесь последовательно применены формулы (3.29), (3.15) и (3.5) для узла j.

Этот же результат можно получить, исходя из формулы Литтла (3.31), связывающей среднее время пребывания и число заявок в сети:

4.8. Самоконтроль: перечень вопросов и задач 1. Как зависит среднее время ожидания заявок в СМО от коэффициента вариации длительности обслуживания? Во сколько раз изменится среднее время ожидания заявок при переходе от постоянной длительности обслуживания к экспоненциально распределенной? Во сколько раз изменится среднее время ожидания при переходе от экспоненциального распределения длительности обслуживания к гиперэкспоненциальному распределению с коэффициентом вариации, равным 2?

2. Какое распределение длительности обслуживания заявок в СМО является предпочтительным для уменьшения среднего времени ожидания заявок?

3. Изменится ли разность между средним временем пребывания и средним временем ожидания заявок в СМО при изменении: а) скорости работы (быстродействия) прибора; б) интенсивности потока заявок;

в) количества приборов?

4. Изменится ли разность между средним числом заявок в системе и средней длиной очереди при изменении: а) скорости работы (быстродействия) прибора; б) интенсивности потока заявок; в) количества приборов?

5. Заявки поступают в одноканальную СМО с интервалом 2, минуты, длительность обслуживания заявок в приборе 45 секунд.

Определить загрузку и коэффициент простоя системы.

6. Интенсивность поступления заявок в трехканальную СМО – заявка в секунду, интенсивность обслуживания – 10 заявок в секунду.

Определить: а) вероятность того, что обслуживающий прибор работает; б) вероятность того, что обслуживающий прибор простаивает; в) среднее число заявок, находящихся на обслуживании; г) среднее число работающих приборов?

7. Интенсивность поступления заявок в четырехканальную СМО равна интенсивности обслуживания заявок одним прибором. Определить:

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

8. Длительность обслуживания заявок в одном приборе четырехканальной СМО равна 4 минуты. Определить предельную интенсивность поступления заявок в систему, при которой в системе существует стационарный режим?

9. Интенсивность поступления заявок в СМО – 15 заявок в секунду, длительность обслуживания одной заявки – 5 секунд. Определить число обслуживающих приборов, при котором в системе существует стационарный режим?

10. Заявки поступают в одноканальную СМО с интервалом 0, секунд, интенсивность обслуживания – 2,5 заявки в секунду, среднее время пребывания заявок в системе – 2 секунды. Определить среднюю длину очереди заявок.

11. Интенсивности поступления и обслуживания заявок в СМО соответственно равны 4 и 5 заявок в секунду. Определить среднее время пребывания заявок в системе, если известно, что средняя длина очереди равна 6.

12. Интенсивность обслуживания заявок в СМО равна 5 заявок в секунду. Определить предельную интенсивность поступления заявок в систему, при которой среднее время пребывания заявок в системе не превысит 1 секунду и средняя длина очереди не превысит 2.

13. При какой дисциплине обслуживания заявок средние времена ожидания заявок разных классов одинаковы?

14. При каких условиях среднее время ожидания заявок для ДО ОП является возрастающей (убывающей) функцией от номера класса заявок?

15. При каких условиях среднее время пребывания заявок для ДО ОП является возрастающей функцией от номера класса заявок?

16. Может ли среднее время пребывания заявок для ДО ОП быть убывающей функцией от номера класса заявок, если среднее время ожидания заявок является возрастающей функцией от номера класса заявок? Ответ пояснить.

17. Может ли заявка с более высоким относительным приоритетом иметь большее время пребывания, чем низкоприоритетная? Ответ обосновать.

18. При каких условиях среднее время ожидания заявок для дисциплины обслуживания с абсолютными приоритетами является возрастающей функцией от номера класса заявок?

19. В каких случаях среднее время ожидания заявок более высокого приоритета при ДО АП может иметь большее значение, чем заявок низкого приоритета?

20. Может ли среднее время ожидания заявок быть убывающей функцией от номера класса (приоритета) заявок?

21. Почему среднее время ожидания заявок наивысшего приоритета при использовании ДОАП отличается от нуля?

22. При каких условиях характер зависимости среднего времени пребывания заявок от номера класса совпадает с характером зависимости среднего времени ожидания? Могут ли зависимости среднего времени пребывания и среднего времени ожидания заявок от номера класса иметь противоположный характер?

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

24. Может ли среднее число заявок в СМО отличаться от средней длины очереди заявок больше, чем на единицу? Изменится ли разность между ними при изменении дисциплины обслуживания?

25. Изменится ли разность между средним временем пребывания и средним временем ожидания для заявок суммарного потока при изменении дисциплины обслуживания?

26. Можно ли утверждать, что если при какой-либо дисциплине обслуживания значение одной из характеристик суммарного потока (например, время ожидания) меньше значений аналогичной характеристики при другой дисциплине обслуживания, то и значения остальных характеристик при первой дисциплине также будут меньше?

Проиллюстрировать на примере.

27. Изменятся ли характеристики обслуживания всех классов заявок или только некоторых из них при ДО БП (ДО ОП, ДО АП), если изменить:

а) интенсивность поступления заявок какого-либо класса; б) среднюю длительность обслуживания какого-либо класса заявок?

28. Нарисовать зависимости среднего времени ожидания и среднего времени пребывания заявок в СМО от номера класса заявок для бесприоритетной дисциплины обслуживания. Объяснить характер этих зависимостей.

29. Нарисовать зависимости среднего времени ожидания заявок в СМО от суммарной загрузки в случае трех классов заявок и дисциплины обслуживания с относительными и абсолютными приоритетами. Провести анализ этих зависимостей.

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

Объяснить характер этих зависимостей.

31. Физический смысл и математическая запись закона сохранения времени ожидания. Сформулировать условия, сопровождающие закон сохранения. При каком условии в случае ДО АП не выполняется закон сохранения времени ожидания?

32. Как получается значение константы в законе сохранения времени ожидания?

33. При каком условии закон сохранения времени ожидания вырождается в закон сохранения: а) суммарной длины очереди заявок: L = Const; б) суммарного числа заявок в системе: M = Const; в) среднего времени ожидания; г) среднего времени пребывания?

34. Можно ли, изменив дисциплину обслуживания, изменить:

а) время ожидания заявок всех классов; б) время пребывания заявок всех классов; в) длительность обслуживания заявок; г) время ожидания заявок только одного класса; д) время ожидания заявок только двух классов?

Показать на примерах.

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

36. Что такое "защита от перегрузок" и для каких дисциплин обслуживания она существует? Проиллюстрировать на графике свойство "защиты от перегрузок".

37. В одноканальную СМО поступают 2 простейших потока заявок с интенсивностями 0,1 и 0,2 заявок в секунду; длительности их обслуживания соответственно 2 и 4 секунды. Чему будет равно среднее время ожидания заявок 1-го класса при использовании бесприоритетной дисциплины?

38. В одноканальную СМО поступают 2 класса заявок с интенсивностями 0,1 и 0,2 заявок в секунду. Длительности их обслуживания соответственно 2 и 3 секунды. Среднее время ожидания заявок при использовании бесприоритетной дисциплины обслуживания – 5 секунд.

После введения приоритетов среднее время ожидания заявок 1-го класса стало равно 2 секундам. Чему равно среднее время ожидания заявок 2-го класса?

39. В систему поступают заявки трех классов с интенсивностями 2, и 0,5 заявок в секунду соответственно. Сформулировать условия, при которых среднее время пребывания заявок всех классов будет одинаково.

40. В одноканальную систему обслуживания поступают заявки двух классов с интенсивностями 0,5 и 2 заявки в секунду. Интенсивности их обслуживания соответственно равны 5 и 1,25 заявок в секунду. а) При каких условиях время пребывания заявок 2-го класса будет равно 0, секунды? б) Чему будет равно время пребывания заявок 2-го класса, если при тех же условиях интенсивность поступления заявок 1-го класса увеличится в два раза? в) Чему будет равно время пребывания заявок 2-го класса, если при тех же условиях интенсивность их поступления увеличится в два раза? г) Чему будет равно время пребывания заявок 2-го класса, если при тех же условиях интенсивность их обслуживания увеличится в два раза?

41. Что показывает коэффициент передачи в СеМО?

42. Дать физическое толкование значения коэффициента передачи узла СеМО, равное: а) 4; б) 0,4.

43. В чём различие между эквивалентным и толерантным преобразованиями СеМО? Привести пример эквивалентного преобразования СеМО.

44. Что такое «узкое место» и какие способы используются для разгрузки «узкого места»?

45. Показать на графике, как изменится зависимость производительности и среднего времени пребывания заявок в замкнутой СеМО от числа циркулирующих в сети заявок после разгрузки узкого места. В каких случаях разгрузка узкого места может не дать положительного эффекта?

46. В двухузловой замкнутой СеМО циркулирует 1 заявка. Определить загрузку узлов 1 и 2, если известно, что загрузка узла 1 в 3 раза больше, чем загрузка узла 2.

47. В замкнутой двухузловой СеМО циркулирует одна заявка, которая последовательно переходит из одного узла в другой. Длительность обслуживания в узлах распределена по экспоненциальному закону с одним и тем же средним значением, равным 5 минут. По какому закону распределено время пребывания заявки в сети? Определить производительность замкнутой СеМО.

48. В замкнутой двухузловой СеМО циркулирует одна заявка, которая последовательно переходит из одного узла в другой. Длительности обслуживания в узлах 1 и 2 сети соответственно равны 2 и 3 с. Определить:

а) коэффициенты простоя узлов замкнутой СеМО; б) среднее число заявок, находящихся в каждом из узлов СеМО.

49. В замкнутой двухузловой СеМО циркулирует 4 заявки, которые последовательно переходят из одного узла в другой. Длительности обслуживания заявок в узлах сети одинаковы и равны 2 с. Среднее время ожидания заявок в узле 1 равно 3 с. Определить: а) производительность замкнутой СеМО; б) загрузку узлов сети; в) среднее число заявок, находящихся в состоянии ожидания.

50. В разомкнутую СеМО поступают заявки с интервалом 5 секунд.

Время пребывания заявок в сети равно 15 секунд. Определить среднее число заявок в сети и интенсивность выходящего из сети потока заявок.

51. Средние времена ожидания заявок в узлах трехузловой СеМО соответственно равны: 1, 2 и 4 секунды, а коэффициенты простоя узлов равны 0,8; 0,4; 0,7. Определить среднее время ожидания заявок в сети, если известно, что длительности обслуживания заявок во всех узлах одинаковы и коэффициент передачи узла 1 равен 2.

52. Известны вероятности состояний двухузловой замкнутой СеМО:

P(0,4)=0,1; P(1,3)=0,4; P(2,2)=0,2; P(3,1)=0,1; P(4,0)=0,2, где состояние (i1, i2) задает число заявок в одноканальном узле 1 и трехканальном узле соответственно. Определить среднее число заявок в СеМО, находящихся в состоянии ожидания.

53. Известны вероятности состояний трехузловой замкнутой СеМО:

P(0,0,2)=0,1; P(0,1,1)=0,2; P(0,2,0)=0,15; P(1,0,1)=0,35; P(1,1,0)=0,05;

P(2,0,0)=0,15, где состояние (i1, i2, i3) задает число заявок в узле 1, 2, соответственно. Определить среднее число параллельно работающих узлов сети.

54. Известны вероятности состояний трехузловой замкнутой СеМО:

Р(0,0,2)=0,1; P(0,1,1)=0,3; P(0,2,0)=0,4; P(1,0,1)=0,05; P(1,1,0)=0,05;

P(2,0,0)=0,1. Длительности обслуживания заявок во всех одноканальных узлах одинаковы. Определить значения коэффициентов передач второго и третьего узлов сети, если известно, что коэффициент передачи первого узла равен 2.

55. Известны вероятности состояний трехузловой замкнутой СеМО:

Р(0,0,2)=0,1; P(0,1,1)=0,3; P(0,2,0)=0,4; P(1,0,1)=0,05; P(1,1,0)=0,05;

P(2,0,0)=0,1. Определить производительность СеМО, если известно, что коэффициент передачи первого узла (четырехканального) равен 2, а средняя длительность обслуживания заявок в этом узле равна 0,1 с.

Раздел 5. ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ (МОДЕЛИ

СЛУЧАЙНЫХ ПРОЦЕССОВ)

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

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

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

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

5.1. Понятие случайного процесса Основными для случайных процессов являются понятия состояния и перехода из одного состояния в другое.

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

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

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

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

Поэтому при моделировании реальных систем часто говорят о состоянии системы и переходе системы из одного состояния в другое.

Если множество состояний, в которых может находиться процесс счётное, то есть все возможные состояния могут быть пронумерованы, то соответствующий процесс называется случайным процессом с дискретными состояниями или просто дискретным случайным процессом. В этом случае переменные, описывающие состояния случайного процесса, принимают либо целочисленные значения, либо вполне конкретные отделённые друг от друга дискретные значения. Обычно состояния дискретного случайного процесса определяются таким образом, чтобы каждое возможное состояние могло быть обозначено порядковым номером, при этом число возможных состояний системы может быть конечным: E1, E 2,..., E n или бесконечным: E1, E 2,..., E n,... (иногда состояния нумеруются, начиная с нуля: E 0, E1,..., E n,... ). Для случайного процесса с дискретными состояниями характерен скачкообразный переход из одного состояния в другое (рис.5.1,а). Например, случайный процесс, протекающий в простейшей СМО с однородным потоком заявок, может быть представлен количеством заявок, находящихся в системе в произвольный момент времени. Тогда состояние E k случайного процесса и, следовательно, самой системы будет означать, что в СМО находится ровно k = 0,1, 2,... заявок.

Если множество состояний не может быть пронумеровано, то имеем случайный процесс с непрерывными состояниями или просто непрерывный случайный процесс, для которого характерен плавный переход из состояния в состояние и который задаётся в виде непрерывной ункции времени: E (t ) (рис.5.1,б). Например, процесс изменения температуры некоторого объекта может рассматриваться как случайный процесс с непрерывными состояниями.

Рис.5.1. Процессы с дискретными (а) и непрерывными (б) состояниями Поскольку модели массового обслуживания относятся к классу дискретных систем, то в дальнейшем будут рассматриваться только случайные процессы с дискретными состояниями.

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

5.1.1. Случайные процессы с дискретными Предположим, что система может находиться в одном из состояний E1, E2,... (часто состояния обозначаются просто номерами 1, 2,...). Пусть состояние системы меняется скачкообразно в зависимости от некоторого параметра t, причем переход из состояния в состояние является случайным. Будем называть параметр t – временем и считать, что t пробегает либо целые, либо действительные числа. Обозначим через Z (t ) случайный процесс, описывающий состояние системы в момент времени t.

Случайный процесс Z (t ) называется случайным процессом с дискретным временем, если переходы из состояния в состояние возможны только в строго определенные заранее фиксированные моменты времени, которые можно пронумеровать: t1, t2,K.

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

Процесс с дискретным временем имеет место либо когда структура системы такова, что ее состояния могут изменяться только в заранее определенные моменты времени, либо когда предполагается, что для описания процесса достаточно знать состояние системы в отдельные моменты времени. Тогда эти моменты можно пронумеровать и говорить о состоянии Ei в момент tk или просто в момент k ( k = 0,1, 2,... ).

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

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

Граф переходов называется размеченным, если на дугах графа указаны условия перехода в виде вероятностей переходов (для процессов с дискретным временем) или интенсивностей переходов (для процессов с непрерывным временем).

Состояния Ei могут быть:

• невозвратными, если процесс после какого-то числа переходов непременно покидает их;

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

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

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

Описывающий поведение системы процесс Z (t ) называется цепью Маркова.

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

Пусть время нахождения случайного процесса в некотором состоянии Ei до его перехода в другое состояние Ej распределено по экспоненциальному закону с функцией распределения Fij ( ) = 1 e ij, где ij - параметр распределения, характеризующий частоту перехода из состояния Ei в состояние Ej и определяемый как величина, обратная среднему времени нахождения случайного процесса в состоянии Ei до момента его перехода в состояние Ej. Вычислим вероятность того, что случайный процесс перейдет в состояние Ej в течение интервала времени при условии, что в состоянии Ei процесс уже находится в течение времени 0. Эта условная вероятность равна Из последнего выражения следует, что вероятность перехода из одного состояния в другое зависит только от исходного состояния Ei и не зависит от интервала времени 0, то есть от того, как долго находился процесс в состоянии Ei, а также от того, какие состояния предшествовали состоянию Ei. Другими словами, поведение случайного процесса не зависит от предыстории и определяется только его состоянием в настоящий момент, то есть процесс является марковским.

Еще одно замечательное свойство экспоненциального распределения вытекает из полученного выражения, а именно: если время нахождения случайного процесса в некотором состоянии Ei до его перехода в другое состояние Ej распределено по экспоненциальному закону с параметром ij, то интервал времени от любого случайного момента времени до момента перехода в состояние Ej имеет такое же экспоненциальное распределение с тем же параметром ij. Эта особенность является следствием отсутствия последействия, присущего всем процессам с экспоненРаздел 5. Численное моделирование циальным распределением времени нахождения в том или ином состоянии.

Таким образом, безусловная Pij ( ) и условная Pij ( 0 ) вероятности перехода в другое состояние за время для марковского процесса одинаковы и равны Пусть интервал времени достаточно мал. Тогда, разлагая e ij в ряд по степеням ij при 0 и пренебрегая величинами высшего порядка малости, получим вероятность перехода из одного состояния в другое за бесконечно малый интервал времени:

5.2. Параметры и характеристики марковского случайного процесса 5.2.1. Параметры марковского случайного Для описания марковского случайного процесса с дискретными состояниями используется следующая совокупность параметров:

• перечень состояний E1,..., E n, в которых может находиться случайный процесс;

• матрица переходов, описывающая переходы случайного процесса между состояниями в виде:

матрицы вероятностей переходов Q для процессов с матрицы интенсивностей переходов G для процессов с • начальные вероятности p1 (0), K, pn (0).

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

Для случайных процессов с дискретным временем изменения состояний происходят только в определенные моменты времени t1, t2,K, tk,K. Переходы между состояниями описываются вероятностями переходов. Если непосредственный переход из одного состояния в другое невозможен, то вероятность, соответствующая данному переходу, равна нулю. Обозначим через qij условную вероятность того, что в момент времени tk +1 случайный процесс перейдет в состояние Ej при условии, что в момент tk процесс находился в состоянии Ei. Если переход из состояния Ei в Ej зависит только от этих двух состояний, то есть условная вероятность qij не изменяется при дополнительной информации о поведении процесса до момента tk, получим цепь Маркова.

Цепь Маркова называется однородной, если вероятности переходов не зависят от момента времени tk, и неоднородной, если вероятности переходов являются функциями tk, то есть qij = qij (k ).

Вероятности переходов задаются в виде квадратной матрицы вероятностей переходов Q = [qij | i, j = 1, n], элементы которой удовлетворяют условиям:

Матрица, элементы которой удовлетворяют указанным условиям, называется стохастической.

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

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

Интенсивность перехода gij из состояния Ei в состояние Ej определяется как предел отношения вероятности перехода Pij ( ) системы за промежуток времени из Ei в Ej к длине этого промежутка:

Отсюда следует, что вероятность перехода за бесконечно малый промежуток времени равна: g ij (i j ). Вероятность двух и более переходов за время имеет порядок ( )2 и выше и предполагается бесконечно малой величиной.

Если интенсивности переходов постоянны и не зависят от времени t, то есть от того, в какой момент начинается промежуток, то марковский процесс называется однородным. Если интенсивности gij представРаздел 5. Численное моделирование ляют собой функции времени t, процесс называется неоднородным.

В дальнейшем будем рассматривать только однородные марковские процессы.

Интенсивности переходов задаются в виде квадратной матрицы G = [ g ij | i, j = 1, n], называемой матрицей интенсивностей переходов, диагональные элементы которой определяются из условия:

откуда Матрица, в которой сумма элементов в каждой строке равна нулю, называется дифференциальной.

Выше было показано, что в случае экспоненциального закона распределения времени нахождения случайного процесса в некотором состоянии вероятность перехода из одного состояния в другое за бесконечно малый интервал времени определяется выражением (5.1) и равно Pij ( ) = ij. Отсюда следует, что интенсивность перехода представляет собой параметр экспоненциального распределения:

Начальные вероятности p1 (0), K, pn (0), где pi (0) – вероятность того, что в момент времени t = 0 система находится в состоянии Ei (i = 1,K n ), задают состояние системы в начальный момент времени t = 0.

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

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

5.2.2. Характеристики марковского случайного Изучение случайных процессов заключается в определении вероятностей того, что в момент времени t система находится в том или ином состоянии. Совокупность таких вероятностей, описывающих состояния системы в различные моменты времени, дают достаточно полную информацию о протекающем в системе случайном процессе.

Рассмотрим систему с конечным числом состояний: E1, …, En.

Обозначим через pi (t ) вероятность того, что в момент времени t система находится в состоянии Ei: pi (t ) = Pr{Z (t ) = Ei }.

В любой момент времени t система может находиться в одном из n возможных состояний, то есть для любого момента времени t выполняется условие:

которое называется нормировочным.

Совокупность вероятностей pi (t ) может быть представлена вектором с числом координат, равным числу возможных состояний системы:

причем Вектор, обладающий свойствами (5.6), называется стохастическим.

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