Математика (стр. 17 )

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

В зависимости от поведения заявки в СМО различают СМО с отказами и СМО с очередью (или ожиданием). В СМО с отказами заявка, поступившая в момент занятости всех каналов, получает отказ и покидает СМО. В СМО с очередью (или ожиданием) заявка, поступившая в момент занятости всех каналов, становится в очередь и ожидает освобождения одного из каналов обслуживания.

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

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

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

5. Простейший поток и его свойства

Рассмотрим входящий поток заявок в СМО как последовательность точек - моментов поступления заявок на оси времени . Здесь - начальный момент.

Поток заявок назовем простейшим, если он удовлетворяет трем условиям

1.  Отсутствие последействия. Это условие означает, что заявки поступают в СМО независимо друг от друга, т. е. поступление заявки после момента времени не зависит от того, когда и в каком количестве появились заявки до момента .

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

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

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

Можно показать, что для простейшего потока вероятность поступления в СМО ровно i заявок за время t вычисляется по формуле

(1)

т. е. вероятности распределены по закону Пуассона с параметром . Этим вызвано другое название простейшего потока – пуассоновский поток.

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

где - вероятность того, что случайная величина Т примет значение, меньше, чем t; -вероятность противоположного события (т. е. за время t в СМО не поступила ни одна заявка). В силу формулы (1) имеем:

,

откуда

, (t>0) .

Найдем плотность распределения случайной величины Т:

, (t>0).

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

, ,.

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

6. Марковские системы массового обслуживания

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

. (2)

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

Пример 1. Автоматизированная система управления АСУ продажей железнодорожных билетов состоит из двух параллельно работающих ЭВМ. При выходе из строя одной ЭВМ АСУ продолжает нормально функционировать за счет работы другой ЭВМ. Поток отказов каждой ЭВМ простейший. Среднее время безотказной работы одной ЭВМ равно 10 суткам. При выходе из строя отказавшую ЭВМ начинают ремонтировать. Время ремонта ЭВМ распределено по показательному закону и в среднем составляет 2 суток. В начальный момент обе ЭВМ исправны. Найти среднюю производительность АСУ, если при исправности хотя бы одной ЭВМ её производительность равна 100%, а при отказе обеих ЭВМ продажа билетов производится вручную, обеспечивая 30% производительности АСУ.

Решение.

Обозначим состояния АСУ по числу вышедших из строя ЭВМ: - обе ЭВМ исправны; - одна исправна, другая ремонтируется; - обе ЭВМ ремонтируются. Так как потоки отказов и восстановления ЭВМ являются простейшими, то их интенсивности вычисляются по формулам:

;

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

Рис. 3

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

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

.

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

.

Расчет показывает, что параллельная работа всего двух ЭВМ обеспечивает достаточно высокую (98.04% от номинальной ) производительность АСУ. Следовательно, нет необходимости повышать производительность системы за счёт, например, присоединения третьей ЭВМ.

7. Показатели эффективности систем массового обслуживания

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

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

– вероятность обслуживания поступившей заявки или относительная пропускная способность СМО. Очевидно, .

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

– среднее число заявок в СМО (имеются в виду все заявки, как обслуживаемые, так и не ожидающие очереди, если она есть).

– среднее число заявок в очереди, если она есть.

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

–среднее время пребывания заявки в очереди.

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

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

, , , (3)

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

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

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

Многоканальная система массового обслуживания

с отказами (задача Эрланга)

Пусть СМО содержит каналов, входящий поток заявок имеет интенсивность , поток обслуживания заявки одним каналом имеет интенсивность . Будем нумеровать состояния СМО по числу занятых каналов: - все каналы свободны; - один канал занят; … … …; - i каналов занято, каналов свободны; … … …; - все каналы заняты.

Размеченный граф состояний имеет вид, представленный на рис.4.

Рис. 4

Сравнивая рисунки 4 и 3, приходим к выводу, что граф на рис.6 является графом процесса гибели и размножения, для которого:

, . (4)

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

(5)

; ; …; ; …; .

Формулы (5) называются формулами Эрланга. С их помощью вычисляются показатели эффективности СМО:

; ; ; , (6)

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

