ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6574
Скачиваний: 50
661
Итак, на входе этой задачи случайный процесс прихода покупателей в магазин. Он является
«марковским», т.е. промежутки между приходами любой последовательной пары покупателей -
независимые случайные события, распределенные по некоторому закону. Реальный характер этого
закона может быть установлен лишь путем многочисленных наблюдений; в качестве простейшей
модельной функции плотности вероятности можно взять равновероятное распределение в диапа-
зоне времени от 0 до некоторого
Т -
максимально возможного промежутка между приходами двух
последовательных покупателей. При этом распределении вероятность того, что между приходами
двух покупателей пройдет 1 минута, 3 минуты или 8 минут одинакова (если
T
> 8).
Такое распределение, конечно, малореалистично; реально оно имеет при некотором значе-
нии
t =
τ
максимум и быстро спадает при больших
t,
т.е. имеет вид, изображенный на рис. 7.56.
Можно, конечно, подобрать немало элементарных функций, графики которых похожи на
тот, что изображен на рис. 7.56. Например, семейство функций Пуассона, широко используемых в
теории массового обслуживания:
(7.70)
где
λ
- некоторая константа,
п -
произвольное целое. Функции (7.70) имеют максимум при
n
и
нормированы:
0
p
n
(t)dt =
1.
Рис. 7.56.
Типичная плотность вероятности распределения времени между приходами покупателей
Второй случайный процесс в этой задаче, никак не связанный с первым, сводится к после-
довательности случайных событий - длительностей обслуживания каждого из покупателей. Рас-
пределение вероятностей длительности обслуживания качественно имеет тот же вид, что и в пре-
дыдущем случае; при отработке первичных навыков моделирования методом статистических ис-
пытаний вполне уместно принять модель равновероятного распределения.
В таблице 7.8 в колонке
А
записаны случайные числа - промежутки между приходами по-
купателей (в минутах), в колонке
В -
случайные числа - длительности обслуживания (в минутах).
Для определенности взято
а
max
= 10 и
b
mах
= 5. Из этой короткой таблицы, разумеется, невозможно
установить, каковы законы распределения приняты для величин
А
и
В;
в данном обсуждении это
не играет никакой роли. Остальные колонки предусмотрены для удобства анализа; входящие в них
числа находятся путем элементарного расчета. В колонке
С
представлено условное время прихода
покупателя, в колонке
D -
момент начала обслуживания,
Е -
момент конца обслуживания,
F -
дли-
тельность времени, проведенного покупателем в магазине в целом,
G -
в очереди в ожидании об-
служивания,
Н -
время, проведенное продавцом в ожидании покупателя (магазин пуст). Таблицу
удобно заполнять по горизонтали, переходя от строчки к строчке. Приведем для удобства соответ-
ствующие формулы (в них
i
= 1, 2, 3,...):
так как начало обслуживания очередного покупателя определяется либо временем его прихода,
если магазин пуст, либо временем ухода предыдущего покупателя;
662
Таблица 7.8
Моделирование очереди
N
А
В
С
D
Е
F
G
Н
1
0
4
0
0
4
4
0
0
2
2
1
2
4
5
3
2
0
3
10
5
12
12
17
5
0
7
4
1
2
13
17
19
6
4
0
5
6
3
19
19
22
3
0
0
Таким образом, при данных случайных наборах чисел в колонках
A
и
В
и покупателям при-
ходилось стоять в очереди (колонка
G),
и продавцу - в ожидании покупателя (колонка
H
).
При моделировании систем такого вида возникают следующие вопросы. Какое среднее
время приходится стоять в очереди к прилавку? Чтобы ответить на него, следует найти
в некоторой серии испытаний. Аналогично можно найти среднее значение величины
h.
Конечно,
эти выборочные средние сами по себе - случайные величины; в другой выборке того же объема
они будут иметь другие значения (при больших объемах выборки, не слишком отличающиеся друг
от друга). Доверительные интервалы, в которых находятся точные средние значения (т.е. матема-
тические ожидания соответствующих случайных величин) при заданных доверительных вероят-
ностях находятся методами математической статистики.
Сложнее ответить на вопрос, каково распределение случайных величин
G
и
Н
при задан-
ных распределениях случайных величин
А
и
В.
Допустим, в простейшем моделировании мы при-
мем гипотезу о равновероятных распределениях величин
A
и
В -
скажем, для
А
в диапазоне от 0 до
10 минут и
В -
от 0 до 5 минут. Для построения методом статистических испытаний распределе-
ний величин
G
и
Н
поступим так: найдем в достаточно длинной серии испытаний (реально - в де-
сятках тысяч, что на компьютере делается достаточно быстро) значения
g
max
(для
Н
все делается
аналогично) и разделим промежуток [0, g
max
] на
т
равных частей - скажем, вначале на 10 - так,
чтобы в каждую часть попало много значений
g
i
. Разделив число попаданий
n
k
в каждую из частей
на общее число испытаний
n
, получим набор чисел
p
k
=
n
n
k
(k =
1, 2,...,
n
). Построенные
по ним
гистограммы дают представление о функциях плотностей вероятности соответствующих распре-
делений. По гистограмме можно составить представление о функции плотности распределения
соответствующей случайной величины. Для проверки же гипотезы о принадлежности такого эм-
пирически найденного распределения тому или иному конкретному виду служат известные стати-
стические критерии.
Располагая функцией распределения (пусть даже эмпирической, но достаточно надежной),
можно ответить на любой вопрос о характере процесса ожидания в очереди. Например: какова ве-
роятность прождать дольше
т
минут? Ответ будет получен, если найти отношение площади кри-
волинейной трапеции, ограниченной графиком плотности распределения, прямой
х = т
и
у
= 0, к
площади всей фигуры.
Следующая программа позволяет моделировать описанный выше процесс. На выходе она
дает средние значения и дисперсии случайных величин
g
и
h,
полученные по выборке, максималь-
ный объем которой порядка 10000 (ограничение связано с малой допустимой длиной массива в
PASCALe; чтобы его смягчить, использовано динамическое описание массивов
g
и
h
). Кроме того,
программа строит гистограммы распределений величин
g
и
h.
663
Программа 152.
Моделирование очереди
Program Cohered;
(входной поток равновероятных событий;
динамические массивы позволяют значительно увеличить объем выборки)
Uses Crt, Graph;
Const N = 10000 (число членов выборки);
W1 = 10 (диапазон времен прихода от 0 дo wl};
W2 = 5 (диапазон времен обслуживания от 0 до w2};
Type Т = Array(l..N] Of Real; U = ^Т;
Var A, B, C, D, E, F, Aa, Bb, Cc, Dd, Ее, Ff, Dg, Dh, M : Real;
Sl, S2 : Double; I, K, J, I1, I2 : Integer;
LI, L2, V : Array [1..11] Of Real; G, H : U; Ch : Char;
Begin
If MaxAvail >= SizeOf(G) Then New(G);
If MaxAvail >= SizeOf(H) Then New(H);
Randomize; (ниже - имитационное моделирование)
Aa := 0; Bb := W2 * Random; Cc := 0; Ее := Bb; Ff := Bb;
G^[l] = 0; H^[1] := 0;
For К = 1 To 11 Do
Begin L1(K] := 0; L2[K] := 0 End;
For I = 2 To N Do
Begin
A := Wl * Random; В := W2 * Random;
С := Cc + A; If С > Ее Then D := С Else D := Ее;
E := D + B; F := E - C; G^[I] := F - B; H^[I] := D - Ее;
Cc := С; Ее := E;
If G^[I] <= 1 Then Ll[l] := Ll[l] + 1; If H^[1] = 0 Then
L2[l] := L2[l] + 1;
For К := 2 To 10 Do
Begin
If (G^[I] > К - 1) And (G^[I] <= K) Then L1[K] := L1[K] + 1;
If (H^[I] > K - 1) And (H^[I] <= K) Then L2[K] := L2[K] + 1;
End;
If G^[I] > 10 Then Ll[l1] := Ll[ll] + 1;
If H^[I] > 10 Then L2[ll] := L2[ll] + 1;
Sl := Sl + G^[l]; S2 := S2 + H^[I];
End;
For I := 1 To 11 Do (ниже - нормировка распределений g и h}
Begin
L1[I] := L1[I] / N; L2[I] := L2[I] / N
End;
(ниже - расчет средних и дисперсий величин g и h}
Sl := Sl / N; S2 := S2 / N; Dg := 0; Dh := 0;
For I := 1 То N Do
Begin
Dg := Dg + Sqr(G^[I] - Sl); Dh := Dh + Sqr(H^[I] - S2)
End;
Dg := Dg / N; Dh := Dh / N;
WriteLn('распределение величины g распределение величины h');
WriteLn;
For K := 1 To 11 Do
WriteLn ('11[', K, ']=', L1[K] : 6 : 4, '' : 20, '12(', К, ']=',
L2[K] : 6 : 4);
WriteLn;
WriteLn('выборочное среднее величины g=', S1 : 6 : 3,
' выборочная дисперсия величины g=', Dg : 6 : 3);
WriteLn('выборочное среднее величины h=', S2 : 6 : 3,
' выборочная дисперсия величины h=', Dh : 6 : 3);
Dispose(G); Dispose(H); WriteLn;
WriteLn('для продолжения нажать любую клавишу');
664
Repeat Until KeyPressed; Ch := ReadKey;
(ниже - построение гистограмм распределений величин g и h)
DetectGraph(I, К); InitGraph(I, К, '');
I := GetMaxX; К := GetMaxY; J := I Div 2; M :'= Ll[l];
For I1 := 2 То 11 Do If L1[I1] > M Then M := L1[I1];
For I1 := 1 To 11 Do V[I1] := L1[I1] / M;
Line(10, К - 10, J - 20, К - 10); Line[l0, К - 10, 10, 5) ;
OutTextXY(20, 100, 'распределение величины g');
For I1 := 1 To 11 Do
Begin
I2 := Round((K - 20) * (1 - V[I1])) + 10;
Line(I1 * 20 - 10, I2, I1 * 20 + 10, I2);
Line(I1 * 20 - 10, I2, I1 * 20 - 10, К - 10);
Line(I1 * 20 + 10, I2, I1 * 20 + 10, К - 10);
End;
Line(J + 20, К - 10, I - 10, К - 10);
Line(J + 20, К - 10, J + 20, 5) ;
OutTextXY(J + 30, 100, 'распределение величины h'); M := L2[l];
For I1 := 2 To 11 Do If L2[I1] > M Then M := L2[I1];
For I1 := 1 To 11 Do V[I1] := L2[I1] / M;
For I1 := 1 To 11 Do
Begin
I2 := Round((K - 20) * (1 - V[I1])) + 10;
Line(J + I1 * 20, I2, J + I1 * 20 + 20, I2);
Line(J + I1 * 20, I2, J + I1 * 20, К - 10);
Line(J + I1 * 20 + 20, I2, J + I1 * 20 + 20, К - 10);
End;
OutTextXY(200, GetMaxY - 10, 'для выхода нажать любую клавишу');
Repeat Until KeyPressed; CloseCraph
End.
Приведем для сравнения результаты расчета средних значений величин
g, h
и соответст-
вующих среднеквадратичных отклонений
Sg,
Sh
, полученные при одинаковых значениях всех па-
раметров в пяти разных сериях испытании по 10000 событий в серии (табл. 7.9) (входной поток
покупателей - процесс равновероятных событий с максимальным временем между приходами 10
мин, длительность обслуживания также распределена равновероятным образом в интервале от 0
до 5
мин).
Таблица 7.9
Сравнение результатов моделирования в разных сериях испытаний
Испытание
g
Sg
h
Sh
1
0,738
1,568
2,508
2,588
2
0,746
1,511
2,500
2,571
3
0,765
1,529
2,446
2,582
4
0,753
1,524
2,451
2,589
5
0,765
1,573
2,482
2,572
Количество цифр выписано таким образом, чтобы отразить значимую разницу между дан-
ными разных серий.
Оценим доверительный интервал математических ожиданий величин
g
и
h
при с достовер-
ности 0,99 по формуле
x
< тх <
x
; ε =
2,58 ∙
n
S
( x
-
среднее значение
х; п -
объем вы-
борки;
S -
среднеквадратичное отклонение). По первой выборке получаем
665
0,738 - 0,025 <
mg <
0,738 + 0,025 (округлим: 0,71 <
mg <
0,77)
2,508 - 0,067 <
mh <
2,508 + 0,067 (округлим: 2,44 <
mh <
2,58).
Таким образом, различия в выборочных средних вполне укладываются в указанные довери-
тельные интервалы.
В рассмотренной задаче, как и в любой более
сложной задаче
об очередях,
может возник-
нуть критическая ситуация, когда очередь неограниченно растет со временем. В самом деле, если
люди заходят в магазин очень часто (или продавец работает слишком медленно), очередь начинает
нарастать, и в любой системе с конечным временем обслуживания наступит кризис. Приведем для
иллюстрации динамики этого процесса распределения величина - времени ожидания покупателем
в очереди и
h -
времени простоя продавца в ожидании покупателя, при трех наборах параметров
w1, w2,
где
w1 -
максимальный интервал времени между приходами покупателей,
w2 -
максималь-
ная длительность обслуживания покупателя (рис. 7.57 - 7.59).
Рис. 7.57. w1
= 10,
w2 =
3 (нет проблем с обслуживанием, вероятность долго простоять в очереди
мала, вероятность бездеятельности продавца достаточно велика)
В чем практическое значение задач об очередях? Прежде всего, стремление рационально
построить обслуживание потребителей. В магазине можно, к примеру, поставить второго продав-
ца, но если при этом продавцы будут мало заняты, возникает ущерб для предприятия. Таким обра-
зом, актуальным является вопрос об отыскании оптимального решения при наличии противоречи-
вых требований, т.е. налицо оптимизационная многокритериальная модель.
Визуально проиллюстрировать формирование очереди поможет следующая программа.
Рис. 7.58. w1 =
10,
w2 =
8 (кризис приближается)