Обработка и анализ результатов моделирования

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

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

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

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

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

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

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

6.1 Основная идея регрессионного анализа

Для исследования взаимосвязи между величинами Х (вход) и y (выход) используются методы корреляционного и регрессионного анализа. Результаты корреляционного анализа позволяют сделать вывод о степени зависимости между переменными, а форма зависимости уточняется методами регрессионного анализа.

На значение величины y оказывают влияние стохастические воздействия разного рода, поэтому форма связи между величинами Х и y определяется линией регрессии, показывающей, как в среднем изменяется величина y при изменении входной величины Х, т.е. приходится говорить о связи средних значений величины y c X. Эту связь характеризуют условным математическим ожиданием величины y, вычисляемым при условии, что величина Х приняла определенное значение, а аппроксимирующая функция строится как функция регрессии.

f(X, B) M[y/X]

где B - неизвестные параметры уравнения регрессии.

Задача регрессионного анализа ставится следующим образом. Для каждого i-го опыта имеется набор значений (x_i1,...,x_ik) входных параметров
X₁ ¸X_k и соответствующее им значение выходного параметра y_i. Пример опытных данных приведен в табл.6.1.

Таблица 6.1

№ опыта	Входы	Выходы Y
X1	X2	---	Xk
	x11	x12	---	x1k	y1
	x21	x22	---	x2k	y2
-----	-----	-----	---	-----	-----
n	xn1	xn2	---	xnk	yn

Необходимо определить зависимость выхода y от входных факторов x_i1,...,x_ik, которая для случая линейной связи будет иметь следующий вид:

y = b₀ + b₁x₁ + b₂x₂+... + (6.1)

Задача сводится к определению оценок коэффициентов уравнения регрессии b₀, b₁,..., b_k, которые с определенной степенью вероятности будут отражать влияние аргументов x_i1,..., x_ik на y.

Для определения b_k используется метод наименьших квадратов.

Таким образом, задача сводится к минимизации:

(6.2)

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

- рассчитанное значение выходной переменной.

Можно выражение (6.2) представить с учетом (6.1):

(6.3)

То есть, процесс сводится к нахождению таких значений коэффициентов b₀, b₁,..., b_k, которые давали бы минимальное расхождение между расчетными и измеренными значениями y.

Это условие может быть выполнено, если приравнять к нулю частные производные S по каждому из коэффициентов b₀, b₁,..., b_k и просуммировать их по индексу i. В результате получается система обычных уравнений:

(6.4)

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

Однако на практике часто предпочитают пользоваться несколько иной методикой определения значений коэффициентов b₀, b₁,..., b_k уравнения регрессии, которая дает возможность определить как значения коэффициентов, ("степень" их участия в "образовании" выходной величины), так и пригодность полученного уравнения для случаев зависимости любой степени.

Если фактор может принимать значения только (+1) и (-1) – верхний и нижний уровень (дробный факторный эксперимент), то соответствующую ему переменную X называют кодированной.

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

для двух переменных: y = b₀ + b₁X₁ + b₂X₂

для трех переменных: y = b₀ + b₁X₁ + b₂X₂ + b₃X₃

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

для двух переменных: y = b₀ + b₁X₁ + b₂X₂ + b₁₂X₁X₂

для трех переменных:

y=b₀+b₁X₁+b₂X₂+b₃X₃+b₁₂X₁X₂+b₁₃X₁X₃+b₂₃X₂X₃+b₁₂₃X₁X₂ X₃

6.2 Общая схема проведения расчетов

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

1. Рассчитывают построчные средние.

,

где n - общее число экспериментов;

m - число повторных опытов (серий).

Таблица 6.2

Пример карты проведения экспериментов для двух переменных.
? опыта	Входы	Выходы	Построчные средние	Построчные дисперсии
X1	X2	X1X2	y 1	...	y m
	-1	-1	+1	y 11	...	y 1m
	+1	-1	-1	y 21	...	y 2m
	-1	+1	-1	y 31	...	y 3m
	+1	+1	+1	y 41	...	y 4m

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

2.1. Определяются построчные дисперсии:

2.2.Определяется сумма построчных дисперсий:

2.3. Определяется максимальная из построчных дисперсий:

2.4. Проверяется воспроизводимость опытов по критерию Кохрена:

