Механики
 Скачать 4.29 Mb.
|
|
E k , причем N k < , то произойдет переход в состояние E k+1 (начнется обслуживание поступившей заявки в одном из свободных приборов), причем интенсивность перехода равна интенсивности поступления λ ; • если же случайный процесс находится в состоянии E N (все приборы заняты обслуживанием заявок), то состояние E N случайного процесса не изменится, что будет соответствовать отказу в обслуживании поступившей заявке. Таким образом, переход из состояний E k в состояние E k+1 (при N k < ) происходит с интенсивностью λ 2. Завершение обслуживания заявки в одном из приборов с интенсивностью µ Это событие может наступить только в том случае, если в системе на обслуживании находится хотя бы одна заявка, то есть случайный процесс находится в состояниях E 1 , E 2 , …, E N ,. При этом случайный процесс переходит соответственно в состояния E 0 , E 1 , …, E N-1 , причём интенсив- ности перехода различны. Действительно, если в системе обслуживается только одна заявка (состояние E 1 ), то интенсивность перехода в состояние E 0 равна µ . Если же в системе обслуживается две заявки (состояние E 2 ), то есть работают два прибора, то переход случайного процесса в состояние E 1 возможен либо в результате завершения обслуживания заявки в первом приборе с интенсивностью µ , либо в результате завершения обслуживания заявки во втором приборе с такой же интенсивностью µ , причём вероят- ность завершения обслуживания заявок в обоих приборах в один и тот же момент времени равна нулю. Таким образом, интенсивность перехода из состояния E 2 в состояние E 1 будет равна µ 2 (как сумма интенсивностей двух рассмотренных способов). В общем случае, если в многоканальной системе на обслуживании находится N k ,..., 2 , 1 = заявок (случайный процесс находится в состоянии λ E 0 E 1 µ E 2 E k E N … … λ λ λ λ λ µ 2 µ 3 µ k µ ) 1 ( + k µ N Рис . 5.7. Граф переходов марковского процесса 198 Раздел 5. Численное моделирование E k ), то интенсивность перехода в состояние E k-1 будет равна µ k . По аналогии с предыдущим примером (п.5.4.1) здесь и в последую- щих примерах можно показать, что случайный процесс, протекающий в системе, при сформулированных предположениях является марковским. 5. Матрица интенсивностей переходов . Графу переходов (рис.5.7) соответствует матрица интенсивностей переходов: µ µ λ µ λ µ λ µ λ µ λ µ λ λ N N N N N N N i − − + − − + − + − − − = 0 0 0 ) ) 1 ( ( 0 0 0 1 0 0 ) 2 ( 2 0 2 0 0 ) ( 1 0 0 0 0 1 2 1 0 E G Диагональные элементы матрицы определяются из условия (5.4) – сумма элементов каждой строки должна быть равна нулю. 6. Система уравнений . Система уравнений для определения стационарных вероятностей имеет вид: = + + + = + + = + + = + = − + − 1 ) 1 ( ) ( 2 ) ( 1 0 1 1 1 2 0 1 1 0 N N N k k k p p p p p N p k p p k p p p p p λ µ µ λ µ λ µ λ µ λ µ λ Используя метод математической индукции можно показать, что: ) , 0 ( ! 0 N k p k y p k k = = , где b y λ = – нагрузка системы. Подставляя полученное выражение в последнее уравнение системы линейных алгебраических уравнений, найдем вероятность простоя системы: ∑ = = N i i i y p 0 0 ! 1 Тогда стационарные вероятности состояний марковского случайного процесса, протекающего в многоканальной СМО с отказами: Раздел 5. Численное моделирование 199 ) , 0 ( ! ! 0 N k i y k y p N i i k k = = ∑ = Из последнего выражения при 1 = N , как частный случай , вытекает результат , полученный в предыдущем примере для одноканальной СМО с отказами Задание на самостоятельную работу: проверить полученные выражения, используя метод математической индукции. 7. Расчет характеристик СМО . Для расчета характеристик СМО можно воспользоваться следующи - ми математическими зависимостями : 1) нагрузка : b y λ µ λ = = / ( по определению ); 2) загрузка : ∑ = = N k k kp N 0 1 ρ , учитывающая долю N k работающих приборов ; действительно , система загружена полностью , когда работают все приборы , если же из 10 приборов работает один , то система загружена на 10%, если работают 5 приборов , то система загружена на 50%; 3) коэффициент простоя системы : ρ η − = − = ∑ = 1 ) ( 1 0 N k k p k N N ; 4) среднее число заявок в системе , равное среднему числу работающих приборов : ρ N kp m N k k = = ∑ = 1 ; 5) среднее число простаивающих приборов : m N N − = ˆ ; 6) вероятность отказа в обслуживании , определяемая как вероятность того , что все приборы заняты обслуживанием заявок : ∑ = = = N i i N N i y N y p 0 ! ! π ; Задание на самостоятельную работу: доказать последнее выра - жение для вероятности потери заявок , подставив полученное выше выражение для стационарных вероятностей состояний в формулу (3.18). 7) производительность системы, определяемая как интенсивность потока обслуженных заявок: ) 1 ( ' π λ λ − = ;;;; 8) интенсивность потока не обслуженных заявок, то есть получивших отказ: π λ λ = '' ;;;; 9) среднее время пребывания заявок в системе: b m u = = ' / λ . 8. Анализ свойств системы . Анализ свойств многоканальной СМО без накопителя показывает, что с увеличением нагрузки уменьшается вероятность простоя системы и увеличивается загрузка системы, а вместе с ней число работающих 200 Раздел 5. Численное моделирование П µ λ ∞ < r Рис . 5.8. СМО с накопителем ограниченной ёмкости приборов и вероятность отказа. 5.4.3. Одноканальная СМО с накопителем ограниченной емкости (M/M/1/r) 1. Описание системы . 1.1. Система (рис.5.8) содержит один обслуживающий прибор (П), то есть является одноканальной 1.2. Поток поступающих в систему заявок однородный . 1.3. Длительность обслуживания заявок в приборе – величина случайная 1.4. Перед прибором имеется r мест для заявок, ожидающих обслуживания и образующих очередь, то есть в системе имеется накопитель ограниченной ёмко- сти: ∞ < r 2. Предположения и допущения . 2.1. Поступающие в систему заявки образуют простейший поток с интенсивностью λ 2.2. Длительность обслуживания заявок в приборе распределена по экспоненциальному закону с интенсивностью b / 1 = µ , где b – средняя длительность обслуживания заявок в приборе. 2.3. Дисциплина буферизации – с потерями : заявка, поступившая в систему и заставшая накопитель заполненным, теряется. 2.4. Дисциплина обслуживания – в порядке поступления по правилу «первым пришел – первым обслужен» (FIFO). В СМО с накопителем ограниченной ёмкости всегда существует установившийся режим, поскольку длина очереди не будет расти до бесконечности даже при больших значениях нагрузки. 3. Кодирование состояний марковского процесса . В качестве параметра, описывающего состояние марковского про- цесса, будем рассматривать количество заявок k, находящихся в СМО (в приборе и в накопителе). Тогда марковский процесс в любой момент времени может находиться в одном из следующих ( 2 + r )-х состояний: 0 E : 0 = k – в системе нет ни одной заявки; 1 E : 2 = k – в системе находится 1 заявка на обслуживании в приборе; 2 E : 2 = k – в системе находятся 2 заявки: одна – на обслуживании в приборе и вторая ожидает в накопителе; … 1 + r E : 1 + = r k – в системе находятся ( 1 + r ) заявок: одна – на обслу- живании в приборе и r – в накопителе. 4. Размеченный граф переходов случайного процесса представлен на рис.5.9. Рис . 5.9. Граф переходов марковского процесса λ λ λ λ E 0 E 1 E 2 … 1 + r E µ µ µ µ Раздел 5. Численное моделирование 201 В один и тот же момент времени в системе может произойти только одно событие: • поступление заявки с интенсивностью λ , что соответствует увеличению на единицу числа заявок в системе и переходу случайного процесса в состояние с номером на единицу больше; • завершение обслуживания заявки в приборе с интенсивностью µ , что соответствует уменьшению числа заявок в системе и переходу случайного процесса в состояние с номером на единицу меньше. Задание на самостоятельную работу: по графу переходов рис .5.9 построить матрицу интенсивностей переходов . 5. Система уравнений . Составим по графу переходов систему уравнений для определения стационарных вероятностей: = = + = + + = + = ∑ + = + 1 ) ( ) ( 1 0 1 3 1 2 2 0 1 1 0 r k k r r p p p p p p p p p p p λ µ µ λ µ λ µ λ µ λ µ λ L Используя метод математической индукции можно показать, что ) 1 , 0 ( 0 + = = r k p y p k k , где b y λ = – нагрузка системы. Подставляя полученное выражение в последнее уравнение системы линейных алгебраических уравнений, найдем вероятность простоя систе- мы в зависимости от нагрузки: = + ≠ − − = = + + = ∑ 1 , 2 1 1 , 1 1 1 2 1 0 0 y r y y y y p r r k k Тогда стационарные вероятности состояний ) 1 , 0 ( + = r k p k : 202 Раздел 5. Численное моделирование µ λ ∞ = r П Рис . 5.10. СМО с накопителем неограниченной ёмкости = + ≠ − − = + 1 , 2 1 , 1 ) 1 ( 2 y r y y y y y p k r k k Задание на самостоятельную работу: вывести представленные математические зависимости . 5. Расчет характеристик СМО . Характеристики СМО при найденных значениях стационарных вероятностей состояний случайного процесса могут быть рассчитаны по следующим формулам: 1) нагрузка b y λ µ λ = = / ; 2) загрузка ∑ + = − = = 1 1 0 1 r k k p p ρ ; 3) коэффициент простоя системы ρ η − = = 1 0 p ;;;; 4) среднее число заявок в очереди ∑ + = − = 1 2 ) 1 ( r k k p k l ; 5) среднее число заявок в системе ρ + = = ∑ + = l p k m r k k 1 1 ;;;; 6) вероятность потери заявок 1 + = r p π ; Задание на самостоятельную работу: используя выражение (3.18), доказать , что вероятность потери заявок равна вероятности того , что система заполнена , то есть в накопителе нет свободных мест для вновь поступающих заявок . 7) производительность системы (интенсивность потока обслужен- ных заявок) ) 1 ( ' π λ λ − = ;;;; 8) интенсивность потока потерянных заявок π λ λ = '' ;;;; 9) среднее время ожидания заявок ' / λ l w = ; 10) среднее время пребывания заявок b w m u + = = ' / λ . 5.4.4. Одноканальная СМО с накопителем неограниченной емкости (M/M/1) 1. Описание системы (рис.5.10). 1.1. Система – одноканальная – с одним обслуживающим прибором. 1.2. Поток заявок однородный . 1.3. В приборе происходит задержка поступающих в систему заявок на некоторое случайное время. 1.4. В системе имеется накопитель неограниченной ёмкости: ∞ = r , то есть любая заявка, поступившая в систему, найдет место для ожидания в очереди и Раздел 5. Численное моделирование 203 не будет потеряна. 2. Предположения и допущения . 2.1. Поступающие в систему заявки образуют простейший поток с интенсивностью λ 2.2. Длительность обслуживания заявок в приборе распределена по экспоненциальному закону с интенсивностью b / 1 = µ , где b – средняя длительность обслуживания заявок в приборе. 2.3. Дисциплина буферизации отсутствует, поскольку накопитель имеет неограниченную ёмкость. 2.4. Дисциплина обслуживания – в порядке поступления по правилу «первым пришел – первым обслужен» (FIFO). 2.5. Нагрузка системы совпадает с загрузкой, причём выполняется условие: 1 < = ρ y , то есть система работает в установившемся режиме без перегрузок. При 1 > y , в отличие от предыдущих моделей, в СМО устанавливается режим перегрузок. 3. Кодирование состояний марковского процесса . В качестве параметра, описывающего состояние марковского процесса, как и в предыдущем примере, будем рассматривать количество заявок k, находящихся в СМО (в приборе и в накопителе). Поскольку в системе в произвольный момент времени может находиться любое сколь угодно большое число заявок, то количество состояний марковского процесса равно бесконечности: |