Методика вывода уравнений Колмогорова

-интенсивность перехода

1. Найдем вероятность того, что в момент времени t система

находится в состоянии S1. Придадим t малое приращение Dt и

определим, что система в момент времени t+Dt находится в состоянии S1.

 

2. Найдем вероятность того, что система находится в состоянии S2:

 

3. Найдем вероятность того, что система находится в состоянии S3:

 

 

4. Найдем вероятность того, что система находится в состоянии S4:

 

В результате получаем систему уравнений Колмогорова:

 

Интегрирование данной системы даст искомые вероятности состояний, как функций времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы. Если при t=0 система находится в состоянии S1, то начальные условия будут p₁ =1, p₂ = p₃ = p₄ =0. Кроме этого, к системе добавляются условия нормировки:

 

 

Все уравнения строятся по определенному правилу:

1. В левой части каждого уравнения стоит производная вероятности состояния, а в правой части содержится столько членов, сколько стрелок связано с этим состоянием.

2. Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.

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

Пример.

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

 

S0 – все каналы свободны

S1 – занят один канал, остальные свободны

Sk – занято k каналов, остальные свободны

Sn – заняты все n каналов.

 

l

l

l

l

l

l

m

2m

3m

km

(k+1)m

nm

 

Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода m. Если занято 2 канала, а не один, то интенсивность перехода составит 2 m.

 

 

Предельные вероятности состояний p₀ и p_n характеризую установившийся режим работы системы массового обслуживания при t ® ¥.

 

 

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

 

 

Зная все вероятности состояний p₀, …, p_{n ,} можно найти характеристики СМО:

· вероятность отказа – вероятность того, что все n каналов заняты

 

 

· относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию

· среднее число заявок, обслуженных в единицу времени

 

Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр l = 1 / t_{ОБРАБОТКИ}, является усредненной характеристикой пользователя. Параметр m является функцией технических характеристик компьютера и решаемых задач.

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

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

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

Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.

Суть метода:

1. Вводим в некотором единичном квадрате любую поверхность S.

2. Любым получаем 2 числа x_i, y_i, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].

3. Полагаем, что одно число определяет координату x, второе – координату y

4. Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.

5. Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.

6. Определяем площадь фигуры как количество попавших точек, к количеству сгенерированных.

Фон-Нейман доказал, что погрешность .

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

 

К недостаткам относится большой объем требуемых вычислений, равный количеству обращений к модели. Поэтому вопрос выбора величины n имеет важнейшее значение. Уменьшая n – повышаем экономичность расчетов, но одновременно ухудшаем их точность.