2.5. Определяется табличное значение критерия Кохрена H_табл, выбираемое в зависимости от числа опытов n, числа повторных опытов (число серий) m, и уровня значимости p (надежности). Опыты считаются равноточными, если: H < H_табл. В случае неравноточности опытов необходимо увеличить число повторных экспериментов или повысить их точность.

3. Определяются коэффициенты уравнения регрессии.

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

В формулах суммирования у кодированной переменной первый индекс r - есть номер опыта (строки) в карте проведения эксперимента, второй индекс i - номер кодированной переменной. Например, - значение кодированной переменной в третьем опыте, равное, например, (+1) (см. табл.5.2).

Коэффициент b₀ по физическому смыслу соответствует опыту с поддержанием всех варьируемых факторов на средних (нулевых) уровнях.

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

Для этого требуется рассчитать следующие показатели.

4.1. Дисперсия эксперимента:

;

4.2. Усредненная дисперсия эксперимента с учетом повторности опытов:

4.3. Определяют дисперсию и среднюю квадратичную ошибку коэффициентов регрессии:

4.4. Определяется область значимости значений коэффициентов регрессии: Db=±t*s_b, где t - табличное значение критерия Стьюдента, выбираемое в зависимости от числа степеней свободы: f₂=n*(m-1) и выбранного уровня значимости (обычно 0.05).

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

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

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

6.3 Оценка качества имитационной модели

Оценка качества модели является завершающим этапом ее разработки и преследует две цели:

проверить соответствие модели ее предназначению (целям исследования);

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

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

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

методической ошибкой, присущей данному методу.

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

– моделирование случайных факторов, основанное на использовании датчиков случайных чисел, которые могут вносить «искажения» в поведение модели;

– наличие нестационарного (переходного) режима работы;

– использование разнотипных математических методов в рамках одной модели;

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

– необходимость синхронизации работы отдельных компонентов модели;

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

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

адекватность;

устойчивость;

чувствительность.

6.3.1 Адекватность модели

В общем случае под адекватностью понимается степень соответствия модели тому реальному объекту или явлению, для описания которого она строится.

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

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

! Статистические критерии не могут доказать ни одной гипотезы: они могут лишь указать на отсутствие опровержения.

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

по средним значениям откликов модели и системы;

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

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

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

В результате No опытов на реальной системе получают множество значений (выборку) у *. Выполнив Nм экспериментов на модели, также получают выборку значение наблюдаемой переменной у.

Затем вычисляются оценки математического ожидания и дисперсии откликов модели и системы, после чего выдвигается гипотеза Н₀ о близости средних значений величин у * и у (в статистическом смысле). Основой для проверки является t-статистика (распределение Стьюдента). Ее значение, вычисленное по результатам испытаний, сравнивается с критическим значением t_кр, взятым из справочной таблицы. Если выполняется неравенство t_n<t_кр, то гипотеза принимается.

Пример. Проведено n2=10 экспериментов на системе (Y) и n1=50 экспериментов на модели (Х). Получились следующие эмпирические оценки математического ожидания и дисперсии:

МХ=112,1 МУ=100,2

DX=211 DY=86.

Соответствует ли модель реальной системе?

Т-критерий

Т = *

В нашем случае

Т=*=2.48

Для уровня значимости a (вероятность погрешности, ошибки) и k=n1+n2-2=58 степеней свободы из таблицы выбираем t_ak=1.960. Если реализация Т удовлетворяет неравенству ½t½> t_ak, то гипотезу Но отвергают.

Следовательно, в нашем примере нельзя принимать эту модель за адекватную.

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

где - рассчитанное по полученному уравнению регрессии значение выхода для i -ого опыта;

- среднее значение выходной переменной, полученное в результате i -ого эксперимента;

k - число факторов;

n - общее число опытов (строк в карте экспериментов).

Далее определяется значение критерия Фишера: и табличное F_табл значение этого критерия при значениях числа степеней свободы:
f₁ = n - k –1 и числа степеней свободы: f₂ = n*(m-1).

Если F < F_табл, то, следовательно, полученная в результате регрессионная модель является адекватной (пригодной).

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

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

6.3.2 Оценка устойчивости

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

