Конспект лекций учебной дисциплины

«Моделирование сетевых процессов»

(наименование дисциплины в соответствии с утвержденным учебным планом подготовки)

Тема № 1 «Общие сведения о случайных процессах»

Лекция № 1 «Методы статистического моделирования систем»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1. Метод статистического моделирования систем

2. Случайные процессы и их классификация

1. Метод статистического моделирования систем

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

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

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

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

Различают две области применения метода статистического моделирования:

- для изучения стохастических систем;

- для решения детерминированных задач.

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

В результате статистического моделирования системы S получается серия частных значений искомых величин или функций, статистическая обработка которых позволяет получить сведения о поведении реального объекта или процесса в произвольные моменты времени. Если количество реализации N достаточно велико, то полученные результаты моделирования системы приобретают статистическую устойчивость и с достаточной точностью могут быть приняты в качестве оценок искомых характеристик процесса функционирования системы S.

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

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

Можно выделить следующие этапы моделирования случайных величин:

• генерирование N реализации случайной величины с требуемой функцией распределения;

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

• статистическая обработка реализации.

Особенностью первого этапа является то, что все методы для получения заданного распределения используют преобразование равномерно распределенной величины.

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

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

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

2. Случайные процессы и их классификация

Случайным процессом называется случайная функция аргумента t, где t текущее время. Случайный процесс обозначается прописными буквами греческого алфавита ,, . Допустимо и другое обозначение, если оно заранее оговорено .

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

Реализации x(t), y(t), z(t) по отношению к соответствующим процессам ,, играют ту же роль, что и возможныезначения х, у, z по отношению к своим случайным величинам ,, . Вид конкретной реализацииx(t) может задаваться определенной функциональной зависимостью аргумента t или графиком. Другими словами, это обычная детерминированная функция аргументаt.

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

Непрерывный случайный процесс характеризуется тем, что t и х являются непрерывными величинами (рис. 1,а). Таким процессом, например, является шум на выходе радиоприемного устройства.

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

Случайная последовательность характеризуется тем, что t является дискретной, а х — непрерывной величинами (рис. 1,в). В качестве примера можно указать на временные выборки в конкретные моменты времени из непрерывного процесса.

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

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

Рис. 1

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

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

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

К случайным модулированным колебаниям относятся модулированные колебания, у которых тот или иной параметр модулируется случайным образом, то есть у которого модулирующая функция является случайным процессом. Таким образом, модулированное колебание, являясь функцией случайного процесса, также представляет собой случайный процесс. Примерами являются AM, ЧМ и ФМ колебания, у которых амплитуда, частота или фаза изменяются в соответствии со случайной модулирующей функцией.

Контрольные вопросы:

1. Что называется случайным процессом?

2. Назовите области статистического моделирования?

3. Назовите этапы моделирования случайных величин?

Тема № 1 «Общие сведения о случайных процессах»

Лекция № 2 «Способы описания случайных процессов»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1. Способы описания случайных процессов

2. Эргодическое свойство стационарных процессов

1. Способы описания случайных процессов.

Существуют два способа представления случайных процессов.

1. Случайный процесс представляется в виде совокупности или ансамбля всех своих возможных реализаций. То, какая конкретно реализация будет наблюдаться в испытании, является случайным событием. На рис. 1,а показан случайный процесс £(t), в ансамбль которого входят три реализации x₁(t)_, x₂(t), x₃(t), наблюдаемые в испытании с определенными вероятностями.

2. Случайный процесс рассматривается какn-мерная случайная величина или n-мерный вектор (,,...,), каждаяпроекция которого является отсчетом случайного процесса в моменты времени t₁, t₂, ..., t (рис. 1,б). Эти проекции вектора или отсчеты процесса будем называть сечениями случайного процесса:

(2.1)

