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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2009 Управление, вычислительная техника и информатика № 1(6)
УДК 519. 2
Н. В. Степанова, А.Ф. Терпугов
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТОРГОВОЙ ТОЧКИ
В ВИДЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ ТИПА М/М/ да С ОТКАЗАМИ ОТ ПОСТАНОВКИ В ОЧЕРЕДЬ.
ЧАСТЬ 1. ВЫХОДЯЩИЙ ПОТОК ОБСЛУЖЕННЫХ ТРЕБОВАНИЙ
Изучаются свойства выходящего потока заявок системы массового обслуживания типа М/М/1А" с отказами от постановки в очередь.
Ключевые слова: система массового обслуживания, выходящий поток.
Системы массового обслуживания (СМО) в качестве математических моделей для самых разнообразных систем с потоками заявок применяются в наше время очень широко. Могут быть они применены и для описания функционирования торговой точки. Ниже рассматривается одна из таких моделей, учитывающая «нетерпеливость» клиентов.
1. Описание модели
Времена всеобщего дефицита, когда в магазинах были пустые полки и за товарами выстраивались многочасовые очереди, канули в прошлое. Сейчас однотипных магазинов очень много, в них продаются однотипные товары и клиент, заходя в магазин, смотрит не только на ассортимент и цены, но и на наличие очереди. И если очередь, с его точки зрения, достаточно большая, то он откажется от покупки в этом магазине и пойдёт в другой магазин, где очередь, возможно, будет меньше.
В качестве математической модели этой ситуации рассмотрим систему массового обслуживания, на вход которой поступает простейший поток заявок с параметром X. В данной работе рассмотрен случай, когда время обслуживания имеет экспоненциальное распределение с параметром ц.
Дисциплина обслуживания заключается в том, что если поступающая заявка застаёт в системе i заявок, то с вероятностью г, 0 & lt- ri & lt- 1 она в очередь не становится и покидает систему, а с вероятностью 1 — ri становится в очередь для ожидания обслуживания.
Обозначения:
т (ґ) — число заявок, отказавшихся от обслуживания (поток уходящих требований) в течение времени t-
п (ґ) — число заявок, обслуженных за время t (выходящий поток заявок) —
i (t) — число заявок в системе в момент времени t.
Для рассматриваемой СМО при заданных значениях параметров X, ц, ri процесс i (t) является цепью Маркова с непрерывным временем (процессом гибели и размножения), управляющим потоками rn (t) и п (0. Поэтому оба этих потока относятся к классу МАР-потоков (Marcovian Arrival Process).
Асимптотические (в условиях растущего времени t) и допредельные численные методы исследования МАР-потоков изложены в диссертации С. В. Лопуховой [1], на основе которых и проведены дальнейшие исследования.
2. Исследование выходящего потока (потока обслуженных заявок)
Так как двумерный случайный процесс {i (t), n (t)} является цепью Маркова, то для его распределения вероятностей
P (i, n, t) = P{i (T) = i, n (t) = n}
используя так называемый At-метод [2], можно записать следующие соотношения
(i & gt- 0, n & gt- 0)
P (i, n, t + At) = P (i, n, t) [1 — (X + |)At ] + P (i, n, t) Xri At +
+ P (i -1, n, t) X (1 — r-1)At + P (i +1, n -1, t)|xAt + o (At). (1а)
При i = 0 эта система приобретает вид
P (0, n, t + At) = P (0, n, t)[1 -XAt] + P (0, n, t) Xr0 At +
+ P (1, n -1, t)|At + o (At), (1б)
так как при i = 0 уход обслуженной заявки невозможен (ведь её нет), а P (-1, n, t) = 0. Обычным способом, переходя к пределу At ^ 0 при i & gt- 0, отсюда получаем
nt) = - [(1 — г) + ц] P (i, n, t) + X (1 — r_i)P (i -1, n, t) + |P (i + 1, n -1, t), (2а) dt
а при i = 0
dP (0, n, t) = -X (1 — r0) P (0, n, t) + |P (1, n -1, t). (2б)
dt
Для решения этой системы введём функцию
H (i, и, t) =? ejunP (i, n, t),
n=0
где j = V-Г. Тогда для этих функций можно получить следующую систему уравнений:
дИ {i, u t) = -[(1 -r) + |]Hi, u, t) +X (1 — r-jH (i -1, u, t) + ie]uH (i+, u, t), (3)
dt
dH (0, U, t) = -X (1 — r0) H (0, u, t) + iejuH (1, u, t). dt
Введём вектор-строку
H (u, t) = {H (0, u, t), H (1, u, t),…} и перепишем систему (3) в виде
dHdut) = H (u, t){Q + |(eju -1)5}, (4)
dt
где Q — трехдиагональная инфинитезимальная матрица процесса гибели и размножения i (t), имеющая следующий вид:
¦-X (1 — r0) X (1 — r0) 0 0 •••& quot-
-[X (1 — r) + |] X (1 — rx) 0 —
Q = 0 | -[X (1 — r2) + |] X (1 — r2) ^
0 0 | -[X (1 — Гз) + |] -
а в матрице В поддиагональные элементы равны 1, а остальные равны нулю.
Введём еще вектор-столбец Е, состоящий из единиц: E = (1,1,1,…)T. Тогда легко видеть, что матрица Q удовлетворяет условию QE = 0.
Рассмотрим решение дифференциально-матричного уравнения (4) при следующих начальных условиях:
1. п (0) = 0 с вероятностью 1.
2. Будем считать, что в начальный момент времени t = 0 в цепи гибели и размножения i (t) установилось стационарное распределение вероятностей P (i (t) = i) = = R (i), которое мы найдём ниже. Тогда, если взять t = 0, то P (i, n, 0) = R (i)5n0, и поэтому H (i, u, 0) = R (i). Вводя вектор-строку
R = (R (0), R (1), R (2),…), имеем H (u, 0) = R.
Далее, если взять и = 0, то
H (i, 0, t) = Y, P (i, n, t) = P (i, t) = R (i)
n=0
в силу стационарности распределения вероятностей R (i). Тогда будет верно соотношение H (0, t) = R.
Таким образом, начальные условия систем (4) имеют вид
H (u, 0) = H (0, t) = R.
3. Нахождение финального распределения вероятностей процесса i (t)
В стационарном состоянии граф переходов процесса i (t) имеет вид (рис. 1), что даёт следующую систему разностных уравнений для компонент финального распределения вероятностей R (i):
Х (1 — r0) R (0) = цЩ),
X (1 — r-)R (i -1) — [X (1 — r) + ц]R (i) + mR (i +1) = 0. (6)
Заметим, что эту систему можно записать в следующем матричном виде: RQ = 0.
Ц1 — Го) Ц1 — Гі) Ц1 — Г2) Ц1 — Гз)
Рис. 1. Граф переходов процесса
Перепишем (6) в виде
Х (1 — r-)R (i -1) — цЛ (i) = X (1 — r) R (i) — mR (i +1),
откуда видно, что
X (1 — r-1) R (i -1) — MR (i) = const.
Из первого уравнения системы (6) следует, что const = 0, так что
Х (1 — r-j) R (i -1) = mR (i),
откуда
г-1
Я (г) = р (1 — г-1)Я (/ -1) =… = Я (0)рг П (1 -к), (7)
к=0
где р = Х/ц.
ОТ
Константа Я (0) находится из условия нормировки? Я (г) = 1, которое можно
г=0
записать в виде ЯЕ = 0. Её явный вид
Я (0) = 1 |1 + ?рг ]-1(1 — Гк)1. (8)
/ I г=1 к=0 J
В частности, из (8) следует, что условием существования стационарного распределения вероятностей в рассматриваемой СМО является сходимость ряда
ад г -1
?рг П (1 — Гк) & lt-+ад.
г =1 к=0
Таким образом, для вектор-строки Н (и, *) имеем следующую задачу Коши:
= Н (и,*){ + ц{е1и -!)Я},
[ Н (и, 0) = Я,
решение Н (и, *) которой определяет характеристическую функцию величины п (*). Действительно, беря
(9)
Н (г, и, *) =? е-ип (*) Р (г, л, *)
п=0
и суммируя по г, получим
ад ад
м{ип (*)} =? е]т? Р (г., л,*) =? Н (г, и, *) = н (и, *)Е,
п=0 г=0 г=0
где Е — единичный вектор-столбец.
4. Нахождение среднего числа обслуженных заявок
Для М{п (*)}, пользуясь свойствами характеристической функции, имеем
1 дН (и, *)
(10)
1 д М {е^)}
М{п (*)} = - 1 '
] ди
] ди
Е.
(Ц)
Обозначим
так что
, ч 1 дН (и, *) п^) = -
] ди М{п (*)} = п1(*)Е.
Тогда из (9) получим
ёщ (*)
= № + ЯцВ ,
(12)
ад
и =0
так как Н (0, г) = Я. Умножая на Е, с учётом того, что QE = 0, имеем
й М{п (г)}
Ж
— = ЯцВЕ = цЯВЕ,
с начальным условием М{п (0)} = 0. Поэтому
М{п (г)} = цЯВЕ • г.
В дальнейшем комбинацию цЯВЕ будем обозначать как к. Так как
ВЕ =
0 0 0 0 ••• 1 0
0 0 0 1 1
0 0 0 1 = 1
0 0 0 1 1

