Массового обслуживания с отказами методом Монте— Карло

Пусть в систему массового обслуживания с отказами (заявка покидает такую систему, если все каналы заняты), состоящую из N каналов, поступает простейший поток заявок (см. гл. VI, § 6), причем плотность распределения промежутка времени между двумя последовательными заявками задана:

f(τ) = λ е^-λτ (λ > 0, 0 < τ <∞).

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

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

Ведется подсчет числа обслуженных заявок и числа отказов. Если заявка обслужена, то в «счетчик обслуженных заявок» добавляют единицу; при отказе единицу добавляют в «счетчик отказов».

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

Введем обозначения:

t_обсл —длительность обслуживания заявки каналом;

t_i,—момент освобождения (i -го канала;

Т_k —момент поступления k-й заявки;

τ_k —длительность времени между поступлениями k- йи (k+1)-й заявок; T_{k+ 1} =T_k+τ_k —момент поступления (k+1)-й заявки, п— число испытаний.

Пусть первая заявка поступила в момент T ₁ = 0, когда все каналы свободны. Эта заявка поступит в первый канал и будет им обслужена за время t_обсл. В счетчик обслуженных заявок надо записать единицу.

Разыграем момент T ₂, поступления второй заявки, для чего выберем случайное число r ₁ и разыграем τ ₁ (учитывая, что τ распределено по показательному закону) по формуле (см. гл. XXI, § 7, пример 2)

τ ₁ = - (1 /λ) lnr1.

Следовательно, вторая заявка поступит в момент времени

T ₂ =T ₁+ τ_i =0+ τ_i = τ_i.

Если окажется, что t ₁≤ T ₂ (вторая заявка поступила после того, как первый канал освободился), то вторая заявка будет обслужена первым каналом и в счетчик обслуженных заявок надо добавить единицу.

Если же окажется, что t ₁> T ₂, то первый канал занят, и заявка поступит во второй канал и будет им обслужена, поскольку расчет начат в предположении, что все каналы свободны; в счетчик обслуженных заявок надо добавить единицу.

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

отказов надо добавить единицу.

Испытание заканчивается, если очередная заявка поступит в момент времени, превышающий момент окончания испытания, т. е. если Т_{k+ 1}> Т.

В итоге i -го испытания в счетчиках окажутся соответственно число обслуженных заявок m_{i обсл} и число отказов m_iотк.

Пусть произведено всего п испытаний, каждое длительностью Т, причем i- м испытании зарегистрировано m_{i обсл} обслуженных заявок и m_iотк отказов. В качестве оценок искомых математических ожиданий принимают выборочные средние:

Для вычисления наименьшего числа испытаний,которыес надежностью γ обеспечат наперед заданнуюверхнююграницу ошибки δ, можно использовать формулу (см. гл. XVI. § 15, замечание 2)

где t находят по равенству Ф(t)=γ/2, σ =1/λ (см. гл. XIII. § 3).

Пусть, например, известны среднее квадратнческое отклонение σ =4 и γ=0,95, δ =0,7. Тогда Ф(t)=0,95/2=0,475 и t =1,96.

Минимальное число испытаний

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

На практике расчет производят ЭВМ.

 

Б. Применение метода Мойте—Карло к вычислению определенных

Интегралов

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

Требуется найти оценку I ₁ ^* определенного интеграла

Рассмотрим случайную величину X, распределенную равномерно в интервале интегрирования (а, b)с плотностью f (х) = 1 / (b — а). Тогда математическое ожидание

Отсюда

Заменим математическое ожидание его оценкой—выборочной средней, получим оценку I ₁ ^* искомого интеграла:

где x_i— возможные значения случайной величины X. Так как величина Х распределена равномерно в интервале (а, b)с плотностью f (x) =1/ (b—а), то х_i, разыгрывают по формуле (см. гл. XXI, § 7, правило 2). Отсюда х_i=а+ (b—а) r_i.

Пример. Наитии: а) оценку I ₁ ^* определенного интеграла б) абсолютную погрешность | I-I ₁ ^* |; в) минимальное число испытаний, которые с надежностью γ= 0,95 обеспечат верхнюю границу ошибки δ =0,1.

Решение. Используем формулу

По условию a =1, b ==3, φ (х) =х+ 1. Примем для простоты число испытаний n =10. Тогда оценка

Результаты 10 испытаний приведены в табл. 36. Случайные числа взяты из приложения 9 с тремя знаками после запятой.

Таблица 36