Каким образом может быть оценена устойчивость модели? Универсальной процедуры проверки не существует. Разработчик вынужден прибегать к методам «для данного случая», частичным тестам и здравому смыслу. Часто бывает полезной апостериорная проверка. Она состоит в сравнении результатов моделирования и результатов измерения на системе после введения в нее изменений. Если результаты моделирования приемлемы, то уверенность в устойчивости модели возрастает.

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

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

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

Проверку указанной гипотезы Н проводят при следующих исходных данных: есть две выборки X=(x₁,x₂,…x_n) и Y=(y₁,y₂,…y_n) полученные различных значений рабочей нагрузки; относительно законов распределения Х и Y никаких предположений не делается.

Значения обеих выборок упорядочиваются вместе по возрастанию, затем анализируется взаимное расположение x_i и y_j. В случае x_i<y_j, говорят, что пара значений (x_i,y_j) образует инверсию.

Пусть, например, n=m=3. После упорядочивания получилась такая последо­вательность -- y₁ x₁ y₃ x₂ y₂ x₃.

Имеем инверсии (x₁,y₁), (x₂,y₁), (x₃,y₁), (x₂,y₃), (x₃,y₂), (x₃,y₃), то есть U=6.

Подсчитывают полное число инверсий U. Если гипотеза верна, то U не должно сильно отклоняться от своего математического ожидания М=. От гипотезы отказы­ваются, если |U-M|>Uкр, (Uкр определяется по таблице для заданного уровня значимости).

6.3.3 Оценка чувствительности

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

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

вычисляется величина относительного среднего приращения параметра X_k:

D X_k =;

проводится пара отдельных экспериментов при значениях X_k=X_kmax и X_k=X_kmin, и средних фиксированных значениях остальных параметров. Определяются значения отклика модели Y1=f(X_kmax) и Y2=f(X_kmin);

вычисляется относительное приращение наблюдаемой переменной Y:

DY=

В результате для k-го параметра модели имеют пару значений (D X_k, D Y_k), характери­зующих чувствительность модели по этому параметру.

Аналогично формируются пары для остальных параметров модели, которые образуют множество {D X_k, D Y_k }.

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

6.4 Калибровка модели

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

Как правило, процесс калибровки носит итерационный характер и состоит из трех основных этапов:

глобальные изменения модели (например, введение новых процессов, изменение типов событий и т.д.);

локальные изменения (в части изменений некоторых законов распределения моделируемых случайных величин);

изменение специальных параметров, называемых калибровочными.

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

Вообще, целесообразно объединить оценку целевых свойств имитационной модели и ее калибровку в единый процесс. Именно такая стратегия принята в статистическом методе калибровки (рис. 6.1).

Рис. 6.1 Статистический метод калибровки

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

Шаг 1. Сравнение выходных распределений.

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

Шаг 2. Балансировка.

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

Шаг 3. Оптимизация модели.

Цель – обеспечение требуемой точности результатов. Здесь возможны 3 основных направления работ: дополнительная проверка качества датчиков случайных чисел; снижение влияния переходного режима; применение специальных методов понижения дисперсии.

6.5 Вопросы для самоконтроля

1. Задачи регрессионного анализа.

2. Уравнение регрессии.

3. Оценка качества модели.

4. Статистические критерии адекватности.

5. Критерии устойчивости.

6. Оценка чувствительности.

7. Назначение и этапы процедуры калибровки модели.

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

7.1 Основные понятия теории массового обслуживания

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

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

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание. Это можно изобразить в виде некоторого i-го прибора обслуживания Пi, состоящего из накопителя заявок Hi, в котором может находиться одновременно li=0¸Li заявок (где Li – емкость i-го накопителя), и канала обслуживания заявок (или просто канала) Ki (рис.7.1)

Ui Hi Ki

Yi

Wi

Пi

Рис. 7.1 Прибор обслуживания П

На каждый элемент прибора поступает два потока событий: в накопитель Hi – поток заявок Wi, на канал Ki – поток обслуживаний Ui. (Поток событий – последо­вательность событий, происходящих одно за другим в какие-то случайные моменты времени).

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

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

Процесс функционирования прибора Пi можно представить как процесс изменения состояний его элементов во времени Zi(t). Переход в новое состояние для Пi означает изменение количества заявок, которые в нем находятся (в канале и в накопителе). Таким образом, вектор состояний для Пi имеет вид Zi=(Zi^H, Zi^K), где Zi^H -- состояние накопителя Hi (Zi^H=0 накопитель пуст, Zi^H =1 – в накопителе 1 заявка, … Zi^H =Li – накопитель полон, Li – емкость накопителя); Zi^K – состояние канала Ki (Zi^K =0 – канал свободен, Zi^K =1 – канал занят обслуживанием).