Сечения (1.1) являются случайными величинами, так как из-за случайного выбора реализации их конкретные значения до опыта неизвестны. На рис. 1. пунктиром показан возможный ход случайного процесса и соответственно случайные величины ,,...,на осях возможных значений

Рис. 1

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

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

В соответствии с этим n-мерая функция распределения случайного процесса определится выражением

(2.2)

Выражение (2.2) показывает, что в общем случае зависит от2n аргументов: от n наперед заданных возможных значений сечений () и от п моментов времени (t₁, t₂, ..., t), в которых эти сечения берутся. Вероятностный смысл выражения (2.2) поясняется рис. 3,а. для n=3: функция определяет вероятностьтого, что реализация случайного процессапройдет нижезаданных значений в моменты времени t₁, t₂, ..., t.

Многомерная плотность вероятности по определению равна частной производной n-го порядка от по возможным значениям

(2.3)

Плотность вероятности n-го порядка в общем случае также зависит от тех же 2n аргументов. Вероятностный смысл выражения (2.3) поясняется рис. 2б, для n=3. Плотность вероятности умноженная на dz₁,dz₂,dz₃, определяет вероятность прохождения реализации x(t) процесса черезdx₁, dx₂ , dx₃, находящихся в сечениях t₁, t₂, t₃ у значений x₁, x₂, x₃.

Рис. 2

Произведение двумерной плотности вероятности на dx₁dx₂ характеризует вероятность того, что реализация x(t) случайного процесса в моменты времени t₁, t₂ пройдет через интервалы . Это означает, что двумерная плотность вероятности содержит сведения о связи между двумя сечениями случайного процесса, проведенными в моменты t_j и t₂.

Одномерная плотность вероятности , гдех₁=х, t₁=t определяет закон распределения случайной величины, полученной в результате сечения случайного процесса в момент t₁=t. Индекс 1 у времени и возможного значения здесь опускается, потому что сечение одно и надобность в индексе отпадает.

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

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

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

(2.4)

(2. 5)

Для определения корреляционной функции требуется использование двумерной плотности вероятности

(2.6)

не изменится, если все отсчеты времени сместить на одну и ту же величину:

(2.7)

Если выбрать , тоn-мерная плотность вероятности не будет зависеть от начала отсчета времени

(2.8)

Таким образом, для стационарного процесса одномерная плот­ность вероятности вообще не зависит от времени, а двумерная плот­ность зависит не в отдельности от t₁ и t₂ , а от их разности

(2.9)

(2.10)

В свою очередь, из выражения (1.9) и (1.10) вытекает, что математическое ожидание и дисперсия стационарного процесса не за висят от времени, а корреляционная функция зависит от :

(2.11)

(2.12)

(2.13)

Из (2.11), (2.12) и (2.13) следует, что математическое ожидание постоянно и поэтому для стационарного процесса характеризует постоянную составляющую процесса; постоянность характеризует то, что в каждой точке времени t средняя удельная мощность флюктуации (то есть мощность переменной составляющей) одна и та же; зависимость отозначает, что для стационарногопроцесса не важно, в каких точках t₁ и t₂ берутся сечения, важна разность между ними .

Если условие (2.7) не выполняется, то случайный процесс называется нестационарным. Иногда о стационарности судят только по выполнению равенств (2.9), (2.10) и, соответственно, (2.11), (2.12), (2.13). Говорят, что, если выполняются равенства (2.9) и (2.10), то процесс является стационарным, не интересуясь при этом, выполняется условие (2.7) или нет. Такой подход дает более широкое толкование стационарности.

2. Эргодическое свойство стационарных процессов

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

Пусть имеется одна длинная реализация x(t) случайного процесса (t). Эта реализация определена на интервале

Найдем среднее значение этой реализации путем ее усреднения во времени на достаточно большом интервале:

(2.14)

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

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

(2.15)

(2.16)