Номер испытания i
r 1 2r 1 xi= 1 + 2 r 1	0,100 0,200 1.200	0,973 1,946 2,946	0,253 0,506 1,506	0,376 0,752 1.752	0,520 1,040 2,040	0,135 0,270 1,270	0,863 1.726 2,726	0,467 0,934 1,934	0,354 0,708 1.708	0.876 1,752 2,752
φ (xi)= xi +1	2,200	3,946	2,506	2,752	3,040	2,270	3,726	2,934	2,708	3,752

 

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

Искомая оценка интеграла

I ₁ ^* =2·(29,834/10) ==5,967.

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

| I- I ₁ ^* |=6—5,967=0,033.

в) Найдем дисперсию усредняемой функции φ (Х) =Х +1, учитывая, что случайная величина Х в интервале интегрирования (1,3) распределена равномерно и ее дисперсия D (X) = (3—1)²/12 (см. гл. XII, § 1, пример 2):

σ ² =D (X +1)= D (X)=1/3.

г) Найдем минимальное число испытаний, которые с надежностью 0,95 обеспечат верхнюю границу ошибки δ =0,1. Из равенства Ф (t)=0,95/2=0,475 по таблице приложения 2 находим t =1,96. Искомое минимальное число испытаний

В. Примеры случайных процессов

1. Процесс Пуассона. Рассмотрим простейший поток случайных событий, наступающих в интервале времени (0, t). Напомним свойства простейшего потока (см. гл. VI, § б):

1) стационарность (вероятность появления k событий за время t зависит только от k и t);

2) отсутствие последействия (вероятность появления k событий в течение промежутка времени (Т, T+t) не зависит от того, сколько событий и как появлялось до момента Т);

3) ординарность (вероятность появления более одного события за малый промежуток времени Δ t есть бесконечно малая более высокого порядка, чем Δ t, т. е. P_k> 1(Δ t) =o (Δt), где

Поставим своей задачей найти вероятность P_k (t) появления k событий за время длительности t. Для упрощения вывода используем следствие, которое можно получить из приведенных выше свойств:

4) вероятность того, что за малое время Δ t наступит ровно одно событие, пропорциональна Δ t с точностью до бесконечно малой высшего порядка относительно Δ t:

P ₁(Δ t) =λ Δ t + ₀ (Δ t)(*)

а) Найдем вероятность Р₀ (t) того, что за время длительности t не наступит ни одного события. Для этого примем во внимание, что на промежутке t+ Δ .t не наступит ни одного события, если на каждом из двух промежутков t и Δ t не появится ни одного события.

В силу свойств 1 и 2, по теореме умножения,

P₀ (t+ Δ t) =P₀ (t) P₀ (Δ t). (**)

События «за время Δ t не появилось ни одного события», «появилось одно событие», «появилось более одного события» образуют полную группу, поэтому сумма вероятностей этих событий равна единице:

P₀ (Δ t) +P ₁(Δ t) +P_k>i (Δ t)=l.

Учитывая, что P_k>i (Δ t)= ₀ (Δ t) (свойство 3), P ₁(Δ t) = λ Δ t + ₀ (Δ t) (свойство 4), имеем

P₀ (Δ t) =1- λ Δ t- ₀ (Δ t). (***)

Заметим, что, перейдя к пределу при Δ t→0, найдем

Р₀ (0)=1. (****)

Подставим (***) в (**):

P₀ (t+ Δ t) =P₀ (t) [1 – λ Δ t - ₀ (Δ t)].

Отсюда

P₀ (t+ Δ t) - P₀ (t) = - λ P₀ (t)Δ - ₀ (Δ t) P₀ (t)

Разделив обе части равенства на Δ t и перейдя к пределу при Δ t→ 0, получим дифференциальное уравнение

Р’₀ (t) = - λР₀ (t),

общее решение которого

Р₀ (t)=Се^{- λt}.

Используя (****), найдем, что С=1 и, следовательно,

Р₀ (t)=е^{- λt}.

Итак, вероятность того, что за время (не появится ни одного события, найдена.

б) Найдем вероятность P ₁(t) появления за время t ровно одного события. Для этого определим вероятность того, что за время t +Δ t событие появится один раз. Так будет в двух несовместных случаях:

1) событие наступит за время t и не наступит за время Δ t,

2) событие не наступит за время t и наступит за время Δ t. По формуле полной вероятности,

P ₁(t+ Δ t) = P ₁(t) P₀ (Δ t) + P₀ (t) P ₁(Δ t).