В практике моделирования систем имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые композицией многих элемен­тарных приборов Пi (сети массового обслуживания). Если каналы Ki различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальные Q-схемы). А если приборы Пi или их композиции соединены последовательно – то имеет место многофазное обслуживание. В этом случае собственными внутренними параметрами Q-схемы будет являться коли­чество фаз Lф, количество каналов в каждой фазе L_Kj, j=1¸Lф, количество накопителей в каждой фазе L_Нj, j=1¸Lф, и емкость i-го накопителя Li^H.

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

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

входной выходной

поток поток

поток

отказов

Рис. 7.2 Пример многоканальной Q-схемы

Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию: системы с потерями (отказами), когда Li^H=0, то есть накопителя нет, а есть только канал обслуживания К, (например, телефонный звонок ); системы с ожиданием (без отказов), когда Li^H=¥, то есть накопитель имеет бесконечную емкость и очередь заявок неограничена, (например, очередь на жилье); системы смешанного типа (с огра­ниченной очередью), емкость накопителя ограничена, (пример – запись на прием к врачу по талонам).

Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.

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

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

При рассмотрении алгоритмов функционирования приборов обслуживания Пi (каналов К и накопителей Н) необходимо так же задать набор правил, по которым заявки покидают Нi и Ki. Для Hi—либо правила переполнения, по которым заявки в зависимости от заполнения Нi покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Нi; для Кi—правило выбора маршрутов или направлений ухода.

Кроме того, для заявок необходимо задать правила, по которым они остаются в канале Кi, или не допускаются до обслуживания каналом Кi, то есть правила блокировок канала. При этом различают блокировки по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q—схеме, регулирующих поток заявок в зависимости от состояний Q – схемы.

Весь набор возможных алгоритмов поведения заявок в Q—схемах можно представить в виде некоторого оператора А алгоритмов поведения заявок.

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

Q = <W, U, H, Z, R, A>, где

W – поток заявок, U – поток обслуживания, H – собственные параметры Q-схе­мы, Z – множество состояний, R – оператор сопряжения элементов схемы, A – алгоритмы поведения.

Обобщим приведенные выше классификационные признаки СМО в таблице 7.1.

Классификация СМО Табл.7.1

Классификационный признак	Тип Q-схемы
тип соединений между приборами	многоканальные
многофазные
емкость накопителей	с отказами
с ожиданием
смешанные
наличие обратной связи	разомкнутые
замкнутые
алгоритмы обслуживания	с приоритетами
без приоритетов

Математический анализ работы СМО значительно облегчается, если процесс этой работы – марковский.

7.2 Марковский процесс

7.2.1 Понятие марковского процесса

Пусть имеется некоторая система S, которая с течением времени t меняет сове состояние, причем заранее неизвестным, случайным образом. Говорят, что в системе S протекает случайный процесс.

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

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

Пусть в настоящий момент t₀ система находится в состоянии S₀ (рис. 7.3)

прошлое t< t₀ будущее t> t₀

t₀ (S₀) t

Рис.7.3 Случайный процесс в системе

Мы наблюдаем процесс со стороны и в момент t₀ знаем состояние системы и всю предысторию процесса, все что было при t< t₀. Нас, естественно, интересует будущее (t>t₀). Можем ли мы его предугадать (предсказать)? В точности – нет, так как процесс случайный. Но какие-то вероятностные характеристики процесса в будущем мы можем найти (например, вероятность того, что через некоторое время t система окажется в состоянии S₁ или останется в состоянии S₀ и т.п.).

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

Пример марковского процесса – система S – счетчик Гейгера, на который попадают космические частицы; состояние счетчика в момент t – показания счетчика (число частиц, пришедшее до данного момента). Вероятность того, что в момент t > t₀ счетчик покажет то или другое число зависит от S₀, но не зависит от того, в какие моменты приходили частицы до момента t₀.