По своему физическому смыслу величины (2.14), (2.15), (2.16) являются числовыми характеристиками, совпадающими со средним значением, дисперсией и корреляционной функцией процесса (t). Однако они получены в результате усреднения во времени одной длинной реализации x(t) или функции от нее.

Говорят, что стационарный процесс обладает эргодическим свойством, если с вероятностью, близкой к единице, числовые характеристики, полученные в результате усреднения одной длинной реализации по времени, равны этим же характеристикам, полученным в результате усреднения по ансамблю. При этом усреднением по ансамблю называют определение числовых характеристик с использованием плотности вероятности, т.е. по формулам (2.11), (2.12) и (2.13), так как плотность вероятности характеризует всю совокупность или ансамбль реализаций.

Таким образом, для эргодического стационарного процесса справедливы равенства:

,

(2.17)

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

Контрольные вопросы:

1. Назовите способы представления случайных процессов?

2. Какой случайный процесс называется стационарным?

3. Какой случайный процесс называется нестационарным?

4. Какой случайный процесс называется эргодическим?

Тема № 2 «Сетевое моделирование процессов»

Лекция № 3 «Назначение сетевого моделирования»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1. Сетевое моделирование

2. Классификация сетевых моделей

3. Правила построение сетевых моделей

1. Сетевое моделирование

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

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

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

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

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

Операции по отношению к затратам средств и времени на их осу­ществление подразделяются на действительные и фиктивные.

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

Фиктивная операция - операция, на осуществление которой не требуется никаких затрат.

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

Событием называется факт достижения требуемого результата.

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

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

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

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

2. Классификация сетевых моделей

По количеству сетей, описывающих исследуемый комплекс операций, различают односетевые и многосетевые модели. По количеству конечных целей, для достижения которых осуществляется комплекс операций, сетевые модели подразделяются на одноцелевые (с одним завершающим событием) и многоцелевые (с несколькими завершающими событиями). По количеству исходных событий или операций различают сеть с одним исходным событием (одной исходной операцией) и несколькими исходными событиями (несколькими исходными операциями). По степени неопределенности сетевой модели разли­чают детерминированные и стохастические сетевые модели. По количеству операций, составляющих комплекс, сетевые модели подразделяются на сети большого объема (свыше 10 000 операций), среднего объема (от 1500 до 10 000 операций) и малого объема (до 1500 операций). На рис. 2. приведена рассмотренная классификация сетевых моделей.

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

Рис. 2.

3. Правила построение сетевых моделей

Правила построения сетевых моделей определяются сферой их при­менения, к которой относится сетевое планирование и управление, и со­ответствующим программным обеспечением современных ЭВМ, раз­работанным для построения и анализа сетей. При построении сетевой модели ее вершинам обычно присваиваются числа, которые служат номерами вершин. Тогда каждой дуге сети может быть сопоставлена пара чисел, первое из которых соответствует вершине, из которой исходит дуга, а второе - вершине, в которую заходит дуга.

К основным правилам, которыми следует руководствоваться при по­строении сетевых моделей, относятся следующие.

Для каждой вершины сети номер любой предшествующей ей вершины должен быть меньше ее собственного номера.

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

3. В сети не должно быть петель, контуров и кратных дуг.

4. В сети должны быть только одна исходная и одна завершающая вершины.

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

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

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

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

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

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

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

составление перечня операций;

составление матрицы смежности;

заполнение таблицы слоев;

нумерация вершин и построение сетевого графика.

Контрольные вопросы:

1. Что такое сетевая модель?

2. Назовите основные правила построения сетевых моделей?

3. Назовите основные этапы построения сетевых моделей?

Тема № 2 «Сетевое моделирование процессов»

Лекция № 4 «Анализ сетевых моделей»

Цель лекции.

а) учебная цель:

Целью является формирование у слушателей целостного представления о принципах применения элементов теории вероятностей при моделировании сетевых процессов – элемента систем массового обслуживания.

План лекции

1. Оценивание продолжительности операций

2. Параметры сетевой модели