Материал. Лекции теория массового обслуживания для студентов экономических специальностей очной, заочной и дистанционной форм обучения Шахты 2006
 Скачать 0.66 Mb.
|
|
0 t 0 t 0 t t < 0 t t > Прош лое Буд уще е Настоящее Пример 1 (немарковского случайного процесса. Возьмем ранее рассмотренную систему, представляющую собой группу из n самолетов, совершающих налет на территорию противника, обороняемую системой ПВО. Состояние системы в будущем зависит оттого, когда и каким образом система пришла в настоящее состояние. В данном случае нельзя не учитывать предысторию процесса, а именно, как быстро часть самолетов данной группы была уничтожена системой ПВО. Пример 2 (немарковского случайного процесса. Рассмотрим процесс игры в шахматы система S – группа шахматных фигур. Состояние системы характеризуется числом фигур (обеих сторон) и позицией на шахматной доске в момент времени 0 t . Будущее состояние системы (в момент 0 t t > ) зависит не только от состояния в настоящем, но и оттого, когда и, главное, каким образом система пришла в это состояние. А именно, если один из противников имеет материальное и/или позиционное преимущество, то важно знать, случайно или закономерно получено это преимущество, как развивалась партия (те. изменялись состояния системы) и т.д., поскольку от ответов на эти вопросы зависит информация о квалификации шахматистов, а следовательно, возможность предсказать изменение состояний системы. На практике марковские процессы в чистом виде обычно не встречаются, но нередко приходится иметь дело с процессами, которые можно приближенно считать марковскими, те. такие, для которых влиянием предыстории можно пренебречь. Кроме того, существуют приемы, позволяющие сводить немарковские случайные процессы к марковским. Например, можно вводить в состав параметров, характеризующих настоящее состояние системы, те параметры из прошлого, от которых зависит будущее (в этом случае говорят о «маркови- зации» случайного процесса. Правда, такая процедура нередко приводит к сильному усложнению математического аппарата. Существуют и другие приемы сведения немарковских случайных процессов к марковским. Уравнения Колмогорова. Предельные вероятности состояний Если все потоки событий, переводящие систему S из состояния в состояние, – простейшие, то процесс, протекающий в системе, будет марковским. Это и естественно, так как простейший поток не обладает последействием в нем будущее не зависит от прошлого. Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями и непрерывным временем наследующем примере. Пример. Техническое устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя (отказать, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. Возможные состояния системы можно перечислить 0 S – оба узла исправны 1 S – первый узел ремонтируется, второй исправен 2 S – второй узел ремонтируется, первый исправен оба узла ремонтируются. Будем полагать, что все переходы системы из состояния i S в j S происходят подвоз- действием простейших потоков событий с интенсивностями ij λ ( 3 , 2 , 1 , 0 , = j i ); так, переход системы из состояния 0 S в 1 S будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния 1 S в 0 S – под воздействием потока окончаний ремонтов первого узла и т.п. Граф состояний системы с проставленными у стрелок интенсивностями называют размеченным (рис. 6). 4 Простейший характер потоков – достаточное, ноне необходимое условие для того, чтобы процесс был марковским Рисунок 6. На графе отсутствуют стрелки изв и изв. Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход изв) или одновременного окончания ремонтов двух узлов (переход изв) можно пренебречь. Напомним, что вероятностью го состояния называется вероятность ) ( t p i того, что в момент t система будет находиться в состоянии i S . При этом для t ∀ ∑ = = 3 Рассмотрим систему в момент t и, задав малый промежуток t Δ , найдем вероятность ) ( 0 t t p Δ + того, что система в момент t t Δ + будет находиться в состоянии 0 S . Это достигается разными способами либо 1) система в момент t с вероятностью ) ( 0 t p находилась в состоянии 0 S , аза время t Δ не вышла из него либо 2) система в момент t с вероятностями ) ( 1 t p (или ) ( 2 t p ) находилась в состоянии 1 S или 2 S и за время t Δ перешла в состояние 0 S 1) Найдем вероятность первого варианта. Вывести систему из состояния 0 S (см. рис) можно суммарным простейшим потоком (при наложении двух простейших потоков, как уже отмечалось, получается опять простейший поток) с интенсивностью 02 01 λ λ + , те. в соответствии с (4), с вероятностью, приближенно равной t Δ + ) ( 02 01 λ λ . А вероятность того, что система не выйдет из состояния 0 S , равна t Δ + − ) ( 1 02 01 λ λ . Вероятность того, что система будет находиться в состоянии 0 S и не выйдет из него за время t Δ (те. вероятность первого варианта, равна по теореме умножения вероятностей ( ) t t p Δ + − ) ( 1 ) ( 02 01 0 λ λ 2) Найдем вероятность второго варианта. Под действием потока интенсивностью или 20 λ ) (см. рис. 6) система перейдет в состояние 0 S с вероятностью, приближенно равной t Δ 10 λ (или t Δ 20 λ ). Вероятность того, что система будет находиться в состоянии 0 S , поэтому способу равна t t p Δ 10 1 ) ( λ (или t t p Δ 20 2 ) ( λ ). 0 S 1 S 2 S 3 S 01 λ 10 λ 02 λ 20 λ 13 λ 31 λ 23 λ 32 λ Применяя теорему сложения вероятностей (для попарно несовместных событий, получим, откуда ) ( ) ( ) ( ) ( ) ( ) ( 0 02 01 20 2 10 1 0 Переходя к пределу при 0 → Δ t (приближенные равенства, связанные с применением формулы (4), перейдут в точные, получим в левой части уравнения производную обозначим ее для простоты 0 p′ ): 0 02 01 2 20 1 10 Получено дифференциальное уравнение первого порядка. Рассуждая аналогично для других состояний системы S , можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + − + = ′ + − + = ′ + − + = ′ + − + = ′ ) ( , ) ( , ) ( , ) ( 3 32 31 2 23 1 13 3 2 23 20 3 32 0 02 2 1 13 10 3 31 0 01 1 0 02 01 2 20 1 10 0 p p p p p p p p p p p p p p p p λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ (5) Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности го состояния. В правой части – сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, умноженных на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему изданного состояния, умноженная на вероятность данного (го) состояния В системе (5) независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необходимо добавить уравнение ∑ = = 3 Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задавать так называемые начальные условия, в данном случае – вероятности состояний системы в начальный момент 0 = t . Так, например, систему уравнений (5) естественно решать при условии, что в начальный момент оба узла исправны и система находилась в состоянии, те. при начальных условиях 1 ) 0 ( 0 = p , 0 ) 0 ( ) 0 ( ) 0 ( 3 Как решать подобные уравнения Вообще говоря, системы линейных дифференциальных уравнений с постоянными коэффициентами можно решать аналитически, но это удобно, когда число уравнений не превосходит двух (иногда – трех. Если уравнений больше, обычно их решают численно – вручную или на ЭВМ. Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы ) (t p i в предельном стационарном режиме, те. при ∞ → t , которые называются предельными финальными) вероятностями состояний. В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое состояние, то предельные вероятности существуют Предельная вероятность состояния i S имеет четкий смысл она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния 0 S , те. 5 , 0 0 = p , то это означает, что в среднем половину времени система находится в состоянии Как же вычислить предельные вероятности Очень просто. Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы S с графом состояний, изображенном на рис. 6, такая система уравнений имеет вид ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + = + + = + + = + + = + ) ( , ) ( , ) ( , ) ( 2 23 1 13 3 32 31 3 32 0 02 2 23 20 3 31 0 01 1 13 10 2 20 1 10 0 02 01 p p p p p p p p p p p p λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ λ (6) Систему можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в уравнениях стоит предельная вероятность данного состояния i p , умноженная на суммарную интенсивность всех потоков, ведущих изданного состояния, а справа – сумма произведений интенсивностей всех потоков, входящих в е состояние, на вероятности тех состояний, из которых эти потоки исходят. Эту систему из четырех уравнений с четырьмя неизвестными 0 p , 1 p , 2 p , 3 p , казалось бы, вполне можно решить. Но вот беда уравнения (6) однородны (не имеют свободного члена) и, значит, определяют неизвестные только с точностью до произвольного множителя. К счастью, мы можем воспользоваться нормировочным условием ∑ = = 3 и сего помощью решить систему. При этом одно (любое) из уравнений можно отбросить оно вытекает как следствие из остальных. Пример 1. Найти предельные вероятности для системы S (см. рисунок 6 и соответствующий пример) при , 1 01 = λ , 2 02 = λ , 2 10 = λ , 2 13 = λ , 3 20 = λ , 1 23 = λ , 3 31 = λ 2 Решение. Система алгебраических уравнений, описывающих стационарный режим для данной СМО, имеет вид (6) или ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + + + + = + = + = 1 , 2 2 4 , 3 4 , 3 2 3 3 2 1 0 3 0 2 3 0 1 2 1 0 p p p p p p p p p p p p p (7) Здесь вместо одного лишнего уравнения системы (6) записали нормировочное условие. Решив систему (7), получим 4 , 0 0 = p , 2 , 0 1 = p , 27 , 0 2 = p , 13 , 0 3 = p , те. в предельном стационарном режиме система S в среднем 40% времени будет находиться в состоянии (оба узла исправны, 20% – в состоянии 1 S (первый узел ремонтируется, второй работает, 27% – в состоянии 2 S (второй узел ремонтируется, первый работает) и 13% времени в состоянии 3 S (оба узла ремонтируются. Пример 2. Найти средний чистый доход от эксплуатации в стационарном режиме системы в условиях предыдущего примера. Если известно, что в единицу времени исправная работа первого и второго узлов приносит доход соответственно виден. еда их ремонт требует затрат соответственно виден. ед. Оценить экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени. Решение. Из предыдущего примера следует, что в среднем первый узел исправно работает долю времени, равную 67 , 0 27 , 0 4 , 0 2 0 = + = + p p , а второй узел – = + 1 0 p p 6 , 0 2 , 0 4 , 0 = + . В тоже время первый узел находится в ремонте в среднем долю времени, равную 33 , 0 13 , 0 2 , 0 3 1 = + = + p p , а второй узел – 4 , 0 13 , 0 27 , 0 Поэтому средний чистый доход в единицу времени от эксплуатации системы, те. разность между доходами и затратами, равен 18 , 8 2 4 , 0 4 33 , 0 6 6 , 0 10 Д ден. ед. Уменьшение вдвое среднего времени ремонта каждого из узлов будет означать увеличение вдвое интенсивностей потока окончаний ремонтов каждого узла. Это следует из равенства для показательного распределения (потоков) с параметром λ , о котором упоминалось ранее. Напомним, что a – это математическое ожидание случайной величины T – промежутка времени между произвольными двумя соседними событиями в простейшем потоке. Таким образом, теперь интенсивности потоков событий будут равны , 4 10 = λ , 6 20 = λ , 6 31 = λ 4 32 = λ (остальные остались прежними. При этом система линейных алгебраических уравнений (6), описывающая стационарный режим системы S , вместе с нормировочным условием примет вид ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = + + + + = + = + = 1 , 4 2 7 , 6 6 , 6 4 3 3 2 1 0 3 0 2 3 0 1 2 1 Решив систему, получим , 6 , 0 0 = p , 15 , 0 1 = p , 2 , 0 2 = p 05 , 0 Учитывая, что 8 , 0 2 , 0 6 , 0 2 0 = + = + p p , = + 1 0 p p 75 , 0 15 , 0 6 , 0 = + , = + 3 1 p p 2 , 0 05 , 0 15 , 0 = + , 25 , 0 05 , 0 2 , 0 3 2 = + = + p p , а затраты на ремонт первого и второго узлов составляют теперь соответственно 8 и 4 ден. ед, вычислим средний чистый доход веди- ницу времени 9 , 9 4 25 , 0 8 2 , 0 6 75 , 0 10 8 , 0 Д ден. ед. Так как Д больше Д примерно на 21% ( % 21 % 100 18 , 8 18 , 8 9 , 9 ≈ ⋅ − ), то экономическая целесообразность ускорения ремонтов узлов очевидна. Процессы гибели и размножения В теории массового обслуживания широко распространен специальный класс случайных процессов – так называемые процессы гибели и размножения. Название это связано с рядом биологических задач, где этот процесс служит математической моделью изменения численности биологических популяций. Граф состояний процесса гибели и размножения имеет вид, показанный на рисунке 7. Рисунок 7. 01 λ 10 λ 12 λ 21 λ 23 λ 32 λ k k , 1 − λ 1 , − k k λ 1 , + k k λ k k , 1 + λ n n , 1 − λ 1 , − n n λ ... ... ... ... 0 S 1 S 2 S k S n S Рассмотрим упорядоченное множество состояний системы n S S S ,..., , 1 0 . Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, те. из состояния k S возможны переходы либо в состояние 1 − k S , либо в состояние Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие с соответствующими интенсивностями 1 , + k k λ или k k По графу, представленному на рис. 7, составим и решим алгебраические уравнения для предельных вероятностей состояний (их существование вытекает из возможности перехода из каждого состояния в каждое другое и конечности числа состояний. В соответствии с ранее сформулированным правилом составления таких уравнений получим для состояния 0 S 1 10 0 01 p p λ λ = , (8) для состояния 1 S ― 2 21 0 01 1 10 12 ) ( p p p λ λ λ λ + = + , которое с учетом (8) приводится к виду 2 21 Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎨ ⎧ = = = = − − − − − − , , , , 1 , 1 , 1 1 , 1 , 1 2 21 1 12 1 10 0 01 n n n n n n k k k k k k p p p p p p p p λ λ λ λ λ λ λ λ (9) к которой добавляется нормировочное условие 1 1 0 = + + + n p p p . (10) Решим эту систему уравнений. Из первого уравнения (9) выразим 1 p через 0 p : 0 10 01 1 p p λ λ = . (11) Из второго, с учетом (11), получим 0 10 21 01 12 1 21 12 2 p p p λ λ λ λ λ λ = = ; (12) из третьего, с учетом (12), 0 10 21 32 01 12 23 3 p p λ λ λ λ λ λ = , и вообще, для любого k (от 1 до n ): 5 При анализе численности популяций считают, что состояние k S соответствует численности популяции, равной, и переход системы из состояния k S в состояние 1 + k S происходит при рождении одного члена популяции, а переход в состояние 1 − k S – при гибели одного члена популяции. 16 0 10 21 1 , 01 12 , 1 p p k k k k k λ λ λ λ λ λ − − = . (13) Обратим внимание на формулы для вероятностей n p p p ,..., , 2 1 : числители представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих слева направо (от начала и доданного состояния k S ); знаменатели – произведения всех интенсивностей, стоящих у стрелок, ведущих справа налево (из состояния k S и до начала. Таким образом, все вероятности состояний n p p p p ,..., , , 2 1 0 выражены через одну из них ( 0 p ). Подставим эти выражения в нормировочное условие (10). Получим, вынося за скобки 0 p : 1 1 10 21 1 , 01 12 , 1 10 21 01 12 10 01 0 = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + + + − − λ λ λ λ λ λ λ λ λ λ λ λ n n n n p , откуда можно получить выражение для 0 p : 1 10 21 1 , 01 12 , 1 10 21 01 12 10 01 0 1 − − − ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + + + + = λ λ λ λ λ λ λ λ λ λ λ λ n n n n p . (14) Заметим, что слагаемые в правой части (14) представляют собой нечто иное, как последовательные коэффициенты при 0 p в формулах для вероятностей n p p p ,..., , 2 1 |