Неожиданный парадокс: в сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит будущее, включить в “настоящее”. Например, пусть речь идет о таком то техническом устройстве; в какой-то момент времени оно еще исправно, и нас интересует вероятность того, что оно проработает еще время t. Если за настоящее состояние системы считать просто «система исправна», то процесс, безусловно, не марков­ский. Вероятность того, что она не откажет за время t зависит от того, сколько времени она уже проработала, и когда был последний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее, то процесс уже можно считать марковским.

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

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

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

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

Возможные состояния системы:

S0 – оба узла исправны;

S1 – первый узел ремонтируется, второй исправен;

S2 – второй узел ремонтируется, первый исправен;

S3 – оба узла ремонтируются.

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

Для нашего примера граф состояний приведен на рис. 7.4.

Рис. 7.4 Граф состояний системы

Стрелка из S0 в S1 означает отказ первого узла, начало его ремонта; из S1 в S0 – переход в момент окончания ремонта этого узла и т.д. А почему нет стрелки S0 в S3? Ведь может быть, в результате короткого замыкания оба узла откажут одновременно?

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

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

7.2.2 Потоки событий

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

Поток событий можно изобразить рядом точек на оси времени (t) (рис.7.5). (Только не забываем, что положение каждой точки случайно и на рисунке приведена только какая-то реализация потока).

t

Рис. 7.5 Поток событий

События, образующие поток, само по себе вероятностями не обладают; вероятностями обладают другие, производные от них, события, например: на участок времени Dt попадает ровно 2 события; или на участок времени t попадает хоть одно событие; или промежуток времени между двумя соседними событиями будет не меньше t и т.д.

Важной характеристикой потока является его интенсивность – среднее число событий, приходящееся на единицу времени. Интенсивность может быть как постоянной (l=const), так и переменной, зависящей от времени t. Например, поток автомобилей днем интенсивней, чем ночью, в часы пик – интенсивней, чем в другие часы.

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

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

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут считаться стационарными. Например, поток вызовов на АТС с 13 до 14 часов практически стационарен; тот же поток в течение суток уже не стационарен.

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t1 и t2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Например, поток пассажиров, входящих в метро – практически не имеет последействия. А поток покупателей, отходящих от прилавка с купленными товарами, уже имеет последействие хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания продавцом. Так же обстоит дело и с потоком поездов, прибывающих на станцию: между ними всегда есть интервал безопасности t_без. Но если минимальный интервал между событиями много меньше среднего интервала между ними t_min <<1/l, наличием последействия в ряде случаев можно пренебречь.

Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по несколько сразу. Например, поток клиентов к врачу обычно ординарен, а поток клиентов в ЗАГС – нет. Поток поездов, приходящих к станции – ординарен, а поток вагонов – нет. Если поток событий ординарен, то вероятностью попадания на малый участок времени Dt двух и более событий можно пренебречь.

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» обусловлено тем, что процессы, связанные с такими потоками, имеют наиболее простое математическое описание.

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

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

Для простейшего потока с интенсивностью интервал времени между сосед­ними событиями имеет так называемое показательное распределение с плот­ностью f(t)=le^-lt (t>0) (рис.7.6).

Величина l называется парамет­ром показательного закона. Для слу­чай­ной величины Т, имеющей показательное распределение, матема­ти­че­ское ожидание есть величина, обратная параметру (mT=1/l), а среднеквадратичное отклоне­ние равно математическому ожиданию sТ = mT = 1/l. В теории вероятности в качестве «меры случайности» неотрицательной случайной величины рассматривается так называемый коэффициент вариации (ковариация) v T=sТ /mT.

Для показательного распределения v T=1, то есть для простейшего потока коэффициент варьирования интервалов между событиями равен 1. Для регулярного потока, у которого интервал между событиями не случаен sТ=0, коэффициент вариации v T =0.

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

Поток событий называется рекуррентным (потоком Пальма), если он стационарен, ординарен, а интервалы времени между событиями Т1, Т2, Т3… представляют собой независимые случайные величины с одинаковым произвольным распределением. Пример: технический элемент работает непрерывно до отказа; отказавший элемент мгновенно заменяется новым. Если отдельные экземпляры элемента выходят из строя независимо друг от друга, то поток отказов (он же поток замен, поток восстановлений) будет рекуррентным.

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

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

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

Простейший поток – поток Эрланга 1-го порядка. При таком просеивании коэффициент вариации интервалов уменьшается; при увеличении порядка n поток Эрланга приближается к регулярному. Коэффициент вариации интервалов между событиями потока Эрланга N-го порядка равен =1/

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