Пример 2 . Диспетчерская служба имеет 5 линий связи. Поток вызовов простейший с интенсивностью вызовов в минуту. Среднее время переговоров с диспетчером составляет 3 мин. Время переговоров распределено по показательному закону. Найти абсолютную и относительную пропускные способности диспетчерской службы; вероятность отказа; среднее число занятых каналов. Определить сколько линий связи должна иметь диспетчерская служба, чтобы вероятность отказа не превышала 0,01.

Решение. Находим интенсивность потока обслуживания разговора в минуту. Коэффициент загрузки СМО составляет . Из формул (19) при имеем:

;

Находим по формулам (6):

а) абсолютная пропускная способность:

(следовательно, СМО обслуживает в среднем 0б75 заявки в минуту);

б) относительная пропускная способность:

(следовательно, вероятность обслуживания вновь поступившей заявки равна );

в) вероятность отказа: ;

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

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

Поскольку вероятность отказа данной диспетчерской службы превышает , то число линий связи следует увеличить. Допустим, что линий связи стало 6. Тогда из формул (5) при получим:

Следовательно, при вероятность отказов превышает 0,01. Значит, число каналов надо увеличить. При получим:

.

Следовательно, при вероятность отказов не превышает 0,01. Таким образом, для обеспечения требуемой вероятности отказов следует увеличить количество линий связи диспетчерской службы до 7.

МАТЕМАТИЧЕСКАЯ СТАТИСТИКА

1. Генеральная совокупность и выборка

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

Существует два способа выборочного отбора:

1)  повторный – каждый выборочный элемент возвращается в общую совокупность и может быть отобран повторно;

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

§2. Вариационные ряды их способы их представления

Если из генеральной совокупности извлечена выборка объема, в которой число х1 повторяется п1 раз, число х2 – п2 раза,…, число хk – nk раз (то есть выборка содержит k различных значений случайной величины), то числа xi называются вариантами, соответствующие им значения ni – частотами, а последовательность вариант, записанных в порядке возрастания, и относящихся к ним частот – вариационным рядом. При этом вместо абсолютных частот ni можно задавать распределение относительных частот

. (1)

Вариационный ряд называется дискретным, если он представляет собой выборку значений дискретной случайной величины:

Варианты

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

Варианты

Пример 1. Дана выборка, состоящая из чисел: 3.2, 4.1, 8.1, 8.1, 6.7, 4.4, 4.4, 3.2, 5.0, 6.7, 6.7, 7.5, 3.2, 4.4, 6.7, 6.7, 5.0, 5.0, 4.4, 8.1. Составить вариационный ряд распределения абсолютных и относительных частот.

Решение. Объем выборки . Перепишем варианты в порядке возрастания:

3.2, 3.2, 3.2, 4.4, 4.4, 4.4, 4.4, 4.4, 5.0, 5.0, 5.0, 6.7, 6.7, 6.7, 6.7, 6.7, 7.5, 8.1, 8.1, 8.1.

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

Сопоставим вариантам их частоты и вычислим относительные частоты:

xi	3.2	4.4	5.0	6.7	7.5	8.1
ni	3	5	3	5	1	3
wi	0,15	0,25	0,15	0,25	0,05	0,15

(относительная частота ).

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

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

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

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

Пример 2. Дана выборка, вариационный ряд которой имеет вид:

10,8; 11,1; 11,7; 12,2; 13,1; 13,4; 13,9; 14,3; 14,3; 14,4; 14,8; 16,5; 17,7; 18,2; 19,9; 20,0; 20,3; 20,8; 23,1; 24,2; 25,1; 25,1; 25,7; 28,4; 28,5; 29,3; 29,8; 29,9; 30,2; 30,4.

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

Решение. Объем выборки . Выберем в качестве границ интервала. Тогда и разбивается на части (10,5; 14,5), (14,5; 18,5), (18,5; 22,5), (22,5; 26,5) и (26,5; 30,5). Статистический ряд распределения имеет вид:

Номер интервала	Границы интервала	Абсолютные частоты	Относительные частоты
1	10,5; 14,5	10
2	14,5; 18,5	4
3	18,5; 22,5	4
4	22,5; 26,5	5
5	26,5; 30,5	7

Построим гистограмму: