Методика вывода уравнений Колмогорова
-интенсивность перехода
1. Найдем вероятность того, что в момент времени t система
находится в состоянии S1. Придадим t малое приращение D t и
определим, что система в момент времени t + D t находится в состоянии S1.
2. Найдем вероятность того, что система находится в состоянии S2:
3. Найдем вероятность того, что система находится в состоянии S3:
4. Найдем вероятность того, что система находится в состоянии S4:
В результате получаем систему уравнений Колмогорова:
Интегрирование данной системы даст искомые вероятности состояний, как функций времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы. Если при t =0 система находится в состоянии S1, то начальные условия будут p 1=1, p 2= p 3= p 4=0. Кроме этого, к системе добавляются условия нормировки:
Все уравнения строятся по определенному правилу:
1. В левой части каждого уравнения стоит производная вероятности состояния, а в правой части содержится столько членов, сколько стрелок связано с этим состоянием.
2. Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.
3. Каждый член равен произведению плотности вероятности перехода (интенсивность), соответствующий данной стрелке, и вероятности того состояния, из которого выходит стрелка.
Пример.
Рассмотрим многоканальную СМО с отказами. Состояние системы характеризуется по числу занятых каналов, т.е. по числу заявок.
|
|
S0 – все каналы свободны
S1 – занят один канал, остальные свободны
Sk – занято k каналов, остальные свободны
Sn – заняты все n каналов.
|
|
|
|
|
| ||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода m . Если занято 2 канала, а не один, то интенсивность перехода составит 2m.
Предельные вероятности состояний p 0 и pn характеризую установившийся режим работы системы массового обслуживания при t® ¥.
- среднее число заявок, приходящих в систему за среднее время обслуживания одной заявки.
Зная все вероятности состояний p 0 , … , pn , можно найти характеристики СМО:
|
|
· вероятность отказа – вероятность того, что все n каналов заняты
· относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию
· среднее число заявок, обслуженных в единицу времени
Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр l = 1 / t ОБРАБОТКИ, является усредненной характеристикой пользователя. Параметр m является функцией технических характеристик компьютера и решаемых задач.
Эта связь может быть установлена с помощью соотношений, называемых интерфейсной моделью. Если время ввода/вывода информации по каждой задачи мало по сравнению со временем решения задачи, то логично принять, что время решения равно 1 / m и равно отношению среднего числа операций, выполненных процессором при решении одной задачи к среднему быстродействию процессора.
На практике далеко не все случайные процессы являются Марковскими или близкими к ним. В СМО поток заявок не всегда Пуассоновский, ещё реже наблюдается показательное или близкое к нему распределение времени обслуживания.
Для произвольных потоков сообщений, переводящих систему из одного состояния в другое, аналитическое решение получено только для отдельных частных случаев. Когда построение аналитической модели по той или иной причине трудно осуществимо, применяется другой метод моделирования – метод статистических испытаний (Монте-Карло). Широкое распространение метода связано с возможностью его реализации на компьютере.
|
|
Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.
Суть метода:
1. Вводим в некотором единичном квадрате любую поверхность S.
2. Любым получаем 2 числа xi, yi, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].
3. Полагаем, что одно число определяет координату x, второе – координату y
4. Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.
|
|
5. Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.
6. Определяем площадь фигуры как количество попавших точек, к количеству сгенерированных.
Фон-Нейман доказал, что погрешность .
Преимущества метода статистических испытаний в его универсальности, обуславливающей возможность всестороннего статистического исследования объекта, однако, для реализации этой возможности нужны довольно полные статистические сведения о параметрах элементов.
К недостаткам относится большой объем требуемых вычислений, равный количеству обращений к модели. Поэтому вопрос выбора величины n имеет важнейшее значение. Уменьшая n – повышаем экономичность расчетов, но одновременно ухудшаем их точность.
Дата добавления: 2019-07-15; просмотров: 166; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!