Если все потоки событий, переводящие систему S из состояния в состояние – простейшие, то процесс, протекающий в системе, будет марковским. (Простейший поток не обладает последействием; в нем будущее не зависит от прошлого).

Если система S находится в каком-то состоянии Si, из которого есть непосредственный переход в другое состояние Sj, то это представляют следующим образом: на систему в состоянии Si действует простейший поток событий, переводящий ее по стрелке Si Sj. Как только появляется первое событие этого потока, происходит «перескок» системы из Si в Sj. Для наглядности удобно на графе состояний у каждой стрелки проставить интен­сив­ность того потока событий, который переводит систему по данной стрелке. Граф состояний, где указаны все интенсивности, называется размеченным.

7.3 Уравнения Колмогорова для вероятностей состояний.
Финальные вероятности состояний

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

S0 – оба узла исправны

S1 – первый узел ремонтируется, второй исправен

S2 – второй узел ремонтируется, первый исправен

S3 – оба узла неисправны

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

m1 m2

l1 l2

l2 l1

m2 m1

Рис. 7.7. Размеченный граф состояний системы

Пусть система находится в состоянии S0. Какой поток переведет ее в состояние S1? – Поток отказов первого узла. Его интенсивность l1 равна 1, деленной на среднее время безотказной работы. Какой поток событий переводит систему обратно, из S1 в S0? Очевидно, поток «окончаний ремонта» первого узла. Его интенсивность m1 равна 1, деленная на среднее время ремонта.

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

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

Пусть рассматривается система S, имеющая n возможных состояний S1, S2, S3…Sn. Назовем вероятностью i-го состояния вероятность pi(t), того, что в момент времени t система будет находиться в состоянии Si. Очевидно, что для любого момента времени сумма всех вероятностей состояний будет равна 1: S p_i(t) =1 (i=1,n)

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

Рассмотрим на конкретном примере, как составляются такие уравнения. Пусть система S имеет 4 состояния (рис. 7.8).

l₂₁ l₁₃

l₁₂

l₃₂

l₂₄ l₄₃

Рис. 7.8 Пример графа состояний системы

Рассмотрим одну из вероятностей состояний, например, p₁(t). Это – вероятность того, что в момент времени t система будет находиться в состоянии S1. Придадим малое приращение Dt и найдем p₁(t+Dt) – вероятность того, что в момент t+Dt система будет в состоянии S1. Как это может произойти? Это может быть достигнуто двумя способами: 1) в момент t система уже была в состоянии S1 и за время Dt еще не вышла из него; 2) в момент t система была в состоянии S2, а за время Dt перешла из него в состояние S1.

Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S1 равна p₁(t). Эту вероятность нужно умножить на вероятность того, что находившись в момент t в состоянии S1 система за время Dt не перейдет из него ни в S2, ни в S3. Суммарный поток событий, выводящий систему из состояния S1, тоже будет простейшим, с интенсивностью l₁₂+l₁₃. (Примечание. При наложении (суперпозиции) простейших потоков получается опять простейший поток, так как свойства стационарности, ординарности и отсутствия последействия сохраняются). Значит, вероятность того, что за время Dt система выйдет из состояния S1, равна (l₁₂+l₁₃)*Dt; вероятность того, что не выйдет – (1-(l₁₂+l₁₃)*Dt).

Отсюда вероятность первого варианта p₁(t)*(1-(l₁₂+l₁₃)*Dt).

Найдем вероятность второго варианта. Она равна вероятности того, что в момент t система будет находиться в состоянии S2, а за время Dt перейдет из него в состояние S1, то есть она равна p₂(t)*l₂₁*Dt.

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

p₁(t+Dt)= p₁(t)*(1-(l₁₂+l₁₃)*Dt)+ p₂(t)* l₂₁*Dt.

Раскроем скобки, перенесем в левую часть p₁(t) и разделим обе части на Dt:

= l_21*p₂(t) – (l₁₂+l₁₃)*p₁(t).

Устремим, как полагается, Dt к 0: Dt®0; слева получим производную функции p₁(t).Таким образом, запишем дифференциальное уравнение

= l_21*p₂(t) – (l₁₂+l₁₃)*p₁(t)

