/
Text
Программно-методический комплекс «Математические модели мас-
сового обслуживания» содержит краткие сведения по теории марковских це-
пей и их применению к исследованию простейших систем массового обслу-
живания, примеры с решениями и изложением проблемных ситуаций. Руко-
водство содержит индивидуальные задания по разделам «Марковские слу-
чайные процессы» и «СМО с отказами и ожиданием», а также программное
обеспечение для их выполнения.
Этот комплекс составлен в соответствии с учебным планом и предна-
значен для студентов всех специальностей дневной и заочной форм обуче-
ния.
Утвержден редакционно-издательским советом университета.
>
Авторы: И.Я. Кац, доктор физ.-мат. наук, профессор, УрГУПС
П.П. Скачков, кандидат физ.-мат. наук, доцент, УрГУ ПС
М.А. Толмачева, ст. преподаватель,УрГУПС
Рецензент: Г.А. Тимофеева, кандидат физ.-мат. наук, доцент,УрГУПС
1
i
© Уральский государственный университет путей сообщения (УрГУПС), 2001
о
I. Основные понятия теории марковских цепей
1 Л. Марковские цепи с дискретным временем и конечным
числом состояний
Пусть физическая система 5 находится в одном из состояний, обра-
зующих конечное множество |Sj,...,S„}, и переходит из одного состояния в
другое S, —> Sj случайным образом только в фиксированные моменты
времени Лз > • • • •
Тогда говорят, что в этой системе происходит случайный процесс.
Важным классом случайных процессов являются марковские процессы
(или процессы без последействия), введенные в научный обиход математи-
ком А.А. Марковым.
На интуитивном уровне это значит, что при известном состоянии сис-
темы в данный момент времени прогноз об ее будущем поведении не зави-
сит от состояний, в которых находилась эта система в прошлом.
Поскольку множество состояний конечно, а множество мо-
ментов времени Л 2 >•••} состоит из изолированных точек, такой случай-
ный процесс называется марковской цепью с дискретным временем и конеч-
ным числом состояний.
Как £лы убедимся позже, такие цепи и некоторые их модификации могут
служить/удобной математической моделью для описания многих интересных
и важных Технических (в частности, транспортных) объектов.
Приведем математическое описание марковских цепей с дискретным
временем, полагая для упрощения выкладок, что система может находиться
только в трех состояниях S4,> *$3’т е- принимая п = 3.
Обозначим символом рц, j = 1,2,3 вероятность перехода системы
из состояния St- в состояние S’у за один шаг. Такие вероятности образуют
матрицу Р вероятностей переходов за один шаг:
(Ри Pl2 Р13У
Р = Р21 Р22 Р23
Р32 РЗЗ'
(1.1.1)
Будем считать, что вероятности не зависят от номера шага, на кото-
•г
ром осуществляется переход St- —> S , и называть такие цепи однородными
марковскими цепями. В дальнейшем будем рассматривать только однород-
ные марковские цепи.
Элементы матрицы (1.1.1) обладают следующими свойствами:
Однородную марковскую цепь принято изображать в виде размеченного
графа состояний (рис. 1).
* Рп
Рис. 1
Рассмотрим матрицу Q{k) = (р1(А:)>Р2(^),Рз(А)), где д-(А:)- вероят-
ность того, что после к шагов система находится в состоянии Sj, / = 1,2,3.
Для элементов этой матрицы при любом к > 0 выполняется равенст-
3
во^рДЛ)-!. При к ~ 0 имеем матрицу 0(0) = (Р1(0),р2(0)>Рз(®)) ~ на-
чальное распределение вероятностей.
Матрицы P)Q{k\Q\ti\ удовлетворяют следующим матричным урав-
нениям ( ।
\ Q{k) = Q{k - 1)р или да = 2(0)^ ;t (1.1.3)
Эти уравнения позволяют определить вероятности состояний после А-го
шага по известному начальному распределению и заданной матрице пере-
ходных вероятностей за один шаг.
Введем следующие понятия.
Определение 1.1.1. Состояние S, называется существенным, если,
выйдя из этого состояния, система может в него вернуться за один или не-
сколько шагов : Ру(п) > 0 и рр(к) > 0.
Состояние S/называется несущественным, если, выйдя из Sit система
не может вернуться в него: Ру(п) > 0, рр(к) - 0, для любого к.
Так марковская цепь, граф которой приведен на рис. 2, имеет одно не-
существенное состояние .
о
Рис. 2
Распределение вероятностей состояний марковской”^
Определение 1.1.2.
цепи называется стационарным, если оно не изменяется во времени.
Стационарное распределение Q удовлетворяет матричному уравнению
или в координатной форме
Р\ ~ Р\Р\\^ Р2Р2\^ РзРз\
Р2 =Р\Р\2^Р2Р22+РЗР32
Рз = Р\Р\3 + P2P 23 + РзРзз
Для получения единственного решения к уравнениям (1.1.4) или (1.1.5) все-
гда необходимо добавить условие нормировки:
Р1+Р2+РЗ=1- (Ы-6)
Определение 1,1.3. Марковская цепь называется регулярной, если из
любого существенного состояния можно попасть в любое другое существен-
ное состояние за конечное число шагов.
I *»
Определение 1.1.4. Вероятности = lim Pj(n) называются предел ь-
п—>00
ными (или финальными) вероятностями состояний системы.
Теорема 1.1.1. Если марковская цепь регулярна, то предельные вероят-
ности состояний системы совпадают со стационарными вероятностями.
Пример 1.1.1. Для марковской цепи с тремя состояниями задана матри-
ца вероятностей переходов за один шаг:
1. Составить размеченный граф состояний этой марковской цепи, опре-
делить, является ли цепь регулярной.
2. Найти матрицу вероятностей за два шага.
3. Определить распределение вероятностей состояний системы за один,
два, три, четыре шага, считая начальным состояние Sj.
4. Найти стационарное распределение вероятностей. Изобразить в сис-
теме координат (к. Pi) стационарное распределение и распределения, полу-
ченные в пункте 3.
и
5. Найти финальные вероятности системы.
Решение.
1. Составим граф состояний. Он представлен на рис. 3.
Рис. 3
2. По графу видно, что все состояния
цепь регулярна. Найдем
Р(2) = Р(1)-Р(1):
о
а
системы существенны, поэтому
матрицу вероятностей переходов
за два шага
8
Р(2)= О
О
О
О
Заметим, что вероятность перехода из состояния S2 в состояние 5] за один
шаг Р2\(1) = 0, а за два шага р21 (2) = ~ * 0.
3. Пусть £>(0) = (1, 0, 0). Найдем распределение вероятностей состояний
за одйн и за два шага, 0(1), Q(2)'.
О
2(2) = (1,0,0) •
4
о
42 12
2(2) можно определить и по-другому:
0(2)=:0(1).Р(1) = (
_5_._8_«J.
18’18’18
Определим распределение вероятностей состояний после третьего шага:
6
к
Q(3) = Q(2) • P(l) =
0
_ ( 25 . 49 . 34
1108’108’108
Распределение вероятностей
шестнадцатого шагов получим на компьютере:
Г >
• М •
состоянии после четвертого, восьмого и
.2(4) = (0,234;0,461;0,303)
2(8) = (0,230;0,460;0,307)
2(16) = (0,231;0,461;0,308).
Построим график функций р\ = 0,231, Р2 = 0,461, Рз == 0,308 и
точки (Л;Р1(А)); (к;р2(к)); (к;р3(к)); к = 0,1,2,...8.
Обратим внимание как точки приближаются к соответствующим пря-
мым при возрастании к (рис.4 ).
4. По формуле (1.1.4 ) найдем стационарное распределение вероятно-
стей:
0
.1
зА + |Рз = Р\
Система (1.1.7) имеет бесчисленное множество решений, причем одно
из уравнений является следствием двух других. Чтобы найти единственное
решение, отбросим лишнее уравнение и
добавим условие нормировки
Р^шим сйЬтему уравнений:
~^Рл +5Р3 = °
- 4р\ + Зрз - 0
< 2/?i - 3/?2 + Зр3 = 0
'стац. = 1з;13;Тз/=(О’231; <М61; 0,308).
7
Марковская цепь регулярна, поэтому предельные вероятности совпадают со
стационарными. Получим рх =
Таблица 1.1
к 0 J 2 3 4 5 6 7 8 • 9
Р1(к) 1 0,333 0,278 0,231 0,234 0,230 0,231 0,231 0,231 0^231
Р2(к) 0 0,333 0,444 0,454 0,461 0,461 0,462 0,462 0,461 0,461
РЩ. 'о 0,334 0,278 0,315 1 0,304 Пэ,309 | 0,307 1 0,308 0.308 0,308
Таблица 1.1 й рис.4 иллюстрируют переходный процесс, протекающий в
Марковской цепи.
к
Рис. 4
Можно заметить, что вероятности всех трех состояний меняются на ка-
ждом шаге, но сумма Р\ + /?2 + Рз ~ 1 остается неизменной.
- 3
\*
8
1.2. Однородные марковские цепи с непрерывным временем
Физическая система S может находиться в одном из состояний
, однако, в отличие от предыдущего будем считать, что пере-
ход из одного состояния в другое возможен в любой случайный момент вре-
мени t, причем множество таких моментов перехода является непрерывным.
Если, как и ранее, выполняется марковское свойство (независимость буду-
щего от прошлого при известном настоящем), то будем называть такой слу-
чайный процесс марковской цепью с конечным числом состояний и непре-
рывным временем.
Обозначим символом Q(t) = (pj(/),..^рп(/)) матрицу вероятностей
состояний системы S в момент времени t9 pj\tj- вероятность того, что в
п
момент времени t система находится в состоянии S,. Ясно, что Pt\4 ~ L
Для того чтобы найти эти вероятности, надо знать характеристики процесса,
аналогичные вероятностям перехода Рц за один шаг (см. п.1.1).
•г
Определение 1.2.1, Интенсивностью Ау перехода системы —> S j
называется предел
Л» = lim ...-, (1-2.1)
J Дг-»0 Az
где р^ДАг)- вероятность перехода -» S (z & j) на интервале времени
Величины Ay при z j, в общем случае, зависят от расположения ин-
тервала / 4- А/ на оси времени (являются функциями времени). Если, од-
нако, Ay — const при z’^ j, то марковская цепь называется однородной. Да-
лее рассматриваются только такие марковские цепи.
Равенство (1.2.1) можно с точностью до бесконечно малых более высо-
кого порядка, чем А/, заменить следующим приближенным равенством
Положим, как и ранее, для упрощения выкладок п = 3 и рассмотрим
следующую матрицу интенсивностей переходов:
9
Л11 л12 л13
Л — ^21
кЯз1
Эдементы матрицы интенсивностей Л удовлетворяют условиям:
.ил,
у=1
Марковскую цепь с непрерывным временем можно изображать разме-
ченным графом состояний (рис. 5).
^12
Рис. 5
Матрица вероятностей состояний £(/) = (pi(z)’P2(z)-»P3(z)) удовлетво-
ряет системе дифференциальных уравнений Колмогорова. Эта система мо-
жет быть записана в матричной форме
2'(/) = е(/)Л (1.2.5)
или в координатной форме
Р\ (z) = Pl(z) + + ^31 Рз(0
Р2 (z) = ^i2/?l(z) +/22P2(Z) + ^32Рз(0 (1.2.6)
РЗ (г)“^13Л(0 + ^23Р2(г)“ь^ЗЗРз(/)-
/ г f f \
Здесь £?'(/) — (Pi \tyP2 v),P3 (z) ” матрица, составленная из произ-
водных Pi U), i = 1, 2, 3 вероятностей состояний в момент времени Л Для
решения системы (1.2.5) или (1.2.6) необходимо, как обычно, задать началь-
ные условия: . • . .
Р1(°) = Р1°. Рг(0) = Р2> Рз(°) = Лз. О-2-7)
О 1 - 0.0.0,
где р^ , i = 1, 2, 3 - заданные числа, причем р\ + р2 + Рз ~ 1
Определение 1.2.2. Распределение вероятностей называется стацио-
нарным, если вероятности pt состояний 5Z не зависят от времени
Р\(0 = Pi, Рг(()- Рз,Рз(1) = Рз или Q(i) = Q = const.
ю
Для стационарного распределения вероятностей системы = 0, то-
гда из (1.2.5) получаем систему алгебраических уравнений
£?-А = 0,
или в координатной форме:
^1\Р\ + ^21Р2 + ^31 РЗ ~ О
Л2Р1 + ^22 Р2 + Л12РЗ ~ О
^13Р1 + ^23Р2
+ ^ззРз - О-
Уравнения для стационарного случая можно составить непосредственно
по графу: сумма произведений Ллр/ для дуг, выходящих из состояния Sif
равна сумме произведений Лр для дуг, входящих в состояние 5;.
Для многих практических задач важно знать, как ведут себя вероятности
состояний системы при неограниченном возрастании времени. Обозначим
Pi = lirn Pi(t), Pj называются предельными (финальными) вероятностями
системы.
Понятия существенного (несущественного) состояния, регулярности
марковской цепи аналогичны тем, что даны для марковской цепи с дискрет-
ным временем.
Если марковская цепь регулярна, то предельные, вероятности состояний
совпадают со стационарными.
Система, для которой существуют предельные вероятности состояний,
называется эргодической и возникающий в ней случайный процесс - эргоди-
ческим.
Пример 1.2.1. Задана матрица интенсивностей марковской цепи с не-
прерывным временем:
Составить граф состояний, записать систему дифференциальных урав-
нений Колмогорова для вероятностей состояний. Найти частное решение
системы при начальных условиях рх (0) = 1, р2 (0) = 0, р3 (0) = 0. Найти ста-
ционарное и предельное распределения вероятностей состояний системы. ’
Решение.
Граф данной марковской цепи изображен на рис. 6.
J
Рис. 6
fl
Составим систему дифференциальных уравнений Колмогорова:
1
Тогда пдлучим
f
(при расчете мы использовали правило умножения двух матриц).
Найдем стационарные вероятности системы, полагая, что р\ = О,
♦
= 0. Получим систему линейных алгебраических уравнений:
P2
Третье уравнение этой системы получается, из первых двух. Отбросим
его и присоединим к системе уравнений условие р\ 4- р^ + р$ = 1:
~2р^ 4 — б
' Р\ - ^Рг + Рз = 0
LPl + Р2 + Л = 1
Решая систему, получим: •
'’-з 2 5 ' ( 3 2 5'
Р'~\0'Р2 \0'Рз~\0' £"110’10’10,
Будем решать теперь систему (1.2.9).
Исключая переменную р3 = 1 - - р2, получим:
fpj =-2pi +3р2
I Pl = -5р2 + 1
4.Ф" 1*14 о tun Гну *1' *41 «V»
'.W if.
12
Сведем систему двух уравнений 1-го порядка к линейному дифференци-
альному уравнению 2-го порядка:
Характеристическое уравнение имеет вид к2 4-7^4-10 = 0 с корнями
= -5, к2 = -2. Общее решение соответствующего однородного уравнения
Частное решение будем искать в виде
р* - А; тогда р* = 0; р* = 0 и А = ~
10
А 3 * 1 10
Используя начальные условия, запишем:
А(0) = 1
Р2 W = о
10
10
С1 -— и
1 10
Pi =
Окончательно имеем:
5
--е
10
Р1(0 - —
ю
10
10
10
ю’
10
10
/л(0 =-----е +—. (1.2.1
3 10 10
При t -» оо получим финальное распределение вероятностей
которое совпадает со стационарным распределением, а сами решения
(2.1.10) описывают переходный процесс, протекающий в рассматриваемой
марковской цепи. Зависимости p^t) представлены на рис. 7.
»
13
Заметим, что при возрастании t вероятности состояний достаточно бы-
стро сходятся к стационарным значениям в соответствии с решениями
(1.2.10), а при t = 0 дают начальное распределение.
14
1
1
1.3. Процесс гибели и размножения
I
<
* - *
Процессом гибели и размножения называется однородная марковская
цепь с непрерывным временем, размеченный граф состояний которой имеет
вид:
Рис. 8
Термин этот заимствован из математической. биологии, а его суть со-
стоит в том, что за малое время At система практически может перейти
только в соседнее состояние (или остаться на месте), но не может переско-
чить через одно или несколько состояний.
Найдем для этого процесса стационарное распределение. Составляя по
графу систему алгебраических уравнений, получим для стационарных веро-
ятностей Pq ,..., рп следующую систему:
(Л + Р\ )А = А)А) + Р2Р2 „ „ , ч
A'n—lPn—X ~~ РпРтг
Выразим из этой системы руу...^рп через р$ и подставим
нормировки ро + Р] +...+рп = 1.
После несложных преобразований получим окончательно
в условие
М Р\Р2
А] • • • Рп
Pfr
п.
Эти формулы широко используются в следующих разделах, поскольку
процессы, изучаемые в теории массового обслуживания, как правило, явля-
ются процессами размножения и гибели.
Отметим также, что этот процесс (рис. 6) является регулярным, поэтому
стационарное распределение (1.3.2) совпадает с предельным.
15
.... J.
ш№и*Т||ЦМ|
МЙЬМХА
1.4. Задачи
ь е
В заключительном параграфе этой главы приведем условия двух задач,
математическая формализация которых может быть построена в рамках тео-
рии марковских цепей.
Задача 1.4.1. В городе W каждый житель имеет одну из трех профессий:
А, В, С. Дети отцов, имеющих профессии А, В, С, сохраняют
3 2 1
профессии отцов с вероятностями ^/-соответственно, а
если не сохраняют, то с равными вероятностями выбирают
любую из двух других профессий.
Найти:
1) распределение по профессиям в следующем поколении, если в дан-
ном поколении профессию А имело 20% жителей, В - 30%, С - 50%;
2) предельное распределение по профессиям, когда число поколений
растет; *
3) распределение по профессиям, не меняющееся при смене поколений.
- ¥ ,
Задача 1.4.2. В прибор входят два устройства А и В. Интенсивность
отказов устройства А - Л| = 1, устройства В - Л2 ~ •
После выхода из строя устройство сразу начинают ремон-
» тировать. Интенсивность ремонта первого устройства
А = 2, второго устройства В - = 3.
1. Описать состояние системы и составить граф состояний марковского
процесса.
2. Записать дифференцированные уравнения вероятностей состояний
системы. , .*> , ...
3. Найти стационарное распределение и финальные вероятности.
4. Известно, что второе устройство более, современно и имеет произво-
дительность вдвое больше, чем первое. Первое устройство приносит доход 5
условных единиц в единицу времени, а второе - 10 условных единиц. Вы-
числил» доход, который приносят эти устройства.
5. (Задача о рационализации.) Предлагается произвести рационализацию
процесса, в результате чего удается сократить время ремонта вдвое. Но мы
Можем (из-за финансовых трудностей) применить её только к одному из уст-
ройств/Показать расчётом, к какому из устройств надо применить рациона-
лизацию.
16
-ч*
- V?
V
$
й
£
1.5. Варианты индивидуальных заданий
к
1. Дана матрица переходных вероятностей марковской цепи с дискрет-
ным временем. Составить граф марковской цепи, найти вероятности перехо-
дов из одного состояния в другое за два шага. Определить финальные веро-
ятности, если они существуют, а в противном случае доказать, что данная
цепь не является регулярной. Изобразить в системе координат прямые
Р\ = РстацЪ Р2 = РстацЪ РЗ = Рстац.З и точки> Соответствующие функ-
циям р} = Ptik), Р2 = Рз = Рз(к)’ k = 0,1,2,3,4,8,16.
Расчеты вероятностей рДк) при к = 1,2,3 производятся вручную, а при
к > 3 используется программа «Марковские цепи».
!
I'
1.13
1.14
1.15
1.30 /1}
2. Задана матрица интенсивностей переходов непрерывной цепи Мар-
кова Л. Составить размеченный граф состояний системы, соответствующей
этой матрице, записать систему дифференциальных уравнений Колмогорова,
найти частное решение системы при начальных условиях Pi(0) = 1, р2(0) = 0 ,
рз(О) = 0- Построить графики функций Pi(t), p2(t), p3(t). Записать стационар-
ные и предельные распределения.вероятностей.
18
19
20
2. Системы массового обслуживания
2Л. Основные понятия и классификация систем массового
обслуживания
Исследуя транспортные процессы, приходится сталкиваться с работой
своеобразных систем. Примерами могут служить билетные кассы, АТС,
справочные бюро, пункты экипировки локомотивов и другие.
Математический аппарат для изучения закономерностей функциониро-
вания систем, удовлетворяющих массовый спрос, и образования очередей в
такого рода системах называется теорией массового обслуживания.
Методы теории массового обслуживания все более широко применяют-
ся на транспорте для расчета рациональной организации подачи вагонов под
разгрузку и погрузку, для расчета мощностей пунктов текущего ремонта ва-
гонов, для выбора рационального числа кассовых аппаратов на вокзалах и
станциях метрополитена. Поэтому современному инженеру железнодорож-
ного транспорта необходимо знать основы теории массового обслуживания.
Заявкой (требованием) называется спрос на удовлетворение какой-либо
потребности. Далее примем, что все заявки однотипные. Удовлетворение
спроса называется обслуживанием заявки.
Системой массового обслуживания (СМО) называется любая система,
предназначенная для обслуживания каких-либо заявок, поступающих в нее в
случайные моменты времени. Устройство, непосредственно обслуживающее
заявку, называется каналом обслуживания. СМО может содержать одно та-
кое устройство, тогда она называется одноканалъной. Если СМО содержит
несколько обслуживающих устройств, то она называется многоканальной.
Поступление заявки в СМО назовем событием. Последовательности со-
бытий, состоящих в поступлении заявок в СМО, назовем входящим потоком
заявок. Последовательность событий, состоящих в выходе заявок из СМО,
назовем выходящим потоком заявок.
В зависимости от поведения заявки в СМО различают СМО с отказами
и СМО с очередью (или с ожиданием). В СМО с отказами заявка, посту-
пившая в момент занятости всех каналов, получает отказ и покидает СМО. В
СМО с очередью (или ожиданием) заявка, поступившая в момент занятости
всех каналов, становится в очередь и ожидает освобождения одного из кана-
лов обслуживания.
Возможны СМО смешанного типа. Например, СМО с ограниченной
очередью. В такой СМО заявка становится в очередь при занятости всех ка-
налов, десли очередь невелика и, скажем, не достигла длины т. Если все т
мест в очереди заняты, заявка покидает СМО. К СМО смешанного типа от-
носятся СМО с ограниченным временем ожидания. Заявка, поступившая в
21
момент занятости всех каналов, становится в очередь, но может уйти из
СМО не обслуженной, если время ожидания слишком велико.
СМО могут быть открытого и замкнутого типа. В открытых CMQ ин-
тенсивность поступающего в нее потока заявок не зависит от состояния са-
мой СМО, так как круг «клиентов» (поступающих заявок) практически не
ограничен. Примерами таких СМО являются вокзальные кассы, метрополи-
тен, телевизионные ателье больших городов и т.д. В СМО замкнутого типа
обслуживается ограниченный круг «клиентов», поэтому интенсивность по-
тока заявок существенно зависит от состояния системы. Примерами таких
СМО являются различные ремонтные системы в автопарках, цехах и т.д.
СМО с очередью и смешанного типа различаются также по дисциплине
обслуживания’, обслуживаются ли заявки в порядке поступления или в слу-
чайном порядке, или есть заявки, которые обслуживаются вне очереди (СМО
с приоритетом).
2.2. Простейший поток и его свойства
Рассмотрим входящий поток в СМО как последовательность точек
*1,^2 ~ моментов поступления заявок на оси временй Ot . Здесь /q ~
начальный момент.
z0
Поток заявок назовем простейшим, если он удовлетворяет трем услови-
! ям:
- J. Отсутствие последействия. Это условие означает, что заявки посту-
« пают в СМО независимо друг от друга, т.е. поступление заявки после момен-
} та времени t не зависит от того, когда и в каком количестве появлялись за-
1 явки до момента t .
2. Стационарность. Это условие означает, что вероятность поступления
некоторого числа заявок в СМО за время Д/ зависит лишь от длины интерва-
! ла Д/ = (/ + Д/) -t и не зависит от точки t отсчета этого интервала на оси
времени Ot. Если выполнено условие стационарности, то можно говорить о
среднем числе заявок, поступающих в СМО за единицу времени, например,
за один час, не указывая за какой именно час.
3. Ординарность. Это условие означает, что одновременное поступле-
ние в&МО двух и более заявок маловероятно, т.е. вероятность появления за
бесконечно малое время А/ более чем одной заявки есть бесконечно малая
более высокого порядка малости, чем Д/.
22
Таким образом, если поток заявок простейший, то случайные моменты
времени /,• (i = 1, 2, ...) поступления заявок в СМО распределены на оси
времени со средней плотностью Л (стационарность); эти точки попадают в
непересекающиеся интервалы независимо друг от друга (нет последействия);
заявки поступают в СМО поодиночке (ординарность), величина Лназыва-
ется интенсивностью потока заявок и представляет собой среднее число
(математическое ожидание числа) заявок, поступающих в систему за еди-
ницу времени.
Можно показать, что для простейшего потока вероятность /?,•(/) посту-
пления в СМО ровно i заявок за время t вычисляется по формуле
т.е. вероятности pAt) распределены по закону Пуассона с параметром At. В
♦
связи с этим простейший поток часто называют пуассоновским потоком.
Обозначим через Т интервал времени между поступлениями, двух по-
следовательных заявок. Найдем функцию распределения случайной величи-
ны Т
F(t) = Р(Т < /) = 1 - р0(/),‘
где Р(Т < /)- вероятность того, что случайная величина Т примет значение,
меньшее, чем г; р$ - вероятность противоположного события (т.е. за время t
в СМО не поступила ни одна заявка). По формуле (2.2.1) имеем
откуда
F(t)= (г>0). (2.2.2)
Найдем плотность распределения случайной величины Т:
Определяя математическое ожидание и дисперсию случайной величины
Т, получим
М|7-) = 1. О(И = ^. (2.2.3)
23
2.3. Марковские системы массового обслуживания
Для задания СМО необходимо задать вероятностные характеристики
времени обслуживания одной заявки. Обозначим это время через Т0^сл. Ве-
личина Т0^сл является случайной. Во многих задачах теории массового об-
служивания закон распределения времени обслуживания предполагается по-
казательным, т.е.
Л 0 = Л ТобеЯ < ') = 1 - е-*
(2.3.1)
Параметр этого распределения № есть величина, обратная среднему времени
t
обслуживания, т.е.
(2.3.2)
Часто А называют интенсивностью потока обслуживания, которая оз-
начает среднее число заявок, обслуживаемых одним каналом в единицу вре-
мени. При этом под потоком обслуживания понимается поток заявок, обслу-
живаемых одна за другой одним непрерывно занятым каналом. Если
представляет собой случайную величину, имеющую показательное распреде-
ление, то поток обслуживания является простейшим.
Если входящий поток и все потоки обслуживания простейшие, то про-
цесс, протекающий в СМО, является марковским случайным процессом (це-
пью) с дискретными состояниями и непрерывным временем. Поэтому СМО,
в которой все потоки простейшие, называют марковской СМО.
Таким образом, предположение о показательном законе распределения
времени обслуживания и интервала времени между двумя последовательны-
ми поступлениями заявок играет исключительную роль в теории массового
обслуживания, так как упрощает аналитическое исследование СМО, сводя
его к исследованию цепей Маркова.
2.4. Показатели эффективности систем массового
обслуживания
Обычно в теории массового обслуживания интересуются предельными
средними характеристиками системы, которые называют показателями эф-
фективности СМО. В качестве показателей эффективности для стационар-
ного режима могут рассматриваться следующие:
- среднее число заявок, обслуживаемое СМО в единицу времени. Эту
характеристику называют абсолютной пропускной способностью СМО;
jQ - вероятность обслуживания поступившей заявки или относительная
пропускная способность СМО. Очевидно,
24
Ротк - вероятность отказа, т.е. вероятность того, что поступившая заяв-
ка не будет обслужена, РОтк = 1 - 0 ;
z - среднее число заявок в СМО (имеются в виду все заявки, как об-
служиваемые, так и ожидающие очереди, если она есть);
Fq - среднее число заявок в очереди, если она есть;
1сист ~ среднее время пребывания заявки в СМО, как в очереди, если
она есть, так и под обслуживанием;
G - среднее время пребывания заявки в очереди;
к - среднее число занятых каналов.
Выбор показателей эффективности СМО зависит от типа СМО. Напри-
мер, абсолютная пропускная способность А , являясь основной 'характери-
стикой обслуживания в СМО с отказами, теряет смысл для СМО с неограни-
ченной очередью.
2.5. Многоканальная СМО с отказами
(задача Эрланга)
Задача Эрланга исторически является одной из первых решенных клас-
сических задач массового обслуживания. Возникла она из нужд телефонии и
была решена датским математиком Эрлангом.
Задача2.5.Е Пусть имеется п каналов обслуживания (линий связи), на
которые поступает поток заявок с интенсивностью Л. Поток обслуживания
имеет интенсивность Ц. Потоки в СМО простейшие.
Найти предельные вероятности состояний СМО, вычислить характери-
стики эффективности ее работы:
А — абсолютную пропускную способность;
Q ~ относительную пропускную способность;
Ротк - вероятность того, что заявка не будет обслужена;
к - среднее число занятых каналов.
Обозначим ‘S’o’*$1 ’—>*$и состояния системы массового обслуживания:
$0 ~ в системе нет заявок,
Si - в системе одна заявка,
Sn - в системе и заявок.
Следующая заявка, пришедшая в систему, получит отказ.
рп - вероятность отказа нашей системы: ротк = рп.
25
1 раф состоянии вреде кшясп ла pnv.^.
Рис. 9.
Входящий поток простейший с интенсивностью Л, поэтому переход из
состояния S; в происходит с одной и той же интенсивностью (условие
ординарности).
Переходы из состояния 5V в соседнее происходит с интенсивно-
стью кр (кратное количеству занятых каналов). Граф на рис.9, соответствует
графу процесса гибели и размножения. Согласно формулам (1.3.2), получим
(2.5.1)
Ир
Л
Ооозначим — - р, тогда получим выражения для вероятностей.
Р
Величина р определяет среднее число заявок, приходящее за среднее
время обслуживания одной заявки. Его называют коэффициентом загрузки
системы.
Вычислим коэффициенты эффективности работы системы массового
обслуживания с отказами:
п пп
Ротк=Рп=^-р^ е = 1-Л,™.=1-£?-Ро; a = qa. (2.5.3)
п\ п\
Найдем среднее число занятых каналов, составим ряд распределения
случайной величины к.
Таблица 2.5.1
к 0 J — *1 1 * - • < • n
Pi A) P\ 9 • tt Pn
= к = 0 • Pq + 1 • р] + 2 • pi +...+л • рп,
26
Можно найти среднее число занятых каналов к с помощью следующих
рассуждений: /(^абсолютная пропускная способность СМО, /л- интенсив-
ность потока обслуженных системой заявок. Каждый канал в единицу вре-
мени обслуживает в среднем /л заявок. Значит, число занятых каналов равно
Пример 2.5.1. Простейшая СМО представляет собой автоматическую
телефонную станцию с пятью линиями связи (число каналов - п ~ 5).
Если заявка приходит в момент, когда все каналы заняты, то она полу-
чает отказ. Интенсивность потока заявок 2 - 0,7 заявки в минуту, среднее
время обслуживания одной заявки t0$c = 3,4 мин.
1. Описать состояния СМО, построить ее граф.
2. Найти предельные вероятности состояний и характеристики эффек-
тивности работы АТС. Оценить ее работу.
3. Найти зависимость среднего числа занятых каналов и пропускной
способности АТС от интенсивности входного потока, сделать выводы.
4. Сколько потребуется каналов для того, чтобы удовлетворить не менее
99 % поступающих заявок? Какая доля каналов при этом будет простаивать?
5. Содержание каждого канала в течение месяца обходится в 10 тысяч
усл. ед. Каждая обслуженная заявка приносит доход в 1,5 ус л. ед. Опреде-
лить, приносит ли АТС доход от обслуживания всех заявок?
Решение.
1.Обозначим 5ц,Si,,—>S5 —состояния СМО:
Sq - в системе все каналы свободны,
5| -один канал занят, четыре свободны,
Si —два канала заняты, три свободны,
-три канала заняты, два свободны,
54 - четыре канала заняты, один свободен,
55 -пять каналов заняты.
Следующая заявка, поступившая в СМО, получает отказ.
Граф системы массового обслуживания имеет вид :
Рис. 10-
27
2. Из условия задачи известно:
3,4л/г/// - 2,38.
= 3,4лш/у;
По формулам (2.5.2-2.5.5) найдем
ки:
нужные вероятности и характериет’;-
'i
Pi = P0'-~ / = 1.2,3,4.5
г.
/?!= 0,228 ... р5 = 0,06100.
Тогда Ротк = р5 =0,061.
Это значит, что в нашей АТС 6 % абонентов получают отказ:
Среднее число занятых каналов-А' = 2.22 -
I С иС ,7»
В системе заявка в среднем находится t- 3,19 лч'//(по форслт'!
Г * С UL ffl . Г Г
Литла:
Результаты расчетов позволяют сделать вызол, что при достаточно вы-
сокой вероятности отказа, загруженность АТС составляет около 45 % кана-
лов.
Дальнейшая работа проводится с использованием ПЭВМ (см. раздел 5).
3. Так как по условию мы можем менять лишь один параметр (число ка-
налов), то задав значения п = 6,7,.., получим значения для Ритк :
п 6 7
р от к. 0,061 0,023 0,008
Следовательно, для того чтобы ЛЖА. <0,01, достаточно использовать 7
( / ! ГIА. . '
каналов.
4. Расчет на ЭВМ при п = 5 дает:
Л 0.7 "в"' 1.0 2.0 4.0 10.0 50.0 200.0 |
к 2.23 2.91 4.04 4.62 . _ _ , 4.84 4.97 4 99 1 1 — »
28
Из таблиц следует, что обе рассматриваемые величины с ростом интен-
сивности входного потока возрастают, стремясь к некоторым предельным
значениям. При этом среднее число занятых каналов стремится к полному
числу каналов в СМО (и = 5), а пропускная способность - к некоторой вели-
чине, больше которой при данном числе каналов и среднем времени обслу-
живания АТС пропускать нс может. Отметим, что фактически при больших
Л СМО не работает из-за неприемлемых значений р()тк (так при Л= 200,
А,™,. = 0.99).
5. На АТС обслуживается в среднем А = 0.66 (1/дшн) с доходом d - 1.5
сел. ед., тогда прибыль за одну минуту: D d • А ~ 0.99vc/,t / „ , a сум-
' ' ' ' / MUH '
марный доход за месяц: Dm - D • 60 • 24 • 30 = 42768 гсл.сО. 11а содержание
5 каналов требуется 50 000 усл. ед., значит, предприятие не рентабельно.
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
Системы массового обслуживания с отказами
АТС имеет 4 линии связи. Поток вызовов простейший с интенсивно-
стью 2 вызовов в минуту. Время переговоров распределено но показатель-
ному закону, среднее время составляет / мин (/) Информация об исход-
ных данных приведена в таблице 2.1.
1. Описать состояния СМО, построить граф состояний.
2. Найти предельные вероятности состояний системы. Найти показатели
эффективности работы АТС, проанализировать эти показатели.
3. Изучить зависимость среднего числа занятых каналов и абсолютной
пропускной способности АТС от интенсивности входного потока, зависимо-
сти представить в виде таблиц и графиков.
4. Определить, сколько линий должна иметь АТС, чтобы вероятность
отказа не превышала 0,01.
5. Содержание каждого канала в месяц обходится в 10 тысяч усл. ед.
Каждая обслуженная заявка приносит доход в 1,5 усл. единицы. Определить,
приносит ли АТС доход от обслуживания всех заявок? Каким должно быть
число каналов, чтобы доход был максимальным?
вари- анта № группы в потоке
? з 4 5
л [ / t
1 2 4 л» 3 7 8 9 10
1.1 > - * ' - * — * О.о 2.5 1 1 1 . 1 ”0\9 ’ 2.5 2.4 ь * Т S ' о 9 L 2 7 2.6 1 .Т" 1 5 2.1
1.3 0.8 2.9 ш-0 , 2 9 tr- ..._j 1 э ' 1 _ т J э 9 ш . 0.8 3.1 1 1 1 ‘ j ОС 1 1 t : 1.9 ! .
Окончание табл. 2.1
. _ . . . .. __. 1..
1 у— Г 2 3 4 5 6 7 8 9 10 -у—г—- 11
1.4 0.6 3.5 0.8 3.5 1.0 3.5 0.6 3.3 1.6 2.5
1.5 0.7 3.5 0.9 3.3 1.1 3.4 0.7 3.3 vl.7 2.5 ,
1.6 0.8 2.2 1.0 2.3 1.2 2.2 0.9 2.4 1.8 3.2 ** А
1.7 0.9 2.6 1.0 2.7 2.6 0.8 2.8 1.8 1 9 J ] Д •
1.8 0.9 2.1 1.1 2.2 j э 1.3 2.1 0.8 2.3 ; 1,9 1
1-9 0.7 3.1 6.9 3.1 1.1 3.2 0.7 2.9 ! i-7 3.0
1.10 0.9 2.8 1.1 2.7 1.3 2.8 т 0.9 3.0 0.8 2.8
1.11 0.9 3.2 1.1 3.3 1.3 3.4 1.3 3.1 1.9 3.3
1:12 0.5 3.1 0.7 3.0 0.9 3.2 0.9 3.4 1.5 2Л
1.13 0.6 2.5 0.8 2.6 1.5 1 2.7 1.5 2.9 1.6 2.5 |
1.14 1.7 2.0 1.8 1.9 1.6 2.1 1.5 .. 2-4. 1.4 f 1.8
1.15 2.1 2.7 1.9 1.6 2.2 1.9 1.9 3.1 2.7
1.16 2.0 3.1 2.5 2.1 0.6 4.1 0.7 4.3 0.8 1 4.2
1.17 0.9 4.1 0.8 4.4 0.9 4.5 i 1.1 4.3 1.2 4.2
1.18 1.1 3.9 3.9 1.5 4.0 1.5 4.2 1.4 4.3
1.19 2.1 3.8 2.2 4.1 2.3 4.5 4.4 2.3
1.20 2.2 3.9 2.1 4.0 2.3 3.9 2.5 4Д 2.6 4.1
1.21 0.5 4.1 0.7 4.2 0.6 3.9 0.8 4.2 0.9 г г . .10- 1- . 5.1
1.22 0.6 4.2 0.8 5.1 0.7 4.0 0.9 3.7 1.2 5.2
1.23 0.7 4.3 0.9 5.0 0.8 3.8 1.1 3.8 3.4
1.24 0.8 4.4 0.9 0.9 3.9 6.8 6.1 1.4 4.2
1.25 0.9 4.5 1.1 5.0 1.1 4.1 0.5 6.2 1.4 4.4
1.26 1.1 4.2 1.2 5.3 4.3 0.4 6Л 1.5 5.0
1.27 1.2 4.1 1.3 4.4 1.3 4.2 0.5 6.3 1.6 4.8
1.28 0.9 4.3 1.5 4.0 1.4 4.3’ 1.5 3.0 1.7 5.1
1.29 0.8 4.2 1.3 4.2 АГ) 1 4.5 16 3.2 1.9 5.7
1.30 0.5 5.1 1.4 5.0 1.6 4.6 1.7 3.4 1.8 5.4
е
Л
30
2.6. Одноканальная СМО с неограниченной очередью
Из СМО с ожиданием самой простой является одноканальная СМО с
неограниченной очередью. Такие СМО часто встречаются в практике: врач,
обслуживающий пациентов; телефон-автомат с одной будкой.
Пусть имеется одноканальная СМО с очередью, на которую не наложе-
• но никаких ограничений. На эту СМО поступает поток заявок с интенсивно-
стью Л; поток обслуживания простейший и имеет интенсивность р,
/ А =“
‘ ООС.1.
к р)
Найти предельные вероятности состояний СМО, а также характеристи-
ки эффективности ее работы.
Запишем состояния СМО (состояния пронумерованы по числу заявок в
системе):
Sq - канал свободен,
S] ~ канал занят, очереди нет,
S2 - канал занят, одна заявка в очереди,
S„ -канал занят; п — 1 заявка в очереди
и так далее.
Теоретически число состояний не ограничено (бесконечно). Граф со-
стояний показан на рис. 11.
. Рис. 11
Существуют ли в этом случае предельные вероятности, ведь число со-
стояний системы бесконечно?
Формула для определения имеет вид
Ро = (1 + р+p^+...+pw+...
В скобке стоит сумма бесконечной геометрической прогрессии. Если
знаменатель прогрессии р =
< 1, то сумму можно вычислить по формуле
Если р > 1, то ряд расходится, сумма растет неограниченно, СМО не может
работать из-за неограниченно возрастающей очереди. Дальнейшие формулы
справедливы только при р < 1.
р0=1-р; рк = рк(1-р), Л = 1,2... (2.6.2)
Среднее число заявок в очереди однокгнальной СМО и время ожидания об-
г
I
служивания равно
о
Среднее число занятых каналов
теме
-сист
и среднее время нахождения заявки в системе
сист
Пример 2.6.1. На железнодорожную сортировочную горку прибывают
составы с интенсивностью Z - 2 состава в час.
Среднее время, в течение которого горка обрабатывает состав, равна 24
минутам. Составы, прибывшие в момент, когда горка занята, становятся в
очередь и ожидают в парке прибытия, где имеются три запасных пути, на
каждом из которых может ожидать один состав.
Состав, прибывший в момент, когда три запасных пути заняты, ставится
на внешний путь. Станция платит штраф за пребывание состава на внешнем
пути (а усл. ед. за 1 час).
1. Описать состояния системы и построить граф состояний.
2. Вычислить вероятности состояний СМО для стационарного случая и
коэффициенты эффективности работы горки. Сделать выводы о качестве ее
работы.
3. Найти функциональную зависимость длины очереди от среднего
времени расформирования составов, а также ее зависимость от изменения
интенсивности А(сост. / ч) потока составов, прибывших на расформирова-
ние: r0 = <p(to6al); го = <р(Л).
4. Вычислить штраф, который должна выплачивать станция за месяц из-
за ожидания обслуживания на внешних путях.
5. Если интенсивность потока составов увеличится в полтора раза, как
будет работать СМО? Подтвердить выводы расчетами.
32
Решение»
1. Состояния СМО описаны в пункте 2.6, а граф представлен на рис. 11.
Нас будут интересовать те состояния, при которых составы попадают на
внешний путь:
- один состав на горке, три в очереди на запасных путях станции,
один на внешних путях,
~ один - на горке, три - на запасных путях, два - на внешних путях
и так далее.
2. Вычислим вероятности стационарных состояний СМО:
Я = 2 сост./'ч; to6cjl = 24мин = 0,4; // = 2,5сост./ч
р = 2-0,4 = 0,8<1 ро=1-р=О,2
Pi =0,16; р2 ~ 0,128; р$ =0,102; р^ =0,082...
Найдем вероятность того, что прибывающий состав попадает на внеш-
ний путь
р(А) = рА «0,41.
Таким образом, в 41% случаев состав попадает на внешний путь.
Вычислим коэффициенты эффективности работы горки.
Среднее число составов, ожидающих в очереди (как в парке, так и вне
его),
- °’64 г то к
г =------= 2Д состава, tn = — = 1,6 часа.
° 1-0,8 ° Я
Среднее число составов в парке расформирования
— 0,8 . 7 %сист. „
% сист. ~ 1 4 состава, * 2 ч.
1 JT11
Таким образом, составу приходится более 1,5 часов стоять в очереди.
3. Придадим to6c4 разные значения с 0,1 ч. до 0,5 ч. Большее значение
придавать нельзя. При to6c4 = 0,5, /9 = 1 стационарный режим не существует.
Полученные результаты расчета для гоприведены в табл. 2.6.1 и показаны на
рис. 12. Из таблицы видно, что после to6cn =0,45 очередь начинает резко воз-
растать, затем СМО перестает работать нормально.
Зафиксируем теперь to6cjl = 0,4 часа и будем изменять Интенсивность
потока составов на горку. Я: 1; 1,5; 1,7; 2; 2.2; 2,4. При Я = 2,5, р-1 систе-
ма не работает. Зависимость приведена в таблице 2.6.2 и изображена на гра-
фике (рис. 13).
33
I
1,
I
Таблица 2.6.1
^обсл 0 1 0,2 0.3 0,4 0,45 ! ' <5 I
0.05 г 0,27 0.9 3.2 : 1 3,1
Л
I
«
I I
i
о
0,2
0,1
0,4
Рис. 12
^обсл
Таблица 2.6.2
1
»
34
4. Вычислим среднее время ожидания обслуживания одним составом на
внешних путях. Составим закон распределения случайной величины гви
(таблица 2.6.3); rew - число составов, поставленных на внешних путях.
Таблица 2.6.3
Г 1 i 0 1 f ' — 11 ! 2 3 А • • •
L_2L__ р(0) Р5 Pl ] PS
р(0)= р0 + Р] + + р3 + р 4
f
В нашем примере:
ычислим штраф за сутки:
Ш = 2 сост./час. • 24 час. * 0,41 • а ~ 39,36 а усл.ед.
2.7. Многоканальная СМО с неограниченной очередью
Рассмотрим многоканальную СМО с неограниченной очередью. Число
каналов - п . В эту систему поступает простейший поток заявок с интенсив-
ностью Я; среднее время обслуживания одной заявки to(-c распределяется по
показательному закону.
Найти вероятности стационарных состояний СМО; оценить работу
СМО по коэффициентам эффективности работы, указанным в п. 2.4.
Запишем состояния системы, они пронумерованы по числу заявок в сис-
теме, т е. по числу занятых каналов, плюс число заявок в очереди.
5ц - все каналы свободны,
51 — один канал занят,
52 - два канала заняты,
Sn - п каналов заняты,
5л+1 - п каналов заняты, одна заявка в очереди,
5л+2 - п каналов заняты, две заявки в очереди,
и так далее.
35
В этой СМО ни одна заявка не получит отказа: ротк = 0.
Граф будет такйм
Рис. 14
Интенсивности переходов 5} в i -ОД,1 одинаковы и рав
яы Л, т.к. входной поток заявок простейший.
Интенсивность обратных переходов является кратной числу занятья
каналов.
Запишем алгебраические уравнения для стационарного случая и опрс
делим из них и нормировочного условия :
лп
• • «-I
рп n-nlp
Л р р
— = р, рассмотрим величину —. гели -
р п п
ста стационарных состояний можно найти по формулам:
Обозначим
вероятно
2!
Р
Р\ = Р' Р& Pl = Р&
п Ли+1
Р . Z
/ P(bPn+\ .'Р0»‘ "^Рп+к
I п-п\ п
п+к
—:Ро
Если — > 1, то предельные вероятности также, как стационарные вероятно-
го
сти, не существуют, очередь растет неограниченно и СМО не может рабо-
тать. Запишем формулы расчета коэффициентов эффективности работы
ГКЛП пне ' 1
СМО для случая — < 1.
п
отк 0,Q 1
Среднее число занятых каналов -
Т" Л
к - — ~ р.
Р
(2.7.2)
(2.7.3)
Среднее число заявок, стоящих в очереди, -
Л Л
А
п Л
Р
п
= 1, А ~ Л
36
(2.7.4)
среднее время ожидания
G»
(2.7.5)
Пример 2.7.7. Ателье по ремонту аппаратуры имеет 5 опытных мастеров. В
среднем в течение рабочего дня от населения поступает в ремонт 10 аппара-
тов. Общее число аппаратов, находящихся у населения, очень велико, а вы-
ходят они из строя независимо друг от друга. Поэтому имеются основания
считать поток заявок простейшим. Пусть все мастера имеют одинаковую
квалификацию и в среднем могут отремонтировать 2,5 аппарата в день каж-
дый. Определить показатели качества обслуживания в данном ателье. Найти
Решение. Запишем данные задали.
Интенсивность
входящего потока заявок аппаратов Л = 10апп. в день
в час, мы считаем, что в ателье восьмичасовой рабочий день.
Интенсивность потока обслуживания р = 2,5 апп. в день, п = 5, р = — - 4;
Используем для расчета формулы 2.7.1 - 2.7.5:
0,01299
Ро = 0,013 , р] = 0,052 ...
Запишем состояния системы:
So — все мастера свободны,
Sj — один мастер занят,
S2 - два мастера заняты,
S5 —пять мастеров заняты ремонтом,
S^ — все мастера заняты, один аппарат ожидает обслуживания,
S-j - все мастера заняты, два аппарата в очереди и так далее.
Заметим, что вероятность того, что все мастера свободны, мала: ро - 0,013.
Среднее число аппаратов, ожидающих ремонта, и время ожидания -
г0 = 2,22; То = 0,22раб.дня = 1,76ч.
Среднее число аппаратов, находящихся в ателье - zcucm = 6,22,
37
«7»
tCUcm.~ Pa6.Дня = 4,96 ч. 5 ч.
Как видно из расчетов, ателье сильно загружено работой, аппараты находят-
ся в ателье в среднем 5 часов.
Вычислим вероятность того, что все мастера заняты (событие А):
/л p5f р р2 ) pS 1
\ / I----
5
р(Л) = 0,554.
Все мастера заняты в 55,4% случаев.
3. Найдем функциональную зависимость = Зависимость представ-
лена в таблице 2.7.1.
Таблица 2.7.1
'Ч ' Л 8 9 10 $ 12
7О. 0,513 - 1,055 2,216 5,268 21,64
Если один из мастеров заболеет или уйдет в отпуск, то при р = 2,5 апп/^ень
ателье не сможет стационарно работать, очередь будет расти неограниченно.
В таблице 2.7.2 приведена зависимость средней очереди от скорости ремонта
(л = 4).
Таблица 2.7.2
Р 3 3,5 4
го. 0,649 0,265 0,130
2.8. Многоканальная СМО
с ограниченным числом мест в очереди
Пусть в СМО п каналов и т мест в очереди. Заявка, пришедшая в СМО,
когда все места в очереди заняты, получает отказ. В этой СМО интересной
характеристикой работы является вероятность отказа пришедшей заявке.
Состояния системы:
$0 — в СМО нет заявок,
5*1 — в СМО одна заявка,
S
Sn — в СМО п заявок,
— в СМО п заявок в обслуживании и одна заявка в очереди,
~ в СМО п заявок в обслуживании и т заявок в очереди.
Следующая заявка, пришедшая в СМО, получает отказ.
Заметим, что число состояний конечно: 5о,51,...,5й+/я.
Граф СМО в этом случае приведен на рис. 15.
Рис. 15
Вероятности состояний будут
(2.8.1)
Таким образом, если 1
п
то
W+1
Ро =
п \п
Если — = 1 , то расчет р$ проводят по формулам:
п
л+1
п+т
2!
п-п!) ’
И
р
>п = —ТРО >
п\
п+т
РО •
(2.8.2)
(2.8.3)
Р\ ~ Р'РоР Р1 - Ро > • ••;
л* •
рл+1
Рп+\ - . Ро> • • • ; Рп+т - т
п-п\. пт
Таким образом, все вероятности состояний найдены.
Найдем коэффициенты эффективности работы СМО:
39
п
п
п
Я = Я • Q .
отк. >
Среднее число занятых каналов
*Ро
т i v
П ’ п\
Среднее число заявок в очереди
(2.8.5)
° »
п • я!
Ро
(2.8.6)
к —
п
р
п
Среднее время ожидания
7 _ ’О
° А ’
Среднее число заявок в системе
сист.
к
z
*
си ст.
сист.
Пример 2.8.1. Автозаправочная станция имеет 2 колонки. Площадка
Возле АЗС позволяет поставить в очередь не более четырех автомобилей. Ес-
ли вся площадка занята, то следующий автомобиль проезжает дальше без за-
правки. Поток автомобилей простейший с интенсивностью А = 1 а*т/мин •
Время ожидания подчиняется показательному закону, to6cn ~ Змйн..
1. Описать состояния СМО, построить граф состояний.
2. Найти стационарные вероятности состояний системы и коэффициен-
ты эффективности работы.
3. В условиях конкуренции требуется, чтобы отказ от обслуживания по-
лучали не более 10 % автомобилей, нуждающихся в заправке. Удовлетворяет
ли АЗС этому требованию? Что можно предпринять, если это требование не
выполняется? о
4. Исследовать зависимость отклонений ротк и Л, полученных мето-
дом статистического моделирования от тех же параметров, рассчитанных по
точным формулам. Выбрать различное время моделирования.
Решение. Запишем состояния АЗС:
Зф - все колонки АЗС свободны, очереди нет,
5] — одна колонка занята, очереди нет,
40
$2 ~ две колонки заняты, очереди нет,
- две колонки заняты, одна машина в очереди,
56 — две колонки заняты, четыре машины в очереди.
Следующая машина, пришедшая в АЗС, получит отказ.
Граф имеет вид (рис. 16).
Рис. 16
2. Найдем стационарные вероятности по формулам (2.8.1), (2.8.2),
Ро =0,0158; =0,047;
Из расчетов видно, что АЗС почти не простаивает = 0,0161
Заметим, что лишь 6,3 % всех автомобилей, пришедших в АЗС для
заправки, получат ее без очереди:
(ро + й)-100% = (0,0158+ 0,0470)-100% « 6,3%.
Вероятность отказа в заправке ротк = р6 =0,36, поэтому около 36 %
автомобилей не будут обслужены.
Относительная и абсолютная пропускные способности
0 = =0>64> А = Q Л = °>64 1аМ/мин. •
Среднее число занятых каналов
k=- = 1,92.
Оно близко к 2, что свидетельствует о большой загрузке АЗС.
Среднее число автомобилей в очереди
го = 2,58 « 3 автомобиля
t<> = 2,58лшн
Среднее число автомобилей в системе и среднее время в системе
^сист. ~~ ’ ^сист. ~ 4,5jWWW.
41
Анализ результатов расчета показывает, что 64 % заявок, попавших в
систему, будут обслужены достаточно быстро {tCUCfnt < 5 мин), но большой
процент автомобилей получает отказ.
3. Заметим, что АЗС не удовлетворяет поставленному в этом пункте ус-
ловию, т.к. отказ получает 36 % автомобилей. Для решения этой задачи
можно либо увеличить число колонок, либо уменьшить to6cjt (улучшение
технологии обслуживания). Возможно, что увеличение числа мест в очереди
(т) также снизит ротк Пусть Л = laew/w;H, 7^.= 3 мин, п = 2, а т меняется,
тогда получим зависимость, представленную в таблице 2.8.1.
Таблица 2.8.1
Увеличение мест в очереди слабо влияет на вероятность отказа.
Пусть теперь Я = 1; to6cn = 3 мин, т - 4, а п меняется.
Таблица 2.8.2
п 2 3 4 5
Ротк. 0,36 0,13 0,046 0,002
Следовательно, увеличение числа работающих каналов до п ~ 4 решает по-
ставленную задачу.
4. Результаты имитационного моделирования сведены в таблицу 2.8.3.
Здесь время моделирования Тт выбрано в единицах характерного времени
входного потока te n = у \ .
Таблица 2.8.3
Ли 10 50 100 200 400 600 1000 точные значения
А 0,4 0,52 0,58 0,65 0,67 0,65 0,64 0,64
^отк. 0,69 0,23 0,44 0,28 0,37 0,34 0,37 0,36
Из таблицы очевидно, что при малых Тт отклонения параметров от
точных значений велики и испытывают сильные колебания. При увеличении
Тт параметры А и Ротк приближаются (сходятся по вероятности) к точным
значениям в соответствии с предельными теоремами теории вероятностей.
42
3. Анализ эффективности работы СМО
по стоимостным показателям
Стоимостные модели массового обслуживания направлены на опреде-
ление такого уровня работы обслуживающей системы, при котором достига-
ется компромисс между следующими двумя экономическими показателями:
1) прибылью, получаемой за счет предоставления услуг;
2) потерями прибыли, обусловленными задержками в предоставле-
нии услуг.
Легко предположить, что увеличение функциональной мощности об-
служивающей системы должно приводить к сокращению времени пребыва-
ния заявок в очереди. Это означает, что по мере того как затраты, связанные
с обслуживанием, возрастают из-за повышения уровня обслуживания, выра-
женные в стоимостных показателях потери, связанные с ожиданием, должны
уменьшаться.
Оптимальным уровнем обслуживания будет тот показатель, при кото-
л ром сумма обоих показателей будет наименьшей.
3.1. Оптимальная скорость обслуживания
в одноканальной СМО
Рассмотрим одноканальную СМО с неограниченной очередью, л - ин-
тенсивность входного потока заявок, А - интенсивность выходного потока,
или скорость обслуживания.
Допустим, что скорость обслуживания поддается регулированию. Тре-
буется определить ее оптимальные значения на основе некоторой стоимост-
ной модели.
Обозначим через q затраты на увеличение // на единицу за единицу
времени, выраженные в стоимостной форме; - цена ожидания в единицу
времени..,и в расчете на одну заявку (т.е. обусловленные вынужденным ожи-
данием экономические потери).
Представим стоимостный показатель в виде суммы:
,. _ р я
Известно, что z т = —-— =------,
Получили функцию от одной переменной, найдем.ее оптимальное зна-
чение:
с'(д) = С] - с2 • ---J = 0 => цопт = Л + • л .
(?-лу уч
Пример 3J;1. Найдем оптимальную скорость обслуживания для одно-
канальной СМО в примере 2.6. Г: Л ~ 2 состава в час, средняя скорость рас-
формирования состава // поддается регулированию. Найти ее оптимальное
значение, если известно, что выигрыш за счет увеличения скорости обеду*
живания на единицу с. = 50 усл. ед., а цена ожидания расформирования ол-
ним составом в течение часа с2 ~ ЮОусл. ед.
'□гласно критерию, оптимальная скорость будет
Иопт
100 ч о о л
• 2 — 2 4- 2 = 4 состава в час.
V 50
Тогда t0^CJl = 0,25 ч (у нас 0,4 ч).
Пусть длина очереди будет ограничена. Тогда стоимостную модель
можно изменить так, чтобы за счет увеличения числа т заявок в очереди
уменьшить число заявок, которые СМО может потерять. В данном случае т
можно рассматривать как управляющую переменную, оптимальное значение
которой вместе с р определяется путем минимизаций функции двух пере-
менных:
I
с(/2, т) = q/z + c2zcucm + с3т + c4^?N,
где Cj,c2 имеют прежний смысл, а с3- стоимость увеличения числа мест,
с 4 — экономические потери из-за потери клиента, Л • - число клиентов,
потерянных в единицу времени.
3.2. Определение оптимального числа
обслуживающих каналов
Рассмотрим многоканальную СМО с неограниченной очередью, п -
число каналов может изменяться; Л и р фиксированы. *
1. Выберем стоимостный показатель в виде:
е(л) = С] n + c2-z^cm(n)
где Ci -затраты на работу одного дополнительного канала в единицу вре-
мени,
С2 ~ цена ожидания в единицу времени в расчете на одно требование.
Число каналов увеличиваем на единицу и вычисляем с(л). Оптималь-
ное число каналов соответствует наименьшему значению с(п).
44
Пример 3.2.1. На складе запасных частей производится замена вы-
шедших из строя механических узлов новыми. Заявки на замену поступают с
интенсивностью Л* = 17,5 заявок в час; средняя скорость обслуживания
// = 10 заявок в час. Затраты, связанные с добавлением к штату обслужи-
вающих одного человека, оцениваются в 60 усл. ед. в час. Производственные
потери из-за простоя станка в период замены тех или иных вышедших из
строя узлов составляют 300 усл. ед. в час. Сколько человек должно быть в
штате обслуживающего персонала на складе запасных частей?
с{п) - 60-п + 300- z(n)
* г
При п = 1 СМО не работает (р > 1).
с(2) = 60•2 + 300 7,467 = 2360,1
с(3 j - 60 - 3 + 300 • 2,217 = 845,1
с(4) - 60 • 4 + 300 • 1,842 = 792,6
с(5) = 60-5+ 300-1,769 = 830,7
^систУ1} вычисляется на компьютере для каждого значения п при фик-
сированных Ли//.
Заметим, что наименьшее значение стоимостной функции
с(п) = 792,6>>сл. ед. достигается при п = 4. Оптимальное число работников на
складе запасных частей четыре.
2. Выберем стоимостный показатель в виде:
c(rt) = c, •п + с2гДи) + с3Гот.(л),
где q - затраты на работу одного дополнительного канала, отнесенные к
единице времени,
с2 - цена ожидания одной заявки в единицу времени,
с3 - стоимостные потери от простоя одного канала в единицу времени.
При расчете с(п) увеличиваем п на единицу, а го и ксв вычисляем для
каждого п. Оптимальным п будет то, которое соответствует наименьшему
с(и).
3. Выберем стоимостный показатель в виде
с{п) = с\ i^n) + с2 t2{n),
где q - стоимостные потери из-за простоя клиента в течение одного часа,
— среднее время простоя одного клиента в СМО,
с2 - стоимость одного часа простоя канала СМО,
среднее время простоя канала.
Пример 3.2.2. Рассмотрим работу склада с инструментом.
Выдают инструмент п кладовщиков. Рабочие приходят на склад в сред-
нем с интенсивностью Л = 1,6 рабочих в минуту. (Информация получена с
45
помощью статистической обработки наблюдений за работой склада.) Время
обслуживания одного рабочего кладовщиком t0QCJl = 1J рабочих в минуту.
Пусть q - себестоимость, одного часа рабочего. Она оценена в 6 ус л.
ед., а себестоимость одного часа кладовщика в 3 усл. ед. Сколько должно ра*
ботать на складе кладовщиков, чтобы стоимость общего простоя приводила
бы к минимальным затратам? Сделаем предварительный расчет потери ра-
бочего времени рабочими и кладовщиками за смену (8 часов). Заметим, что
стационарный режим СМО существует только при п > 2 , т.к. р = 1,77 > 1.
В течение рабочего дня на склад приходят
N = Л»60 • 8 = 768 чел.
N рабочих:
Подсчитаем потери времени рабочего :
п = 2, t0 = 4mwh ,
п = 3, То = 0,3 \мин,
п — 4, То = 0,06лшн,
t(2) =------= 51,2 часа,
60
768-0,31 _
ZG) ------------ 3 96 часа,
60
768-0,06 л«,
j(4) =-----1— = 0,76часа.
60
Вычислим общее время обслуживания 768 рабочих кладовщиками:
to6cjl ‘768 = 853мин =14,21 часа. Ежедневная продолжительность простоя
кладовщиков:
п - 2; 2-8 часов - 14,21 часа =1,79 часа,
и “ 3; з . 8 часов - 14,21 часа = 9,79 часа,
и = 4; 4.8 часов - 14,21 часа = 17,79 часа.
Теперь вычислим общую стоимость потерь времени:
с(2) = 6-51,2 + 3-1,79 = 312,57усл.ед.,
с(3) = 6- 3,96+3-9,79 = 53,13усл.ед.,
с(4) = 6 • 0,76 + 3> 17,79 = 57,93усл.ед,
с(5)^ 75,37усл.ед.
Таким образом, лучше всего, чтобы на складе работало три кладовщика.
Впрочем, не следует абсолютизировать результаты расчета, ибо жизнь слож-
нее нашей схемы. Например, управляющий нашим производством решил,
что лучше взять четырех кладовщиков. Если взять еще одного кладовщика,
то это потребует дополнительно 4,8 усл.ед. С другой стороны, известно, что
отсутствие служащих на своем рабочем месте занимает 8 % рабочего време-
ни.
Поэтому при трех кладовщиках потери составят 20,75 усл.ед., что почти
в 5 раз превышает затраты на одного лишнего кладовщика.
4. Индивидуальные задания
Варианты № 1 и № 16
В приемно-отправочный парк станции поступает простейший поток по-
ездов со средней интенсивностью 2 составов в час.
Одна бригада осмотрщиков обрабатывает состав со средней продолжи-
тельностью обсл ). Время обработки распределено по показательному
закону. Очередь не ограничена.
Исходные данные приведены в таблице 4.1.
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний для стационарного случая и показатели
эффективности работы бригады осмотрщиков. Оценить эффективность рабо-
ты бригады.
3. Найти функциональную зависимость длины очереди от времени об-
служивания го ~ Ф^обсл}* от интенсивности 2, го = ^>(2). Зависимость
представить в виде таблиц и графиков.
4. Проверить, выгодно ли ограничить очередь (т = 6).
5. Пусть скорость осмотра поддается регулированию. Найти Цопт, если
затраты на увеличение скорости обслуживания на единицу за час составля-
ют Cj = 50 усл. ед., цена ожидания осмотра одним составом в течение часа
С2 = У00усл.ед.
6. Известно, что в летние месяцы интенсивность потока составов воз-
растает вдвое, время осмотра также возрастает в 1,5 раза за счет увеличения
длины состава. Определить необходимое число бригад для формальной ра-
боты станции.
Варианты № 2 и № 17
*
На сортировочной станции работают две сортировочные горки. На рас-
формирование прибывает простейший поток составов с интенсивностью 2
составов в сутки. Горочный технологический интервал составляет
Время подчинено показательному закону. Очередь не ограни-
чена. Исходные данные приведены в таблице 4.2.
47
о
t
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и по-
казатель эффективности работы сортировочной станции. Определить про-
цент составов, идущих сразу в обработку.
3. Найти функциональную зависимость длины очереди от интенсивно-
сти потока го = и от времени обслуживания r0 = (p(to^CJl). Предста-
вить зависимость в виде таблиц и графиков.
4. Найти величину среднесуточного штрафа за пребывание составов в
очереди на внешних путях, если известно, что в парке сортировочной стан-
ции могут находиться одновременно не более трех составов. За один час
пребывания на внешних путях станция платит штраф 100 у с л. ед.
5. В результате неполадок в горочном механизме время обслуживания
на станции увеличилось в 1,5 раза. Как распределить поток составов между
горками? Провести соответствующие расчеты.
6. На соседней станции проведена реконструкция, и она может обрабо-
1 " ' ' '
тать дополнительно — часть составов нашей сортировочной станции. Можно
4
ли в этом случае начать профилактический ремонт одного горочного меха-
низма?
Варианты № 3 и № 18
На контейнерную площадку с двумя кранами прибывает простейший
поток автомашин с интенсивностью Л автомашин в час. Время погрузки-
выгрузки показательное, составляет в среднем 1мин(1обсл ). Очередь не ог-
раничена. Исходные данные - в таблице 4.3.
Таблица 4.3
г
1
i
1
J
i
j
№ гр. 1 2 3 4 5 1 2 3 4 5
А 12 14 ' 16 18 ' 20 ' 13 22 21 19 17
t 7 6 5 5 4 6 4 5 5 6
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и по-
казатели эффективности работы контейнерной площадки. Проанализировать
эти показатели, оценить работы контейнерной площадки .
48
3. Найти зависимость средней длины очереди от интенсивности вход-
ного потока го и от среднего времени обслуживания гй = ф^обсл)*
Представить зависимость в виде таблиц и графиков.
4. Один из кранов требует профилактического ремонта. Как будет рабо-
тать контейнерная площадка с одним краном? Какую часть потока автома-
шин она сможет обслужить? с
5. В летние месяцы интенсивность потока машин увеличивается вдвое.
Определить оптимальное’ число кранов, необходимое для нормальной рабо-
ты площадки. Использовать для расчетов критериальную функцию.
с(и) = С] • п + с2 • г0 + с3 • ксв ,
где С] = 300усл. ед. - затраты на работу одного дополнительного крана, от-
несенные к единице времени;
с2 = 100усл.ед. - потери от ожидания в очереди автомашины (в ед.
времени);
с$ - 25усл.ед. составляют потери от простоя крана (в ед. времени).
6. Выгодно ли ограничить очередь (т = 5 автомашин)? Ответ подтвер-
дить расчетами.
Варианты № 4 и № 19
» * О’*
На железнодорожной станции имеется п кассовых аппаратов. Поток
пассажиров, желающих приобрести билеты, простейший с интенсивностью
Я пассажиров в минуту. Время обслуживания распределено по показатель-
ному закону, среднее время обслуживания составляет t сек. Очередь не ог-
раничена. Исходные данные приведены в таблице 4.4.
блица 4.4
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и по-
казатели эффективности работы железнодорожных ка’сс. Вычислить вероят-
ность того, что пассажир сразу будет обслужен. Оценить работу касс.
3. Найти зависимость средней длины очереди от интенсивности входно-
го потока и от времени обслуживания г0 и г» =<p(to6cjf ). Предста-
вить зависимость в виде таблиц и графиков.
4. Найти оптимальное число кассовых аппаратов, при котором функция
с(п) ~ q • п + с2 • ^сист. (") будет иметь наименьшее значение.
49
I
Известно, что С\ = 500усл. ед.- затраты на работу дополнительного ап-
парата (к ед. времени);
с2 =100- цена ожидания обслуживания одним пассажиром (к ед. вре-
мени).
5. В летнее время интенсивность потока пассажиров увеличивается в 1,5
раза. Проанализировать работу касс в этом случае. Внести предложения от-
носительно улучшения работы касс. •
Варианты № 5 и № 20
О
Билетная касса обслуживается п кассирами. Поток пассажиров про-
стейший с интенсивностью Я пассажиров в час. Время обслуживания рас-
пределено по показательному закону, среднее время обслуживания одного
пассажира составляет Исходные данные приведены в таблице
4.5.
Таблица 4.5
№гр. 1 2 3 4 5 1 1 2 3 4 5
Я 16 18 21 30 18 30 24 23 20 25
12 15 6 7 8 7 7 6
п 4 .4 5 3 5 _и 4 4 3 4
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы билетной кассы. Проанализировать результа-
ты и оценить ее работу. Найти процент пассажиров, обслуженных без очере-
ди.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока г0 = ^>(Я) и от времени обслуживания
* = <P<f оба)
Представить зависимость в виде таблиц и графиков.
4. Один из кассиров заболел. Проверить расчетом, будет ли работать
касса, и оценить ее работу.
5. В связи с юбилеем города поток пассажиров увеличился вдвое. Найти
оптимальное число кассиров для этого времени, если известно, что затраты
на работу еще одного кассира составляют cj =200 усл.ед. в час, а цена ожи-
дания пассажира С2 =100 усл.ед. в час. Стоимостный показатель
с(п) = С] • п + с2 • 2^^ (п) должен быть минимальным.
6. В кассе продают билеты на п равнозначных направлений. Проверить,
будет ли лучше работать касса, если все кассы специализировать: каждый
50
кассир продает билеты только в одно направление» в этом случае интенсив-
ность1 потока пассажиров Л\ = —, время обслуживания то же.
п
Варианты № 6 и № 21
В депо железнодорожной станции на экипировку поступает простейший
поток электровозов с интенсивностью Л электровозов в час. Время экипи-
ровки показательное, среднее время обслуживания 1мин(1оба1). Депо имеет п
экипировочных мест. Очередь не ограничена. Исходные данные - в таблице
4.6.
Таблица 4.6
№гр. 1 2 3 4 5 1 1 2 3 4 5
Л 4 5 3 5 3 4 3 4 г 5 , 4
t 30 25 15 22 25 1 20 18. 20 23 20
п 3 4 1 3 3 2 2 2 3 3
1. Описать состояния системы и построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы депо, проанализировать эти показатели, дать
оценку работы депо.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности потока электровозов г0 » (р{Л) и от среднего времени обслужи-
вания r0 = <p(J0^CJl). Представить зависимость в виде таблиц и графиков.
4. Планируется ликвидация некоторых депо - в этом случае в нашем де-
по будет проходить экипировку большее число электровозов (Л] =? 2Л).
Найти, оптимальное число экипировочных мест в- депо, если известно,
что с-[ = 50 усл. ед.- себестоимость одного часа работы электровоза;
С2 =? 10усл.ед.- себестоимость одного часа работы экипировочного места.
Стоимостный показатель с(п) = с^ • (и) + С2 ’ ^2 (и) •
5. Проверить, будет ли выгодно ограничить очередь т = 5. Интенсив-
ность для расчета взять такой же, как в пункте 4.
Вариант № 7 и № 22
*
I
СМО представляет собой автозаправочную станцию (АЗС) с п колонка-
ми. Площадка возле АЗС позволяет ожидание в очереди не более т автома-
шин. Если вся площадка занята, то следующий автомобиль не обслуживает-
ся. Поток автомашин на заправку простейший, с интенсивностью
J*
51
о
I1
Л автомашин в минуту. Время заправки показательное со средним значением
) • Исходные данные приведены в таблице 4.7.
Таблица 4.7
№гр. 1 2 | 3 4 5 { 1 2 3 4 5
1,0 2,0 1,5 3,0 1,5 2,0 1,5 I 1 2
t 3 2 4 3 3 4 4 4 3 3
п 3 4 5 7 4 9 5 3 3 5
т 4 5 5 4 4 1 '4 5 5 4 5
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы СМО, проанализировать их, оценить работу
АЗС.
3. Найти зависимости средней длины очереди от интенсивности входя-
щего потока го = 0>(Л) и от времени обслуживания ro — Предста-
вить зависимость в виде таблиц и графиков.
4. В условиях конкуренции нужно, чтобы отказ от обслуживания полу-
чили не более двух автомашин, нуждавшихся в заправке. Проверить, удовле-
творяет ли АЗС этому условию. Если нет, то найти число колонок, при кото-
ром это условие будет выполняться.
5. В связи с тем, что закрылись ближайшие АЗС, очередь стала неогра-
ниченной. Найти новые показатели работы АЗС. Продумать и просчитать
предложения по совершенствованию работы СМО.
6. Найти оптимальное число колонок АЗС для данных пункта 5. Исполь-
зовать стоимостную функцию
с( п) = Cj • п + с2 • Го + с3 • ксв
Она должна иметь наименьшее значение.
Известно, что С\ = ЮОусл.еЭ.- стоимость установки одной колонки (к
ед. времени); с2 50усл. ед. - цена ожидания заправки одной автомашиной
в течение одного часа; = 15уел. ед. - стоимость потерь от простоя одной
колонки в течение одного часа.
Варианты № 8 и № 23
На заводе выпускается продукция малыми партиями. Каждый рабочий
день рабочие берут инструменты на складе. Выдают инструменты п кладов-
щиков. Поток рабочих на склад простейший с интенсивностью Я рабочих в
минуту.
Время обслуживания показательное, среднее время выдачи инструмента
. Очередь не ограничена.
Исходные данные приведены в таблице 4.8.
52
Таблица 4.8
№гр. 1 2 3 4 5 1 2 3 4 5
Я 2,0 1,5 3,0 5,0 1,6 1,3 2,3 3,1 2,5.. 1,8'
t 1,5 2,6 2,0 1,2 ъо 1,3 1,1 1,2 2,0 1,5
п * 0 4 <* . 5 1 7 8 3 3.: 3 с 5 6 4
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы СМО, проанализировать их и оценить работу
склада.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока г0-(р{К) и от времени обслуживания
г- = <Р(‘обсл.) • Представить зависимость в виде таблиц и графиков.
4, На завод поступил срочный заказ. Интенсивность потока рабочих
увеличилась в: 1,3 раза. Сколько необходимо взять кладовщиков дополни-
тельно, чтобы рабочие не простаивали долго у склада?
5. Определить оптимальное число кладовщиков, чтобы время, потерян-
ное рабочими за рабочий день, и простой кладовщиков приводило к мини-
мальным потерям. Рассмотреть функцию е(и) = С] •?1(л) + С2 *^2(л)» если
Cj = ед — себестоимость одного рабочего часа, а себестоимость одного
рабочего часа кладовщика оценена с 2 40усл.ед. (см. пример на стр. 43).
Варианты № 9 и № 24
«г « «
? И *
На пункт очистки и подготовки порожняка прибывает простейший по-
ток составов с интенсивностью Я составов в час. Время очистки состава по-
.. 1- 1Г
казательное сб средним значением .Пункт очистки имеет п мест очи-
I
стки. Очередь не ограничена. Исходные данные приведены в таблице 4.9.
Таблица 4.9
№гр. 1 2 3 4 5 [ 1 2 3 4 '. 5"
л 1.0 2.0 2.5 3.0 1.8 I 2.6 3.0 2.5 1.6 3.1
t 1.5 1.1 1.0 1.5 0.9 | 1.2 1.1 2.0 1.8 ' JI 1.5
п 2 3 4 .6 3 4 4 6 4 6
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний jCMO для стационарного случай и по-
казатели Эффективности работы СМО. Проанализировать их, оценить работу
пункта очистки.
J
3. Найти функциональную зависимость средней длины очереди
г0 = 0>(Л)и от среднего времени очистки состава г- = <p(t06ai.) •
L
4. Проверить, выгодно ли ограничить очередь до т = 5. Ответ подтвер-
дить расчетом.
5. Определить оптимальное число мест очистки порожняка, используя
стоимостную функцию:
с(л) = q п + с2 • Го + с3 • ксе
У
Известно, что организация нового места очистки требует
q = 100усл.ед. (к единице времени) , потери от ожидания очистки одним
составом в течение 1 часа составляют с2 = 150 усл. ед.; потери от простоя
канала в течение одного часа = 50усл.ед. Функция должна иметь наи-
меньшее значение.
6. В летние месяцы интенсивность потока составов увеличивается в 1.5
раза. Вычислить показатели эффективности работы СМО в этом случае, оце-
нить их, предложить способы улучшения, если оценка будет неудовлетвори-
тельной.
Варианты № 10 и № 25
На прирельсовый склад общего пользования поступает простейший по-
ток грузов с интенсивностью Л партий в минуту. Формирование партий гру-
зов производится с помощью п погрузчиков. Очередь ограничена, число мест
в очереди т. Время обслуживания показательное со средним значением
1мин(1обсл ). Исходные данные приведены в таблице 4.10.
Таблица 4.10
№гр. 1 2 3 4 5 и 1 1 1 2 3 2 3 4 5
я 3.0 4.0 2.0 2.5 1.8" 2.3 3.1 1.9 2.6 4,3
t 1.0 0.9 1.3 1.2 1.5 1.1 1.0 1.4 1.3 0.9
п 5 5 4 4 4 4 4 5 5 4
т 5 5 4 . 4 4 1 5 5 4 4 5
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы склада, проанализировать их, оценить работу
склада.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока г0 = (р(Х) и от среднего времени обслужива- ,
ния г» = <р(?обсл). Представить зависимости в виде таблиц и графиков.
54 .
4
4. В связи с реорганизацией прирельсового склада выделены средства >
для приобретения автопогрузчиков. Сколько должно работать автопогрузчи-
ков, чтобы отказ получили не. более 5% грузов?
6. Пусть очередь будет не ограничена. Найти оптимальное число авто-
погрузчиков, чтобы стоимостная функция с(и) имела наименьшее значение:
с(п) = с} п + с2 -г0 + с3 -ксв
Известно, что q = 200усл, ед, - стоимость одного часа работы допол-
нительного автопогрузчика; с 2 = 100усл. ед, ** стоимость одного часа ожи-
дания формирования одной партии груза, с$ 50усл. ед. -стоимость одного
часа потери от простоя одного автопогрузчика.
Варианты № 11 и № 26
Л
На грузовой станции работают одни стационарные весы ( п =1). На гру-
зовую станцию поступает простейший поток машин для взвешивания перед
погрузкой-выгрузкой. Интенсивность потока - Л машин в час. Очередь не
ограничена. Время взвешивания показательное со средним Ис-
ходные данные приведены в таблице 4.11.
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы СМО. Проанализировать полученные резуль-
таты, оценить работу весовой на грузовой станции.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока го=<р(Л) и от времени обслуживания
г. = <р(1обсл). Представить зависимость в виде таблиц и графиков.
4. Как изменятся Показатели эффективности работы СМО, если очередь
ограничить (т = 5)? Проанализировать работу весовой в этом случае.
5. Пусть скорость обслуживания машин поддается регулированию. Тре-
буется определить оптимальную скорость обслуживания машин на основе
стоимостного показателя (см. стр. 42)
С(А) = С1 -^ + С'2 -1 2 3 4 5сист.
Известно, что q = 25 усл; ед. - стоимость, представляющая затраты на
увеличение скорости обслуживания одной машины в ед. времени,
с2 ^100 усл. ед. - цена ожидания одной машиной взвешивания в течение
одного часа.
6. В летние месяцы интенсивность потока машин возрастает вдвое.
Сколько нужно весов, чтобы весовая работала нормально?
о
I
Варианты № 12 и № 27
Парикмахерская на вокзале имеет п мастеров в одну смену. Поток кли-
ентов простейший с интенсивностью Л клиентов в час. Очередь ограничена
т = 4 места. Время обслуживания показательное со средним временем
tMun(to6ai). Исходные данные приведены в таблице 4.12.
Таблица 4.12
№гр. 1 2 3 4 - 5 1 1 2 3 4 _5_
А, 12 14 16 е 10 8 12 10 И 15 9
t 10 11 12 11 12 . 13 L1 12 10 10
п 3 3 4 3 2 : 4 3 4 4 2
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы парикмахерской. Проанализировать получен-
ные показатели, оценить работу парикмахерской.
3. Найти функциональную зависимость числа клиентов в очереди от ин-
тенсивности входного потока го = (р{Х) и от времени обслуживания
Я = (р(^обся ). Представить зависимость в виде таблиц и графиков.
4. Будет ли работать парикмахерская в стационарном режиме, если оче-
редь будет неограниченной? Найти оптимальное число мастеров в смену,
используя стоимостную функцию вида
с(п) = Cl п + с2 Zcucm ,
если известно, что q = 50усл.ед. - затраты на работу одного дополнитель-
О1
ного мастера в час, = ЗОусл.ед. - цена ожидания клиентом обслуживания
в течение часа.
5. Интенсивность входного потока возросла в 1.5 раза, очередь стала не-
ограниченной. Найти оптимальное число мастеров в этом случае, используя
ту же функцию.
Варианты № 13 и № 28
На вокзале железнодорожной станции работает камера хранения ручной
клади. Поток пассажиров, желающих сдать или забрать багаж из камеры
56
4
хранения, простейший с интенсивностью 2 пассажиров в час. Обслуживают
пассажиров п кладовщиков. Время обслуживания показательное со средним
значением 1мин(1обсл ). Очередь не ограничена. Исходные данные приведены
в таблице 4.13.
Таблица 4.13
№гр. 1 1 '2 3 1 4 5 | 1 1 2 3 4 5
X 15 13 14 16 17 20 15 12 19 21
t *. ' 7 6 7 10 5 10 5 9 8 8
п 2 2- 2 4 3 4 2 3 4 4
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая, пока-
затели эффективности работы камеры хранения. Проанализировать результа-
ты и оценить работу камеры хранения.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока го = и от времени обслуживания
Я = <p(to6cjj ). Представить зависимость в виде таблиц и графиков.
4. Найти оптимальное число кладовщиков камеры хранения, используя
для этого стоимостную функцию:
которая должна принять наименьшее значение. Известно, что
q = 100jcw.ed. - стоимость одного часа работы дополнительного кладов-
щика, С2 = 50 усл. ед. - цена ожидания пассажиром в течение одного часа,
С3 = 25усл. ед. - стоимость потерь от простоя одного кладовщика в течение
одного часа.
5. В летнее время года интенсивность потока пассажиров увеличивается
вдвое. Найти число кладовщиков, при котором камера хранения будет обес-
печивать обслуживанием поток пассажиров.
6. Один из кладовщиков не вышел на работу. Определить скорость об-
служивания камеры хранения остальными кладовщиками (2 рассмотреть из
исходных данных).
Варианты № 14 и № 29
Ателье по ремонту телеаппаратуры имеет п опытных мастеров одной
квалификации. В среднем в течение часа от населения поступает в ремонт 2
аппаратов в час. Входной поток заявок простейший. Среднее время ремонта
одного аппарата одним мастером t час . Время обслуживания пока-
зательное. Очередь не ограничена. Исходные данные приведены в таблице
4.14.
о
57
Таблица 4.14
1. Описать состояния системы, построить граф состояний.
2. Найти вероятности состояний СМО для стационарного случая и пока-
затели эффективности работы ателье, проанализировать результаты расче-
тов, оценить работу ателье.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потрка . г0 ~ (р{ Л) и от времени обслуживания
Я y(to6cji). Представить зависимость в виде таблиц и графиков,
4. Вычислить процент аппаратов, отремонтированных без очереди, а
также вероятность того, что все мастера будут заняты в тот момент., когда
придет следующая заявка. г
5. Найти оптимальное число мастеров в ателье, используя стоимостную
функцию: .
Известно, что Cj = 500усл, ед, ~ стоимость дополнительного мастера в
ателье, су ~ 50 усл.ед. - потери от простоя аппарата в ожидании ремонта,
с у ~ ЮОусл.ед. - потери от простоя одного мастера,
6. Если интенсивность потока аппаратов, отданных в ремонт, увеличит-
ся в1.5 раза, сколько мастеров потребуется ателье на это время?
Варианты № 15 и № 30
Центральный вычислительный комплекс локальной компьютерной сети
имеет п процессоров и может одновременно обрабатывать п расчетных про-
грамм; Другие поступающие с терминалов пользователей программы могут
храниться в памяти и выполняться по мере освобождения процессоров.
Среднее число заявок, которые одновременно находятся в памяти, равно т.
Входной поток заявок простейший с интенсивностью Л заявок в минуту.
Время обработки программы случайное, распределено по показательному
закону со средним значением tceK ^0^сл ). Исходные данные приведены в
таблице 4.15.
о
58
Таблица 4.15
*
1. Описать состояния СМО, построить граф состояний.
2. Найти вероятности состояний для стационарного случая и показатели
эффективности работы комплекса. Проанализировать полученные результа-
ты. Оценить работу комплекса.
3. Найти функциональную зависимость средней длины очереди от ин-
тенсивности входного потока го = (р(к) и от среднего времени обслужива-
ния r0 = (p(to6cji ). Зависимость представить в виде таблиц и графиков.
4. Один из процессоров не работает. Как организовать работу комплек-
са, чтобы не получить больших сбоев?
5. Найти оптимальное число процессоров, используя стоимостную
функцию:
с(л) = с2 ' ^сист. + £) * л •
Известно, что Cj = 50 усл. ед. - затраты на введение в работу одного
процессора, отнесенные к ед. времени; С2 - 280усл.ед. - стоимость произ-
водственных потерь от задержки выполнения программы в течение той же
единицы времени.
6. Выполнение срочного заказа увеличило интенсивность входного по-
тока в 2 раза. Сколько процессоров нужно задействовать в комплексе, чтобы
. вероятность отказа возросла не более, чем в 1.5 раза?
Л
59
1
ЛИТЕРАТУРА
" - * •
1 .f. *
1. Вентцель, Е.С. Исследование операций (задачи, принципы, ме-
тодология).- М.: Наука, 1988.
2. Кац, И.Я., Скачков, П.ГГ, Толмачева, М.А. Математические модели
массового обслуживания программно-методический комплекс. - Екатерин-
бург: Изд-во УрГАПС, 1999.
3. Кац, И.Я. Элементы теории массового обслуживания. - Свердловск:
Изд-во У ЭМИИТа, 1981.
4. Кофман, А., Фор, Р. Займемся исследованием операций.- М.: Мир,
1981.
5. Скачков, П.П., Толмачева, М.А. Теория массового обслуживания в за-
дачах эксплуатации железных дорог. - Свердловск: Изд-во УЭМИИТ, 1988.
6. Таха, X. Введение в исследование операций. - М.: Мир, 1985.
62
Содержание
>
1. Основные понятия теории марковских цепей
1.1. Марковские цепи с дискретным временем и конечным
числом состояний............................................3
1.2. Однородные марковские цепи с непрерывным временем.......9
1.3. Процесс гибели и размножения.................... —.....15
1.4. Задачи.................................................16
1.5. Варианты индивидуальных заданий........................17
2. Системы массового обслуживания
2.1. Основные понятия и классификация систем
массового обслуживания.......................................21
2.2. Простейший поток и его свойства........................22
2.3. Марковские системы массового обслуживания............. 24
2.4. Показатели эффективности систем массового обслуживания..24
2.5. Многоканальная СМО с отказами (задача Эрланга)..........25 *
2.6. Одноканальная СМО с неограниченной очередью.............31
2.7. Многоканальная СМО с неограниченной очередью............35
2.8. Многоканальная СМО с ограниченным числом мест в очереди.38
3. Анализ эффективности работы СМО по стоимостным показателям
I
№
3.1 .Оптимальная стоимость обслуживания в одноканальной СМ...43
3.2 . Определение оптимального числа обслуживающих каналов...44
4. Индивидуальные задании....................................46
5. Программное обеспечение
5.1. Инструкция по использованию программы «Системы
массового обслуживания»......................................60
5.2. Инструкция по использованию программы «Марковские цепи».60
Литература................................................ 62