то
ЯВЕ = [Я (0) Я (1) Я (2) •••]•
= Ё Я (і) =
Хр! П (1 — гк)
= 1 — Я (0) = І=1 к=°--------
так что окончательно
1+Ер! П (1 — г)
і=1 к=0
М{п (ґ)} = к1/ = ц (1 -Я (0)К.
(13)
(14)
(15)
(16)
5. Решение задачи методом преобразования Фурье
Обозначим через У (и, а) преобразование Фурье по г от вектор-функции Н (и, г):
У (и, а) = | е/агУ (и, г) йг.
0
Тогда, интегрируя по частям, имеем
| е]Ш дН (и, г) йг = I (и, г) =
(17)
= е1 агН (и, г)| -/а| е1 агН (и, г) йг = -Я -/аУ (и, а)
0
и из (9) получим уравнение
-Я — /а У (и, а) = У (и, а) { + ц (е/и -1) В}.
(18)
і =1
Его решение У (и, а) имеет вид
У (и, а) = Я {цВ — Q -/а/ - е/ицВ} =
= Я {(цВ — ^ - /а/) [/ - е/а (цВ — Q — /а/)-1 цВ]}-1 =
= Я [/ - е1 (цВ — Q — /а/)-1 цВ] (цВ — Q — /а/)-1 =
I
= Я X е]ип [(цВ — Q — /а/) — цВ]" (цВ — Q — /а/) —.
п=0
В силу этого равенства определения функции Н (/, и, г) и равенства (17), для преобразования Фурье функции Р (п, г) запишем
1 I I
Р (п, г) = - | е~/агЯ X е/ип [(цВ — Q — /а/)-1 цВ ]п (цВ — Q — /а/)-1 Ей, а.
2п -I п=0
Численная реализация этих формул в общем случае достаточно проблематична, так как вычисления произведения и обращения бесконечных матриц и нахождения и нахождения значений несобственных интегралов. Поэтому рассмотрим асимптотический метод решения задачи (9) в условиях растущего времени г.
6. Решение задачи (9) асимптотическим методом в условиях растущего времени
Пусть Т — некоторая достаточно большая величина, для которой будем полагать, что Т ^ I.
Условие г = тТ будем называть асимптотическим условием растущего времени. Дальнейшее исследование производится асимптотическим методом, разработанным А. А. Назаровым [3].
Асимптотикой первого порядка для характеристической функции
Н (и, г) Е = М{е/Ип (г)}
числа п (г) событий, наступивших в выходящем потоке за время г, будем называть функцию Н1(и, г) вида
к1 (и, г) = ехр{/ик1г}, где величина к1 определена выше методом моментов и имеет вид
к1 =ц ЯВЕ = ц (1 -Я (0)).
6.1. Асимптотика второго порядка Для построения асимптотики второго порядка к2(и, г) в уравнении (4)
дН^ = н (и, гш + ц (е/" -1)В}
дг
выполним замену
Н (и, г) = Н2 (и, г) ехр (]ик}г). (19)
Тогда для Н2и, г) получим уравнение
НР = Н2 (и, г) { + ц{ -1)В — /иК/}, (20)
где / - диагональная единичная матрица.
В силу замены (19) начальное условие для решения Н2(и, /) уравнения (20) то же самое, что и для функции Н (и, /) в задаче (4):
Н2(и, 0 = Я. (21)
В уравнении (20), обозначив є2 = 1/Т, выполнив замены
/є2 = т, и = є^, Н2(и, /) = -Р2(^, т, є), (22)
получим уравнение
є2 д2 (дТ т, є) = Е2 (w, т, є) {б + ц (е-1)В — I}. (23)
Это уравнение решим в два этапа.
Этап 1. Решение -Р2(^, т, є) уравнения (23) запишем в виде
(w, т, є) = Ф2 (w, т){Я + ]єм& gt-/} + 0(є2) (24)
и найдём вектор/ а скалярную функцию Ф2(^, т) определим ниже на втором этапе. Перепишем уравнение (23) в виде
0(є2) = (м& gt-, т, є) { + цjєwB — jєwкlI} = (Я + ]єм& gt-/) {б + jєw[цB — К^І ]} =
= Яб + у^Я[цВ — V] + ]єм& gt-/б = ]єм& gt-{/б + Я (цВ — V)} ,
где учтено, что Яб = 0.
Отсюда получаем, что вектор / является решением неоднородной системы
/б + Я (цВ -V) = 0. (25)
В силу того, что б — вырожденная матрица, на / для его однозначного определения, можно наложить дополнительное условие. Наложим его в виде
/ Е = 0. (26)
Этап 2. Умножая дифференциально-матричное уравнение (23) на Е, получим
є2 ^тє) Е = (м& gt-, т,є){бЕ + ц{в]єк -1)ВТ -]єм& gt-к1Е} =
=*(,. >- е+ц & amp-? ве }+0& lt-л.
Подставляя сюда разложение (24), получим
є2 дФ^т) ЯЕ = Ф2 (м& gt-, т)(Я + ]єм& gt-/) & lt-|ує^(цБ — к^І)Е + ц2- ВЕ| =
= Ф2 (w, т) {уєц& gt-Я (цВ — к1І)Е + ц (^ ЯВЕ + (]єм& gt-)2 /(цВ — к1І)Е} + 0(є3) =
= ф 2(w, т)^^{ЦЯВЕ + 2 ^ цЖ} + 0(є3).
Из этого равенства запишем уравнение, определяющее скалярную функцию Ф2^, т):
2
дФ 2(w, т) (jw)
-2"т = Ф2 (w, т)^- к2,
дт 2
где к2 = цЯВЕ + 2ц/ВЕ = к + 2ц/ВЕ. (27)
Очевидно, что Ф2(У, т) имеет вид
I (jw)2
Ф2 (w, т) = exp j 2 К2т
Подставляя это выражение в (24), получим
F2 (w, т, e) E = Ф2 (w, t){RE + JewfE} + O (e3) =
Ф2^, т) + O (e3) = exp jjp- к2т^| + O (e3).
Выполнив здесь обратные к (22) замены, получим
H2 (u, т) E = exp jK2tj + OTj. (28)
Подставляя это выражение в (19), запишем асимптотику h2(u, t) второго порядка для характеристической функции величины n (t)
h2(u, t) = expjJuKit + (J2-K2tj. (29)
Здесь к2 определяется равенством (27), а вектор f определяется системой (25) -(26).
Отсюда следует, что при больших t D{t}=K2t. Очевидно, что если fBE = - f (0) Ф 0, то поток n (t) не пуассоновский, так как нарушено его необходимое условие M{n (t)} Ф D{n (t)}.
6.2. Нахождение вектора f В явном виде система (25) имеет вид
-X (1 — Го) f (0) + yf (1) + Ц (1) — KiR (0) = 0 ,
X (1 — Г0) f (0) — [X (1 — ri) + y]f (1) + yf (2) + yR (2) — KiR (1) = 0, (30)
X (1 — г-1) f (i -1) — [X (1 — г) + y] f (i) + yf (i + 1) + yR (i + 1) — K1(i) = 0,
Суммируя первые i уравнений этой системы, получим
-X (1 — Г0) f (0) + yf (1) + yR (1) — K1R (0) = 0,
-X (1 — Г1) f (1) + yf (2) + y[ R (1) + R (2)] - K1 [ R (0) + R (1)] = 0, (31)
-X (1 — г-1) f (i -1) + yf (i) + y? R (v) -K1? R (v) = 0,
v=1 v=0
откуда получаем рекуррентное соотношение для /г):
/(0 = Р (1 — Г-)/(I -1) + ^ X1 Я (у) -^Я (у). (32)
ц v=0 v=1
Введём обозначение
К г -1 г ?-1 г
6(г) = ^ X ЯМ — XЯМ = (1 -Я (0))X Я (V) — Xям =
ц v=0 v=1 v=0 v=1
г-1 I
= Я (0) — Я (г) — Я (0) X Я (v) = Я (0^ Я (v) — Я (г). (33)
v=0 v=i
Таким образом, (32) принимает вид
I
/(г) = р (1 — Г-1)/(г -1) + 6(0, Р = Уц, 6(г) = Я (0^ Я (v) — Я (г).
v=i
Отсюда имеем
/ (1) = р (1 — г0) / (0) + 6(1),
/ (2) = р (1 — г1) / (1) +6(2) = р (1 — г1)[ р (1 — Г0) / (0) + 6(1)] +6(2) =
= р (1 — /)р (1 — /)/(0) + р (1 — /)6(1) +6(2),
/ (3) = р (1 — /2) / (2) + / (3) =
= р (1 — /2)[ р (1 — /1) р (1 — /0) / (0) + р (1 — /1) 6(1) + 6(2)] + 6(3) =
= р (1 — /2)р (1 — /)р (1 — /)/(0) + р (1 — /)р (1 — /)6(1) + р (1 — /2)6(2) + 6(3).
В общем виде получаем
/(г) = /(0)рг П (1 — /) + X 6МП ^ - /к) + 6(г). (34)
Для нахождения/(0) используем условие/ Е = 0, то есть X /(0 = 0. Тогда
г=0
I I Г г -1 г -1 г-1 1
0 = X /(г) = /(0) + X1 /(0)рг П, А — /к) + X 6МП (: — /к) + 6(г) [ =
і=1 I к=0 v=1 к^
ад і-1 І ад Г і-1 і-1
= / (0) 11 + Xpг П ^ - /к)^ + X^X 6(v)П ^ - /к) + 6(0[-. (35)
I г =1 к=0 г=1 и=1 к=v
Отсюда имеем окончательно
I Г г-1 г -1 1
XIX 6мП (1- /ъ)+6(г)
-/(0) = г= lv=1 I к=^--------------- = /ВЕ, (36)
1+Xpг п, а — /к)
г =1 к =0
что и определяет к2, а вместе с ним и Б{п (г)}.
6.3. Частный случай Г0, если г & lt- N,
Пусть /г =
11, если г = N.
В этом случае Я (г) = Я (0)рг, Я (0) = = 1 рр+1.
Хр
к=0
к
1 -р
Далее имеем
ДО = /(0)рг + ЕЬ^) + Ь ('-) = /(0)рг + ЕьМ, г & lt- ж,
v=l
ж ж '-
0 = X / (О = / (0)+/ (0)Е рг + Е X Ь (у) =
г=0 '-=1 '-=0 v=0
ж ж ж ж ж
=/ (0)Е рг+Е ь (v)Е 1=/ (0)Е рг+Е (ж +1 -V)Ь^).
'-=0 v=0 г=v г=0 v=0
ж
Е (ж+1 — 0Ь (0
Отсюда — / (0) = ---ж-------•
Е Р
г=0
Вычислим теперь величины Ь (г). Имеем
ж ж Р — рж+1
Ь (г) = Л (0)Е R (v) — Я (0 = я 2(0)ЕpV- я (0)р'- = я2(0)^-----------Я (0)рг =
v=г v=г 1-Р
Г 1 -пж+1-г 1 N -пж+1-г 1 _ж+1
=Я (0)рг | я (°)^{^ -1]=Я (°)рг -1|=Я (°)(рг — «^-р+т.
Итак, окончательно,
ж
Е (ж+1 — 0Ь (0 ж+1
-/(0) =----ж------------, Ь (г) = Я (0)(рг — 1)-РжГ. (37)
Ер'- 1-Р
г=0
Если / (0) Ф 0, то выходящий поток не является пуассоновским.
Заключение
Построена математическая модель торговой точки в виде системы массового обслуживания типа М/М/ да с отказами от постановки в очередь. Выполнено исследование выходящего потока обслуженных требований. Определено среднее число обслуженных заявок и построено финальное распределение вероятностей числа заявок в системе.
ЛИТЕРАТУРА
1. Лопухова С. В. Асимптотические и численные методы исследования специальных потоков однородных событий: Автореф. дис. … канд. физ. -мат. наук. Томск, 2008.
2. Назаров А. А., Терпугов А. Ф. Теория массового обслуживания. Томск: Изд-во НТЛ, 2004.
3. Назаров А. А. Асимптотический анализ марковизируемых систем. Томск: Изд-во Том. ун-та, 1991.
Статья представлена кафедрой программной инженерии факультета информатики Томского государственного университета. Поступила в редакцию 13 октября 2008 г.

ПоказатьСвернуть
Заполнить форму текущей работой