Заменим P ₁(Δ t)и P₀ (Δ t) соответственно по формулам (*) и (***), перенесем P ₁(t)в левую часть равенства, разделим обе его части на Δ t и перейдем к пределу при Δ t→ 0. В итоге получим линейное неоднородное уравнение первого порядка

P` ₁(t) + λР ₁(t) = λe^-λt

Учитывая начальные условия, найдем С=0 и, следовательно,

P ₁(t) = (λt) e^-λt (*****)

Итак, вероятность того, что за время t появится ровно одно событие, найдена.

в) Найдем вероятность Р ₂(t) появленияза время t ровно двух событий. Для этого определим вероятность того, что за время t+ Δ t событие появится два раза. Так будет в трех несовместных случаях: 1) событие наступит 2 раза за время t и не наступит за время Δ t, 2) событие наступит 1 раз за время t и I раз за время Δ t, 3) событие не наступит за время t и наступит 2 раза за время Δ t.

По формуле полной вероятности,

P ₂(t+ Δ t) = P ₂(t) P₀ (Δ t) + P ₁(t) P ₁(Δ t) + P₀ (t) P ₂(Δ t).

Заменим P₀ (t), P ₁(Δ t) и P ₁(t) соответственно по формулам (***), (*) и (*****); примем во внимание условие 4; перенесем Р ₂(t) в левую часть равенства, разделим обе его части на Δ t и перейдем к пределу при Δ t→ 0. В итоге получим дифференциальное уравнение

P` ₂(t) + λР ₂(t) = λ ² еe^-λt

Решив это уравнение, найдем вероятность того, что за время t появится ровно два события:

Аналогично можно получить вероятность того, что за время t наступит k событий:

Таким образом, если события, наступающие в случайные моменты времени, удовлетворяют указанным выше условиям, то число событий, наступающих за фиксированное время t распределено по закону Пуассона с параметром λt. Другими словами, если Х (t)—число событий простейшего потока, наступивших за время t, то при фиксированном t функция Х (t) есть случайная величина, распределенная по закону Пуассона с параметром λt. Функцию Х (t), называют случайным процессом Пуассона. Очевидно, каждая реализация Х (t) есть неубывающая ступенчатая функция.

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

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

F (t) = 1 - e^-λt.

События Т < t и T≥t противоположны, поэтому

Р (Т < t)+ Р (Т≥t) = l,

или

F (t) +P (Т≥t) =1.

Отсюда

F (t) = 1 - P (Т≥t).

P (Т≥t)есть вероятность того, что за время длительности t не появится ни одного события потока; эта вероятность, как показано выше, равна е^-λt.

Итак,

F (t) = 1 - е^-λt.

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

2. Винеровский процесс. Известно, что если в жидкость погрузить маленькую частицу, то она под влиянием ударов молекул жидкости будет двигаться по ломаной линии со случайными направлениями звеньев. Это явление называют броуновским движением по имени английского ботаника Р. Броуна, который в 1827 г, открыл явление, но не объяснил его. Лишь в 1905 г. А. Эйнштейн описал броуновское движение математически. В 1918 г. и в последующие годы американский ученый Н. Винер построил математическую модель, более точно описывающую броуновское движение. По этой причине процесс броуновского движения называют винеровским процессом.

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

Случайный процесс Х (t) называют нормальным (гауссовым), если совместное распределение Х (t ₁), Х (t ₂) ,…, Х (t_k) является нормальным для каждого k и всех t_i (i =1, 2,..., k). Нормальный процесс полностью определяется его характеристиками: математическим ожиданием и корреляционной функцией.

Случайный процесс Х (t) называют процессом с независимыми приращениями, если его приращения на неперекрывающихся интервалах взаимно независимы, т.е. случайные величины Х (t ₂) - Х (t ₁), X (t₃) - Х (t ₂),..., Х (t_k) - Х (t_{k- 1}) для t ₁ <t ₂ <…< t_k взаимно независимы. Процесс с независимыми приращениями определяется распределением приращений Х (t) —Х (s) для произвольных t и s. Если приращение Х (t) —Х (s) зависит только от разности t —s, то процесс называют процессом со стационарными приращениями.

Винеровским процессом (процессом броуновского движения) называют нормальный случайный процесс Х (t) с независимыми стационарными приращениями, для которого Х (0)=0, M [ X (t)] =0, M [ X (t)²] =σ ² 4 для всех t > 0.

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