или, отбросив аргумент t у функций p₁, p₂:

= l_21*p₂ – (l₁₂+l₁₃)*p₁

Рассуждая аналогично для всех остальных состояний, напишем еще 3 дифференциальных уравнения. Получаем систему (7.1) из четырех дифференци­аль­ных уравнений для вероятностей состояний:

= l_21*p₂ – (l₁₂+l₁₃)*p₁

= l_12*p₁ + l_32*p₃ – (l₂₁+l₂₄)*p₂ (7.1)

= l_13*p₁ + l_43*p₄ – l₃₂*p₃

= l_24*p₂ – l₄₃*p₄

Система (7.1) – система 4-х дифференциальных уравнений с четырьмя неизвест­ными функциями p₁, p₂, p₃, p₄. Заметим, что любое из них можно отбро­сить, пользуясь тем, что p₁+p₂+p₃+p₄=1. Надо выразить любое p_i через другие функции и подставить это выражение в (7.1), а соответствующее уравнение производной отбросить.

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

Запишем уравнения Колмогорова для нашего технического примера:

= m_1*p₁ + m_2*p₂ – (l₁+l₂)*p₀

= l_1*p₀ + m_2*p₃ – (l₂+m₁)*p₁ (2)

= l_2*p₀ + m_1*p₃ – (l₁+m₂)*p₂

= l_2*p₁ + l_1*p₂ – (m₁₊ +m₂)*p₃

Чтобы решить уравнения Колмогорова и найти вероятности состояний, прежде всего надо задать начальные условия. Если мы точно знаем начальное состояние системы Si, то в начальный момент времени (при t=0) р_i(0)=1, а все остальные начальные вероятности равны 0. Так, например, уравнения (2) можно решать при начальных условиях р₀(0)=1, р₁(0)=р₂(0)=р₃(0)=0 (оба узла исправны).

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

Таким образом, уравнения Колмогорова дают возможность найти все вероят­ности состояний как функции времени.

Поставим вопрос: что будет происходить с вероятностями состояний при t®¥? Будут ли р₁ и т.д. стремиться к каким-то пределам? Если эти пределы суще­ствуют и не зависят от начального состояния системы, то они называются финальными вероятностями системы. В теории случайных процессов дока­зывается, что если число состояний системы конечно, и из каждого из них можно за конечное число шагов перейти в любое другое, то финальные вероятности существуют (это условие достаточное, но не необходимое).

Предположим, что это условие выполнено, и финальные вероятности существуют: p_i(t)=p_i (i=1,2,..n). Финальные вероятности будем обозначать теми же буквами р₁, р₂ и т.д., что и сами вероятности состояний, но разумея под ними уже не переменные величины (функции времени), а постоянные числа. Очевидно, что они тоже образуют в сумме 1: S p_i =1 (i=1,n)

Как понимать эти вероятности? При t®¥ в системе S устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния Si можно истолковать как среднее относительное время пребывания системы в этом состоянии.

Например, если система S имеет 3 состояния S1, S2, S3 и их финальные вероятности 0.2, 0.3, 0.5 соответственно, это значит, что в предельном стацио­нар­ном режиме система в среднем 2/10 времени проводит в состоянии S1, 3/10 – S2, и половину времени – в S3.

Как вычислить финальные вероятности? Если р₁, р₂ и т.д. постоянны, то их производные равны 0. Значит, чтобы найти финальные вероятности, нужно все левые части уравнений Колмогорова положить равными 0, и решить полученную систему уже не дифференциальных, а линейных алгебраических уравнений!

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

Для системы уравнений (7.2)

(l₁+l₂)*p₀= m_1*p₁ + m_2*p₂

(l₂+m₁)*p₁= l_1*p₀ + m_2*p₃ (7.3)

(l₁+m₂)*p₂= l_2*p₀ + m_1*p₃

(m₁₊ +m₂)*p₃= l_2*p₁ + l_1*p₂

Эту систему (7.3), казалось бы, вполне можно было решить! Но эти уравнения – однородны (не имеют свободного члена, и, значит, определяют неизвестное только с точностью до произведения множителей). Необходимо воспользоваться так называемым нормировочным условием р₀+р₁+р₂+р₃=1, и с его помощью решить систему. При этом одно (любое) из уравнений можно отбросить, оно вытекает как следствие из остальных.