Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Циклический процесс



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

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

Решая эти уравнения, получим:

После элементарных преобразований получим

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

3.Процесс “Гибели и размножения”

Марковская непрерывная цепь называется процессом «гибели и размножения», если её граф состояний имеет следующий вид:

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

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

и нормированное уравнение .

Решая эту систему, получим:

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

Из нормировочного условия получим:


 

4. СМО типа M/M/m

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

– интенсивность входного потока требований

– интенсивность обслуживания требований (среднее число обслуживаний в единицу времени)

– среднее время обслуживания каждого времени

– параметр обслуживания

– число требований

– число обслуживающих устройств

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

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

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

Тогда – вероятность того, что в системе в момент времени тоже имеется требований.

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

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

В силу ординарности входного потока и потока обслуживания получаем:

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

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

Рассмотрим возможные случаи появления события .

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

Тогда при получаем

а при получаем

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

Тогда при получаем

а при получаем

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

Тогда при получаем

а при получаем

 

Вероятность равна сумме вероятностей рассмотренных выше случаев.

Для случая

 

Для случая

Эти формулы справедливы для .

 

Для случая имеем:

В момент времени 0 требований, а за время нет новых прибытий

В момент времени 1 требование, за время нет новых прибытий, и завершилось 1 обслуживание

Таким образом, получено, что СМО типа M/M/m в установившемся режиме описывается системой уравнений:

(3)

Методом математической индукции можно доказать:

для : ,

для : , где

Доказательство:

Для и доказано, что и

Предположим:

для : ;

для : ;

Тогда для

Для

,

что и требовалось доказать.

 

Алгебраические уравнения (3) позволяют представить систему M/M/m в виде следующего графа:

Тогда – вероятность того, что в системе нет требований, можно вычислить как следующим образом:

где , но

так как

Вычислим среднее число требований в очереди:

, где

Обозначим через .

Но – производная .

Тогда и

 

Вычислим среднее число требований в обслуживающем устройстве:

(В G/G/m )

Таким образом, для системы M/M/m получено:


 

6. Многоканальная СМО с ограниченным ожиданием M/M/m/k

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

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

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

---

Sm+1 – заняты все m каналов, одна заявка в очереди

---

Sm+k – заняты все m каналов, k заявок в очереди

 
 

 


Выражения для предельных вероятностей состояний будут выглядеть:

Найдем некоторые характеристики обслуживания:

Pотк=pm+k q=1-Pотк A=l q

Каждый занятый канал обслуживает в среднем m заявок в единицу времени; вся СМО за это время обслуживает A заявок.

Среднее число занятых каналов:

V= A/m =r q

Среднее число заявок в очереди:


 

7. Замкнутая многоканальная СМО (M/M/m/k/l)

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

Предполагается, что имеется конечное число источников требований (l). Интенсивность каждого генератора требований – l.

Система содержит m обслуживающих приборов, каждый из которых характеризуется параметром m. Наконец в системе имеется конечное число мест для ожидания, такое, что m+k ³ l.

Это приводит к следующему множеству параметров процесса гибели и размножения:

 

 

Обозначая l/m=r, получим:

Среднее число занятых каналов:

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

В СМО в среднем работает (l-N) источников, каждый из тех порождает поток l:

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

Q=l-V (1/r+1); W=Q/A

Q=N–V


 

8. Распределение числа требований в системе M/G/1/

Предположим, что все требования обслуживаются в порядке поступления.

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

– число требований, остающихся в системе в момент ухода

требования ;

– число требований, остающихся в системе в момент ухода требования ;

Рассмотрим два случая:

Первый имеет место, когда уходящее требование не оставляет систему пустой, то есть

-время обслуживания

- число требований за

случай

Так как требования покидает систему

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

случай

Обобщая оба случая, приходим к выводу, что система M/G/1 характеризуется равенством:

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

и производящую функцию предельной случайной величины :

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

так как случайная величина - число требований поступивших за

не зависит от – число требований в системе в момент ухода требования ,

тогда

где

так как входящий поток – пуассоновский, то имеем:

Меняя порядок операций суммирования и интегрирования, получаем:

Так как

Определяем теперь преобразование Лапласа плотности времени обслуживания: .

Сравнивая , получим важный результат:

.

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

Итак:

;

.

Теперь отдельно рассмотрим

Решая относительно , получим первое уравнение Поллячика-Хинчина для преобразований:


 

9. Распределение времени пребывания в системе M/G/1

Учитывая , первое уравнение Поллячика-Хинчина можно записать в виде:

Введя замену переменной , имеем

Это второе уравнение Поллячика-Хинчина для преобразований даёт выражение преобразования Лапласа распределения времени пребывания требования в системе.

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

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

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

Используем теперь равенство для получения моментов случайной величены

Полагая теперь , то есть , имеем

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

Уравнение Поллячика-Хинчина для преобразований позволяет найти моменты распределения числа требований в системе:

Дисперсия случайной величины x или второй центральный момент

здесь:

– второй начальный момент;

– квадрат первого начального момента;

Если обозначить:

– нормированная дисперсия;

– стандарт;

– коэффициент вариации;

То учитывая:

Это и есть результат, к которому мы стремились. Это выражение представляет собой среднее число преобразований в системе M/G/1, которое обычно называют формулой Поллячика - Хинчина для среднего значения.

Среднее число преобразований в очереди

так как из анализа системы G/G/1 следует, что

В качестве примера применения формулы Поллячика–Хинчина рассмотрим систему M/M/1

В качестве второго примера рассмотрим регулярное обслуживание, то есть систему M/D/1

Таким образом, система типа М/D/1 содержит на требований меньше, чем система М/М/1.

Для системы M/Er/1

Это позволяет сделать вывод, что

Для системы G/G/m Кингман получил следующую оценку времени ожидания в очереди:

– дисперсия промежуточного интервала времени между прибытиями;

– дисперсия времени обслуживания;

– математическое ожидание времени обслуживания;

– математическое ожидание интервала между прибытиями;

– коэффициент обслуживания

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


 

10.уравнение Поллячика–Хинчина для преобразования Лапласа в системе M/G/1

Учитывая , первое уравнение Поллячика-Хинчина можно записать в виде:

Введя замену переменной , имеем

Это второе уравнение Поллячика-Хинчина для преобразований даёт выражение преобразования Лапласа распределения времени пребывания требования в системе.

Так как и учитывая


 

11. формула Поллячика - Хинчина для среднего значения в системе M/G/1

Учитывая , первое уравнение Поллячика-Хинчина можно записать в виде:

Введя замену переменной , имеем

Это второе уравнение Поллячика-Хинчина для преобразований даёт выражение преобразования Лапласа распределения времени пребывания требования в системе.

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

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

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

 

Используем теперь равенство для получения моментов случайной величены

Полагая теперь , то есть , имеем

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

Уравнение Поллячика-Хинчина для преобразований позволяет найти моменты распределения числа требований в системе:

 

Дисперсия случайной величины x или второй центральный момент

здесь:

– второй начальный момент;

– квадрат первого начального момента;

Если обозначить:

– нормированная дисперсия;

– стандарт;

– коэффициент вариации;

То учитывая:

Это и есть результат, к которому мы стремились. Это выражение представляет собой среднее число преобразований в системе M/G/1, которое обычно называют формулой Поллячика - Хинчина для среднего значения.


 

12. Теорема Бёрка (Burke)

Рассмотрим простейшую последовательную систему с двумя узлами, каждый из которых представляет СМО типа М/ М/1.

 

Фрагмент временной диаграммы для этой сети выглядит так, как это показано на рисунке слева.

 

Пусть - плотность распределения вероятностей промежутков времени между последовательными требова-ниями на выходе, а - преобразование Лапласа . Когда требование покидает узел 1, возможно одно из двух событий:

(a) в очереди имеется хотя бы одно требование (узел 1 не пуст)

(b) в очереди нет требований (узел 1 пуст)

В первом случае - промежуток времени, через которое следующее требование покинет систему 1, распределен так же, как и время обслуживания:

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

Так как эти два промежутка времени распределены независимо, то плотность распределения вероятностей их суммы равна свертке плотностей распределения суммируемых величин. Соответственно преобразование Лапласа плотности распределения: .

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

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

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

Этот результат, в 1956 году установленный Бёрк, справедлив и для СМО типа M/M/m.