3. Марковский случайный процесс. Используем терминологию, введенную в гл. XXII, § 1. Пусть в каждый момент времени некоторая система может находиться в одном из состояний E ₁, E ₂,… (число состояний конечно или счетно). Если система случайно переходитизодного состояния, например E_i, в другое, например E_j, то говорят, что в системе происходит случайный процесс. Если при этом вероятность перехода из состояния E_i в состояние E_j зависит только от состояния Е_i, и не зависит от того, когда и как система пришла в это состояние, то случайный процесс Х (t) называют марковским. Другими словами, если для каждого момента времени t₀ протекание случайного процесса Х (t) в будущем (при t > t_o) определяется его настоящим (значением Х (t₀) и не зависит от прошлого (от значений Х (t) при t < t₀, то Х (t) — марковский случайный процесс.

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

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

Допустим, что в момент времени t₀ система находилась в некотором определенном состоянии (обслуживается некоторое число заявок, причем обслуживание каждой из них уже длилось определенное время). Назовем условно «будущим обслуживанием» обслуживание для моментов времени t > t₀, которое определяется:

а) длительностью оставшегося времени обслуживания

заявок, поступивших до момента t₀;

б) числом заявок, которые поступят после момента t₀;

в) длительностью обслуживания этих заявок. Убедимся, что будущее обслуживание не зависит от того, как происходило обслуживание до момента t₀.

Действительно:

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

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

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

Итак, будущий процесс обслуживания (при t > t₀) зависит только от состояния системы в момент t₀ и не зависит от того, как протекала работа системы до момента t₀. Другими словами, процесс обслуживания простейшего потока заявок системой с ожиданием и показательным законом времени обслуживания является марковским процессом.

ПРИЛОЖЕНИЯ

Приложение 1

Таблица эначений функции

							б
0,0	0,3989
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0	0,2420
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1.8
1,9
2,0	0,0540
2,1
2,2
2,3
2,4
2,5
2,6		0132'
2.7
2,8
2,9
3,0	0,0044
3,1
3,2
3,3
3,4
3.5
3,6
3,7
3.8
3,9

 

 

Приложение 2

Таблица значений функции

x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)	x	Ф(x)
0,00	0,0000	0,31	0,1217	0,61	0,2291	0,91	0,3186	1.21	0.3869	1,51	0,4345	1,81	0,4649	2,22	0,4868	2,82	0,4976
0,01	0,0040	0,32	0,1255	0,62	0,2324	0,92	0,3212	1,22	0,3883	1,52	0,4357	1,82	0,4656	2,24	0,4875	2,84	0,4977
0,02	0,0080	0,33	0,1293	0,63	0,2357	0,93	0,3238	1,23	0,3907	1,53	0,4370	1,83	0,4664	2,26	0,4881	2,86	0,4979
0,03	0,0120	0,34	0,1331	0,64	0,2389	0,94	0,3264	1,24	0,3925	1,54	0,4.382	1,84	0,4671	2,28	0,4887	2,88	0,4980
0,04	0,0160	0.35	0,1368	0,65	0,2422	0,95	0,3289	1,25	0,3944	1,55	0,4394	1,85	0,4678	2,30	0,4893	2,90	0,4981
0,05	0,0199	0,36	0,1406	0,66	0,2454	0,96	0.3315	1,26	0,3962	1,56	0,4406	1,86	0.4686	2,32	0,4898	2.92	0,4982
0,06	0,0239	0,37	0,1443	0,67	0,2486	0,97	0,3340	1,27	'0,3980	1,57	0,4418	1,87	0,4693	2,34	0,4904	2,94	0,4984
0,07	0,0279	0,38	0,1480	0,68	0,2517	0,98	0,3365	1,28	0,3997	1,58	0,4429	1,88	0,4699	2,30	0,4909	2,96	0,4985
0,08	0,0319	0,39	0,1517	0,69	0,2549	0.99	0,3389	1,29	0,4015	1,59	0,4441	1,89	0,4706	2,38	0.4913	2,98	0,4985
0,09	0.0359	0,40	0,1554	0,70	0,2580	1,00	0,3413	1,30	0,4032	1,60	0,4452	1,90	0,4713	2,40	0,4918	3,00	0,49865
0,10	0.0398	0,41	0,1591	0,71	0,2611	1,01	0,3438	1,31	0,4049	1,61	0,4463	1,91	0,4719	2,42	0.4922	3,20	0,49931
0.11	0,0438	0,42	0,1628	0,72	0,2642	1,02	0,3461	1,32	0,4066	1,62	0,4474	1,92	0,4726	2.44	0,4927	3,40	0,49966
0.12	0,0478	0,43	0,1664	0,73	0,2673	1,03	0,3485	1.33	0,4082	1,'33	0,4484	1,93	0.4732	2,46	0,4931	3,60	0,499841
0,13	0,0517	0,44	0,1700	0,74	0,2703	1,04	0,3508	1,34	0,4099	1,64	0,4495	1,94	0,4738	2,48	0,4934	3,80	0,499928
0,14	0,0557	0,45	0,1736	0,75	0,2734	1,05	0,3531		0,4115	1,65	0,4505	1,95	0,4744	2.50	0,4938	4,00	0,499968
0,15	0,0596	0,46	0,1772	0,76	0,2764	1,06	0,3554		0,4131	1,60	0.4515	1,96	0,4750	2,52	0,4941	4,50	0,499997
0,16	0,0636	0,47	0,1808	0,77	0,2794	1,07	0,3577	1,37	0,4147	1.67	0,4525	1,97	0,4756	2,54	0,4945	5,00	0,499997
0,17	0,0675	0,48	0,1844	0,78	0,2823	1,08	0,3599	1,38	0,4162	1,68	0,4535	1,98	0,4761	2,56	0,4948
0,18	0,0714	0,49	0,1879	0.79	0,2852	1,09	0,3621	1,39	0,4177	1,69	0.4545	1,99	0,4767	2,58	0,4951
0,19	0.0753	0,50	0,1915	0,80	0,2881	1,10	0,3643	1,40	0,4192	1,70	0,4554	2,00	0,4772	2,60	0,4953
0,20	0,0793	0.51	0,1950	0,81	0,2910	1,11	0,3665	1,41	0,4207	1.71	0,4564 1	2,02	0,4783	2,62	0,4956
0,21	0.0832	0,52	0,1985	0,82	0,2939	1,12	0,3686	1,42	0,4222	1,72	0,4573!	2,04	0,4793	2,64	0,4959
0,22	0,0871	0,53	0,2019	0,83	0,2967	1,13	0,3708	1,43	0,4230	1,73	0.4582	2,06	0,4803	2,66	0,4961
0,23	0,0910	0,54	0,2054	0,84	0,2995	1,14	0.3729	,144	0,4251	1,74	0,4591	2,08	0,4812	2,68	0,4963
0,24	0,0948	0,55	0,2088	0,85	0,3023	1,15	0,3749	1,45	0,4265	1,75	0,4599	2,10	0,4821	2,70	0,4965
0,25	0,0987	0,56	0.2123	0,86	0,3051	1,16	0,3770	1,46	0,4279	1,76	0,4608	2,12	0,4830	2,72	0,4967
0,26	0,1026	0,57	0,2157	0,87	0,3078	1,17	0,3790	1,47	0,4292	1,77	0,4616	2,14	0.4838	2,74	0,4969
0,27	0,1064	0,58	0,2190	0,88	0,3106	1,18	0,3810	1,48	0,4305	1,78	0.4625	2,16	0,4846	2,76	0,4971
0,28	0,1103	0,59	0,2224	0,89	0,3133	1,19	0,3830	1.49	0,4319	1,79	0,4633	2,18	0,4854	2,78	0,4973
0,29	0,1141	0,60	0,2257	0,90	0,3159	1.20	0,3849	1,50	0,4332	1,80	0,4641	2,20	0,4861	2,80	0,4974
0,30	0,1179

 

 

Приложение 3

Таблица значений

n		n
0,95	0,99	0,999	0,95	0,99	0,999
	2,78 2,57 2,45 2,37 2,31 2.26 2.23 2,20 2,18 2,16 2,15 2,13 2,12 2,11 2,10	4,60 4.03 3,71 3,50 3,36 3,25 3,17 3,11 3,06 3,01 2,98 2.95 2,92 2,90 2,88	8,61 6,86 5,96 5,41 5,04 4,78 4,59 4,44 4,32 4,22 4,14 4,07 4,02 3,97 3,92	∞	2,093 2,064 2,045 2,032 2,023 2,016 2,009 2,001 1,996 1,001 1,987 1,984 1,980 1,960	2,861 2.797 2.756 2,720 2.708 2,692 2,679 2,662 2,649 2,640 2.633 2,627 2,617 2.576	2,861 2.797 2.756 2,720 2.708 2,692 2,679 2,662 2,649 2,640 2.633 2,627 2,617 2.576

 

Приложение 4

Таблица значений